偶发实时系统可调度性分析问题的整数规划方法

• 作者: 关楠 孙景昊 孙景昶 邓庆绪
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 截止期优先 可调度性分析 整数规划 多面体分析 线性松弛
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 操作系统
• 页码范围: 411-428
• 页数: 18页
• 分类号: TP316
• 字数: 18173字
• 语种: 中文
• DOI: 10.13328/j.cnki.j0s.005025

摘要

偶发实时任务最早截止期优先(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％的算例,该算法将可调度上界的值平均降低了近104倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邓庆绪	东北大学信息科学与工程学院	41	189	8.0	12.0
2	关楠	东北大学信息科学与工程学院	11	82	6.0	8.0
3	孙景昊	东北大学信息科学与工程学院	6	30	3.0	5.0
4	孙景昶	四川大学计算机学院	2	6	1.0	2.0