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

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

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

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

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

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

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

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

參考文獻
[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]. 計算機應(yīng)用，2005，25(4).
[5] 王輝.改進了的RM與EDF以及兩者的混合調(diào)度算法[D].吉林：吉林大學(xué)，2004.