調度程序的功能是調度任務的執行順序，非調度實體的存在卻會導致調度程序的效率下降，為時限調度程序而設計的系統總是盡可能地減少非調度實體的數量以及這些實體所占用的CPU時間，本文介紹嵌入式系統設計過程中任務優先級調度的策略。

    在過去的幾年里，固定優先級調度技術的發展迅速。分時系統和一些實時系統，要求所有的任務要同時運行。它賦予每個任務一個有效的優先級，并且該優先級在任務等候執行的過程中逐步遞增。每一個任務都將獲得一個有效的優先級，該優先級將確保該任務至少會獲得一個短暫的CPU執行時間。

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

    實際上，絕大多數的實時操作系統都采用靜態優先級調度方式，本文介紹如何通過時限調度(deadline scheduling)來保證系統的實時性。

    速率單調分析

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

    為此，人們研發了RMA調度，RMA的一個重要特征是可以分析系統的可實現性(feasibility)。采用RMA，結構設計人員可以收集系統的情況，然后分析系統的可實現性，從而獲得“調度程序正是如此工作”或者是“固定優先級調度程序不能進行這樣的調度”等分析結果。

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

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

    然后，要考慮軟實時方面的問題。通過彈出一個任務的優先級使之高于該時段指示的優先級水平，從而在RMA中可以對重要性進行度量。這樣就會造成那些沒有施加優先級彈出的任務出現問題，這種情況正好與RMA的整體設想相反。程序將分析可實現性，然后確保系統的成功。RMA不是為不可實現的系統而設計的。

    固定優先級調度

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

    一個有經驗的實時程序設計師可能用一些設計技巧來處理這樣的問題，如在系統運行時巧妙地處理優先級，或者是用加鎖的方法來實現，然而在此工程師面臨的是如何處理調度程序而不是如何使用調度程序的問題。

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

    固定優先級調度程序需要幾百字節的資源以及占用很少的CPU時間。相比之下，動態優先級調度程序通常都很復雜。動態優先級調度程序則明顯要超出上面的指標。

    硬實時

    一個好的實時操作系統是獨立于具體應用而設計的，但這并非意味著它不必干預硬實時處理。

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

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

    時限調度

    動態優先級調度通常都從時限調度開始，或者對于周期性任務來說，是從時限集開始。調度程序將根據這些時限來決定任務的執行順序。

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

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

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

    早時限

    個硬實時動態優先級調度程序稱為早時限(EDF)。Liu和Layland的文獻證明，如果存在某一種調度能夠滿足所有的時限要求，那么每一次總是執行當前具有早未完成時限的任務就可以滿足所有時限的要求。

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

    EDF調度的實現相對容易。執行隊列總是由下一個時限來分類。當一個任務處于激活狀態時必須將該任務加入到執行隊列中，或者如果任務的時限在當前正在執行的任務的時限之前，那么該任務就會搶先占用當前的任務。

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

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

    松弛時間

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

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

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

    非周期性任務

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

    非周期性任務對動態優先級調度程序來說是一個挑戰。1. 可實現性分析通常是一個必不可少的任務。如果系統需要盡可能地滿足時限的要求，那么可實現性分析就不適合。2. 如果一個事件已經到達，而這時可實現性分析的結果表明不應該為這個任務提供服務。3. 非周期性事件的負載通常都描述為一種統計分布。

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

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

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

    本文總結

    本文討論的問題具備一定的前瞻性。也許今天還不需要動態優先級調度這樣的技術和工具，但是其發展潛力巨大，尤其在實時設計方面。