徐德

嵌入式操作系統(tǒng)實時調(diào)度算法研究

徐 德

（中國人民銀行烏魯木齊中心支行，新疆 烏魯木齊 834002）

摘要： 在嵌入式操作系統(tǒng)中，實時調(diào)度算法性能的好壞直接對系統(tǒng)的實時性起著決定性的作用。因此，該文介紹實時調(diào)度和實時調(diào)度算法的概念，分析了目前常見的靜態(tài)優(yōu)先級調(diào)度算法和動態(tài)優(yōu)先級調(diào)度算法的不同。

關(guān)鍵詞： 嵌入式操作系統(tǒng)；實時性；調(diào)度算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）13-3177-02

1 實時調(diào)度與實時調(diào)度算法

多任務的系統(tǒng)必須擔負起調(diào)度任務的責任，不斷地進行切換進程，以使CPU獲得最大的利用率。當有多個任務就緒時，操作系統(tǒng)必須決定先運行那一個，對CPU訪問權(quán)限裁決的過程被稱為調(diào)度（Scheduling）。本質(zhì)上調(diào)度其實就是系統(tǒng)根據(jù)調(diào)度算法策略與資源控制協(xié)議的規(guī)則，為一組處于就緒狀態(tài)的任務分配資源并選擇符合系統(tǒng)要求的任務組成一個隊列到處理機上去依次執(zhí)行，并而在這一過程中要保證所有任務對時限的要求。假如實時系統(tǒng)若有m個周期性任務，任務i的周期為Pi，其中每個事件任務需要Ci秒的CPU時間來處理，則只有滿足以下條件：

[i=1mcipi1]

才可能處理所有負載。滿足該條件的系統(tǒng)任務集認為是可調(diào)度的（Schedulable）。實時調(diào)度強調(diào)的是任務的時間約束，尤其是在硬實時系統(tǒng)的設計中，評價調(diào)度程序好壞與否不在于調(diào)度的公平性和最小響應時間，而是所有硬實時任務能否在最后截止期限內(nèi)完成。在實時調(diào)度過程中使用的調(diào)度策略方法或資源控制協(xié)議，通常我們稱為實時調(diào)度算法。

2 嵌入式操作系統(tǒng)常見的實時調(diào)度算法

嵌入式操作系統(tǒng)必須保證在確定的時間內(nèi)對事件進行處理，因此必須要有一個良好的任務調(diào)度算法，它具有如下特點：

①公平，保證每個任務都能得到合理的CPU時間；

②高效，使CPU沒有空閑，總是有任務在CPU上處于運行狀態(tài)；

③響應及時，使交互用戶的響應時間盡可能的短；

④利用率高，使單位時間內(nèi)為盡可能多的任務服務。

很明顯，在任何一個操作系統(tǒng)中同時滿足這幾個目標是不太現(xiàn)實的，必須在這幾個方面進行相應的取舍與折中考慮，從而確定自己的調(diào)度算法。目前在嵌入式系統(tǒng)中常見的實時調(diào)度算法有單調(diào)速率調(diào)度算法（RMS），最早截止時間優(yōu)先調(diào)度算法（EDF）等。還有一些在此基礎上進行優(yōu)化或者改進而成的算法，如截止期限單調(diào)調(diào)度算法（Deadline Monotonic Scheduling，DMS）、最小空閑時間優(yōu)先調(diào)度算法（Least Laxity First，LLF）等。

1）速率單調(diào)調(diào)度算法

單調(diào)速率調(diào)度（RMS）算法是C.L.Liu和J.W.Layland在1973年引入提出的一種基于周期和多任務的靜態(tài)優(yōu)先級可搶占調(diào)度算法。RMS是針對周期任務的優(yōu)先級調(diào)度算法，當任務的截止時間等于其周期時，RMS算法已被證明是靜態(tài)最優(yōu)的調(diào)度算法。C.L.Liu和J.W.Layland給出了RMS算法可調(diào)度的充分非必要條件，其中C為任務，T為周期，n為任務個數(shù)。

[C0T0+C1T1+……+CnTnn（21n-1）]

這種算法執(zhí)行起來開銷很小，可調(diào)度性測試簡單，但最大的局限性就在于該算法不可能總使CPU被完全利用。在最差情況下可調(diào)度的范圍為：

[Wn=n（21n-1]

從公式中不難看出：

①當系統(tǒng)中只有一個任務運行時，最差的可調(diào)度范圍為100%；

②當系統(tǒng)中有多個任務運行時，可調(diào)度范圍逐漸降低，達到極限值69.3%左右。

所以，當系統(tǒng)中的任務總量不超過n（21/n-1）時，RMS算法可以調(diào)度執(zhí)行系統(tǒng)所有的任務并滿足它們的時限要求。當系統(tǒng)超過此負載限制時，系統(tǒng)調(diào)度就有可能出現(xiàn)不能滿足任務執(zhí)行時限的現(xiàn)象。

2） 最早截止期限優(yōu)先調(diào)度

最早截止期限優(yōu)先調(diào)度算法（EDF）是一種基于優(yōu)先級的搶占式動態(tài)最優(yōu)調(diào)度算法，也稱為死限驅(qū)動調(diào)度算法（Deadline Driver Scheduling，DDS）。該算法的任務優(yōu)先級初始之時并不固定，而是隨著啟動時間的變化而動態(tài)地改變，以距離最后截止期限時間的長短來分配優(yōu)先級，具體地說就是距離最后截止期限時間越短的任務越緊急，相應的任務優(yōu)先級也就越高；距離最后截止期限時間越長的任務對完成截止時間要求越松弛，該任務的優(yōu)先級也就越低。系統(tǒng)每時每刻總是在就緒隊列中挑選最早到達絕對最后截止期限的任務在處理機上執(zhí)行。事實上，EDF算法是一種最優(yōu)的單處理器調(diào)度算法，對于相對期限等于周期且總資源利用率不大于n（21/n-1）的周期任務集，可由該算法進行調(diào)度。實踐表明，EDF算法的優(yōu)點在于系統(tǒng)負載較低時，效率較高，相對容易實現(xiàn)。缺點在于該算法理論上能對系統(tǒng)可調(diào)度負載進行優(yōu)化，但不能解決系統(tǒng)負載較重時，系統(tǒng)性能急劇下降的問題。C.L.Liu和J.W.Layland給出了采用EDF算法可調(diào)度的充分必要條件，其中C為任務，T為周期，n為任務個數(shù)。

[C0T0+C1T1+……+CnTn1]

由于EDF算法在運行時系統(tǒng)開銷較大，特別是在過載情況下，由于大量任務錯過最后截止期限引發(fā)CPU頻繁的任務調(diào)度，消耗了大量的CPU時間，這時候系統(tǒng)的性能可能還不如先來先服務FIFO（First In First out）調(diào)度算法穩(wěn)定。另外EDF算法在實際應用中可能會出現(xiàn)優(yōu)先級倒置的現(xiàn)象，所以EDF算法在實際應用中還存在一些問題。

3）最短空閑時間優(yōu)先調(diào)度

最短空閑時間優(yōu)先調(diào)度算法（LLF）也叫最小松弛時間優(yōu)先調(diào)度算法，是在EDF算法的基礎之上發(fā)展起來的一種動態(tài)調(diào)度算法。該算法首先根據(jù)任務完成的截止時間和剩余的執(zhí)行時間來計算任務的空閑時間，即空閑時間=截止時間-剩余執(zhí)行時間；然后再根據(jù)任務的空閑時間來動態(tài)分配優(yōu)先級，空閑時間越短，優(yōu)先級越高，空閑時間越長，優(yōu)先級越低。在執(zhí)行的過程中，隨著時間的向前推進，等待任務的空閑時間越來越短，相應的任務等待執(zhí)行的緊急程度也就越來越緊迫，因此，等待任務隨時可能會搶占當前執(zhí)行的任務，從而造成了任務之間的相互競爭，導致了任務之間的頻繁切換現(xiàn)象較為嚴重，大大增加了系統(tǒng)時間開銷，其實際應用受到了一定的限制。endprint

3 嵌入式操作系統(tǒng)實時調(diào)度算法分析比較

1）固定優(yōu)先級調(diào)度算法

在實時調(diào)度算法中，固定優(yōu)先級調(diào)度算法事先根據(jù)任務的屬性，如任務的周期、截止期限等為系統(tǒng)中的所有任務靜態(tài)分配一個優(yōu)先級。當任務的截止期限等于周期時，提出了RMS調(diào)度算法，它根據(jù)任務的執(zhí)行周期長短的不同來決定優(yōu)先級，即任務的周期越小優(yōu)先級越高，任務的周期越大優(yōu)先級越低。以RMS為代表的固定優(yōu)先級調(diào)度算法，一方面不僅具有運行時間開銷小和易于實現(xiàn)的優(yōu)點，而且在系統(tǒng)超載情況下，仍然可以保證高優(yōu)先級的任務得到執(zhí)行；但另一方面卻是不能充分地利用系統(tǒng)資源。

2）動態(tài)優(yōu)先級調(diào)度算法

在實時調(diào)度算法中，動態(tài)優(yōu)先級調(diào)度算法根據(jù)任務資源需求的變化以及任務的屬性，如任務周期、截止期限等動態(tài)地決定任務的優(yōu)先級。當任務的截止期限等于周期時，提出了EDF調(diào)度算法，該算法根據(jù)就緒隊列中任務的截止期限分配優(yōu)先級，距離絕對截止期限的最近的任務具有最高的優(yōu)先級，即任務的絕對截止期限越小優(yōu)先級越高，任務的絕對截止期限越大優(yōu)先級越低。以EDF為代表的動態(tài)優(yōu)先級調(diào)度算法，一方面可以充分地利用系統(tǒng)的資源；但是另一方面在系統(tǒng)負荷嚴重超載時，系統(tǒng)性能很不穩(wěn)定，導致大多數(shù)任務在截止期限到來之時仍無法滿足。

3）靜態(tài)優(yōu)先調(diào)度算法與動態(tài)優(yōu)先調(diào)度算法的比較

靜態(tài)調(diào)度是指系統(tǒng)脫機地進行調(diào)度可行性分析后生成一個可調(diào)度表，在運行的過程中，調(diào)度表中的信息不再發(fā)生任何變化。該類調(diào)度算法假定系統(tǒng)實時任務的屬性是提前已知的并且在執(zhí)行過程中很少發(fā)生變化，特別適合于對那種確定問題的求解，具有較好的可預測性。

動態(tài)調(diào)度與靜態(tài)調(diào)度剛好相反，是根據(jù)任務在執(zhí)行過程中的動態(tài)屬性來選擇某個就緒任務到處理機上去執(zhí)行。此類調(diào)度算法它僅僅只根據(jù)目前就緒任務的相關(guān)屬性來決定調(diào)度序列，而對以后將要到達的任務的特性完全不知，也不進行任何評估。這類算法的優(yōu)點是它能夠?qū)\行環(huán)境的變化做出反應，具有較高的靈活性，特別適用于那些在運行過程中不斷添加新任務且特性又不明確的動態(tài)實時系統(tǒng)。但是該類算法的運行時間開銷一般比靜態(tài)調(diào)度算法大。

參考文獻：

[1] 趙慧斌，李小群.改善Linux核心可搶占性方法研究與實現(xiàn)[J].計算機學報，2004.27：240-250.

[2] 蘇曙光，劉云生.基于RTHAL的Linux研究與實現(xiàn)[J].計算機科學，2009，7：143-148.

[3] 顧勝元，楊丹.嵌入式實時動態(tài)內(nèi)存管理機制[J].計算機工程， 2009，20：250-257.

[4] 文星，張輝宜.嵌入式Linux的實時性改進技術(shù)[J].計算機技術(shù)與發(fā)展，2006，16（10）.

[5] 左天軍，左園園.Linux操作系統(tǒng)的實時化分析[J].計算機科學，2004，31（5）：110-112.

[6] 趙明富.Linux嵌入式系統(tǒng)實時性分析與實時化改進[J].計算機應用研究，2004（4）.

[7] 趙明富.嵌入式Linux操作系統(tǒng)的實時化研究[J].西南師大學報，2003，28（3）.endprint