調(diào)度程序的功能是調(diào)度任務(wù)的執(zhí)行順序，非調(diào)度實(shí)體的存在卻會(huì)導(dǎo)致調(diào)度程序的效率下降，為時(shí)限調(diào)度程序而設(shè)計(jì)的系統(tǒng)總是盡可能地減少非調(diào)度實(shí)體的數(shù)量以及這些實(shí)體所占用的CPU時(shí)間，本文介紹嵌入式系統(tǒng)設(shè)計(jì)過程中任務(wù)優(yōu)先級(jí)調(diào)度的策略。

    在過去的幾年里，固定優(yōu)先級(jí)調(diào)度技術(shù)的發(fā)展迅速。分時(shí)系統(tǒng)和一些實(shí)時(shí)系統(tǒng)，要求所有的任務(wù)要同時(shí)運(yùn)行。它賦予每個(gè)任務(wù)一個(gè)有效的優(yōu)先級(jí)，并且該優(yōu)先級(jí)在任務(wù)等候執(zhí)行的過程中逐步遞增。每一個(gè)任務(wù)都將獲得一個(gè)有效的優(yōu)先級(jí)，該優(yōu)先級(jí)將確保該任務(wù)至少會(huì)獲得一個(gè)短暫的CPU執(zhí)行時(shí)間。

    一個(gè)高優(yōu)先級(jí)的任務(wù)可能會(huì)發(fā)現(xiàn)自己正在等待一個(gè)低優(yōu)先級(jí)的任務(wù)釋放資源。這樣將高優(yōu)先級(jí)任務(wù)的有效優(yōu)先級(jí)下降到了低優(yōu)先級(jí)任務(wù)的有效優(yōu)先級(jí)以下。這種技術(shù)可以實(shí)現(xiàn)，但是對(duì)于調(diào)試卻是有害的。優(yōu)先級(jí)繼承以及優(yōu)先級(jí)限制協(xié)議就是專為解決這樣的問題而發(fā)明的。該技術(shù)推進(jìn)了低優(yōu)先級(jí)任務(wù)的優(yōu)先級(jí)，與此同時(shí)保留了一定的資源確保高優(yōu)先級(jí)的任務(wù)在需要時(shí)可以使用。

    實(shí)際上，絕大多數(shù)的實(shí)時(shí)操作系統(tǒng)都采用靜態(tài)優(yōu)先級(jí)調(diào)度方式，本文介紹如何通過時(shí)限調(diào)度(deadline scheduling)來保證系統(tǒng)的實(shí)時(shí)性。

    速率單調(diào)分析

    速率單調(diào)性分析(rate monotonic analysis)證明，如果一個(gè)固定優(yōu)先級(jí)搶占系統(tǒng)在執(zhí)行的一系列彼此獨(dú)立的周期性任務(wù)，那么不存在為周期性任務(wù)靜態(tài)分配優(yōu)先級(jí)的算法，而為這樣的任務(wù)分配較短的時(shí)間來獲得較高的優(yōu)先級(jí)卻更容易找到辦法。

    為此，人們研發(fā)了RMA調(diào)度，RMA的一個(gè)重要特征是可以分析系統(tǒng)的可實(shí)現(xiàn)性(feasibility)。采用RMA，結(jié)構(gòu)設(shè)計(jì)人員可以收集系統(tǒng)的情況，然后分析系統(tǒng)的可實(shí)現(xiàn)性，從而獲得“調(diào)度程序正是如此工作”或者是“固定優(yōu)先級(jí)調(diào)度程序不能進(jìn)行這樣的調(diào)度”等分析結(jié)果。

    簡(jiǎn)單、通用版本的RMA使用超出69%的CPU時(shí)間，這將構(gòu)成實(shí)際系統(tǒng)的可實(shí)現(xiàn)性方面的問題。如果結(jié)構(gòu)設(shè)計(jì)工程師退回到老式的時(shí)間線分析，RMA甚至要占用的CPU時(shí)間，問題是我們采用的是單調(diào)乏味的手工仿真，而不是高等的代數(shù)運(yùn)算。

    在某些系統(tǒng)中，幾乎所有的事件都是周期性的，但是大多數(shù)的系統(tǒng)中都存在大量的非周期性事件，現(xiàn)實(shí)就是如此。可以在一個(gè)周期嚴(yán)格的系統(tǒng)中處理非周期性事件，通常是將它們分配到一個(gè)周期性調(diào)度的時(shí)隙中，由于需要實(shí)現(xiàn)這種時(shí)隙的輪詢，所以會(huì)極大地降低系統(tǒng)的性能。系統(tǒng)設(shè)計(jì)工程師也必須決定輪詢這些非周期性事件的頻度，以及處理這些事件允許的時(shí)間長(zhǎng)度。

    然后，要考慮軟實(shí)時(shí)方面的問題。通過彈出一個(gè)任務(wù)的優(yōu)先級(jí)使之高于該時(shí)段指示的優(yōu)先級(jí)水平，從而在RMA中可以對(duì)重要性進(jìn)行度量。這樣就會(huì)造成那些沒有施加優(yōu)先級(jí)彈出的任務(wù)出現(xiàn)問題，這種情況正好與RMA的整體設(shè)想相反。程序?qū)⒎治隹蓪?shí)現(xiàn)性，然后確保系統(tǒng)的成功。RMA不是為不可實(shí)現(xiàn)的系統(tǒng)而設(shè)計(jì)的。

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

    固定優(yōu)先級(jí)調(diào)度的問題是對(duì)時(shí)限的要求具有易忘性，也就是說這種優(yōu)先級(jí)調(diào)度對(duì)硬實(shí)時(shí)不敏感。這就像是一個(gè)基于定時(shí)器的交通燈，沒有任何的交通流量傳感器。如圖1所示。上面的時(shí)間線(H)表示一個(gè)高優(yōu)先級(jí)的任務(wù)，下面的時(shí)間線(L)表示一個(gè)低優(yōu)先級(jí)的任務(wù)。調(diào)度程序會(huì)首先執(zhí)行高優(yōu)先級(jí)的任務(wù)，這樣就容易在該任務(wù)的時(shí)限內(nèi)完成該任務(wù)。任務(wù)H完成后，調(diào)度程序就切換到任務(wù)L，然而在任務(wù)L的時(shí)限內(nèi)可能沒有足夠的時(shí)間來完成任務(wù)L。如果調(diào)度程序?qū)@些時(shí)限的情況很了解，那么調(diào)度程序就有可能在任務(wù)H之前先運(yùn)行任務(wù)L，這樣可能能夠滿足兩個(gè)任務(wù)所有的時(shí)限要求。

    一個(gè)有經(jīng)驗(yàn)的實(shí)時(shí)程序設(shè)計(jì)師可能用一些設(shè)計(jì)技巧來處理這樣的問題，如在系統(tǒng)運(yùn)行時(shí)巧妙地處理優(yōu)先級(jí)，或者是用加鎖的方法來實(shí)現(xiàn)，然而在此工程師面臨的是如何處理調(diào)度程序而不是如何使用調(diào)度程序的問題。

    固定優(yōu)先級(jí)調(diào)度的優(yōu)勢(shì)在于：1. 每一個(gè)主流的操作系統(tǒng)或者任務(wù)切換內(nèi)核都支持固定優(yōu)先級(jí)調(diào)度。2. 實(shí)時(shí)工程師在他們的職業(yè)生涯中一直都在使用這種技術(shù)。3. 許多書籍、論文和專業(yè)課程都是圍繞固定優(yōu)先級(jí)調(diào)度技術(shù)來編寫的。

    固定優(yōu)先級(jí)調(diào)度程序需要幾百字節(jié)的資源以及占用很少的CPU時(shí)間。相比之下，動(dòng)態(tài)優(yōu)先級(jí)調(diào)度程序通常都很復(fù)雜。動(dòng)態(tài)優(yōu)先級(jí)調(diào)度程序則明顯要超出上面的指標(biāo)。

    硬實(shí)時(shí)

    一個(gè)好的實(shí)時(shí)操作系統(tǒng)是獨(dú)立于具體應(yīng)用而設(shè)計(jì)的，但這并非意味著它不必干預(yù)硬實(shí)時(shí)處理。

    嚴(yán)格意義上說，沒有幾個(gè)系統(tǒng)是真正的硬實(shí)時(shí)系統(tǒng)。即使錯(cuò)過了時(shí)限一切仍將繼續(xù)。也許一個(gè)真正的硬實(shí)時(shí)系統(tǒng)同真正意義上的“不停頓”計(jì)算是同樣的類型。

    硬實(shí)時(shí)也許非常稀少，然而有關(guān)這種技術(shù)的應(yīng)用卻是大量存在。以數(shù)據(jù)流媒體服務(wù)器為例，如果不能夠及時(shí)地發(fā)送信息包，世界并不會(huì)因此而完結(jié)；即便有時(shí)候錯(cuò)過了時(shí)限，也許都不會(huì)出現(xiàn)問題。服務(wù)器的評(píng)判部分取決于服務(wù)器并發(fā)服務(wù)的數(shù)據(jù)流的數(shù)目，同時(shí)也部分取決于這些數(shù)據(jù)流的品質(zhì)。在確保足夠確定性的情況下，可以判定一個(gè)服務(wù)器何時(shí)仍然能夠投入全力來運(yùn)行，這種情況下服務(wù)器可以發(fā)揮的能力同時(shí)確保數(shù)據(jù)流不出現(xiàn)錯(cuò)誤，這樣的軟件就非常有價(jià)值。

    時(shí)限調(diào)度

    動(dòng)態(tài)優(yōu)先級(jí)調(diào)度通常都從時(shí)限調(diào)度開始，或者對(duì)于周期性任務(wù)來說，是從時(shí)限集開始。調(diào)度程序?qū)⒏鶕?jù)這些時(shí)限來決定任務(wù)的執(zhí)行順序。

    調(diào)度程序可以從時(shí)限中獲得許多信息，但是要滿足時(shí)限的要求需要很高的開銷。如果一個(gè)任務(wù)記錄了時(shí)限以及達(dá)到該時(shí)限時(shí)所需要的CPU時(shí)間總數(shù)，調(diào)度程序就可以實(shí)施可實(shí)現(xiàn)性分析。如果調(diào)度程序確定可以構(gòu)造一種調(diào)度，在確保滿足新的時(shí)限要求的同時(shí)也能滿足所有已經(jīng)接受的時(shí)限，那么系統(tǒng)將接受這個(gè)時(shí)限。除非經(jīng)授權(quán)調(diào)度程序允許實(shí)現(xiàn)該類型任務(wù)準(zhǔn)入的管理控制，否則它不可能作出一個(gè)現(xiàn)實(shí)的承諾。

    如果所有任務(wù)都運(yùn)行正常，并且從不試圖使用比它們?cè)诔杀径攘恐猩暾?qǐng)的CPU時(shí)間更多的話，那么準(zhǔn)入控制就足夠了。如果有時(shí)任務(wù)低估了它們對(duì)處理器的需求，一個(gè)獲準(zhǔn)參與控制的調(diào)度程序允許具有對(duì)不準(zhǔn)確資源度量的任務(wù)與其它任務(wù)的時(shí)限進(jìn)行折衷考慮。

    為了防止出現(xiàn)這種情況，調(diào)度程序可能會(huì)采取一種強(qiáng)制措施。如果一個(gè)任務(wù)試圖超出其時(shí)限，那么就可能會(huì)出現(xiàn)一些不良的情況。比如可能會(huì)從系統(tǒng)中消除該任務(wù)。也許這些任務(wù)只是被別的任務(wù)搶先占用，并且允許這些任務(wù)在稍后的時(shí)間再繼續(xù)運(yùn)行。在上述任何的情況下，這些任務(wù)很有可能會(huì)超過其時(shí)限的約束，但是并不會(huì)影響其它調(diào)度的正確性。老式批處理計(jì)算機(jī)用戶對(duì)此可能非常熟悉，在那樣的計(jì)算機(jī)系統(tǒng)中采用的任務(wù)調(diào)度策略非常像現(xiàn)在的時(shí)限調(diào)度。

    早時(shí)限

    個(gè)硬實(shí)時(shí)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度程序稱為早時(shí)限(EDF)。Liu和Layland的文獻(xiàn)證明，如果存在某一種調(diào)度能夠滿足所有的時(shí)限要求，那么每一次總是執(zhí)行當(dāng)前具有早未完成時(shí)限的任務(wù)就可以滿足所有時(shí)限的要求。

    EDF的吸引力在于效率高、容易計(jì)算和推斷。這是動(dòng)態(tài)優(yōu)先級(jí)調(diào)度研究的一個(gè)主要組成部分。EDF的缺點(diǎn)在于，理論表明這種算法能對(duì)可調(diào)度負(fù)載進(jìn)行優(yōu)化，但是它不能解決過載問題。發(fā)生過載時(shí)，EDF性能退化很快。這種情況不會(huì)對(duì)嚴(yán)格的硬實(shí)時(shí)系統(tǒng)造成問題。

    EDF調(diào)度的實(shí)現(xiàn)相對(duì)容易。執(zhí)行隊(duì)列總是由下一個(gè)時(shí)限來分類。當(dāng)一個(gè)任務(wù)處于激活狀態(tài)時(shí)必須將該任務(wù)加入到執(zhí)行隊(duì)列中，或者如果任務(wù)的時(shí)限在當(dāng)前正在執(zhí)行的任務(wù)的時(shí)限之前，那么該任務(wù)就會(huì)搶先占用當(dāng)前的任務(wù)。

    如果所有的任務(wù)都是周期性的(這些任務(wù)的出現(xiàn)僅僅由于時(shí)間的流逝)，那么搶先占用就沒有必要。這樣就簡(jiǎn)化了調(diào)度程序并且降低了任務(wù)切換的開銷。

    如果任務(wù)可以在周期中的任何時(shí)刻執(zhí)行，那么可實(shí)現(xiàn)性分析就簡(jiǎn)單可行。也就是說，早期的結(jié)果是可以接受的，并且任務(wù)準(zhǔn)備好隨時(shí)執(zhí)行。從另一個(gè)角度來看，這樣就允許任務(wù)的執(zhí)行可以根據(jù)周期小幅變化。微小的時(shí)限控制要在偽多項(xiàng)式時(shí)間類型中進(jìn)行分析。

    松弛時(shí)間

    松弛時(shí)間(slack time)是指一個(gè)任務(wù)從開始執(zhí)行到下一次的時(shí)限開始之間的時(shí)間長(zhǎng)短。這就是可實(shí)現(xiàn)的調(diào)度窗口的寬度。

    基于調(diào)度任務(wù)的松弛時(shí)間需要為調(diào)度進(jìn)行成本度量，它在過載的情況下性能會(huì)略微下降，并且通過擴(kuò)充可以相對(duì)更好地調(diào)度多個(gè)處理器。這種算法就稱為小松弛(LLF)方法。

    LLF算法需要進(jìn)行適當(dāng)修改來防止出現(xiàn)過多的任務(wù)間切換。如果多個(gè)任務(wù)具有近乎一樣的松弛時(shí)間，那么嚴(yán)格意義上的LLF就要求調(diào)度程序在每一次獲得控制權(quán)時(shí)都必須對(duì)這些任務(wù)進(jìn)行切換。LLF對(duì)算法進(jìn)行了修改，如果任務(wù)切換不會(huì)改變已經(jīng)滿足的時(shí)限，那么調(diào)度程序不會(huì)進(jìn)行任務(wù)的切換。

    非周期性任務(wù)

    調(diào)度程序的功能是調(diào)度一切任務(wù)，但是也有例外，像中斷服務(wù)、DMA以及某些任務(wù)由于某些原因必須調(diào)度比原定執(zhí)行序列更高的優(yōu)先級(jí)，因而破壞原有的執(zhí)行順序。這些都稱之為非調(diào)度的實(shí)體，且在時(shí)限調(diào)度程序中是不受歡迎的。一些分析技術(shù)允許非調(diào)度實(shí)體的存在，但是卻會(huì)導(dǎo)致調(diào)度程序的效率下降。為時(shí)限調(diào)度程序而設(shè)計(jì)的系統(tǒng)總是盡可能地減少非調(diào)度實(shí)體的數(shù)量以及這些實(shí)體所占用的CPU時(shí)間。

    非周期性任務(wù)對(duì)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度程序來說是一個(gè)挑戰(zhàn)。1. 可實(shí)現(xiàn)性分析通常是一個(gè)必不可少的任務(wù)。如果系統(tǒng)需要盡可能地滿足時(shí)限的要求，那么可實(shí)現(xiàn)性分析就不適合。2. 如果一個(gè)事件已經(jīng)到達(dá)，而這時(shí)可實(shí)現(xiàn)性分析的結(jié)果表明不應(yīng)該為這個(gè)任務(wù)提供服務(wù)。3. 非周期性事件的負(fù)載通常都描述為一種統(tǒng)計(jì)分布。

    非周期任務(wù)/事件可以使用比動(dòng)態(tài)優(yōu)先級(jí)任務(wù)更高的優(yōu)先級(jí)來調(diào)度。這種方法有效的前提是非周期性事件需要硬實(shí)時(shí)服務(wù)并且周期性事件相對(duì)來說是軟實(shí)時(shí)。主要的問題是調(diào)度程序必須將所有的非周期性活動(dòng)視為不可調(diào)度的實(shí)體，這樣就使得在調(diào)度周期性任務(wù)時(shí)效率低下，這是因?yàn)榇嬖诖罅坎豢烧{(diào)度的任務(wù)的緣故。

    經(jīng)由動(dòng)態(tài)優(yōu)先級(jí)調(diào)度程序調(diào)度的周期性服務(wù)器能夠?yàn)榉侵芷谛允录峁┓?wù)。這種方法將非周期性事件置于調(diào)度程序的控制之下。為了使得這種方法切實(shí)可行，調(diào)度問題專家進(jìn)行了充分的研究。問題在于：如何給非周期性事件提供較快的反應(yīng)時(shí)間而不會(huì)為此而占用太多處理器時(shí)間。為了給非周期性事件提供與優(yōu)先級(jí)調(diào)度系統(tǒng)中近乎一樣的反應(yīng)時(shí)間，服務(wù)器必須具有很短的調(diào)度周期。為了處理某一瞬間同時(shí)到達(dá)的非周期性事件的峰值負(fù)載，服務(wù)器為此而付出的代價(jià)就會(huì)很高，所以有時(shí)需要占用所有的處理器時(shí)間來處理這些非周期性的事件。

    如果可以將非周期性事件分類為軟實(shí)時(shí)，那么調(diào)度程序就可以更好地處理這些非周期性事件。這是符合實(shí)際情況的。比如，鍵盤輸入可能希望在1/10秒的時(shí)間內(nèi)得到響應(yīng)，但是如果碰巧某一次的鍵盤響應(yīng)時(shí)間是2/10秒問題也不會(huì)太大，所以非周期性服務(wù)器在每一個(gè)周期可以保留比平均資源開銷略微多一點(diǎn)的系統(tǒng)資源而不是占用的系統(tǒng)資源。

    本文總結(jié)

    本文討論的問題具備一定的前瞻性。也許今天還不需要?jiǎng)討B(tài)優(yōu)先級(jí)調(diào)度這樣的技術(shù)和工具，但是其發(fā)展?jié)摿薮螅绕湓趯?shí)時(shí)設(shè)計(jì)方面。