淺析rm與edf實(shí)時(shí)調(diào)度算法

《淺析rm與edf實(shí)時(shí)調(diào)度算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、淺析RM與EDF實(shí)時(shí)調(diào)度算法1引言與非實(shí)時(shí)系統(tǒng)相比，嵌入式實(shí)時(shí)系統(tǒng)因其所控制物理過(guò)程的動(dòng)態(tài)性，要求運(yùn)行于其中的單個(gè)任務(wù)必須滿足其時(shí)限要求，以確保整個(gè)系統(tǒng)的正確性和安全性[1]。在航空航天、電信、制造、國(guó)防等領(lǐng)域，對(duì)實(shí)時(shí)系統(tǒng)有著強(qiáng)烈的應(yīng)用需求。實(shí)時(shí)處理和實(shí)時(shí)系統(tǒng)的研究和應(yīng)用工作已經(jīng)有了相當(dāng)長(zhǎng)的歷史，在實(shí)時(shí)任務(wù)調(diào)度理論、實(shí)時(shí)操作系統(tǒng)、實(shí)時(shí)通信等方面取得了大量成果。實(shí)時(shí)任務(wù)調(diào)度理論是實(shí)時(shí)處理技術(shù)的核心和關(guān)鍵[2]。這是因?yàn)?，?shí)時(shí)任務(wù)具有時(shí)限要求，在一個(gè)或多個(gè)處理器之間調(diào)度實(shí)時(shí)任務(wù)，需要判斷是否每個(gè)任務(wù)的執(zhí)行都能在其截止期限內(nèi)完成。如果每個(gè)任務(wù)的執(zhí)行都能在其截止期

2、限內(nèi)完成，則稱該調(diào)度是可行。可調(diào)度性判定就是判定給定的個(gè)實(shí)時(shí)任務(wù)在應(yīng)用某種調(diào)度算法的前提下能否產(chǎn)生一個(gè)可行的調(diào)度。調(diào)度算法的設(shè)計(jì)要盡可能滿足任務(wù)可調(diào)度性的要求[3]。2實(shí)時(shí)調(diào)度分類由于實(shí)時(shí)系統(tǒng)的側(cè)重點(diǎn)不同，實(shí)時(shí)調(diào)度亦有多種分類方式。常見(jiàn)的分類有，根據(jù)任務(wù)實(shí)時(shí)性要求的重要程度，分為硬實(shí)時(shí)調(diào)度和軟實(shí)時(shí)調(diào)度——在硬實(shí)時(shí)調(diào)度中任務(wù)必須在其截止期限內(nèi)執(zhí)行完畢，否則將產(chǎn)生嚴(yán)重后果。而對(duì)于軟實(shí)時(shí)任務(wù)，當(dāng)系統(tǒng)負(fù)載過(guò)重的時(shí)候，允許發(fā)生錯(cuò)過(guò)截止期限的情況，根據(jù)任務(wù)是在一個(gè)或多個(gè)處理器上運(yùn)行，分為單處理器實(shí)時(shí)調(diào)度和多處理器實(shí)時(shí)調(diào)度，多處理器實(shí)時(shí)調(diào)度又可分為集中式調(diào)度和分布式調(diào)度

3、；根據(jù)調(diào)度算法和可調(diào)度性判定是在任務(wù)運(yùn)行之前還是運(yùn)行期間進(jìn)行的，分為靜態(tài)調(diào)度、動(dòng)態(tài)調(diào)度和混合調(diào)度；根據(jù)被調(diào)度的任務(wù)是否可以互相搶占，分為搶占式調(diào)度和非搶占式調(diào)度；根據(jù)任務(wù)請(qǐng)求到達(dá)的情況不同。分為周期性任務(wù)調(diào)度和非周期性任務(wù)調(diào)度。不同調(diào)度方式具有各自的優(yōu)缺點(diǎn)，適用于不同類型的實(shí)時(shí)系統(tǒng)。3RM與EDF調(diào)度算法簡(jiǎn)介51973年，Liu和Layland提出了一種適用于可搶占的硬實(shí)時(shí)周期性任務(wù)調(diào)度的靜態(tài)優(yōu)先級(jí)調(diào)度算法——速率單調(diào)（RateMonotonic，簡(jiǎn)稱RM）調(diào)度算法，并對(duì)其可調(diào)度性判定問(wèn)題進(jìn)行了研究。RM算法是一種靜態(tài)分配優(yōu)先級(jí)算法，它根據(jù)任務(wù)的周期來(lái)分配

4、優(yōu)先級(jí)，周期越小，任務(wù)的優(yōu)先級(jí)越高。Liu和Layland在文獻(xiàn)[4]中證明了RM算法是最優(yōu)的，即對(duì)于在任何其他靜態(tài)優(yōu)先級(jí)算法下可調(diào)度的任務(wù)集合，在RM算法下也是可調(diào)度的。RM算法基于建立在一系列理想假設(shè)基礎(chǔ)上的理想調(diào)度模型，而在應(yīng)用中，考慮到各種因素的影響，需要對(duì)這些假設(shè)進(jìn)行修正[5]，目前已有大量關(guān)于RM算法及其各種擴(kuò)展情況下的調(diào)度算法以及實(shí)時(shí)任務(wù)在這些下的可調(diào)度性判定研究的文獻(xiàn)。最早截止期優(yōu)先（EarliestDeadlineFirst，簡(jiǎn)稱EDF）調(diào)度算法是一種動(dòng)態(tài)優(yōu)先級(jí)任務(wù)調(diào)度算法，它按照當(dāng)前作業(yè)的絕對(duì)截止期為其分配優(yōu)先級(jí)，作業(yè)的絕對(duì)截止期越短，

5、其優(yōu)先級(jí)別越高，相反，作業(yè)的絕對(duì)截止期越長(zhǎng)，其優(yōu)先級(jí)別越低。在EDF調(diào)度算法中，具有最高優(yōu)先級(jí)別的作業(yè)總是最先得到執(zhí)行。如果當(dāng)前有其他較低優(yōu)先級(jí)作業(yè)正在執(zhí)行，則該較低優(yōu)先級(jí)作業(yè)被搶占，讓位給具有最高優(yōu)先級(jí)的作業(yè)執(zhí)行那個(gè)，直至就緒隊(duì)列中沒(méi)有高于該作業(yè)優(yōu)先級(jí)的作業(yè)時(shí)，該作業(yè)恢復(fù)執(zhí)行。Liu和Layland已經(jīng)證明，EDF調(diào)度算法的可調(diào)度利用率等于1，EDF調(diào)度算法也是一種最優(yōu)的調(diào)度算法。盡管EDF調(diào)度算法在處理器利用率小于等于1的情況下能夠?qū)崿F(xiàn)最優(yōu)調(diào)度，但是，當(dāng)系統(tǒng)超載時(shí)，任務(wù)調(diào)度成功率降低，切換次數(shù)增多，系統(tǒng)的調(diào)度性能下降。4相關(guān)工作首先對(duì)于一些符號(hào)、概念、

6、術(shù)語(yǔ)進(jìn)行如下定義：——第個(gè)實(shí)時(shí)任務(wù)；——任務(wù)集合中任務(wù)的數(shù)量；——任務(wù)的執(zhí)行時(shí)間；——任務(wù)的周期；——系統(tǒng)運(yùn)行的時(shí)間，；5——任務(wù)的釋放時(shí)間；——任務(wù)的相對(duì)時(shí)間限（相對(duì)于釋放時(shí)間）；——任務(wù)的絕對(duì)時(shí)間限。任務(wù)的釋放時(shí)間是指所有用來(lái)開(kāi)始執(zhí)行任務(wù)的資源都可用的時(shí)間，即任務(wù)開(kāi)始執(zhí)行的時(shí)間。任務(wù)的絕對(duì)時(shí)間限是指任務(wù)必須完成的時(shí)間。任務(wù)的相對(duì)時(shí)間限是指絕對(duì)時(shí)間限減去釋放時(shí)間。RM、EDF調(diào)度算法基于如下假設(shè)條件：(1)高優(yōu)先級(jí)的任務(wù)可以搶占低優(yōu)先級(jí)的任務(wù)；(2)沒(méi)有任務(wù)有非搶先的部分，并且搶先的成本可以忽略；(3)只有處理器資源是競(jìng)爭(zhēng)的，內(nèi)存、I/O和其他資源是足夠

7、的，即無(wú)需競(jìng)爭(zhēng)；(4)所有任務(wù)都是無(wú)關(guān)的，不存在先后次序的約束；(5)任務(wù)集合中的所有任務(wù)都是周期性的；(6)任務(wù)的相對(duì)時(shí)間限等于它的周期。這些假設(shè)是RM和EDF算法的基礎(chǔ)，是對(duì)理想情況的研究，在實(shí)際實(shí)時(shí)系統(tǒng)項(xiàng)目中會(huì)考慮各種因素的影響。本文提到的混合算法也是基于以上假設(shè)。5RM、EDF及混合調(diào)度算法分析在RM調(diào)度算法中，任務(wù)的優(yōu)先級(jí)與它的周期反向相關(guān)，如果任務(wù)比的周期小，則比的優(yōu)先級(jí)高。處理器總是優(yōu)先執(zhí)行當(dāng)前處于就緒狀態(tài)的優(yōu)先級(jí)最大的任務(wù)，并且任務(wù)的優(yōu)先級(jí)固定。RM調(diào)度算法對(duì)于給定周期性任務(wù)集可調(diào)度性的充分條件是：(1)在EDF調(diào)度算法中，任務(wù)的優(yōu)先級(jí)與它

8、的絕對(duì)時(shí)間限相關(guān)，處理器總是優(yōu)先執(zhí)行當(dāng)前處于就緒狀態(tài)的絕對(duì)時(shí)間限最