在一個單處理器的實時調(diào)度系統(tǒng)中,任務加速或者新任務插入所導致的超負荷可以通過任務壓縮來應對,這就是彈性調(diào)度中的帶寬轉(zhuǎn)讓。但是為了避免實際的新任務插入過程中可能會發(fā)生的截止期丟失,就有必要采用平滑插入方法,而平滑插入問題的關鍵就是最早平滑時刻的求取�，F(xiàn)有一個初步的最早平滑時刻求取方法——Simple way,該方法的核心就是在逐步延遲的釋放過程當中試探新任務的平滑插入點,本文以文獻研究和仿真實驗等方法對該問題做了進一步的考察,獲得了比該方法更先進的研究結(jié)果�；贓DF（Earliest Deadline First）算法,本文首先在多任務的帶寬轉(zhuǎn)讓情形下將實時周期任務的模型簡化為一個由執(zhí)行時間,初始周期和受壓后周期所組成的三元組,并且以此為基礎重新描述了彈性調(diào)度中的實時多任務帶寬轉(zhuǎn)讓過程和過渡過程。然后對現(xiàn)行任務的壓縮過程做了細致的分析,分析了該過程中的處理器需求計算方法,接著提出了一個準則——延遲判斷準則,在該準則的證明過程中,本文指出新任務的插入所導致的截止期丟失只有兩種情況,第一種是現(xiàn)行任務的截止期丟失,第二種是新任務的截止期丟失,并且最終證明了該準則在這兩種情形下都成立。延遲判斷... 

【文章來源】：湖南師范大學湖南省 211工程院校

【文章頁數(shù)】：57 頁

【學位級別】：碩士

【部分圖文】：

速率固定算法調(diào)度模擬

碩士學位論文10以支持更高的使用率，最理想的情形則是：任務周期之間“兩兩調(diào)和”——即任意選一對任務，它們的周期都存在整數(shù)倍數(shù)關系，此時RM的可調(diào)度使用率可以達到1[58]。但是現(xiàn)實的任務往往是隨機的，很難滿足上述條件。因此公式（2.1）限定了RM在一般情形下的使用率上界，如果任務周期之間不存在調(diào)和關系，那么隨著任務數(shù)量的增加，RM的可調(diào)度上限將會逼近ln2≈0.69，意味著接近30%的處理器資源無法被利用，如圖2-2：圖2-2：RM的可調(diào)度上限與任務數(shù)量的關系此外，在RM調(diào)度中，最高優(yōu)先級的任務總是不會丟失截止期，因為其總是能夠優(yōu)先得到足夠的資源，而在一般情況下，只要任務集的使用率滿足公式（2.1），那么就是RM可調(diào)度的，但是如果系統(tǒng)載荷超過該值時，調(diào)度就會發(fā)生不可預測的截止期丟失，因此RM無法充分的利用處理器資源，因而也就無法應用于高負載情形[59]。2.3.2最早截止期優(yōu)先調(diào)度算法最早截止期優(yōu)先調(diào)度算法即EDF調(diào)度算法，是一種可搶占式的動態(tài)優(yōu)先級調(diào)度算法，和RM相比，EDF的主要優(yōu)點在于其對系統(tǒng)資源的利用率更高。EDF的動態(tài)優(yōu)先級意味著任務的優(yōu)先級會隨著任務的運行而變化，在任意時刻，任務的優(yōu)先級都由其截止期決定，截止期越近意味著該任務的處理需求越緊急，因此相應的任務優(yōu)先級就越高[60]。在EDF調(diào)度中，任務的優(yōu)先級會隨著調(diào)度過程的進行而變化，具體的，由于EDF算法中，任務的優(yōu)先級取決于該任務當前作業(yè)的截止期，截止期越近的任務被執(zhí)行的優(yōu)先級就越高，而當本周期的執(zhí)行量完成之后，該任務的截止期就會回到最初的初始優(yōu)先級，而其它優(yōu)先級更高的任務會被選擇執(zhí)行[1]。因此每個任務的優(yōu)先級都會隨著調(diào)度的進行而變化，而且由于實時任務的周期性特點，這個變化也呈現(xiàn)出周期性。下面舉一個簡單的例子來說

碩士學位論文12圖2-3：最早截止期優(yōu)先算法調(diào)度示例圖2-3的上面三行表示三個任務的調(diào)度執(zhí)行，在每一行的最左邊為任務名，如τ0[1,4]表示該任務的名稱為τ0，執(zhí)行量為1，周期為4，豎的實線表示該任務的周期線，黑色的矩形表示該任務在該時刻被執(zhí)行，最后一行time表示時間軸，部分調(diào)度過程如前面所述。由于任務總是周期性的發(fā)起請求，因此，每個任務的相對截止期是不斷變化的。顯然，維護一個不斷更新的優(yōu)先隊列需要付出巨大的開銷，因此EDF一般只在調(diào)度事件發(fā)生時才選取截止期最接近的任務，這就意味著每個任務都要維護自身的截止期數(shù)據(jù)，在每個周期開始時都要重置自身的截止期數(shù)據(jù)，并且在運行時不斷更新其截止期數(shù)值。雖然在EDF中，任務的優(yōu)先級是隨著任務截止期的變化而變化的，但是EDF的調(diào)度邏輯從根本上依然是基于優(yōu)先級的，因此EDF和RM在實現(xiàn)時的主要區(qū)別在于，EDF需要實現(xiàn)額外的截止期的維護工作。當然，EDF和RM算法的區(qū)別和特點還有許多，此處不再過多贅述。如果不考慮任務的中斷、遷移等操作所引入的額外開銷，且沒有實時新任務的情況下（即所有任務都在時刻0釋放），那么對于EDF算法，有定理2.1成立[61]。定理2.1（EDF可調(diào)度準則）：如果一個實時周期任務集的使用率之和不大于1，那么就是EDF可調(diào)度的。因此，EDF對處理器資源的利用率更高，能夠很好的適應高負載情形下的實時調(diào)度環(huán)境。2.4彈性調(diào)度與平滑插入彈性調(diào)度（ElasticScheduling）一種基于EDF的實時調(diào)度模型，是一種能夠根據(jù)外部環(huán)境或?qū)嶋H需要的變化來動態(tài)調(diào)整任務集合的自適應模型，其彈性概念的引入可以很好的適用于有動態(tài)計算需求的實時應用程序。在彈性調(diào)度模型中，

【參考文獻】：
期刊論文
[1]最晚截止期優(yōu)先帶寬轉(zhuǎn)讓算法[J]. 錢光明,楊揚.  計算機工程. 2013(09)
[2]實時任務調(diào)度算法最早可行時刻的求取模式[J]. 錢光明,姜輝,陳湘華.  計算機工程. 2012(04)
[3]平滑而快速地插入新任務[J]. 錢光明.  湖南文理學院學報(自然科學版). 2008(02)
[4]一種改進的時間片輪轉(zhuǎn)調(diào)度算法[J]. 肖建明,張向利.  計算機應用. 2005(S1)
[5]四種嵌入式實時操作系統(tǒng)關鍵技術(shù)分析[J]. 季志均,馬文麗,陳虎,鄭文嶺.  計算機應用研究. 2005(09)
[6]實時系統(tǒng)任務模型初探[J]. 錢光明.  儀器儀表用戶. 2005(04)

博士論文
[1]實時系統(tǒng)動態(tài)優(yōu)先級任務調(diào)度算法的研究[D]. 巴巍.大連理工大學 2010

碩士論文
[1]實時多任務壓縮和插入問題的研究[D]. 梁麗穩(wěn).湖南師范大學 2019
[2]EDF算法中任務對帶寬轉(zhuǎn)讓問題的研究[D]. 周垠宇.湖南師范大學 2017



本文編號：3128717