一種基于EDF的實時任務調度算法淺析

劉偉

摘 要 實時系統的高可靠性、計算準確性及輸出結果的實時性使得其在各領域的應用越來越廣泛。而實時調度算法是實時系統中的關鍵技術。本文在EDF算法的基礎上提出了一種新的實時調度算法，該算法通過任務的可推遲執行時間逐次逼近，能夠快速準確的計算出每個任務的最大可挪用時間。

關鍵詞 實時性；實時調度算法；單調速率優先；最早截止期優先；計算時間

前言

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

1 實時調度算法

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

2 任務模型

本文使用以下概念來描述實時系統。

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

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

定義3（周期任務集的負載）：系統中周期任務集中所有周期任務的負載之和，記為U，U= （n為周期任務集中的周期任務數）[3]。

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

（1）系統中有且只有一個處理器；

（2）系統中任務之間相互獨立，即除CPU外，它們沒有依賴關系和共享資源；

（3）任務都是可以被剝奪的，任務切換和調度的時間為0或可以忽略；

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

3 最早截止期優先調度算法的改進

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

算法的具體過程如下：

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

（2）m=m+1；

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

（4）如果P>m⊿P，轉（2）。

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

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

4 結束語

論文提出了對EDF算法的改進算法。該算法通過任務的可推遲執行時間逐次逼近，能夠快速準確的計算出每個任務的最大可挪用時間，并證明了該算法的時間復雜度只和周期任務集的總負載及周期任務數有關。

參考文獻

[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] 喬穎，王宏安，戴國忠. 一種新的實時多處理器系統的動態調度算法[J].軟件學報，2002，13（1）：51-58.

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

[5] 涂剛，陽富明，盧炎生.基于動態優先級策略的最優軟非周期任務調度算法[J].計算機研究與發展，2004，41（21）：2026-2034.