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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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