時間調度演算法

⑴ 什麼rm調度演算法

一個任務的響應時間(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) 優先順序分配方法: 動態分配, 距要求時限所剩時間越短優先順序越高。 理論上，EDF和LLF演算法都是單處理器下的最優調度演算法。但是由於EDF和LLF在每個調度時刻都要計算任務的deadline或者空閑時間，並根據計算結果改變任務優先順序，因此開銷大、不易實現，其應用受到一定限制。多處理器實時調度