簡介
嵌入式系統在當今的生產和生活中得到了廣泛的套用,鑒於嵌入式實時系統的特點,要求任務調度等實時核心功能精簡和高效。綜合了EDF 和RM調度策略的CSD 調度策略,更加適合嵌入式系統的特點,滿足其核心的要求。任務調度策略是實時系統核心的關鍵部分,如何進行任務調度,使得各個任務能在其期限之內得以完成是實時作業系統的一個重要的研究領域。它的精簡和高效,對提高低處理能力,小記憶體系統整體性能具有重大的意義。
定義
對於什麼是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的回響時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決於程式的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯。
實時調度分類
實時系統根據其對於實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對於事件的回響時間的截止期限是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限到來之前得到處理，但違反截止期限並不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。
根據建立調度表和可調度性分析是脫機還是在線上實現分為靜態調度和動態調度，靜態調度無論是單處理器調度還是分散式調度，一般是以RMS算法為基礎；而動態調度則以EDF、LLF為主。
按系統分類實時調度可以分為單處理器調度，集中式多處理器調度和分散式處理器調度。
實時調度按任務是否可搶占又能分為搶占式調度和不可搶占式調度。
舉例
按系統分類
單處理器調度，集中式多處理器調度和分散式處理器調度
單處理器實時調度
問題描述：假設一任務集S={t1,t2,t3,...,tn}，周期分別是T1,T2,...,Tn，執行時間為c1,c2,...,cn，deadline為D1,D2,...,Dn，Di=Ti。任務ti可以被搶占。
CPU利用率用U=sum(ci/Ti)來表示。對於單處理器，U<=1是S可調度的前提條件，否則S不可調度。
RMS（Rate-Monotonic Scheduling）
任務按單調速率優先權分配（RMPA）的調度算法，稱為單調速率調度（RMS）。RMPA是指任務的優先權按任務周期T來分配。它根據任務的執行周期的長短來決定調度優先權，那些具有小的執行周期的任務具有較高的優先權，周期長的任務優先權低。
不考慮n=1的情況。RMS是單處理器下的最優靜態調度算法。1973年Liu和Layland發表的這篇文章的前半部分首次提出了RM調度算法在靜態調度中的最優性. 它的一個特點是可通過對系統資源利用率的計算來進行任務可調度性分析, 算法簡單、有效, 便於實現。不僅如此, 他們還把系統的利用係數(utilization factor)和系統可調度性聯繫起來, 推導出用RM調度所能達到的最小系統利用率公式. 同時, 這篇論文中透露出來的證明思想和方法也被人們所效仿. 下面就讓我們來看看這篇文章中關於RM調度算法的重要結論。
任何一個結論都有一個模型假設, 讓我們先列出這裡的假設:
(A1) 所有的任務請求都是周期性的,必須在限定的時限內完成；
(A2) 任務的作業必須在該任務的下一個作業發生之前完成, 這樣避免了考慮佇列問題; 在這裡, 我們對任務和作業不作特別的區分, 因為一個任務請求就是一個作業。
(A3) 任務之間都是獨立的,每個任務的請求不依賴於其他任務請求的開始或完成；
(A4) 每個任務的運行時間是不變的,這裡任務的運行時間是指處理器在無中斷情況下用於處理該任務的時間；
(A5) 所有的非周期性任務都在特殊的情況下運行,比如系統初始化或系統非正常緊急處理程式。
(A6) 其它一些假設, 比如, 單處理器, 可搶占調度, 任務切換的時間忽略不計等等。
RMS算法
(1) 任務T i (P i, Ci, D i) 模型: 周期為P i,計算時間為Ci, 時限D i 為周期終點。任務在周期起點釋放, 高優先權任務可搶占低優先權任務的執行。
(2) 優先權分配方法: 靜態固定分配。優先權與周期成反比, 周期越短優先權越高。
(3) 可調度性分析: 如果任務集滿足下式, 則該任務集可調度。
定理1：n個獨立的周期任務可以被RMPA調度，如果U<=n(2^(1/n)-1)。
一個任務的回響時間(response time)是指一個任務請求, 這個任務實際完成的時間跨度. 在靜態調度中, 任務的臨界時刻(critical instant)這個概念被首先提出來. 它被定義為一個特定的時刻, 如果在這個時刻有這個任務的請求, 那么這個任務就會需要最大的回響時間. 由此得出
定理1: 一個任務的臨界時間就是比這個任務優先權高的所有任務同時發出請求的時刻.
證明: 由於一個任務的回響時間是它自己的負載時間加上被其它優先權高的任務所打斷的時間. 由於自己的負載時間是固定的, 我們考慮在什麼時候任一高優先權的任務會有最長的打斷時間. 顯然, 只有當這一高優先權的任務與該任務同時請求處理時, 才能可能產生最大的打斷時間.
定理1的價值在於它找到了一個證明一個調度算法能否調度任一任務集充分必要條件, 那就是所有任務同時請求執行的時的情況下每個任務仍能滿足各自的期限, 那么這個任務集就可以被這個調度算法調度.
有了這個推論, 我們就可以證明RM調度的最優性了.
定理2: 如果一個任務集能夠被靜態調度, 那么RMS算法就能夠調度這個任務集. 從這個意義上說, RMS是最優的靜態調度算法.
這個定理的證明方法就是有名的交換法. 證明思路如下:
假設一個任務集S採用其他靜態優先權算法可以調度,那么總有這樣兩個優先權相鄰的任務i和j, 有Ti>Tj,而Pi≤Pj.把Ti和Tj的優先權Pi和Pj互換,明顯可以看出這時S仍然可以調度, 因為在所有任務同時請求的情況下, 交換這兩個任務不會影響其它任務的完成時間, 同時這兩個任務都可以在各自期限內完成. 按照這樣的方法,其他任何靜態優先權調度最終都可以轉換成RM調度.
RMS已被證明是靜態最優調度算法, 開銷小, 靈活性好, 是實時調度的基礎性理論。即使系統瞬時過載, 也完全可預測哪些任務丟失時限。缺點是處理機利用率較低, 最壞的情況下，當n→∞時, 不超過ln2 (≈ 70%)。另外, RMS是充分但非必要條件。而在一般情況下，對於隨機的任務集大約只有88%. 70%或者88%的處理器利用率對於許多實時套用來說是一個嚴重的限制，動態調度算法如最早截止期最先（earliest deadline first，EDF）或者最少空閒時間最先（least laxity first，LLF）已經被證明是最優的，並且能夠實現100% 的處理器利用率.
具有資源同步約束的RMS調度
當實時任務間共享資源時, 可能出現低優先權任務不可預測地阻塞高優先權任務執行的情況, 叫優先權倒置。這時RMS 算法不能保證任務集的調度, 必須使用有關協定控制優先權的倒置時間。常用的協定有優先權頂級協定和堆資源協定, 使用這些協定可使優先權的倒置時間最多為一個資源臨界段的執行時間, 並且不會發生死鎖。
基於RMS 的非周期任務的調度
實時系統中的非周期任務可採用延遲伺服器算法或隨機伺服器算法進行調度。它們的最大特點是可在周期任務的實時調度環境下處理隨機請求。兩者的基本思想是將非周期任務轉化成周期任務, 再利用RMS算法進行調度。前者用一個或幾個專用的周期任務執行所有非周期任務, 這種周期任務叫非周期任務伺服器。根據周期大小,伺服器有固定優先權, 伺服器的執行時間被稱為預算, 它在每個伺服器周期Ts 的起點補充。只要伺服器有充足的預算, 就可在其周期內為非周期任務服務。該算法實現簡單, 但可調度性分析較難, 有時會出現抖動, 可能發生一個非周期任務在相鄰兩個伺服器周期中連續執行2倍預算的現象, 與RMS理論不符, 需要適當修改RMS算法。隨機伺服器算法與延遲伺服器算法相似, 但預算不是在每個周期起點補充, 而是在預算消耗Ts時間之後再補充。該算法與RMS分析算法一致, 但實現複雜。
EDF
最早截止時間優先算法（EDF）也稱為截止時間驅動調度算法（DDS），是一種動態調度算法。EDF指在調度時，任務的優先權更具任務的截止時間動態分配。截止時間越短，優先權越高。EDF有如下定理：
定理2：如果一個任務集按EDF算法調度，若且唯若U<=1。
EDF的特點
(1) 任務模型: 與RMS 調度相同。
(2) 優先權分配方法: 動態分配, 距要求時限所剩時間越短優先權越高。
(3) 可調度性分析: 如果任務集滿足下式, 則該任務集可調度。
EDF 調度算法已被證明是動態最優調度, 而且是充要條件。處理機利用率最大可達100% 。但瞬時過載時, 系統行為不可預測, 可能發生多米諾骨牌現象, 一個任務丟失時會引起一連串的任務接連丟失。另外, 它的線上調度開銷比RMS大。
LLF
最短空閒時間優先算法（LLF）也是一種動態調度算法。LLF指在調度時刻，任務的優先權根據任務的空閒時間動態分配。空閒時間越短，優先權越高。空閒時間=deadline-任務剩餘執行時間。LLF可調度條件和EDF相同。
理論上，EDF和LLF算法都是單處理器下的最優調度算法。但是由於EDF和LLF在每個調度時刻都要計算任務的deadline或者空閒時間，並根據計算結果改變任務優先權，因此開銷大、不易實現，其套用受到一定限制。
多處理器實時調度
靜態調度
問題描述：一組具有優先權關係的任務在m個處理器上運行，任務優先權關係用“<”表示，即如果兩個任務（t1,t2）存在優先關係t1< t2，則t1必須在t2開始運行前完成。任務優先關係可用一個無環圖來表示，稱為計算圖G，如圖1.表示任務集S={t1,t2,t2,t4,t5}中任務存在優先關係<={(t1,t2),(t1,t3),(t1,t4),(t2,t6),(t3,t6),(t4,t5),(t5,t6)}。多處理其調度就是要找出長度最短的調度表。
靜態多處理器調度又可以有如下三種調度規範：
1）基本（或非搶占）調度BS（Basic Scheduling）。任務在執行過程中不能被打斷。
2）可搶占調度PS（Preemptable Scheduling），任務可被搶占，此處搶占不必基於優先權。
3）廣義調度GS（General Scheduling）。 GS是一個理論上的概念，允許一個處理器可在同一時刻執行多個任務。事實上每個處理器在每一時刻最多只能執行能夠一個任務。GS基於的前提是：在給定的時間段，處理器可以將其計算能力的一部分分配給一個任一個任務。並且規定同一任務不可以同時在多於一個處理器上並行執行。
定義 CA(G,k)表示調度規範A(BS、PS或GS)下，k個處理其的計算圖G的最小計算時間。
定理3： 可搶占調度和廣義調度的最小計算時間等於對任一k個處理器的計算圖G，有
C_GS (G,k)=C_PS (G,k)
BS不能得到最短調度表，GS雖然能夠得到最短調度表，但只是理論結果。定理三可知，PS和GS具有相同的最小計算時間，而PS在實際中是可實現的。
PS的一般生成過程是這樣的：
1）更具任務優先權關係畫出計算圖G
2）按G生成GS調度表（為什麼？）
3）採用某種方法將GS調度表換成PS調度表
動態調度
問題描述：到達時間不確定而計算時間c和截止時間D已知的n個任務，運行在m個處理器上，n不確定，動態調度的目標是使系統能夠對變化的環境做出迅速的反應。
動態調度的任務狀態可以用l-c空間表示。橫坐標表示任務的空閒時間l(t)，縱坐標表示任務的剩餘時間c(t)。任務空閒時間l(t)=D - c(t)。圖中虛線間隔表示一個時間單位，如t2的當前時刻剩餘計算時間為3，空閒時間為2，因此deadline為3+2=5。
每隔一定時間，l-c空間將刷新一次。任務在l-c空間的位置變化具有不同含義：
1）任務執行：任務向下移動，c(t)變小
2）任務不執行：任務向左移動，l(t)變小
3）任務未到達：任務不動。有些任務未到達時已經確認，那么這些任務在l-c圖上預留位置，當其到達時被激活
4）新任務到達：根據任務的計算時間c和空閒時間l，設定其在l-c空間的位置
5）任務執行完畢：任務到達l軸，此時c(t)=0
6）任務運行逾時失敗：任務落在c軸左邊，此時l(t)<0
任務的截止時間的屬性在l-c空間中由角度表示。相同截止時間的任務都位於125度叫的同一直線上，而截止時間沿45度叫遞增。t1和t3截止時間相等，t2比t1，t3長。
在l-c空間裡，任務可以按EDF和LLF調度算法調度。但是多處理器下EDF和LLF不是最優算法。
定理4：在多處理器下，如果任務計算時間、截止時間或到達時間不能預先確定，則最優調度算法不存在。
定理4表明基於l-c空間的多處理器動態調度算法沒有最優解。由於該算法不能保證所有任務的截止時間，因此屬於軟實時調度。（軟硬實時調度：）
分散式實時調度
分散式實時調度算法可以分為兩類：
1）以RMS為基礎的廣義RMS調度
2）以風車調度Sr為基礎的DSr調度
GRMS
GRMS將RMS用於分散式實時系統，對RMS的一些基本概念如可調度性，可搶占星等進行擴展，同時引入一些新的概念，如系統一致性。
DSr
風車調度算法，略
