實時調度

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不可調度。

任務按單調速率優先順序分配（RMPA）的調度演演算法，稱為單調速率調度（RMS）。RMPA是指任務的優先順序按任務周期T來分配。它根據任務的執行周期的長短來決定調度優先順序，那些具有小的執行周期的任務具有較高的優先順序，周期長的任務優先順序低。

不考慮n=1的情況。RMS是單處理器下的最優靜態調度演演算法。1973年Liu和Layland發表的這篇文章的前半部分首次提出了RM調度演演算法在靜態調度中的最優性. 它的一個特點是可通過對系統資源利用率的計算來進行任務可調度性分析, 演演算法簡單、有效, 便於實現。不僅如此, 他們還把系統的利用係數(utilization factor)和系統可調度性聯繫起來, 推導出用RM調度所能達到的最小系統利用率公式. 同時, 這篇論文中透露出來的證明思想和方法也被人們所效仿. 下面就讓我們來看看這篇文章中關於RM調度演演算法的重要結論。

任何一個結論都有一個模型假設, 讓我們先列出這裡的假設:

(A1) 所有的任務請求都是周期性的，必須在限定的時限內完成；

(A2) 任務的作業必須在該任務的下一個作業發生之前完成, 這樣避免了考慮隊列問題; 在這裡, 我們對任務和作業不作特別的區分, 因為一個任務請求就是一個作業。

(A3) 任務之間都是獨立的，每個任務的請求不依賴於其他任務請求的開始或完成；

(A4) 每個任務的運行時間是不變的，這裡任務的運行時間是指處理器在無中斷情況下用於處理該任務的時間；

(A5) 所有的非周期性任務都在特殊的情況下運行，比如系統初始化或系統非正常緊急處理程序。

(A6) 其它一些假設, 比如, 單處理器, 可搶佔調度, 任務切換的時間忽略不計等等。

(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)這個概念被首先提出來. 它被定義為一個特定的時刻, 如果在這個時刻任務請求到來, 那麼會導致這個任務的響應時間最大（A critical instant of a task is the time atwhich the release of a task will produce the largestresponse time）. 由此得出

定理1: 一個任務的臨界時刻就是比這個任務優先順序高的所有任務同時發出請求的時刻.

（Lemma: For any task, the critical instant occurs if thattask is simultaneously released with all higher prioritytasks .）

證明: 由於一個任務的響應時間是它自己的負載時間加上被其它優先順序高的任務所打斷的時間. 由於自己的負載時間是固定的, 我們考慮在什麼時候任一高優先順序的任務會有最長的打斷時間. 顯然, 只有當這一高優先順序的任務與該任務同時請求處理時, 才能可能產生最大的打斷時間.

如果有任務1和任務2，且任務1的優先順序比任務2高，那麼任務2的響應時間會被任務1延遲。

當任務1的請求到來的更早，那麼任務2的響應時間就更長了。

定理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演演算法進行調度。前者用一個或幾個專用的周期任務執行所有非周期任務, 這種周期任務叫非周期任務伺服器。根據周期大小，伺服器有固定優先順序, 伺服器的執行時間被稱為預算, 它在每個伺服器周期Ts 的起點補充。只要伺服器有充足的預算, 就可在其周期內為非周期任務服務。該演演算法實現簡單, 但可調度性分析較難, 有時會出現抖動, 可能發生一個非周期任務在相鄰兩個伺服器周期中連續執行2倍預算的現象, 與RMS理論不符, 需要適當修改RMS演演算法。隨機伺服器演演算法與延遲伺服器演演算法相似, 但預算不是在每個周期起點補充, 而是在預算消耗Ts時間之後再補充。該演演算法與RMS分析演演算法一致, 但實現複雜。

最早截止時間優先演演算法（EDF）也稱為截止時間驅動調度演演算法（DDS），是一種動態調度演演算法。EDF指在調度時，任務的優先順序根據任務的截止時間動態分配。截止時間越短，優先順序越高。EDF有如下定理：

定理2：如果一個任務集按EDF演演算法調度，當且僅當U<=1。

EDF的特點

(1) 任務模型: 與RMS 調度相同。

(2) 優先順序分配方法: 動態分配, 距要求時限所剩時間越短優先順序越高。

(3) 可調度性分析: 如果任務集滿足下式, 則該任務集可調度。

EDF 調度演演算法已被證明是動態最優調度, 而且是充要條件。處理機利用率最大可達100% 。但瞬時過載時, 系統行為不可預測, 可能發生多米諾骨牌現象, 一個任務丟失時會引起一連串的任務接連丟失。另外, 它的在線調度開銷比RMS大。

最短空閑時間優先演演算法（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將RMS用於分散式實時系統，對RMS的一些基本概念如可調度性，可搶佔星等進行擴展，同時引入一些新的概念，如系統一致性。

定義：設?X={Xi}是一個分散式的任務集合，1≤i≤n，分散式系統中有m個節點，對於Xi∈X,Xi={Ti1,?Ti2,…，?Tim}，Tij是Xi在Nj節點上的任務，Xi有距離約束ci。對於Tij?有執行時間eij。

定義lk=ck/2「lg(ck/cl)， Bik=lk·2lg(ci/lk)」。

ΦNj(lk）=∑eij/Bik,（i=1..n）為調度任務集在節點Nj上的密度。

選擇一個使∑ΦNj(lk)，j=1..m）最小值的lk作為系統的劃分基r*。?

演演算法前提：所有的任務有相同的執行節點，每個任務在網路節點上有同樣的距離約束。