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

1、最早期限優(yōu)先調(diào)度算法（EDD的特點(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)度開(kāi)銷增大、不能確定優(yōu)先級(jí)低的任務(wù)截止之間能否得到滿足的缺點(diǎn)，從而產(chǎn)生了EDF算法的優(yōu)化算法NEDF和DPDS較好的解決了上述問(wèn)題，平衡了CPU使用率、響應(yīng)時(shí)間、公平性和截止時(shí)間的問(wèn)題。關(guān)鍵詞：任務(wù)調(diào)度；動(dòng)態(tài)調(diào)度；優(yōu)先級(jí)；EDF引言：隨著計(jì)算機(jī)的發(fā)展，多道程序處理的出現(xiàn)需要強(qiáng)大的調(diào)度算法來(lái)對(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è)按照先來(lái)先服務(wù)的方式進(jìn)行處理，體現(xiàn)了一種非常簡(jiǎn)單的調(diào)度概念。隨著多道程序處理方式的出現(xiàn)，調(diào)度逐漸變得重要和復(fù)雜起來(lái)。在多任務(wù)的實(shí)時(shí)操作系統(tǒng)中，調(diào)度是一個(gè)非常重要的功能，用來(lái)確定多任務(wù)環(huán)境下任務(wù)執(zhí)行的順序和獲得CPU資源后能夠執(zhí)行的時(shí)間長(zhǎng)度。操作系統(tǒng)通過(guò)一個(gè)調(diào)度程序看來(lái)實(shí)現(xiàn)調(diào)度功能，調(diào)度程序以函數(shù)的形式存在，用來(lái)實(shí)現(xiàn)操作系統(tǒng)的調(diào)度算法。調(diào)度

3、程序是影響系統(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)度方法來(lái)說(shuō)，主要存在以下幾種劃分方法：1、離線（off-line）和在線（on-line）調(diào)度根據(jù)獲得調(diào)度信息的時(shí)機(jī)，調(diào)度算法可以分為離線調(diào)度和在線調(diào)度兩類。對(duì)于離線調(diào)度算法，運(yùn)行過(guò)程中使用的調(diào)度信息在系統(tǒng)運(yùn)行之前就確定了，如時(shí)間驅(qū)動(dòng)的調(diào)度。離線調(diào)度算法具有確定性，但缺乏靈活性，適用于特征能夠預(yù)先確

4、定，且不容易發(fā)生變化的應(yīng)用。在線調(diào)度算法的調(diào)度信息則在系統(tǒng)運(yùn)行過(guò)程中動(dòng)態(tài)獲得，如優(yōu)先級(jí)驅(qū)動(dòng)的調(diào)度（如EDF,RM野）。在線調(diào)度算法在形成最佳調(diào)度決策上具有較大的靈活性。2、搶占（preemptive）和非搶占（non-preemptive）調(diào)度根據(jù)任務(wù)在運(yùn)行過(guò)程中能否被打斷的處理情況。調(diào)度算法分為搶占式調(diào)度和非搶占式調(diào)度兩類。在搶占式調(diào)度方法中，正在運(yùn)行的任務(wù)可能被其他任務(wù)打斷。在非搶占式調(diào)度算法中，一旦任務(wù)開(kāi)始運(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)鍵任務(wù)的截止時(shí)

5、間能夠得到滿足。相對(duì)來(lái)說(shuō)，搶占式調(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)確定下來(lái)，且在運(yùn)行過(guò)程中不會(huì)發(fā)生變化（如RMS）。在動(dòng)態(tài)調(diào)度算法中，任務(wù)的優(yōu)先級(jí)則在運(yùn)行過(guò)程中確定，并可能不斷發(fā)生變化（如EDF。靜態(tài)調(diào)度算法適用于能夠完全把握系統(tǒng)中所有任務(wù)及其時(shí)間

6、約束（如截至?xí)r間、運(yùn)行時(shí)間、優(yōu)先順序和運(yùn)行過(guò)程中的到達(dá)時(shí)間）特性的情況。靜態(tài)調(diào)度比較簡(jiǎn)單，但缺乏靈活性，不利于系統(tǒng)擴(kuò)展；動(dòng)態(tài)調(diào)度有足夠的靈活性來(lái)處理變化的系統(tǒng)情況，但需要消耗更多的系統(tǒng)資源。三、最早期限優(yōu)先調(diào)度算法（EDF1、EDF算法的基本理解最早期限優(yōu)先調(diào)度算法（EDF是一種采用動(dòng)態(tài)調(diào)度的優(yōu)先級(jí)調(diào)度算法，任務(wù)的優(yōu)先級(jí)根據(jù)任務(wù)的截止時(shí)間來(lái)確定。任務(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)通過(guò)分析如下一系列任務(wù)來(lái)理解EDF算法:任務(wù)名稱到達(dá)時(shí)刻執(zhí)行時(shí)間絕對(duì)時(shí)間限01030431051025當(dāng)?shù)竭_(dá)時(shí)，

7、它是唯一等待運(yùn)行的任務(wù)，因此立即開(kāi)始執(zhí)行。在時(shí)刻4到達(dá)，因?yàn)椋膬?yōu)先級(jí)高于因而打斷搶先開(kāi)始運(yùn)行。在時(shí)刻5達(dá)到，由于，因此的優(yōu)先級(jí)低于，必須等待執(zhí)行完畢。當(dāng)執(zhí)行完（在時(shí)刻7）以后，開(kāi)始執(zhí)行（由于它的優(yōu)先級(jí)高于）。一直運(yùn)行到時(shí)刻17,此時(shí)繼續(xù)執(zhí)行直到完成。2、EDF算法的基本假設(shè)EDF算法的分析是基于一系列假設(shè)的基礎(chǔ)上的：a）沒(méi)有任務(wù)非搶先的區(qū)域，并且搶先的成本是極小的；b）只有處理要求是顯著的，內(nèi)存、I/O和別的資源要求都可以忽略；c）所有的任務(wù)都是獨(dú)立的，沒(méi)有優(yōu)先約束。這些假設(shè)都極大地簡(jiǎn)化了EDF的分析。假設(shè)a表明，我們可以在任何時(shí)間搶占任何任務(wù)，此后還可以還原它，這個(gè)過(guò)程沒(méi)有損失，一個(gè)任務(wù)

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

9、單的：如果任務(wù)集的總利用率不大于1,那么任務(wù)集就可以由EDF算法在一個(gè)單處理器上進(jìn)行合理的調(diào)度。對(duì)于那些任務(wù)的時(shí)間限并不全等于其周期的情況，沒(méi)有簡(jiǎn)答的調(diào)度性測(cè)試。在這樣的情況下，需要使用EDF算法生成一個(gè)時(shí)間表，來(lái)判斷是不是在一個(gè)給定的時(shí)間區(qū)間內(nèi)所有的時(shí)間限都被滿足。在這種情況下EDF的一個(gè)可調(diào)度性測(cè)試如下：定義，以及（這里的“l(fā)cm”表示最小公倍數(shù)）。定義是任務(wù)集T中所有滿足其時(shí)間限的絕對(duì)值小魚(yú)t的任務(wù)執(zhí)行時(shí)間之和。一個(gè)由n個(gè)任務(wù)構(gòu)成的集合不是可行的EDF的充分必要條件是：或存在某個(gè)使得（其中n為任務(wù)集中任務(wù)的數(shù)量；為任務(wù)的執(zhí)行時(shí)間；為周期任務(wù)的周期；為任務(wù)的相對(duì)時(shí)間限；為在絕對(duì)時(shí)間不遲于t

10、的任務(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)用的屬性來(lái)分配優(yōu)先級(jí)，其可控性較強(qiáng)，而動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法在資源分配和調(diào)度時(shí)具有更大的靈活性。如果結(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)度算法（NewEarliestDeadlineFirst）1、NEDF算法概述NEDF算法以任務(wù)的截止期限作為任務(wù)調(diào)度的

11、首要指標(biāo)，但不是唯一的指標(biāo)。當(dāng)兩任務(wù)的截止期限在一定的范圍內(nèi)時(shí)，根據(jù)任務(wù)的優(yōu)先級(jí)來(lái)決定要運(yùn)行的任務(wù)，這時(shí)以任務(wù)的靜態(tài)優(yōu)先級(jí)來(lái)選擇任務(wù)，一定程度上增強(qiáng)了算法的可控性。確定任務(wù)的靜態(tài)優(yōu)先級(jí)，主要依據(jù)有以下幾個(gè)。1）執(zhí)行時(shí)間：以執(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算法說(shuō)明先假定任務(wù)的優(yōu)先級(jí)均不相同，則在某個(gè)調(diào)度時(shí)刻t,NEDF算法先查找距

12、截止期限最近的任務(wù)。這時(shí)，可能有多個(gè)任務(wù)的截止期限相等或較為接近。如果截止期限相等，則選擇高優(yōu)先級(jí)的任務(wù)運(yùn)行。如果截止期限均不相等，且最小截止期限比次小截止期限小許多，則選擇最小截止期限的任務(wù)運(yùn)行。若最小截止期限與次小截止期限的差值在一定的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）:DPDg法1、DPDST法概述DPDS是在EDF算法基礎(chǔ)上進(jìn)行改進(jìn)而來(lái)的，DPDS基于截止時(shí)間和優(yōu)先級(jí)兩個(gè)特征參數(shù)。這里的優(yōu)先級(jí)指的是綜合考慮

13、任務(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)過(guò)載情況下，先對(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)度算法占用過(guò)多的計(jì)算時(shí)間，影響系統(tǒng)整體性能。2、算法的實(shí)現(xiàn)DPDSff務(wù)算法主要分為3步實(shí)現(xiàn)：第1步：判斷當(dāng)前系統(tǒng)任務(wù)是否超負(fù)荷

14、，如果沒(méi)有超負(fù)荷，就調(diào)用EDF算法調(diào)度；否則，調(diào)用DPDSJJ法；第2步：對(duì)任務(wù)進(jìn)行分類，將任務(wù)按照優(yōu)先級(jí)進(jìn)行分類，優(yōu)先級(jí)高的為一個(gè)集合，稱之為關(guān)鍵任務(wù)集；優(yōu)先級(jí)相對(duì)較低的為一個(gè)集合，稱為非關(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ù)集沒(méi)有可運(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í)也存在開(kāi)銷大、在臨時(shí)過(guò)載情況下不能確定哪個(gè)任務(wù)的截止時(shí)間不能得到滿足的缺點(diǎn)。在此基礎(chǔ)上，提出了改進(jìn)后的EDF算法：NEDF算法以及DPDS算法，具有了更好的調(diào)度性能。任務(wù)調(diào)度是實(shí)時(shí)內(nèi)核的關(guān)鍵，是整