【摘要】：偶發(fā)實時任務最早截止期優(yōu)先(earliest deadline first,簡稱EDF)可調度分析是實時系統(tǒng)領域經典的NP困難問題.現有的偽多項式時間判定算法(pseudo-polynomail time decision algorithm,簡稱PTDA)均局限于利用率U嚴格小于1的同步任務系統(tǒng).對于U≤1的同步系統(tǒng)或更加困難的異步系統(tǒng),現有PTDA則不再適用.針對以上問題,為同步和異步兩類實時系統(tǒng)建立了統(tǒng)一的整數規(guī)劃模型,其規(guī)模并不依賴于利用率U的取值.基于多面體理論證明了模型維數和極大誘導不等式,進而提出了同/異步系統(tǒng)上EDF可調度性分析問題統(tǒng)一的多項式時間線性松弛求解方法.實驗結果表明,該方法能夠獲得較緊的問題解下界,在異步和同步系統(tǒng)中,線性松弛解與最優(yōu)解之間的平均百分界差gap分別為0.78%和1.27%.另外,隨機生成了大量同步和異步系統(tǒng)的算例,用于該算法和傳統(tǒng)算法進行性能比較.對于同步算例,實驗結果表明,在U0.99時,該算法能夠對70%的算例給出判定結果,算法性能與QPA算法相比有指數級提升.對于異步算例,實驗結果表明,該算法能夠對近96%的算例給出可調度性判定.與傳統(tǒng)算法相比,該方法將不能判定可調度性的算例比例平均降低了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