實時調度

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) 其它一些假設, 比如, 單處理器, 可搶佔調度, 任務切換的時間忽略不計等等。

(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*。?

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