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

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

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

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

    速率單調(diào)分析

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

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

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

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

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

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

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

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

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

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

    硬實時

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

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

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

    時限調(diào)度

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

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

    如果所有任務(wù)都運行正常，并且從不試圖使用比它們在成本度量中申請的CPU時間更多的話，那么準(zhǔn)入控制就足夠了。如果有時任務(wù)低估了它們對處理器的需求，一個獲準(zhǔn)參與控制的調(diào)度程序允許具有對不準(zhǔn)確資源度量的任務(wù)與其它任務(wù)的時限進(jìn)行折衷考慮。

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

    早時限

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

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

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

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

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

    松弛時間

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

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

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

    非周期性任務(wù)

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

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

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

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

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

    本文總結(jié)

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