2017, Vol. 28
2. 中国科学院 软件研究所 基础软件国家工程研究中心, 北京 100190;
3. 中国科学院 软件研究所 互联网软件技术实验室, 北京 100190;
4. 中国科学院大学, 北京 100190
2. National Engineering Research Center for Fundamental Software, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;
3. Laboratory for Interact Software Technologies, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;
4. University of Chinese Academy of Sciences, Beijing 100190, China
实时系统在工程领域中有着广泛的应用, 例如工业自动化系统、监控与数据采集系统、资源管理、能耗等[1].与非实时系统相比, 实时系统的一个显著特点是, 它需要同时实现计算在逻辑上和时间上的正确性, 即计算的正确性不仅取决于逻辑结果, 也取决于逻辑结果产生的时间[2].任务可调度性的判定是实时系统研究的核心问题之一, 1973年, Liu和Layland提出了一种适用于可抢占的硬实时周期性任务调度的静态优先级调度算法——单调速率(rate monotonic, 简称RM)调度算法[3], 并对其可调度性判定问题进行了研究.RM可调度性判定问题是计算机理论中的一个经典问题, 相关的研究成果发表在《IEEE Trans. on Computers》等经典期刊上[2-5].RM的研究主要集中在寻找高效的可调度性断定算法以及针对RM算法的扩展.
假设任务集τ={τ1, τ2, ..., τn}是一个含有n周期性任务的集合, 集合中的每个任务由三元组τi=(Ci, Di, Ti)表示.其中, Ci是运行时间, Di是截止期限, Ti是任务周期.每隔时间Ti所生成的任务ti必须在截止期限Di内完成.对于每个任务ti, 根据任务周期和截止期限的关系, 可分为3种任务模型[4]:隐式期限(implicit-deadline)模型, 即Di=Ti; 限制期限(constrained-deadline)模型, 即Di≤Ti; 任意期限(arbitrary-deadline)模型, Di与周期Ti无关.其中, 隐式期限模型的应用最为广泛[6], 本文也针对这类实时系统进行研究.
目前已有大量关于RM可调度性判定的文献, 判定的方法可以分为多项式时间调度判定和确切性判定两类.多项式时间调度判定算法使用了最坏条件下CPU利用率的最小上界, 若任务集的CPU利用率小于这个最小上界, 则任务集可调度; 若任务集的CPU利用率大于这个最小上界, 则无法判定.该类判定算法包括CPU利用率最小上界判定法[2, 3]、双曲线上界判定法[7]、调和链法[8, 9]、线性规划法[10]等.由于判定条件CPU利用率是在最坏情况下考察其可调度性而产生的, 因此它是一个充分但不必要条件, 该类算法通常被认为是悲观的.确切性判定利用充要条件进行判定.文献[11]给出了RM可调度的充分必要条件, 文献[12]研究了RM在各种扩展条件下的充分必要条件.确切性判定算法的时间复杂度是假多项式的, 任务集较大时需要更多的计算时间.确切性判定算法包括有限时间点测试法[13, 14]和最坏响应时间法[15, 16]等.
从任务可调度性判定问题可以引出两个新问题:(1) 若给定任务集τ不可调度, 那么该如何调整参数Ci, 以使该任务集可调度; (2) 若任务集τ可调度, 能否在一定区间内调整任务参数Ci, 使得系统的某个性能指标(如CPU利用率)得到提升.刘军祥等人[17]针对以上两个问题对RM可调度性判定问题进行了扩展, 提出了实时系统RM优化问题.给定周期性任务集t及任务周期T1, T2, …, Tn, 任务运行时间Ci在区间[Cimin, Cimax]内, 需要在RM可调度的约束条件下寻找一组Ci, 使得系统某一性能指标(如CPU利用率)最优.扩展形成的RM优化问题更具有一般性.对于RM可调度性判定问题, 任务执行时间Ci是区间[Cimin, Cimax]中的固定点, 因此, RM可调度性判定相当于针对RM优化问题中Ci取某一具体值的实例进行判定.
实时系统RM优化问题对实时系统的研究具有重要意义.一些研究者在Liu和Layland提出了理想任务模型的基础上, 针对具体应用和需求, 提出了非精度计算(imprecise computation)[5, 18]、IRIS(increased reward with increased service)[19]、QoS资源分配[20]等模型.在这些模型中, 每个任务可被分为必须执行任务和可选择执行任务.前者必须在任务截止期之前完成以保证最低的可接受质量, 而后者在任务截止时间之前、必须执行任务结束之后运行, 并且可在任意时刻停止, 运行时间越长, 计算的结果越精确.这些模型具有广泛的应用, 一方面, 可以根据任务执行时间设计高效算法, 合理地选择硬件, 提高资源的利用率; 另一方面, 当系统过载无法调度时, 可以调整任务的运行时间进行过载处理.
RM优化问题的约束条件中逻辑“与”和“或”关系并存的特点, 使得该问题成为广义约束优化问题[21]的一个重要实例.文献[21]同时给出了一种函数变换方法来求解该问题.若将广义约束优化问题的约束条件看作逻辑变量, 则该问题的约束条件可以看作合取范式(conjunction normal form, 简称CNF), 而任意合取范式可以通过逻辑运算转化为析取范式(disjunction normal form, 简称DNF), 因此, 该类问题也可以被称为析取优化问题(disjuntive programming)[22].目前, 析取优化问题主要采用将问题转化为混合整数规划的方式进行求解[23, 24].
目前对RM优化问题已有较为深入的研究.刘军祥等人[17]通过引入0-1整数变量, 将逻辑“或”的约束条件转换为混合整数约束条件, 进而将问题转变为混合布尔型整数规划问题后求解, 我们将该方法称为基于MBP的方法.Min-Allah等人[25]根据文献[21]中“等价变换”的方法将约束条件等价变换为只含有逻辑“与”的约束条件, 进而将问题转换为非线性约束优化问题再进行求解, 该方法被称为基于NLP的方法.2015年陈力等人[26]提出了一种基于树状线性规划搜索的LPS算法, 将RM算法可调度的充分必要条件转化为含与逻辑“与”“或”运算的线性约束不等式, 并建立优化模型, 将模型拆分成若干个线性规划子问题, 构造线性规划搜索树, 利用深度优先搜索及剪枝算法求解部分线性规划问题, 并最终求得原问题的最优值.文献[26]的结果表明, LPS方法比基于MBP和基于NLP的方法能够节省20%~70%的求解时间, 并且随着问题规模的扩大, 节省的时间会越多.LPS方法可以取代基于MBP和基于NLP的方法作为求解RM优化问题的高效算法.但是, LPS算法没有充分考虑搜索过程中各兄弟节点对最优值影响的大小以及父子节点约束条件中的包含关系, 并且, 在实验过程中我们发现, LPS在搜索过程中可能会掉入局部搜索陷阱中而使求解时间过长, 求解时间存在一定的波动.
本文改进了LPS方法中的深度优先搜索, 提出了基于线性规划的混合搜索算法(linear programing based hybrid search, 简称LPHS).本文的主要创新点如下:(1) 将深度优先搜索与广度优先搜索策略相结合, 在搜索过程中根据子节点对最优值的影响选取待求解的线性规划子问题.(2) 提出了一种新的剪枝策略, 在求解过程中根据RM优化问题中若父节点约束满足, 则可能存在该节点的某一子节点约束也可满足的关系进行动态剪枝, 极大地缩小了搜索空间.实验结果表明, LPHS算法比LPS方法的求解速度更快, 至少有10倍的效率提升.同时, 求解时间的波动性更小.
本文第1节介绍研究基础, 包括实时系统RM可调度性判定条件及约束优化问题.第2节介绍RM优化问题及已有的3种解法.第3节介绍基于线性规划的混合搜索算法.第4节给出实验设计与结果分析.第5节对全文内容进行总结.
1 研究基础 1.1 实时系统RM可调度性判定条件设实时系统的任务集τ={τ1, τ2, ..., τn}集合中的每个任务用τi=(Ti, Ci)表示.其中, Ci是运行时间, Ti是任务周期.可调度性判定问题是RM调度算法的一个根本问题, 目前已有大量关于RM可调度性判定的文章[14, 27, 28].本文以Bini等人2002年提出的RM可调度性的充要条件为基础[13].
定理1 (Bini等人提出).任务集τ是RM可调度的当且仅当下式为真:
| $\mathop \wedge \limits_{i = 1, \ldots ,n} {\rm{ }}\mathop \vee \limits_{t \in {P_{i - 1}}\left( {{T_i}} \right)} {\rm{ }}\left( {\mathop \sum \limits_{j = 1}^t \frac{t}{{{T_j}}}{C_j} \le t} \right)$ | (1) |
其中,
| ${P_i}\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {\left\{ t \right\},} & {i = 0}\\ {{P_{i - 1}}\left( {\left\lfloor {t/{T_i}} \right\rfloor {T_i} \cup {P_{i - 1}}\left( t \right)} \right),} & {i \ge 1} \end{array}} \right.$ | (2) |
该方法利用有限个时间点进行判定.文献[18]提出了一种计算Pi(t)的二叉树剪枝方法, 在计算Pi(t)的过程中, 该方法可以避免产生相同元素, 减少了不必要的开销.
1.2 约束优化问题标准的约束优化问题(standard constrained optimization problem, 简称SCOP)是指在一系列由等式和不等式组成的约束条件中寻找使目标函数取得最大或最小值的一个最优点.SCOP问题的约束条件必须同时满足, 相当于逻辑“与”的关系.SCOP在工程领域已经得到了广泛的应用, 如实时系统、控制理论、结构优化设计、机器人路径规划等[17, 21].SCOP的形式定义如下:
| $\left. \begin{array}{l} \max {\rm{ }}f\left( x \right)\\ {\rm{s}}{\rm{.t}}.{\rm{ }}{g_i}\left( x \right) = 0,{\rm{ }}i = 1,2, \ldots ,{m_1}\\ \quad {\rm{ }}{g_i}\left( x \right) \le 0,{\rm{ }}i = {m_1} + 1,{m_1} + 2, \ldots ,{m_2} \end{array} \right\}$ | (3) |
其中, 变量x=(x1, x2, …, xn)是n维向量, f(x)是目标函数, gi(x)=0(i=1, 2, ..., m1)和gi(x)≤0(i=m1+1, m1+2, …, m2)是约束条件.目前有大量的求解SCOP的成熟算法, 包括序贯二次规划法和内点法等.当目标函数与约束条件均为线性表达式时, 该问题即为线性规划问题, 使用单纯形法可以高效求解.
文献[21]在SCOP的基础上提出了更一般的广义约束优化问题(generalized constrained optimization problem, 简称GCOP).GCOP在SCOP约束条件仅含逻辑”与”关系的基础上, 将约束条件进行了扩展, 加入了逻辑“或”运算.GCOP可描述为
| $\left. \begin{array}{l} \max {\rm{ }}f\left( x \right)\\ {\rm{s}}{\rm{.t}}.{\rm{ }}\left( {{h_{11}}\left( x \right) \le 0 \vee {h_{12}}\left( x \right) \le 0 \vee \ldots \vee {h_{1{k_1}}}\left( x \right) \le 0} \right)\\ \quad {\rm{ }} \wedge \left( {{h_{21}}\left( x \right) \le 0 \vee {h_{22}}\left( x \right) \le 0 \vee \ldots \vee {h_{2{k_2}}}\left( x \right) \le 0} \right)\\ \quad {\rm{ }} \wedge \ldots \\ \quad {\rm{ }} \wedge \left( {{h_{s1}}\left( x \right) \le 0 \vee {h_{s2}}\left( x \right) \le 0 \vee \ldots \vee {h_{s{k_s}}}\left( x \right) \le 0} \right) \end{array} \right\}$ | (4) |
文献[21]同时还给出了一种求解GCOP的方法, 将带有逻辑“或”的不等式等价变换成一个不等式, 从而将GCOP转化为SCOP, 然后再利用求解SCOP的算法进行求解即可.
定理2 (Wang和Lane提出).已知函数h1(x), h2(x), ..., hm(x), 那么,
| ${h_1}(x) \le 0 \vee {h_2}(x) \le 0 \vee \ldots \vee {h_k}(x) \le 0 \Leftrightarrow {\rm{\Delta }}v - \mathop \sum \limits_{i = 1}^m \left( {\sqrt {{h_1}{{(x)}^2}} - {h_1}(x)} \right) \le 0$ | (5) |
其中, △v为任意小的正数.
2 实时系统RM优化问题及已有的3种解法RM优化问题可描述如下:给定实时系统的任务集τ={τ1, τ2, ..., τn}, 每个任务τi的周期为Ti, 运行时间Ci在区间[Cimin, Cimax]内, 如何设计各项任务的运行时间以使得该系统的某个性能指标(例如CPU利用率
文献[17]将实时系统RM优化问题建模成一个广义约束优化问题.目标函数为CPU利用率
| $\left. \begin{array}{l} \max f = \mathop \sum \limits_{i = 1}^n \frac{{{C_i}}}{{{T_i}}}\\ {\rm{s}}.{\rm{t}}.{\rm{ }}\mathop \wedge \limits_{i = 1, \ldots ,n} \left( {\mathop \vee \limits_{t \in {P_{i - 1}}\left( {{T_i}} \right)} {\rm{ }}\left( {\mathop \sum \limits_{j = 1}^t \frac{t}{{{T_j}}}{C_j} - t \le 0} \right)} \right)\\ \quad {\rm{ }}C_i^{{\rm{min}}} \le {C_i} \le C_i^{{\rm{max}}},i = 1,2, \ldots ,n \end{array} \right\}$ | (6) |
从模型(6) 可以看出, 与标准的约束优化问题相比, RM优化问题的约束条件中不仅包含逻辑“与”关系, 还加入了逻辑“或”关系.约束条件同时包含逻辑“与”“或”关系的RM优化问题是广义约束优化问题的一个重要实例.
目前模型(6) 已有多种求解算法.文献[17]提出了基于混合布尔整数规划的求解方法.对于约束条件
| $\left. \begin{array}{l} {h_i}(x) - {y_i}M \le 0,i = 1,2, \ldots ,m,\\ {y_1} + {y_2} + \ldots + {y_m} = m - 1 \end{array} \right\}$ | (7) |
通过引入0-1整数变量, 将约束条件中的逻辑“或”转换为“与”的关系, 模型(6) 进一步被转换为混合型整数规划(MBP)问题, 然后再利用分支定界法[29]来求解转换后的优化问题.这种方法需要大量引入新的整数变量, 并将原来连续的约束函数变成了既含有连续变量又含有布尔变量的约束条件, 增大了求解难度.
文献[25]则提出了基于非线性约束优化算法的方法来求解该问题.该文根据定理2中的方法将模型中每一组含有逻辑“或”的约束条件转换为一个非线性的约束不等式, 得到一个标准的约束优化问题(SCOP)中的非线性规划(NLP)问题, 然后再利用NLP中的成熟算法——序贯二次规划[30]或内点法[31]求解SCOP.这种转换方法适用于线性及非线性约束等情况.针对RM优化问题, 该方法将线性不等式变成了非线性不等式, 而非线性约束优化问题比求解线性约束优化问题难得多, 并且转化后的SCOP的可行域并不是凸的, 在求解时容易掉入局部解.
2015年, 陈力等人[26]根据约束条件为线性不等式并且可以分组计算的性质提出了基于树状线性规划搜索算法, 首先将RM算法可调度的充分必要条件转换成具有逻辑“与”和“或”的线性约束不等式, 建立了优化模型, 然后将模型分拆成若干个线性规划子问题, 再构造线性规划问题的搜索树, 利用深度优先搜索及其剪枝算法, 选择部分线性规划问题进行求解, 最终找到线性规划子问题中最大的最优值, 从而得到使得CPU利用率最大的任务运行时间.该方法比前两种方法有20%~70%的性能提升, 是目前求解RM优化问题最有效的算法.
3 基于线性规划的混合搜索算法(LPHS) 3.1 模型描述模型(6) 中的约束条件是一个合取范式, 该约束条件可以通过逻辑运算转化为如下所示的析取范式:
| $\mathop \wedge \limits_{i = 1, \ldots ,n} \left( {\mathop \vee \limits_{t \in {P_{i - 1}}\left( {{T_i}} \right)} {\rm{ }}\left( {\mathop \sum \limits_{j = 1}^t \frac{t}{{{T_j}}}{C_j} - t \le 0} \right)} \right) \Leftrightarrow \mathop \vee \limits_{\begin{array}{*{20}{c}} {{t_1} \in {P_0}\left( {{T_1}} \right)}\\ {{t_2} \in {P_1}\left( {{T_2}} \right)}\\ \ldots \\ {{t_n} \in {P_{n - 1}}\left( {{T_n}} \right)} \end{array}} \left( {\mathop \wedge \limits_{i = 1, \ldots ,n} {\rm{ }}\left( {\mathop \sum \limits_{j = 1}^i \frac{t}{{{T_j}}}{C_j} - t \le 0} \right)} \right)$ | (8) |
因此, 模型(6) 代表的约束优化问题就等价于如下问题:
| $\left. \begin{array}{l} \max f = \mathop \sum \limits_{i = 1}^n \frac{{{C_i}}}{{{T_i}}}\\ {\rm{s}}{\rm{.t}}.{\rm{ }}\mathop \vee \limits_{\begin{array}{*{20}{c}} {{t_1} \in {P_0}\left( {{T_1}} \right)}\\ {{t_2} \in {P_1}\left( {{T_2}} \right)}\\ \ldots \\ {{t_n} \in {P_{n - 1}}\left( {{T_n}} \right)} \end{array}} \left( {\mathop \wedge \limits_{i = 1, \ldots ,n} {\rm{ }}\left( {\mathop \sum \limits_{j = 1}^i \frac{t}{{{T_j}}}{C_j} - t \le 0} \right)} \right)\\ {\rm{ }}C_i^{{\rm{min}}} \le {C_i} \le C_i^{{\rm{max}}},i = 1,2, \ldots ,n \end{array} \right\}$ | (9) |
为了便于描述, 我们给出如下定义.
设集合Pi–1(Ti)中的元素以升序排列, 集合中含有Sizei个元素, 令pilk表示集合Pi–1(Ti)中的第lk个元素, 令
| $\mathop \wedge \limits_{i = 1}^m {\rm{ }}\mathop \sum \limits_{j = 1}^{{k_i}} \left\lceil {\frac{{val\left( {{p_{{k_i}{l_i}}}} \right)}}{{{T_j}}}} \right\rceil {C_j} - val\left( {{p_{{k_i}{l_i}}}} \right) \le t$ | (10) |
引入记号
| $\left. \begin{array}{l} \max f = \mathop \sum \limits_{i = 1}^n \frac{{{C_i}}}{{{T_i}}}\\ \mathop \wedge \limits_{i = 1}^m {\rm{ }}\mathop \sum \limits_{j = 1}^{{k_i}} \left\lceil {\frac{{val\left( {{p_{{k_i}{l_i}}}} \right)}}{{{T_j}}}} \right\rceil {C_j} - val\left( {{p_{{k_i}{l_i}}}} \right) \le t \end{array} \right\}$ | (11) |
对于式(8) 中析取范式中的每一个简单合取式, 与目标函数相结合后会产生一个线性规划问题.原约束优化问题即由
LPS方法利用约束条件为线性不等式以及在计算过程中可以将约束条件分组计算的性质, 设计了高效的深度优先搜索及剪枝算法, 这是目前效率最高的算法.LPS方法提出的深度优先搜索策略忽视了两个问题:(1) 对于具有相同父节点和搜索深度的兄弟节点, 各兄弟节点与目标函数组成的线性规划问题最优值的大小对深度优先搜索顺序的影响.(2) RM优化问题中, 在父节点的约束条件已满足的情况下, 子节点的可满足性是否可以根据父节点中的约束条件推导得出.此外, 在实验中我们也发现, LPS方法在求解过程中可能会陷入局部搜索陷阱, 求解时间的波动性较大.针对以上所提出的问题, 我们对LPS算法进行了改进, 提出了一种基于线性规划的混合搜索算法.该算法的主要内容包括:
(1) 使用深度广度混合的搜索策略.以已搜索到的最优值作为剪枝条件, 利用深度优先搜索及剪枝策略求解新的最优值, 在深度优先搜索的基础上, 结合广度优先搜索, 对深度优先搜索的顺序进行调整.
(2) 利用贪心算法求一个初始最优解.
(3) 在求解过程中, 根据父子节点之间约束条件的关系提出了一种全新的动态剪枝策略, 加快求解过程, 有效避免了程序进入局部搜索的陷阱.
3.2 混合搜索算法实时系统RM优化问题的约束条件可以描述为图 1所示的树状结构.
|
Fig. 1 Constraints tree of RM optimal design problem 图 1 优化问题约束条件树 |
设搜索的起点为Root, 此时搜索的深度为0, 即不包含任何约束条件.搜索过程中深度为1的所有节点为
在搜索开始之前可以先计算出一个初始局部最优解.一种简单的方法是随机选取部分子问题并求出这些子问题的最优解, 并将初始的局部最优值记为这些最优解中的最大值, 初始最优值的具体计算方法在第3.3节中有进一步描述.初始局部最优值计算完成后开始进行混合搜索算法.LPHS算法将深度优先与广度优先搜索相结合, 在深度优先搜索的框架下结合广度优先搜索进行.
深度优先搜索是LPHS算法的框架.在搜索过程中, 当搜索到深度为k的节点
广度优先搜索根据当前节点的子节点对最优值的影响程度对深度搜索的顺序进行适当调整.当计算完深度为k的节点
混合搜索算法描述如下.
算法 1.混合搜索算法.
glb_max; //已搜索到的局部最优解
bf_queue; //保存可能需要进行深度搜索的节点
HybridSearchOptimal(PROB){
for prob in child(PROB)
local_opt=calcProbOptimal(prob);
if local_opt > glb_max then
bf_queue.pushback((prob, local_opt))
endif
SortByOptimal(bf_queue);
for (prob, local_opt) in bf_queue
if (local_opt > glp_max)
if deep(prob) < n then
if DynamicPrune(PROB, prob)==true then
HybridSearchOptimal(PROB);
else
HybridSearchOptimal(prob);
endif
else
glb_max=local_opt
endif
endif
}
child()函数表示PROB节点的所有子节点.calcProbOptimal(PROB)计算由PROB节点中的约束条件与目标函数组成的线性规划问题OPT的最优值.SortByOptimal根据计算最优值将PROB降序排列.deep(PROB)表示约束个数, 即目前的搜索深度.DynamicPrune()在第3.4节中有具体的介绍.
3.3 初始最优解的计算初始最优值的选择对搜索过程的剪枝有着重要的影响, 初始的局部最优值越大, 该最优值起到的剪枝作用就越显著, 需要搜索的总节点数也越小.我们可以通过简单的随机算法来选取最优值, 比如从约束条件为
算法 2.初始局部最优值的计算.
GreedyInitialOptimal(PROB){
localtmp//保存局部最优解
while deep(PROB) < n
localtmp=0;
for prob in child(PROB)
local_opt=calcProbOptimal(prob);
if local_opt > localtmp then
PROB=prob
endif
glb_max=localtmp
}
3.4 动态剪枝算法随着实时系统任务数n的增大, 形成的子问题数目将成倍地增长.剪枝对缩小问题的搜索空间具有重要的影响.文献[26]中就提出了通过减少线性规划子问题数量的算法来缩小搜索空间.其中提到的深度优先搜索策略是一个非常高效的剪枝策略, 但是该算法只有在求出的最优值小于局部最优值时才会起到剪枝的作用.本节通过对不等式系数的判定, 提出一种新的在运行过程中使用的高效剪枝策略, 该方法在求出的最优值大于局部最优值时同样可以使用.下面首先给出该方法的使用条件及理论依据.
定理3.对于任意两个约束条件:
| $\mathop \sum \limits_{i = 1}^n {a_{1i}}{x_i} \le {b_1},{{\rm{\Phi }}_1} = \{ {x_i}|{a_{1i}} \ne 0,i = 1,2, \ldots ,n\} $ | (12) |
| $\mathop \sum \limits_{i = 1}^n {a_{2i}}{x_i} \le {b_2},{{\rm{\Phi }}_2} = \{ {x_i}|{a_{2i}} \ne 0,i = 1,2, \ldots ,n\} $ | (13) |
若
证明:
设(x1, x2, x3, …, xn)为任意一组使条件式(13) 满足的赋值,
| $\mathop \sum \limits_{i = 1}^n {a_{2i}}{x_i} = \sum\limits_{{x_i} \in {{\rm{\Phi }}_1}} {{a_{2i}}{x_i}} + \sum\limits_{{x_i} \in {{\rm{\Phi }}_2} - {{\rm{\Phi }}_1}} {{a_{2i}}{x_i}} \le {b_2},$ |
| $\sum\limits_{{x_i} \in {{\rm{\Phi }}_1}} {{a_{2i}}{x_i}} \le {b_2} - \sum\limits_{{x_i} \in {{\rm{\Phi }}_2} - {{\rm{\Phi }}_1}} {{a_{2i}}{x_i}} ,$ |
| $\mathop \sum \limits_{i = 1}^n {a_{1i}}{x_i} = \sum\limits_{{x_i} \in {{\rm{\Phi }}_1}} {{a_{1i}}{x_i}} \le \sum\limits_{{x_i} \in {{\rm{\Phi }}_1}} {{a_{2i}}{x_i}} \le {b_2} - \sum\limits_{{x_i} \in {{\rm{\Phi }}_2} - {{\rm{\Phi }}_1}} {{a_{2i}}{x_i}} .$ |
因为,
| ${b_2} - \sum\limits_{{x_i} \in {{\rm{\Phi }}_2} - {{\rm{\Phi }}_1}} {{a_{2i}}{x_i}} \le {b_2} - \sum\limits_{{x_i} \in {{\rm{\Phi }}_2} - {{\rm{\Phi }}_1}} {{a_{2i}}x_i^{{\rm{min}}}} \le {b_1},$ |
因此,
| $\mathop \sum \limits_{i = 1}^n {a_{1i}}{x_i} \le {b_1}.$ |
定理3得证.
由定理3可知, 使约束条件式(13) 成立的可行域是使条件式(12) 成立的可行域的子集, 因此, 在定理3的前提条件得到满足时, 由式(12)、式(13) 组成的约束条件等价于式(12), 即:
| $\mathop \sum \limits_{i = 1}^n {a_{1i}}{x_i} \le {b_1} \wedge \mathop \sum \limits_{i = 1}^n {a_{2i}}{x_i} \le {b_2} \Leftrightarrow \mathop \sum \limits_{i = 1}^n {a_{2i}}{x_i} \le {b_2}$ | (14) |
在实时系统优化问题中, 当i=k时, 含k个变量, 而当i=k–1时, 含k–1个变量.i=k时的约束条件比i=k–1时的约束条件仅多出变量xk.因此, 设在第k层取到的约束条件为
算法 3. DynamicPrune算法.
bool DynamicPrune(parent, child){
Constraint=constraints(child)-constraints(parent); //求子节点比父节点新增的约束条件
for cons in constraints (parent)
if satisfy(cons, constraint) then
return true;
endif
return false;
}
constraints(PROB)函数计算用来返回PROB中所包含的约束条件.satisfy(constraint1, constraint2) 根据定理3判定在constraint 1满足的条件下constraint 2是否成立, 若成立, 则返回true.
3.5 LPHS求解算法经过上述3节的叙述, 我们给出最终的LPHS算法.
算法 4. LPHS算法.
LPHS(input){//input为RM优化问题的约束条件和目标函数
PROB=parseSearchTree(input); //将输入文件解析为图 1所示的搜索树, PROB为root节点.
GreedyInitialOptimal(PROB);
HybridSearchOptimal(PROB);
retrun glb_max;
}
4 实验结果对比与分析本文比较了LPS、LPHS两种方法求解实时系统RM优化问题(以CPU最大利用率为目标函数)的时间开销.算法运行的机器环境为Windows 10, Intel Core i7处理器, 8GM RAM.
本文使用了与文献[26]中实验相同的实验条件, 该条件描述如下:算法的精度为10–4.任务周期Ti从[50, 5000]中均匀、随机地选取, 这样选取有两个原因:(1) 区间跨度大, 不等式的变量系数范围可在1~100之间; (2) 各个系数的值会尽量保证不同.任务执行时间Ci的区间为
|
Table 1 Comparasive study result between LPHS and LPS method 表 1 LPHS与LPS方法运行时间与求解问题个数比较 |
实验结果表明, 新的LPHS算法的效率远高于LPS方法, 并且随着问题规模的扩大, 效果依然明显.图 2更加直观地展现了相比于LPS算法, LPHS算法有10倍以上的效率提升.在给出的90个用例中, LPHS算法求解出了所有问题的最优值, 而LPS算法中有12个用例超时.从任务数为55、60、75、85等实验数据可以看出, 求解的平均时间为100s左右, 距1 000s的超时时间仍有一段距离.但是, 这几组实验中均有未解出的问题, 这表明, LPS方法的有效性并不能得到保证, 进入局部搜索的陷阱后会有难以跳出的情况发生.为了进一步比较两种算法求解时间的波动性, 我们统计了每组任务中求解时间的方差, 由于计算结果的平均时间数值差异较大, 我们先将每组数据均除以该组的平均运行时间(超时用例统一用1 000s计算), 统计的方差结果如图 3所示.从图中可以看出, LPS在求解相同规模的任务时, 求解时间的波动性比LPHS方法大很多.
|
Fig. 2 Comparision of execution time between LPS and LPHS method 图 2 LPS与LPHS算法求解时间比较 |
|
Fig. 3 Variance of excectuion time with the same task number 图 3 相同问题规模的求解时间方差 |
LPHS算法比LPS方法效率更高的原因主要包括如下两点.
(1) LPS算法在深度优先搜索中, 没有确定同一层可选子问题求解的优先顺序, 单纯使用了深度优先算法.而LPHS算法通过广度优先搜索, 将同一层各子节点约束下的最优值进行排序, 从最优值大的子节点开始计算.即对Node1和Node2两个节点, 假设Node1节点的最优值opt1小于Node2节点的最优值opt2, LPHS算法会先求解Node2的子节点.因为Node2子节点求出的最优值opt'有可能大于opt1时, 此时可以将Node1节点剪掉, 避免了对Node1子节点的计算, 所以LPHS算法的混合搜索策略比LPS算法的深度优先策略更加高效.
(2) RM优化问题在转化为搜索树后, 对于任一节点Nodeparent=
本文提出了一种求解RM优化问题的新算法——基于线性规划的混合搜索算法(LPHS).将模型(6) 表示的约束优化问题构造为线性规划搜索树, 将深度优先搜索与广度优先搜索策略相结合, 在搜索过程中比较各子节点的最优值, 最优值大的子问题优先计算, 并且在求解过程中自动根据已选择的子问题进行动态剪枝, 高效地求得该问题的最优值, 即CPU利用率的最大值.与LPS方法相比, LPHS方法的效率有了10倍的提高, 并且求解问题的稳定性也更高.
RM优化问题的约束条件中同时包含逻辑“与”和“或”关系, 是广义约束优化问题(析取优化问题)的一个重要实例, 本文的研究对该类问题的求解具有重要意义.同时, 本文的工作可与计算机领域中另一著名的理论问题——可满足性模理论(satisfiability modulo theroies, 简称SMT)[32-35]的研究相结合.SMT在模型检测[36]、软件测试[37]等领域有着非常广泛的应用.SMT背景理论中线性算术(linear arithmetic)理论[38, 39]的约束条件中也同时包含逻辑“与”“或”关系, 该问题的可行解、最优解的计算可以与LPHS方法相结合.接下来我们将进一步研究SMT求解器的线性算术求解部分, 进一步改进LPHS算法, 并尝试提高SMT线性算术部分的求解效率.
| [1] |
Mall R. Real-TIme Systems: Theory and Practice. New Delhi: Pearson Education India., 2009.
|
| [2] |
Burchard A, Liebeherr J, Oh Y, Son SH. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans.on Computers, 1995, 44(12): 1429–1442.
[doi:10.1109/12.477248] |
| [3] |
Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM (JACM), 1973, 20(1): 46–61.
[doi:10.1145/321738.321743] |
| [4] |
Davis R, Zabos A, Burns A. Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans. on Computers, 2008, 57(9): 1261–1276.
[doi:10.1109/TC.2008.66] |
| [5] |
Chung JY, Liu JW, Lin KJ. Scheduling periodic jobs that allow imprecise results. IEEE Trans.on Computers, 1990, 39(9): 1156–1174.
[doi:10.1109/12.57057] |
| [6] |
Stankovic JA, Spuri M, Ramamritham K, Buttazzo GC. Deadline scheduling for real-time systems: EDF and related algorithms. LNSC 460, 2012.
[doi:10.1007/978-1-4615-5535-3] |
| [7] |
Bini E, Buttazzo G. A hyperbolic bound for the rate monotonic algorithm. In: Proc. of the 13th Euromicro Conf.on Real-Time Systems.IEEE, 2001: 59–66.
[doi:10.1109/EMRTS.2001.934000] |
| [8] |
Kuo T, Liu YH, Lini KJ. Efficient on-line schedulability tests for priority driven real-time systems. In: Proc. of the 6th Real-Time Technology and Applications Symp.IEEE, 2000: 4–13.
[doi:10.1109/RTTAS.2000.852446] |
| [9] |
Kuo TW, Mok AK. Load adjustment in adaptive real-time systems. In: Proc. of the 12th Real-Time Systems Symp.IEEE, 1991: 160–170.
[doi:10.1109/REAL.1991.160369] |
| [10] |
Park DW, Natarajan S, Kanevsky A. Fixed-Priority scheduling of real-time systems using utilization bounds. Journal of Systems and Software, 1996, 33(1): 57–63.
[doi:10.1016/0164-1212(95)00105-0] |
| [11] |
Lehoczky J, Sha L, Ding Y. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In: Proc. of the Real-Time Systems Symp.IEEE, 1989: 166–171.
[doi:10.1109/REAL.1989.63567] |
| [12] |
Katcher DI, Arakawa H, Strosnider JK. Engineering and analysis of fixed priority schedulers. IEEE Trans.on Software Engineering, 1993, 19(9): 920–934.
[doi:10.1109/32.241774] |
| [13] |
Bini E, Buttazzo GC. The space of rate monotonic schedulability. In: Proc. of the 23th IEEE Real-Time Systems Symp.IEEE, 2002: 169–178.
[doi:10.1109/REAL.2002.1181572] |
| [14] |
Min-Allah N, Khan SU, Wang X, Zomaya AY. Lowest priority first based feasibility analysis of real-time systems. Journal of Parallel and Distributed Computing, 2013, 73(8): 1066–1075.
[doi:10.1016/j.jpdc.2013.03.016] |
| [15] |
Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 1993, 8(5): 284–292.
[doi:10.1049/sej.1993.0034] |
| [16] |
Sjodin M, Hansson H. Improved response-time analysis calculations. In: Proc. of the 19th Real-Time Systems Symp.IEEE, 1998: 399–408.
[doi:10.1109/REAL.1998.739773] |
| [17] |
Liu JX, Wang YJ, Cartmell M.An improved ratemonotonic schedulabilitytest algorithm.Ruan Jian Xue Bao/Journal of Software, 2005, 16(1):89-100 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/17/1641.htm[doi: 10.1360/jos171641] |
| [18] |
Liu JW, Lin KJ, Shih WK, Yu AC, Chung JY, Zhao W. Algorithms for scheduling imprecise computations. Computer, 1991, 24(5): 58–68.
[doi:10.1109/2.76287] |
| [19] |
Dey JK, Kurose J, Towsley D. On-Line scheduling policies for a class of IRIS (increasing reward with increasing service) real-time tasks. IEEE Trans.on Computers, 1996, 45(7): 802–813.
[doi:10.1109/12.508319] |
| [20] |
Rajkumar R, Lee C, Lehoczky J, Siewiorek D. A resource allocation model for QoS management. In: Proc. of the 18th Real-Time Systems Symp.IEEE, 1997: 298–307.
[doi:10.1109/REAL.1997.641291] |
| [21] |
Wang Y, Lane DM. Solving a generalized constrained optimization problem with both logic AND and OR relationships by a mathematical transformation and its application to robot motion planning. IEEE Trans. on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2000, 30(4): 525–536.
[doi:10.1109/5326.897079] |
| [22] |
Raman R, Grossmann IE. Modelling and computational techniques for logic based integer programming. Computers & Chemical Engineering, 1994, 18(7): 563–578.
[doi:10.1016/0098-1354(93)E0010-7] |
| [23] |
Vecchietti A, Grossmann I. Computational experience with logmip solving linear and nonlinear disjunctive programming problems. In: Floudas CA, ed.Proc.of the FOCAPD.New Jersey: Princeton University Press, 2004: 587–590.
http://www.academia.edu/9563311/COMPUTATIONAL_EXPERIENCE_WITH_LOGMIP_SOLVING_LINEAR_AND_NONLINEAR_DISJUNCTIVE_PROGRAMMING_PROBLEMS |
| [24] |
Sawaya NW, Grossmann IE. A cutting plane method for solving linear generalized disjunctive programming problems. Computers & Chemical Engineering, 2005, 29(9): 1891–1913.
[doi:10.1016/j.compchemeng.2005.04.004] |
| [25] |
Min-Allah N, Khan SU, Wang Y. Optimal task execution times for periodic tasks using nonlinear constrained optimization. The Journal of Supercomputing, 2012, 59(3): 1120–1138.
[doi:10.1007/s11227-010-0506-z] |
| [26] |
Chen L, Wang YJ, Wu JZ, Lü YR. Rate-Monotonic optimal design based on tree-like linear programming search. Ruan Jian Xue Bao/Journal of Software, 2015, 26(12): 3223–3241(in Chinese with English abstract).
[doi:10.13328/j.cnki.jos.004853] |
| [27] |
Wang YJ, Chen QP. On schedulability test of rate monotonic and its extendible algorithms. Ruan Jian Xue Bao/Journal of Software, 2004, 15(6): 799–814(in Chinese with English abstract).
http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=20040602&journal_id=jos |
| [28] |
Díaz-Ramírez A, Mejía-Alvarez P, Leyva-del-Foyo LE. Comprehensive comparison of schedulability tests for uniprocessor rate-monotonic scheduling. Journal of Applied Research and Technology, 2013, 11(3): 408–436.
[doi:10.1016/S1665-6423(13)71551-7] |
| [29] |
Hillier FS. Introduction to Operations Research. NewYork: Tata McGraw-Hill Education, 1995.
|
| [30] |
Boggs PT, Tolle JW. Sequential quadratic programming. Acta Numerica, 1995, 4: 1–51.
[doi:10.1017/S0962492900002518] |
| [31] |
Byrd RH, Hribar ME, Nocedal J. An interior point algorithm for large-scale nonlinear programming. SIAM Journal on Optimization, 1999, 9(4): 877–900.
[doi:10.1137/S1052623497325107] |
| [32] |
De Moura L, Bjørner N. Satisfiability modulo theories: Introduction and applications. Communications of the ACM, 2011, 54(9): 69–77.
[doi:10.1145/1995376.1995394] |
| [33] |
Barrett CW, Sebastiani R, Seshia SA, Tinelli C. Satisfiability modulo theories. In: Handbook of Satisfiability, 2009, 185: 825–885.
http://research.microsoft.com/en-us/um/redmond/projects/z3/z3.pdf |
| [34] |
de Moura L, Dutertre B, Shankar N. A tutorial on satisfiability modulo theories. In: Computer Aided Verification.Springer-Verlag, 2007: 20–36.
[doi:10.1007/978-3-540-73368-3_5] |
| [35] |
Li Y, Albarghouthi A, Kincaid Z, Gurfinkel A, Chechik M. Symbolic optimization with SMT solvers. In: ACM SIGPLAN Notices. ACM, 2014: 607–618.
[doi:10.1145/2535838.2535857] |
| [36] |
Cordeiro L, Fischer B, Marques-Silva J. SMT-Based bounded model checking for embedded ANSI-C software. IEEE Trans. on Software Engineering, 2012, 38(4): 957–974.
[doi:10.1109/TSE.2011.59] |
| [37] |
Wang H, Xing J, Yang Q, Song W, Zhang X. Generating effective test cases based on satisfiability modulo theory solvers for service-oriented workflow applications. Software Testing, Verification and Reliability, 2015, 26(2): 149–169.
[doi:10.1002/stvr.1592] |
| [38] |
Dutertre B, De Moura L. A fast linear-arithmetic solver for DPLL (T). In: Computer Aided Verification.Springer-Verlag, 2006: 81–94.
[doi:10.1007/11817963_11] |
| [39] |
King T, Barrett C, Dutertre B. Simplex with sum of infeasibilities for SMT. In: Formal Methods in Computer-Aided Design. IEEE, 2013: 189–196.
[doi:10.1109/FMCAD.2013.6679409] |
| [17] |
刘军祥,王永吉,王源,邢建生,曾海涛.基于逻辑“或”约束优化的实时系统设计.软件学报,2006,17(7):1641–1649. http://www.jos.org.cn/1000-9825/17/1641.htm [doi: 10.1360/jos171641]
|
| [26] |
陈力, 王永吉, 吴敬征, 吕荫润. 基于树状线性规划搜索的单调速率优化设计. 软件学报, 2015, 26(12): 3223–3241.
[doi:10.13328/j.cnki.jos.004853]
|
| [27] |
王永吉, 陈秋萍. 单调速率及其扩展算法的可调度性判定. 软件学报, 2004, 15(6): 799–814.
http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=20040602&journal_id=jos
|