徐德

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

徐 德

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

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）13-3177-02

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

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

[i=1mcipi1]

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

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

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

①公平，保證每個(gè)任務(wù)都能得到合理的CPU時(shí)間；

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

③響應(yīng)及時(shí)，使交互用戶的響應(yīng)時(shí)間盡可能的短；

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

很明顯，在任何一個(gè)操作系統(tǒng)中同時(shí)滿足這幾個(gè)目標(biāo)是不太現(xiàn)實(shí)的，必須在這幾個(gè)方面進(jìn)行相應(yīng)的取舍與折中考慮，從而確定自己的調(diào)度算法。目前在嵌入式系統(tǒng)中常見(jiàn)的實(shí)時(shí)調(diào)度算法有單調(diào)速率調(diào)度算法（RMS），最早截止時(shí)間優(yōu)先調(diào)度算法（EDF）等。還有一些在此基礎(chǔ)上進(jìn)行優(yōu)化或者改進(jìn)而成的算法，如截止期限單調(diào)調(diào)度算法（Deadline Monotonic Scheduling，DMS）、最小空閑時(shí)間優(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年引入提出的一種基于周期和多任務(wù)的靜態(tài)優(yōu)先級(jí)可搶占調(diào)度算法。RMS是針對(duì)周期任務(wù)的優(yōu)先級(jí)調(diào)度算法，當(dāng)任務(wù)的截止時(shí)間等于其周期時(shí)，RMS算法已被證明是靜態(tài)最優(yōu)的調(diào)度算法。C.L.Liu和J.W.Layland給出了RMS算法可調(diào)度的充分非必要條件，其中C為任務(wù)，T為周期，n為任務(wù)個(gè)數(shù)。

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

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

[Wn=n（21n-1]

從公式中不難看出：

①當(dāng)系統(tǒng)中只有一個(gè)任務(wù)運(yùn)行時(shí)，最差的可調(diào)度范圍為100%；

②當(dāng)系統(tǒng)中有多個(gè)任務(wù)運(yùn)行時(shí)，可調(diào)度范圍逐漸降低，達(dá)到極限值69.3%左右。

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

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

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

[C0T0+C1T1+……+CnTn1]

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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