最早期限優(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)先級低的任務(wù)截止之間能否得到滿足的缺點，從而產(chǎn)生了EDF算法的優(yōu)化算法NEDF和DPDS，較好的解決了上述問題，平衡了CPU使用率、響應(yīng)時間、公平性和截止時間的問題。關(guān)鍵詞：任務(wù)調(diào)度；動態(tài)調(diào)度；優(yōu)先級；EDF引言：隨著計算機的發(fā)展，多道程序處理的出現(xiàn)需要強大的調(diào)度算法來對多任務(wù)進行調(diào)度，以確定多任務(wù)環(huán)境下任務(wù)的執(zhí)行順序以及占有CPU時間。相對于靜態(tài)、不可搶占的調(diào)度方法，EDF的出現(xiàn)使之憑借靈

2、活性高、CPU占有率高很快成為最優(yōu)的單處理器調(diào)度算法。一、任務(wù)調(diào)度的基本概念在計算機發(fā)展的初期，需要使用計算機時，通常要集中在計算機所在的地方，人為的以作業(yè)的方式把工作內(nèi)容一件一件的交給計算機處理，也就不存在調(diào)度的概念。隨后，出現(xiàn)了計算機的批處理方式，計算機把作業(yè)按照先來先服務(wù)的方式進行處理，體現(xiàn)了一種非常簡單的調(diào)度概念。隨著多道程序處理方式的出現(xiàn)，調(diào)度逐漸變得重要和復(fù)雜起來。在多任務(wù)的實時操作系統(tǒng)中，調(diào)度是一個非常重要的功能，用來確定多任務(wù)環(huán)境下任務(wù)執(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)性能（如吞吐率、延遲時間等）的重要部分。在設(shè)計調(diào)度程序時，通常要綜合考慮如下因素：CPU的使用率、輸入、輸出設(shè)備的吞吐率、響應(yīng)時間、公平性和截止時間。這些因素之間有一定的沖突性，在設(shè)計調(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、預(yù)先確定，且不容易發(fā)生變化的應(yīng)用。在線調(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ù)任務(wù)在運行過程中能否被打斷的處理情況。調(diào)度算法分為搶占式調(diào)度和非搶占式調(diào)度兩類。在搶占式調(diào)度方法中，正在運行的任務(wù)可能被其他任務(wù)打斷。在非搶占式調(diào)度算法中，一旦任務(wù)開始運行，該任務(wù)只有在運行完成而主動放棄CPU資源，或是因為等待其他資源被阻塞的情況下才會停止運行。實時內(nèi)核大都采用了搶占式調(diào)度算法，使關(guān)鍵任務(wù)能夠打斷非關(guān)鍵任務(wù)執(zhí)行，確保關(guān)鍵任

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

6、所有任務(wù)及其時間約束（如截至?xí)r間、運行時間、優(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)度算法，任務(wù)的優(yōu)先級根據(jù)任務(wù)的截止時間來確定。任務(wù)的截止時間越近，任務(wù)的優(yōu)先級越高；任務(wù)的截止時間越遠，任務(wù)額優(yōu)先級越低。當(dāng)有新的任務(wù)處于就緒狀態(tài)時，任務(wù)的優(yōu)先級就有可能需要進行調(diào)整?，F(xiàn)通過分析如下一系列任務(wù)來理解EDF算法： 任務(wù)名稱 到達時刻 執(zhí)行時間 絕對時間限 T1 0

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

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

9、集，那么其他所有的調(diào)度算法也不能做到。3、EDF算法的測試如果所有的任務(wù)都是周期性的，并且對應(yīng)的時間限等于它們的周期，對任務(wù)集的調(diào)度性的測試是非常簡單的：如果任務(wù)集的總利用率不大于1，那么任務(wù)集就可以由EDF算法在一個單處理器上進行合理的調(diào)度。對于那些任務(wù)的時間限并不全等于其周期的情況，沒有簡答的調(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)是任務(wù)

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

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

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

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

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

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