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