常用的幾種實時調度算法
最早截止時間優先即EDF(Earliest Deadline First)算法
最低松弛度優先即LLF(Least Laxity First)算法
該算法是根據任務緊急(或松弛)的程度來確定任務的優先級任務的緊急程度愈高為該任務所賦予的優先級就愈高 以使之優先執行例如一個任務在ms時必須完成而它本身所需的運行時間就有ms因此調度程序必須在ms之前調度執行該任務的緊急程度(松弛程度)為ms又如另一任務在ms時必須完成它本身需要運行ms則其松弛程度為ms在實現該算法時要求系統中有一個按松弛度排序的實時任務就緒隊列松弛度最低的任務排在隊列最前面調度程序總是選擇就緒隊列中的隊首任務執行該算法主要用於可搶占調度方式中假如在一個實時系統中有兩個周期性實時任務A和B任務A要求每 ms執行一次執行時間為ms任務B只要求每ms執行一次執行時間為ms
在剛開始時(t=)A必須在ms時完成而它本身運行又需ms可算出A的松弛度為msB必須在ms時完成 而它本身運行就需ms可算出B的松弛度為ms故調度程序應先調度A執行在t=ms時A的松弛度可按下式算出
A的松弛度=必須完成時間其本身的運行時間當前時間
=msmsms=ms
類似地可算出B的松弛度為ms故調度程序應選擇B運行在t=ms時A的松弛度已減為(即)而B的松弛度為ms(即)於是調度程序應搶占B的處理機而調度A運行在t=ms時A的松弛度為ms(即)而B的松弛度僅為ms(即)故又應重新調度B執行在t=ms時B執行完成而此時A的松弛度已減為ms(即)而B的松弛度為ms(即)於是又應調度A執行在t=ms時任務A尚未進入第周期而任務B已進入第周期故再調度B執行在t=ms時A的松弛度已減至ms(即)而B的松弛度為ms(即)故此時調度又應搶占B的處理機而調度A執行
——返回教材目錄
了解更多計算機相關基礎課程視頻
From:http://tw.wingwit.com/Article/program/czxt/201311/24091.html
