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

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

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

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

    觀察上面每一個任務的第一次迭代。啟動任務T1，這是最高優(yōu)先級的任務，它不會被系統(tǒng)中的其他任務耽擱。當T1被釋放時，處理器會中斷正在運行的工作，而去執(zhí)行T1。因此，為保證T1能夠被可行地調(diào)度而滿足的唯一條件為e1≤p1，這顯然是一個必要條件，也是一個充分條件。
    現(xiàn)在考察T2。如果它的第一次迭代能在[0，p2]上找到足夠的時間，它就可以成功運行。假設T2在t時刻結(jié)束，在[0，t]上釋放的任務T1的總迭代次數(shù)是[t/p1]，為了使T2在t時刻結(jié)束，在[0，t]釋放的任務T1的每一次迭代都必須被完成，此外還必須有可用的時間e2去執(zhí)行T2，即必須滿足條件：
  
其中Wi(t)是被T1，T2，…，Ti所執(zhí)行的工作總量。因此可調(diào)度性的充分必要條件為：給定一個由n個周期性任務構(gòu)成的集合，任務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)度算法性能的一個重要指標。所謂的截止期錯失率就是指系統(tǒng)中未被調(diào)度成功的任務的個數(shù)與參與調(diào)度的任務個數(shù)之比。它與調(diào)度成功率成反比，截止期錯失率越高，則調(diào)度成功率越低。在實驗中，比較了RM、EDF和混合調(diào)度算法在不同工作負載情況下的截止期錯失率。
    實驗的硬件平臺是一個基于32位ARM微控制器的嵌入式系統(tǒng)。實時任務集由5個周期性任務組成，這個任務集的屬性描述如表1所示。

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

    從圖3可以看出，在一定的負載范圍內(nèi)，RM算法和EDF算法都能夠保證任務的截止期成功率，可以很好地用來調(diào)度實時任務。隨著負載的增加，RM算法的截止期錯失率開始增加，性能開始下降，而EDF仍然具有很好的性能，即EDF算法比RM算法可以承受更多的負載。但是當系統(tǒng)過載時，EDF算法截止期錯失率急劇上升，性能下降很快，而RM算法則相對穩(wěn)定，到一定程度時EDF算法性能低于RM算法性能。混合調(diào)度算法性能曲線介于RM算法與EDF算法之間，在一定的負載范圍內(nèi)，同樣能夠?qū)崟r調(diào)度任務，而且可以承受的負載范圍比RM范圍大；當負載增加時，這種算法性能比EDF算法性能下降慢，表現(xiàn)出很好的穩(wěn)定性。
    本文基于RM與EDF調(diào)度算法，提出了一種基于閾值δ的混合調(diào)度算法。這種算法可以根據(jù)需要調(diào)節(jié)閾值δ，制定符合需要的算法性能。當δ取較小值時，混合調(diào)度算法側(cè)重于RM算法性能；當δ取較大值時，混合調(diào)度算法側(cè)重于EDF算法性能。實驗表明，在實際應用中，使用混合調(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)度算法及應用[J]. 計算機應用，2005，25(4).
[5] 王輝.改進了的RM與EDF以及兩者的混合調(diào)度算法[D].吉林：吉林大學，2004.