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

《最早期限優(yōu)先調(diào)度算法(edf)的特點(diǎn)和實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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í)行順序以

2、及占有CPU時(shí)間。相對(duì)于靜態(tài)、不可搶占的調(diào)度方法，EDF的出現(xiàn)使之憑借靈活性高、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)了一種非常簡單的調(diào)度概念。隨著多道程序處理方式的出現(xiàn)，調(diào)度逐漸變得重要和復(fù)雜起來。在多任務(wù)的實(shí)時(shí)操作系統(tǒng)中，調(diào)度是一個(gè)非常重要的功能，用來確定多任務(wù)環(huán)境下任務(wù)

3、執(zhí)行的順序和獲得CPU資源后能夠執(zhí)行的時(shí)間長度。操作系統(tǒng)通過一個(gè)調(diào)度程序看來實(shí)現(xiàn)調(diào)度功能，調(diào)度程序以函數(shù)的形式存在，用來實(shí)現(xiàn)操作系統(tǒng)的調(diào)度算法。調(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-

4、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)度算法具有確定性，但缺乏靈活性，適用于特征能夠預(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)度決策上具有較大的靈活性。1、搶占（preemptive）和非搶占（non-preemptive）調(diào)度根據(jù)任務(wù)在運(yùn)行過程中能否被打斷的處理情況。調(diào)度算法分為搶占式調(diào)

5、度和非搶占式調(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)鍵任務(wù)的截止時(shí)間能夠得到滿足。相對(duì)來說，搶占式調(diào)度算法要更復(fù)雜些，且需要更多的資源，并可能在使用不當(dāng)?shù)那闆r下造成低優(yōu)先級(jí)任務(wù)出現(xiàn)長時(shí)間得不到執(zhí)行的情況。非搶占式調(diào)度算法常用于那些任務(wù)需要按照預(yù)先確定的順序執(zhí)行，且只有當(dāng)任務(wù)主動(dòng)放棄CPU資源后，其他

6、任務(wù)才能得到執(zhí)行的情況。2、靜態(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)中所有任務(wù)及其時(shí)間約束（如截至?xí)r間、運(yùn)行時(shí)間、優(yōu)先順序和運(yùn)行過程中的到達(dá)時(shí)間）特性的情況。靜態(tài)調(diào)度比較簡單，但缺乏靈活性，不利于系統(tǒng)擴(kuò)展；動(dòng)態(tài)調(diào)度有足夠的靈活性來處理變化的系統(tǒng)情

7、況，但需要消耗更多的系統(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í)間限T101030T24310T351025當(dāng)T1到達(dá)時(shí)，它是唯一等待運(yùn)行的任務(wù)，因此立即開始執(zhí)行。T2在時(shí)刻4到達(dá)，因?yàn)閐2

8、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算法的分析是基于一系