處理器調度演算法
Ⅰ 操作系統應該如何在多CPU上調度工作
操作系統在多CPU上調度工作時，主要採取以下策略：
應用程序並行化：
- 應用程序需要被重寫為並行執行，利用多線程或多進程在多個CPU上分工合作。這要求開發者深入理解並發編程原理，並合理地劃分任務，以實現高效的並行處理。
處理緩存一致性問題：
- 在多CPU系統中，多個CPU可能同時訪問共享數據。為確保數據的一致性，操作系統需要處理緩存一致性問題，防止數據沖突和臟讀。這通常通過硬體和軟體的協同工作來實現。
負載均衡：
- 調度器需要在多個CPU之間平衡工作負載，以確保每個CPU都能得到充分利用。這可以通過多種策略來實現，如單隊列多處理器調度和多隊列多處理器調度。MQMS通過為每個CPU分配獨立的調度隊列來避免同步問題，但可能引發負載不均。為解決此問題，可以採用工作遷移策略，如工作竊取演算法，動態調整工作在CPU之間的分布。
調度演算法選擇：
- 操作系統提供多種調度演算法，如O、CFS和BFS等。每種演算法都有其優點和局限性，需要根據具體應用場景進行選擇。例如，CFS注重公平性和響應時間，而BFS則更注重低延遲和高性能。
考慮性能、復雜度和可維護性：
- 設計一個高效、靈活的調度程序是一項復雜任務，需要平衡性能、復雜度和可維護性等多個因素。隨著技術的進步，調度策略也在不斷演進，以適應日益復雜的多核環境。
綜上所述，操作系統在多CPU上調度工作時，需要綜合考慮應用程序並行化、緩存一致性、負載均衡、調度演算法選擇以及性能、復雜度和可維護性等多個方面。
Ⅱ 實時調度的單處理器實時調度
問題描述：假設一任務集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 proce 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% 的處理器利用率. 最早截止時間優先演算法（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或者空閑時間，並根據計算結果改變任務優先順序，因此開銷大、不易實現，其應用受到一定限制。
