最早期限優(yōu)先調(diào)度算法(EDF)的特點和實現(xiàn)

1、最早期限優(yōu)先調(diào)度算法（EDF）的特點和實現(xiàn)摘要：最早期限優(yōu)先調(diào)度算法是基于優(yōu)先級的動態(tài)調(diào)度方法，是最優(yōu)的單處理器調(diào)度算法，具有靈活性高、能充分利用CPU計算能力的特點。但是同時也具有調(diào)度開銷增大、不能確定優(yōu)先級低的任務截止之間能否得到滿足的缺點，從而產(chǎn)生了EDF算法的優(yōu)化算法NEDF和DPDS，較好的解決了上述問題，平衡了CPU使用率、響應時間、公平性和截止時間的問題。關鍵詞：任務調(diào)度；動態(tài)調(diào)度；優(yōu)先級；EDF引言：隨著計算機的發(fā)展，多道程序處理的出現(xiàn)需要強大的調(diào)度算法來對多任務進行調(diào)度，以確定多任務環(huán)境下任務的執(zhí)行順序以及占有CPU時間。相對于靜態(tài)、不可搶占的調(diào)度方法，EDF的出現(xiàn)使之憑借靈

2、活性高、CPU占有率高很快成為最優(yōu)的單處理器調(diào)度算法。一、任務調(diào)度的基本概念在計算機發(fā)展的初期，需要使用計算機時，通常要集中在計算機所在的地方，人為的以作業(yè)的方式把工作內(nèi)容一件一件的交給計算機處理，也就不存在調(diào)度的概念。隨后，出現(xiàn)了計算機的批處理方式，計算機把作業(yè)按照先來先服務的方式進行處理，體現(xiàn)了一種非常簡單的調(diào)度概念。隨著多道程序處理方式的出現(xiàn)，調(diào)度逐漸變得重要和復雜起來。在多任務的實時操作系統(tǒng)中，調(diào)度是一個非常重要的功能，用來確定多任務環(huán)境下任務執(zhí)行的順序和獲得CPU資源后能夠執(zhí)行的時間長度。操作系統(tǒng)通過一個調(diào)度程序看來實現(xiàn)調(diào)度功能，調(diào)度程序以函數(shù)的形式存在，用來實現(xiàn)操作系統(tǒng)的調(diào)度算法。

3、調(diào)度程序是影響系統(tǒng)性能（如吞吐率、延遲時間等）的重要部分。在設計調(diào)度程序時，通常要綜合考慮如下因素：CPU的使用率、輸入、輸出設備的吞吐率、響應時間、公平性和截止時間。這些因素之間有一定的沖突性，在設計調(diào)度程序時需要優(yōu)先考慮最重要的需求，然后再各種因素之間進行折中處理。二、調(diào)度方法的分類對于大量的實時調(diào)度方法來說，主要存在以下幾種劃分方法：1、 離線（off-line）和在線（on-line）調(diào)度根據(jù)獲得調(diào)度信息的時機，調(diào)度算法可以分為離線調(diào)度和在線調(diào)度兩類。對于離線調(diào)度算法，運行過程中使用的調(diào)度信息在系統(tǒng)運行之前就確定了，如時間驅(qū)動的調(diào)度。離線調(diào)度算法具有確定性，但缺乏靈活性，適用于特征能夠

4、預先確定，且不容易發(fā)生變化的應用。在線調(diào)度算法的調(diào)度信息則在系統(tǒng)運行過程中動態(tài)獲得，如優(yōu)先級驅(qū)動的調(diào)度（如EDF,RMS等）。在線調(diào)度算法在形成最佳調(diào)度決策上具有較大的靈活性。2、 搶占（preemptive）和非搶占（non-preemptive）調(diào)度根據(jù)任務在運行過程中能否被打斷的處理情況。調(diào)度算法分為搶占式調(diào)度和非搶占式調(diào)度兩類。在搶占式調(diào)度方法中，正在運行的任務可能被其他任務打斷。在非搶占式調(diào)度算法中，一旦任務開始運行，該任務只有在運行完成而主動放棄CPU資源，或是因為等待其他資源被阻塞的情況下才會停止運行。實時內(nèi)核大都采用了搶占式調(diào)度算法，使關鍵任務能夠打斷非關鍵任務執(zhí)行，確保關鍵任

5、務的截止時間能夠得到滿足。相對來說，搶占式調(diào)度算法要更復雜些，且需要更多的資源，并可能在使用不當?shù)那闆r下造成低優(yōu)先級任務出現(xiàn)長時間得不到執(zhí)行的情況。非搶占式調(diào)度算法常用于那些任務需要按照預先確定的順序執(zhí)行，且只有當任務主動放棄CPU資源后，其他任務才能得到執(zhí)行的情況。3、 靜態(tài)（static）和動態(tài)（dynamic）調(diào)度 根據(jù)任務優(yōu)先級的確定時機，調(diào)度算法分為靜態(tài)調(diào)度和動態(tài)調(diào)度兩類。在靜態(tài)調(diào)度算法中，所有任務的優(yōu)先級在設計時已經(jīng)確定下來，且在運行過程中不會發(fā)生變化（如RMS）。在動態(tài)調(diào)度算法中，任務的優(yōu)先級則在運行過程中確定，并可能不斷發(fā)生變化（如EDF）。靜態(tài)調(diào)度算法適用于能夠完全把握系統(tǒng)中

6、所有任務及其時間約束（如截至時間、運行時間、優(yōu)先順序和運行過程中的到達時間）特性的情況。靜態(tài)調(diào)度比較簡單，但缺乏靈活性，不利于系統(tǒng)擴展；動態(tài)調(diào)度有足夠的靈活性來處理變化的系統(tǒng)情況，但需要消耗更多的系統(tǒng)資源。三、最早期限優(yōu)先調(diào)度算法（EDF）1、EDF算法的基本理解最早期限優(yōu)先調(diào)度算法（EDF）是一種采用動態(tài)調(diào)度的優(yōu)先級調(diào)度算法，任務的優(yōu)先級根據(jù)任務的截止時間來確定。任務的截止時間越近，任務的優(yōu)先級越高；任務的截止時間越遠，任務額優(yōu)先級越低。當有新的任務處于就緒狀態(tài)時，任務的優(yōu)先級就有可能需要進行調(diào)整?，F(xiàn)通過分析如下一系列任務來理解EDF算法： 任務名稱 到達時刻 執(zhí)行時間 絕對時間限 T1 0

7、 10 30 T2 4 3 10 T3 5 10 25當T1到達時，它是唯一等待運行的任務，因此立即開始執(zhí)行。T2在時刻4到達，因為d2<d1，它的優(yōu)先級高于T1因而打斷T1搶先開始運行。T3在時刻5達到，由于d3>d2，因此T3的優(yōu)先級低于T2，必須等待T2執(zhí)行完畢。當T2執(zhí)行完（在時刻7）以后，T3開始執(zhí)行（由于它的優(yōu)先級高于T1）。T3一直運行到時刻17，此時T1繼續(xù)執(zhí)行直到完成。2、EDF算法的基本假設EDF算法的分析是基于一系列假設的基礎上的：a)沒有任務非搶先的區(qū)域，并且搶先的成本是極小的；b)只有處理要求是顯著的，內(nèi)存、I/O和別的資源要求都可以忽略；c)所有的任務都

8、是獨立的，沒有優(yōu)先約束。這些假設都極大地簡化了EDF的分析。假設a表明，我們可以在任何時間搶占任何任務，此后還可以還原它，這個過程沒有損失，一個任務被搶占的次數(shù)不改變處理器的總工作負荷。從b可以得出，為了檢查可行性，我們只需要保證足夠的處理容量，以在時間期限的要求下執(zhí)行任務，沒有內(nèi)存或者其他的約束條件而導致問題變得復雜。c則表明不存在優(yōu)先約束，意味著任務的釋放時間不依賴于其他任務的結束時間。但是對于部分系統(tǒng)不滿足上述三條假設，則需要采用優(yōu)先的和排斥的約束來解決相應問題。EDF算法是最優(yōu)的單處理器動態(tài)調(diào)度算法，其可調(diào)度上限為100%。也就是說，如果EDF算法不能夠在一個處理器上合理的調(diào)度一個任務

9、集，那么其他所有的調(diào)度算法也不能做到。3、EDF算法的測試如果所有的任務都是周期性的，并且對應的時間限等于它們的周期，對任務集的調(diào)度性的測試是非常簡單的：如果任務集的總利用率不大于1，那么任務集就可以由EDF算法在一個單處理器上進行合理的調(diào)度。對于那些任務的時間限并不全等于其周期的情況，沒有簡答的調(diào)度性測試。在這樣的情況下，需要使用EDF算法生成一個時間表，來判斷是不是在一個給定的時間區(qū)間內(nèi)所有的時間限都被滿足。在這種情況下EDF的一個可調(diào)度性測試如下：定義u=i=1n(ei/Pi)，dmax=max1indi以及P=lcm(P1,Pn)（這里的“l(fā)cm”表示最小公倍數(shù)）。定義hT(t)是任務

10、集T中所有滿足其時間限的絕對值小魚t的任務執(zhí)行時間之和。一個由n個任務構成的集合不是可行的EDF的充分必要條件是：u>1或存在某個t<minP+dmax,u1-umax1inPi-di使得hTt>t（其中n為任務集中任務的數(shù)量；ei為任務Ti的執(zhí)行時間；Pi為周期任務的周期；di為任務Ti的相對時間限；hTt為在絕對時間不遲于t的任務集合T中，所有重復的任務執(zhí)行時間和。）四、EDF算法的改進（1）：NEDF算法基于優(yōu)先級的調(diào)度算法在實時進程調(diào)度中使用很廣泛，靜態(tài)優(yōu)先級調(diào)度算法根據(jù)應用的屬性來分配優(yōu)先級, 其可控性較強, 而動態(tài)優(yōu)先級調(diào)度算法在資源分配和調(diào)度時具有更大的靈活性。

11、如果結合這兩種算法的優(yōu)點, 揚長避短, 就能夠?qū)崟r任務進行更合理、更高效的任務調(diào)度。利用最著名的動態(tài)優(yōu)先級調(diào)度算法EDF 算法的高CPU 利用率、可調(diào)度較大的任務集的特點, 結合靜態(tài)優(yōu)先級調(diào)度算法的可控性就形成了一種新的調(diào)度算法NEDF調(diào)度算法( New Earliest Deadline First )1、NEDF算法概述NEDF 算法以任務的截止期限作為任務調(diào)度的首要指標, 但不是唯一的指標。當兩任務的截止期限在一定的范圍內(nèi)時, 根據(jù)任務的優(yōu)先級來決定要運行的任務, 這時以任務的靜態(tài)優(yōu)先級來選擇任務, 一定程度上增強了算法的可控性。確定任務的靜態(tài)優(yōu)先級, 主要依據(jù)有以下幾個。1）執(zhí)行時間

12、：以執(zhí)行時間為依據(jù), 執(zhí)行時間越短, 靜態(tài)優(yōu)先級越高。2）任務周期：以任務周期為依據(jù), 任務周期越短, 靜態(tài)優(yōu)先級越高。3）任務的CPU 利用率：任務的CPU 利用率為任務執(zhí)行時間與任務周期的比值越高, 靜態(tài)優(yōu)先級越高。4）任務緊急程度：根據(jù)任務的緊急程度, 人為安排任務的優(yōu)先級。任務越緊急, 靜態(tài)優(yōu)先級越高。2、NEDF算法說明先假定任務的優(yōu)先級均不相同，則在某個調(diào)度時刻t，NEDF 算法先查找距截止期限最近的任務。這時，可能有多個任務的截止期限相等或較為接近。如果截止期限相等，則選擇高優(yōu)先級的任務運行。如果截止期限均不相等，且最小截止期限比次小截止期限小許多，則選擇最小截止期限的任務運行。

13、若最小截止期限與次小截止期限的差值在一定的IM 值范圍內(nèi)，則選擇高優(yōu)先級的任務運行。截止期限IM 值的設定應保證最高優(yōu)先級任務能夠如期完成，一般可取最小相對截止期限的值，以確保在最小相對截止期限的周期范圍內(nèi)，最高優(yōu)先級任務能夠優(yōu)先運行。五、 EDF算法的改進（2）：DPDS算法1、DPDS算法概述 DPDS是在EDF 算法基礎上進行改進而來的，DPDS基于截止時間和優(yōu)先級兩個特征參數(shù)。這里的優(yōu)先級指的是綜合考慮任務的運行時間和迫切度而得到的一個全局優(yōu)先級。這樣,每個任務擁有截止時間等級和全局優(yōu)先級兩個參數(shù)。在系統(tǒng)正常工作的情況下按照最早期限優(yōu)先調(diào)度算法（即EDF算法）的調(diào)度方式運行；當系統(tǒng)過載

14、情況下，先對所有任務按照全局優(yōu)先級分成2個組，全局優(yōu)先級較高的分為一個組，全局優(yōu)先級相對較低的分為另一組；優(yōu)先對全局優(yōu)先級高的任務進行調(diào)度，對于優(yōu)先級低的任務采用后臺處理算法，即在處理器空閑時調(diào)度非關鍵任務集中的任務。考慮到嵌入式系統(tǒng)資源的有限性，DPDS盡量采用比較簡單的算法，防止調(diào)度算法占用過多的計算時間,影響系統(tǒng)整體性能。2、算法的實現(xiàn)DPDS任務算法主要分為3步實現(xiàn)：第1步：判斷當前系統(tǒng)任務是否超負荷，如果沒有超負荷，就調(diào)用EDF算法調(diào)度；否則，調(diào)用DPDS算法；第2步：對任務進行分類，將任務按照優(yōu)先級進行分類，優(yōu)先級高的為一個集合，稱之為關鍵任務集；優(yōu)先級相對較低的為一個集合，稱為非

15、關鍵任務集；每當任務中有優(yōu)先級發(fā)生變化時，都要對現(xiàn)有的全部任務進行劃分。第3步：任務調(diào)度。當前任務完成之后,必須刷新當前任務的截止時間，然后判斷任務的全局優(yōu)先級是否有變化，如果優(yōu)先級有變化，就對所有任務按優(yōu)先級重新劃分集合。劃分好任務優(yōu)先級后優(yōu)先對周期任務集中的任務實例采用EDF調(diào)度算法進行調(diào)度。只有當周期任務集沒有可運行的實例時才對隊列中的任務實例同樣采用EDF算法進行調(diào)度運行。由此保證優(yōu)先調(diào)度關鍵任務集中的任務。六、總結最早期限優(yōu)先調(diào)度算法（EDF）作為最佳的單處理器調(diào)度算法，具有靈活性高、CPU利用率高的特點，但是同時也存在開銷大、在臨時過載情況下不能確定哪個任務的截止時間不能得到滿足的缺點。在此基礎上