劉偉

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

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

前言

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

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

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

2 任務(wù)模型

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

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

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

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

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

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

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

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

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

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

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

算法的具體過程如下：

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

（2）m=m+1；

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

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

（5）完成。P為最大可挪用時間。

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

4 結(jié)束語

論文提出了對EDF算法的改進算法。該算法通過任務(wù)的可推遲執(zhí)行時間逐次逼近，能夠快速準確的計算出每個任務(wù)的最大可挪用時間，并證明了該算法的時間復雜度只和周期任務(wù)集的總負載及周期任務(wù)數(shù)有關(guā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] 喬穎，王宏安，戴國忠. 一種新的實時多處理器系統(tǒng)的動態(tài)調(diào)度算法[J].軟件學報，2002，13（1）：51-58.

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

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