基于EDF的帶寬轉(zhuǎn)讓算法研究.pdf

1、EDF是1973年由海外學(xué)者提出的一個實時調(diào)度算法，作為一個經(jīng)典算法，它出現(xiàn)在很多的實時系統(tǒng)教材中，至今盡管已跨越了數(shù)十年的歷史，但關(guān)于EDF的動態(tài)性能方面，仍有許多問題有待解決。
　　實時領(lǐng)域著名學(xué)者Buttazzo早在2002年的時候就給出了一個彈性調(diào)度模型。經(jīng)過眾多海內(nèi)外學(xué)者對它不斷的改進和補充，研究成果可以說是十分豐碩。但直至今日，該模型依然沒有完善，尤其是關(guān)于任務(wù)的選擇性壓縮方向還有許多值得我們進行深入研究的地方。

2、>　　本文正是在這個研究背景的基礎(chǔ)上對EDF動態(tài)模型中的任務(wù)選擇性壓縮方向進行的再深入探究。提出了最晚截止期壓縮算法(LatestDeadlineFirst，簡稱LDF)。LDF算法是一種基于任務(wù)截止期的算法，通過比較所有受壓的任務(wù)的截止期，找出具有最晚截止期的那個受壓任務(wù)進行壓縮。在超過80％的情況下LDF算法只需1-2次的比較就能實現(xiàn)新任務(wù)的最快插入?？紤]到單靠壓縮單個任務(wù)出讓的帶寬畢竟有限，文章同時又對多個任務(wù)聯(lián)合壓縮的問題進行了

3、探討。
　　很顯然，單靠壓縮現(xiàn)有任務(wù)出讓的即時帶寬終歸是有限的，所以我們對新任務(wù)的插入方式也做了一定的研究?？紤]到很多場景下新任務(wù)是彈性任務(wù)，本文提出了一個專門針對彈性任務(wù)的新任務(wù)分步插入策略(PartUtilizationFirst，簡稱PUF)。PUF的具體做法就是當(dāng)系統(tǒng)出讓的即時帶寬不足以讓新任務(wù)以最小周期插入時，就讓新任務(wù)先以最大周期插入系統(tǒng)運行，等到過了被壓縮任務(wù)的截止期后再讓新任務(wù)全速運行，它能實現(xiàn)彈性任務(wù)的更早插入。