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

发布时间：2019-08-26 10:13

【摘要】：偶发实时任务最早截止期优先(earliest deadline first,简称EDF)可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法(pseudo-polynomail time decision algorithm,简称PTDA)均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统,现有PTDA则不再适用.针对以上问题,为同步和异步两类实时系统建立了统一的整数规划模型,其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式,进而提出了同/异步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明,该方法能够获得较紧的问题解下界,在异步和同步系统中,线性松弛解与最优解之间的平均百分界差gap分别为0.78%和1.27%.另外,随机生成了大量同步和异步系统的算例,用于该算法和传统算法进行性能比较.对于同步算例,实验结果表明,在U0.99时,该算法能够对70%的算例给出判定结果,算法性能与QPA算法相比有指数级提升.对于异步算例,实验结果表明,该算法能够对近96%的算例给出可调度性判定.与传统算法相比,该方法将不能判定可调度性的算例比例平均降低了29.27%.对于剩余的4%的算例,该算法将可调度上界的值平均降低了近10~4倍.
[Abstract]:The earliest deadline first (earliest deadline first, (EDF) schedulable analysis of occasional real-time tasks is a classical NP difficult problem in the field of real-time systems. The existing pseudo-polynomial time decision algorithms (pseudo-polynomail time decision algorithm, for short PTDA) are limited to synchronous task systems with utilization U strictly less than 1. For synchronous systems with U 鈮，

本文编号：2529198