實(shí)時(shí)系統(tǒng)是指能夠在確定時(shí)間內(nèi)執(zhí)行計(jì)算或者處理事務(wù)并且對(duì)外部的異步事件做出及時(shí)響應(yīng)的計(jì)算機(jī)系統(tǒng)[1]。實(shí)時(shí)系統(tǒng)最大的特點(diǎn)是時(shí)間的確定性，即實(shí)時(shí)性。由于實(shí)時(shí)調(diào)度算法是實(shí)時(shí)系統(tǒng)的核心算法，是影響實(shí)時(shí)系統(tǒng)實(shí)時(shí)性的最大因素，因此，對(duì)實(shí)時(shí)調(diào)度算法的研究具有重要的意義。
    RM速率單調(diào)（Rate Monotonic）算法是一種靜態(tài)分配優(yōu)先級(jí)的算法，它根據(jù)任務(wù)的周期來(lái)分配優(yōu)先級(jí)，周期越小，任務(wù)的優(yōu)先級(jí)越高[5]。而最早截止期限優(yōu)先EDF(Earliest Deadline First)算法是一種動(dòng)態(tài)分配優(yōu)先級(jí)的算法，它根據(jù)任務(wù)的緊迫程度來(lái)分配優(yōu)先級(jí)[4]。在現(xiàn)有實(shí)時(shí)系統(tǒng)中，RM算法和EDF算法是使用最多的兩種實(shí)時(shí)調(diào)度算法。但是，這兩種算法都是在系統(tǒng)中單獨(dú)使用，適用面較窄，穩(wěn)定性差。如果將兩者結(jié)合將是一條有效的解決途徑。本文在這方面進(jìn)行了探索，提出了一種嶄新的混合調(diào)度算法，并驗(yàn)證了算法的有效性。
1 相關(guān)工作
    對(duì)一些符號(hào)、概念、術(shù)語(yǔ)進(jìn)行如下定義：
  
    任務(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è)條件[3]：
    (1)高優(yōu)先級(jí)的任務(wù)可以搶先低優(yōu)先級(jí)的任務(wù)。
    (2)沒(méi)有任務(wù)有非搶先的部分，并且搶先的成本可以忽略。
    (3)只有處理器資源是競(jìng)爭(zhēng)的，內(nèi)存、I/O和其他資源是足夠的，即無(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í)際因素的影響。文中提出的混合調(diào)度算法也是基于以上假設(shè)。
2 RM與EDF調(diào)度算法介紹及分析
    在RM調(diào)度算法中，任務(wù)的優(yōu)先級(jí)與它的周期反向相關(guān)，如果任務(wù)Ti比任務(wù)Tj的周期小，則Ti比Tj的優(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)度性的充分條件是[2]：
  
    另外，RM屬于靜態(tài)調(diào)度算法，適合于問(wèn)題要求比較明確的系統(tǒng)，額外開(kāi)銷小，可預(yù)測(cè)性好。但是，由于靜態(tài)調(diào)度算法一旦做出調(diào)度決定后，在整個(gè)運(yùn)行期間就無(wú)法再進(jìn)行更改，因此，它的靈活性不如動(dòng)態(tài)調(diào)度算法，不適合于不可預(yù)測(cè)環(huán)境下的調(diào)度。EDF是一種動(dòng)態(tài)調(diào)度算法，需要在變化的環(huán)境中做出反應(yīng)，這類算法應(yīng)用比較靈活，適合于任務(wù)不斷生成的動(dòng)態(tài)實(shí)時(shí)系統(tǒng)中。但是，動(dòng)態(tài)調(diào)度算法的可預(yù)測(cè)性差并且運(yùn)行開(kāi)銷較大。
3 混合調(diào)度算法
    關(guān)于混合調(diào)度算法的研究，參考文獻(xiàn)[5]中提出了一種方案。對(duì)于一個(gè)任務(wù)集而言,其中任務(wù)1，2，…，k，這k個(gè)任務(wù)是具有最短周期的任務(wù),采用固定分配優(yōu)先級(jí)的RMS調(diào)度算法調(diào)度執(zhí)行,而余下的任務(wù)k+1，…，m采用EDF調(diào)度算法調(diào)度執(zhí)行[5]。這種調(diào)度算法只是簡(jiǎn)單地將任務(wù)分為兩組，每組分別采用不同的調(diào)度算法，并沒(méi)有很好地將RM與EDF調(diào)度算法結(jié)合。因此，本文提出了一種嶄新的混合調(diào)度算法。

3.1 算法描述
    周期性任務(wù)集符合RM、EDF算法假設(shè)條件(1)～(5)，Ti、Tj為任務(wù)集中處于就緒態(tài)任務(wù)的絕對(duì)時(shí)間限最小的兩個(gè)任務(wù)，絕對(duì)時(shí)間限分別為Di、Dj，且Di≥Dj。調(diào)度方法分兩種情況：
 (1)當(dāng)Di＞Dj時(shí)，若Di－Dj＜δ，則說(shuō)明任務(wù)間的緊迫性高，采用EDF調(diào)度方法；若Di－Dj≥δ，則說(shuō)明任務(wù)間的緊迫性低，采用RM調(diào)度方法。
 (2)當(dāng)Di＝Dj時(shí)，采用RM調(diào)度方法。

 算法主要流程如圖1所示。

    圖1中δ為閾值，其意義代表任務(wù)間的緊迫性，要根據(jù)具體實(shí)時(shí)系統(tǒng)進(jìn)行確定。當(dāng)δ足夠小，如 δ=0時(shí)，混合調(diào)度算法就退化為RM調(diào)度算法；當(dāng)δ足夠大時(shí)，混合調(diào)度算法就退化為EDF調(diào)度算法。由此可見(jiàn)，混合調(diào)度算法是RM與EDF的一個(gè)很好的折中。
3.2 算法的可調(diào)度性分析
    調(diào)度算法調(diào)度任務(wù)集，調(diào)度算法的核心任務(wù)[4]是使各個(gè)任務(wù)滿足各自的時(shí)間限，因此，研究調(diào)度算法的可調(diào)度性與任務(wù)的周期、執(zhí)行時(shí)間等屬性之間的關(guān)系、給出調(diào)度算法可調(diào)度性的判斷依據(jù)是必須完成的工作。
    下面研究混合調(diào)度算法可調(diào)度性的充分必要條件。先給出一個(gè)示例，從這個(gè)特殊的示例中，可以得到一般性的結(jié)論。
    有三個(gè)周期任務(wù)，周期為p1=2，p2=5，p3=10；執(zhí)行時(shí)間是e1=0.5，e2=3.5，e3=0.5；閾值選取為δ=1.5。由于是周期任務(wù)，所以任務(wù)的絕對(duì)時(shí)間限D(zhuǎn)i即為任務(wù)各個(gè)周期的結(jié)束時(shí)刻，任務(wù)的釋放時(shí)刻ri為任務(wù)各個(gè)周期的開(kāi)始時(shí)刻，則任務(wù)在混合調(diào)度算法下的執(zhí)行流程如圖2所示。

    觀察上面每一個(gè)任務(wù)的第一次迭代。啟動(dòng)任務(wù)T1，這是最高優(yōu)先級(jí)的任務(wù)，它不會(huì)被系統(tǒng)中的其他任務(wù)耽擱。當(dāng)T1被釋放時(shí)，處理器會(huì)中斷正在運(yùn)行的工作，而去執(zhí)行T1。因此，為保證T1能夠被可行地調(diào)度而滿足的唯一條件為e1≤p1，這顯然是一個(gè)必要條件，也是一個(gè)充分條件。
    現(xiàn)在考察T2。如果它的第一次迭代能在[0，p2]上找到足夠的時(shí)間，它就可以成功運(yùn)行。假設(shè)T2在t時(shí)刻結(jié)束，在[0，t]上釋放的任務(wù)T1的總迭代次數(shù)是[t/p1]，為了使T2在t時(shí)刻結(jié)束，在[0，t]釋放的任務(wù)T1的每一次迭代都必須被完成，此外還必須有可用的時(shí)間e2去執(zhí)行T2，即必須滿足條件：
  
其中Wi(t)是被T1，T2，…，Ti所執(zhí)行的工作總量。因此可調(diào)度性的充分必要條件為：給定一個(gè)由n個(gè)周期性任務(wù)構(gòu)成的集合，任務(wù)Ti能夠使用混合調(diào)度算法切實(shí)可行地調(diào)度的充分必要條件是存在某個(gè)t∈[0，pi],且t為p1，p2，…，或pi的倍數(shù)，使得Li(t)≤1。

4 實(shí)驗(yàn)結(jié)果及分析
    對(duì)于實(shí)時(shí)系統(tǒng)調(diào)度算法來(lái)說(shuō)，截止期錯(cuò)失率DMR(Deadlines Missed Rate)是衡量調(diào)度算法性能的一個(gè)重要指標(biāo)。所謂的截止期錯(cuò)失率就是指系統(tǒng)中未被調(diào)度成功的任務(wù)的個(gè)數(shù)與參與調(diào)度的任務(wù)個(gè)數(shù)之比。它與調(diào)度成功率成反比，截止期錯(cuò)失率越高，則調(diào)度成功率越低。在實(shí)驗(yàn)中，比較了RM、EDF和混合調(diào)度算法在不同工作負(fù)載情況下的截止期錯(cuò)失率。
    實(shí)驗(yàn)的硬件平臺(tái)是一個(gè)基于32位ARM微控制器的嵌入式系統(tǒng)。實(shí)時(shí)任務(wù)集由5個(gè)周期性任務(wù)組成，這個(gè)任務(wù)集的屬性描述如表1所示。

    為了對(duì)實(shí)時(shí)任務(wù)進(jìn)行定期的統(tǒng)計(jì)，系統(tǒng)在實(shí)時(shí)任務(wù)建立之前，首先產(chǎn)生內(nèi)核任務(wù)和空閑任務(wù)。內(nèi)核任務(wù)具有最高優(yōu)先級(jí)，每隔一段時(shí)間，對(duì)各個(gè)任務(wù)的截止期錯(cuò)失率進(jìn)行一次統(tǒng)計(jì)；空閑任務(wù)具有最低優(yōu)先級(jí)，當(dāng)所有任務(wù)均處于不可調(diào)度狀態(tài)時(shí)，可以運(yùn)行空閑任務(wù)。統(tǒng)計(jì)結(jié)果如圖3所示。

    從圖3可以看出，在一定的負(fù)載范圍內(nèi)，RM算法和EDF算法都能夠保證任務(wù)的截止期成功率，可以很好地用來(lái)調(diào)度實(shí)時(shí)任務(wù)。隨著負(fù)載的增加，RM算法的截止期錯(cuò)失率開(kāi)始增加，性能開(kāi)始下降，而EDF仍然具有很好的性能，即EDF算法比RM算法可以承受更多的負(fù)載。但是當(dāng)系統(tǒng)過(guò)載時(shí)，EDF算法截止期錯(cuò)失率急劇上升，性能下降很快，而RM算法則相對(duì)穩(wěn)定，到一定程度時(shí)EDF算法性能低于RM算法性能。混合調(diào)度算法性能曲線介于RM算法與EDF算法之間，在一定的負(fù)載范圍內(nèi)，同樣能夠?qū)崟r(shí)調(diào)度任務(wù)，而且可以承受的負(fù)載范圍比RM范圍大；當(dāng)負(fù)載增加時(shí)，這種算法性能比EDF算法性能下降慢，表現(xiàn)出很好的穩(wěn)定性。
    本文基于RM與EDF調(diào)度算法，提出了一種基于閾值δ的混合調(diào)度算法。這種算法可以根據(jù)需要調(diào)節(jié)閾值δ，制定符合需要的算法性能。當(dāng)δ取較小值時(shí)，混合調(diào)度算法側(cè)重于RM算法性能；當(dāng)δ取較大值時(shí)，混合調(diào)度算法側(cè)重于EDF算法性能。實(shí)驗(yàn)表明，在實(shí)際應(yīng)用中，使用混合調(diào)度算法比單獨(dú)使用RM或EDF調(diào)度算法具有更好的靈活性，能夠根據(jù)需要產(chǎn)生理想的調(diào)度性能。

參考文獻(xiàn)
[1] KRISHNA C M，SHIN G K.Real-time systems[M].Columbus，OH：McGraw-Hill Company，Ine.1997.
[2] LIU C L，LAYLAND J W.Scheduling algorithms for multiprogramming in a hard real time environment[J].Journal of  the ACM，1973，20(1).
[3] BUTTAZZO G.Rate monotonic vs.EDF：judgment day[J].  Real-Time Systems，2005，29(3)：5-26.
[4] 葉明，羅克露，陳慧.單調(diào)比率(RM)調(diào)度算法及應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用，2005，25(4).
[5] 王輝.改進(jìn)了的RM與EDF以及兩者的混合調(diào)度算法[D].吉林：吉林大學(xué)，2004.