-
题名偶发实时系统可调度性分析问题的整数规划方法
被引量：6
- 1
-
-
作者
孙景昊
孙景昶
关楠
邓庆绪
-
机构
东北大学信息科学与工程学院
四川大学计算机学院
-
出处
《软件学报》
EI
CSCD
北大核心
2017年第2期411-428,共18页
-
基金
国家重点基础研究发展计划(973)(2014CB360509)
国家自然科学基金(61672147
+2 种基金
61300194
61300022
61472072)~~
-
文摘
偶发实时任务最早截止期优先(earliest deadline first,简称EDF)可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法(pseudo-polynomail time decision algorithm,简称PTDA)均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统,现有PTDA则不再适用.针对以上问题,为同步和异步两类实时系统建立了统一的整数规划模型,其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式,进而提出了同/异步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明,该方法能够获得较紧的问题解下界,在异步和同步系统中,线性松弛解与最优解之间的平均百分界差gap分别为0.78%和1.27%.另外,随机生成了大量同步和异步系统的算例,用于该算法和传统算法进行性能比较.对于同步算例,实验结果表明,在U>0.99时,该算法能够对70%的算例给出判定结果,算法性能与QPA算法相比有指数级提升.对于异步算例,实验结果表明,该算法能够对近96%的算例给出可调度性判定.与传统算法相比,该方法将不能判定可调度性的算例比例平均降低了29.27%.对于剩余的4%的算例,该算法将可调度上界的值平均降低了近10~4倍.
-
关键词
截止期优先
可调度性分析
整数规划
多面体分析
线性松弛
-
Keywords
earliest deadline first
schedulability
integer programming
polyhedral analysis
linear relaxation
-
分类号
TP316
[自动化与计算机技术—计算机软件与理论]
-
