一種基于EDF的實(shí)時(shí)任務(wù)調(diào)度算法淺析

劉偉

摘 要 實(shí)時(shí)系統(tǒng)的高可靠性、計(jì)算準(zhǔn)確性及輸出結(jié)果的實(shí)時(shí)性使得其在各領(lǐng)域的應(yīng)用越來(lái)越廣泛。而實(shí)時(shí)調(diào)度算法是實(shí)時(shí)系統(tǒng)中的關(guān)鍵技術(shù)。本文在EDF算法的基礎(chǔ)上提出了一種新的實(shí)時(shí)調(diào)度算法，該算法通過(guò)任務(wù)的可推遲執(zhí)行時(shí)間逐次逼近，能夠快速準(zhǔn)確的計(jì)算出每個(gè)任務(wù)的最大可挪用時(shí)間。

關(guān)鍵詞 實(shí)時(shí)性；實(shí)時(shí)調(diào)度算法；單調(diào)速率優(yōu)先；最早截止期優(yōu)先；計(jì)算時(shí)間

前言

實(shí)時(shí)系統(tǒng)是指能夠及時(shí)響應(yīng)外部發(fā)生的隨機(jī)事件，并在規(guī)定時(shí)間內(nèi)完成對(duì)事件處理的計(jì)算機(jī)系統(tǒng)。實(shí)時(shí)系統(tǒng)具有高可靠性、實(shí)時(shí)性、少人工干預(yù)、專用性等特征，廣泛應(yīng)用于航天控制、工業(yè)控制、機(jī)器人智能控制、云計(jì)算、多處理器下多媒體流調(diào)度以及嵌入式智能設(shè)備等各個(gè)重要領(lǐng)域。實(shí)時(shí)系統(tǒng)不僅應(yīng)用廣泛，而且要求嚴(yán)格。對(duì)實(shí)時(shí)調(diào)度算法的研究，是實(shí)時(shí)領(lǐng)域的一個(gè)重要的研究課題[1]。

1 實(shí)時(shí)調(diào)度算法

實(shí)時(shí)調(diào)度算法可以分為兩類：靜態(tài)調(diào)度算法和動(dòng)態(tài)調(diào)度算法。RM 和 EDF 調(diào)度算法分別是經(jīng)典的靜態(tài)和動(dòng)態(tài)實(shí)時(shí)高度算法，在實(shí)時(shí)調(diào)度領(lǐng)域占有重要地位。EDF調(diào)度算法按照實(shí)時(shí)任務(wù)截止期的遠(yuǎn)近來(lái)分配優(yōu)先級(jí)，截止期越近的任務(wù)優(yōu)先級(jí)越高，任何時(shí)刻總是運(yùn)行優(yōu)先級(jí)最高的任務(wù)，即總是優(yōu)先運(yùn)行最緊迫的任務(wù)。因?yàn)樵诓煌瑫r(shí)刻，兩個(gè)周期任務(wù)截止期的遠(yuǎn)近關(guān)系可能會(huì)改變，所以EDF調(diào)度算法是一種動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法。EDF算法不僅對(duì)于硬實(shí)時(shí)周期任務(wù)調(diào)度，而且對(duì)于硬實(shí)時(shí)非周期任務(wù)的調(diào)度來(lái)說(shuō)都是最優(yōu)的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法本文在EDF算法的基礎(chǔ)上提出了一種新的實(shí)時(shí)調(diào)度算法，該算法通過(guò)任務(wù)的可推遲執(zhí)行時(shí)間逐次逼近，能夠快速準(zhǔn)確的計(jì)算出每個(gè)任務(wù)的最大可挪用時(shí)間[2]。

2 任務(wù)模型

本文使用以下概念來(lái)描述實(shí)時(shí)系統(tǒng)。

定義1（超周期，hyperperiod）：硬實(shí)時(shí)周期任務(wù)集中的所有任務(wù)周期的最小公倍數(shù)，記為H，H=LCM（T1，T2，…，Tn），其中LCM是最小公倍數(shù)函數(shù)。

定義2（周期任務(wù)的負(fù)載）：一個(gè)周期任務(wù)平均對(duì)處理器的占用率，記為u，u=C/T，C為周期任務(wù)每次的執(zhí)行時(shí)間，T為周期任務(wù)的周期，即每次釋放的時(shí)間間隔。

定義3（周期任務(wù)集的負(fù)載）：系統(tǒng)中周期任務(wù)集中所有周期任務(wù)的負(fù)載之和，記為U，U= （n為周期任務(wù)集中的周期任務(wù)數(shù)）[3]。

另外，針對(duì)該任務(wù)模型本文還作如下假定：

（1）系統(tǒng)中有且只有一個(gè)處理器；

（2）系統(tǒng)中任務(wù)之間相互獨(dú)立，即除CPU外，它們沒(méi)有依賴關(guān)系和共享資源；

（3）任務(wù)都是可以被剝奪的，任務(wù)切換和調(diào)度的時(shí)間為0或可以忽略；

（4）所有硬實(shí)時(shí)周期任務(wù)的相對(duì)截止期都等于它們的周期，即D=T。

3 最早截止期優(yōu)先調(diào)度算法的改進(jìn)

根據(jù)EDF算法調(diào)度硬實(shí)時(shí)周期任務(wù)集的可調(diào)度性判定條件，當(dāng)周期任務(wù)集的負(fù)載U等于1時(shí)，EDF算法仍然是可調(diào)度的，所以如果單獨(dú)把第i個(gè)周期任務(wù)的執(zhí)行時(shí)間增大（1-u）Ti，使得所有周期任務(wù)的負(fù)載之和剛好等于1，這時(shí)所有任務(wù)也都可以在截止時(shí)刻前完成，顯然如果不增加第i個(gè)周期任務(wù)的執(zhí)行時(shí)間，那么它至少可以在截止時(shí)刻前（1-u）Ti時(shí)刻完成，即第i個(gè)周期任務(wù)的最大可挪用時(shí)間至少為（1-U）Ti。把所有周期任務(wù)按照周期的從小到大排序，使得T1T2……Tn。令⊿P=（1-U）T1，那么所有任務(wù)的最小可延遲時(shí)間，即所求的最大可挪用時(shí)間P⊿P。然后用⊿P去逼近最大可挪用時(shí)間P。如圖1所示，根據(jù)最小周期T，可以把時(shí)間劃分為等分的[ti，ti+1]時(shí)間段，使得ti=iT1：（i=0，1，…）[4]。

算法的具體過(guò)程如下：

（1）找出周期任務(wù)集中的周期最小的一個(gè)，假定為周期任務(wù)1。令⊿P=（1-u）T1，P=（T1-C1），m=1；

（2）m=m+1；

（3）對(duì)每一個(gè)周期任務(wù)i，計(jì)算它的截止時(shí)刻，如果，則根據(jù)公式計(jì)算該任務(wù)的可延遲時(shí)間，求出截止時(shí)刻在中的所有任務(wù)的最小可延遲時(shí)間Pm。如果Pm

（4）如果P>m⊿P，轉(zhuǎn)（2）。

（5）完成。P為最大可挪用時(shí)間。

因?yàn)槊恳粋€(gè)時(shí)間段[tm-1，tm]的長(zhǎng)度是最小的周期T1，所以截止期在一個(gè)時(shí)間段中的任務(wù)最多只有n個(gè)（n為周期任務(wù)數(shù)），可得在第（3）步中的最多只需要計(jì)算n次可延遲時(shí)間。令M表示算法結(jié)束時(shí)的m，根據(jù)算法的結(jié)束條件可知：其中（1-U1）T1是P的一個(gè)上界。所以算法的時(shí)間復(fù)雜度是。如果周期任務(wù)集的總負(fù)載不大于90%，可以保證最多10步就可以算出P[5]。

4 結(jié)束語(yǔ)

論文提出了對(duì)EDF算法的改進(jìn)算法。該算法通過(guò)任務(wù)的可推遲執(zhí)行時(shí)間逐次逼近，能夠快速準(zhǔn)確的計(jì)算出每個(gè)任務(wù)的最大可挪用時(shí)間，并證明了該算法的時(shí)間復(fù)雜度只和周期任務(wù)集的總負(fù)載及周期任務(wù)數(shù)有關(guān)。

參考文獻(xiàn)

[1] Burns A，Prasad D，Bondavalli A，et al. The meaning and role of value in scheduling flexible real-time systems[J]. Journal of Systems Architecture，2000，46（4）：305-325.

[2] Kim Dong-Sung，Choi Dong-Hyuk，Mohapatra Prasant.Real-time scheduling method for networked discrete control systems[J]. Control Engineering Practice，2009，17（5）：564-570.

[3] 喬穎，王宏安，戴國(guó)忠. 一種新的實(shí)時(shí)多處理器系統(tǒng)的動(dòng)態(tài)調(diào)度算法[J].軟件學(xué)報(bào)，2002，13（1）：51-58.

[4] 何軍，孫玉方.提高軟非周期任務(wù)相應(yīng)性能的調(diào)度算法[J].軟件學(xué)報(bào)，1998，9（10）：721-727.

[5] 涂剛，陽(yáng)富明，盧炎生.基于動(dòng)態(tài)優(yōu)先級(jí)策略的最優(yōu)軟非周期任務(wù)調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展，2004，41（21）：2026-2034.