作業系統 第五章 排程

第五章 排程 排程概念 行程行為 CPU 排程器 排程時機 分派器 排程準則 排程方法 特殊用途排程 排程評估 摘要

排程概念 一個行程在執行期間會有很多時間在等待（如：等待 I/O 完成）。 在單一行程或批次的系統中，當行程在等待時 CPU 是閒置的。 排程就是將系統資源作更有效的利用。

行程行為 行程的執行會在兩個狀態間不停的切換 CPU 暴衝 I/O 暴衝 行程一開始都是 CPU 暴衝，接著是 I/O 暴衝，然後再回到 CPU 暴衝和 I/O 暴衝。在正常的狀況下，行程就在這兩個狀態間一直循環，最後以 CPU 暴衝作為結束。

CPU 暴衝與 I/O 暴衝 load store add store read from file CPU暴衝 等待 I/O I/O暴衝 store increment index write to file CPU暴衝 等待 I/O I/O暴衝 load store add store read from file CPU暴衝 …

CPU 暴衝時間統計示意圖 160 140 120 頻率 100 80 60 40 20 8 16 24 32 40 暴衝時間（毫秒）

CPU 排程器 短程排程器（或是 CPU 排程器），由就緒佇列中選出下一個可以執行的行程。 實作一個就緒佇列可根據不同的需求使用 先進先出（FIFO)佇列 優先權佇列 樹 鏈結 例如：在分時作業系統中，使用鏈結就很適合。

行程狀態圖 新建 允許進入 離開 中斷 結束 就緒 執行 排程器分派 I/O或事件結束 I/O或等待事件 等待

排程時機 有 4 種行程狀態的變化，需要進行排程。 前兩種狀態為行程主動放棄執行權，而後 2 種狀態為被動的。 由執行狀態切換到等待狀態 由執行狀態切換到結束狀態 由執行狀態切換到就緒狀態 由等待狀態切換到就緒狀態 前兩種狀態為行程主動放棄執行權，而後 2 種狀態為被動的。 一個系統中若只有行程主動放棄執行權時才會進行重新排程的話，則這個系統的排程方法為不可搶先的，反之，稱為可搶先的。

分派器 當排程器選出下一個行程後，就把工作交給分派器。 一個分派器會做下面幾件事： 內文切換 切換回使用者模式（排程是在管理者或核心模式進行） 重新回到使用者的程式，並且從適當位址重新開始執行 由分派器停止一個行程到開始執行另一個行程的這段時間稱為分派延遲。

排程準則 在選擇一個排程器時有下列幾項準則： 根據不同的系統需求，可以使用不同的準則來選擇不同的排程器。 CPU 使用率 產量 回覆時間 等待時間 反應時間 根據不同的系統需求，可以使用不同的準則來選擇不同的排程器。 舉例來說，為了保證使用者能得到最好的服務，我們會盡量減小最大反應時間。

第五章 排程 排程概念 排程方法 特殊用途排程 排程評估 摘要 先到先做排程 最短工作優先排程 優先權排程 循環分時排程 多層佇列排程 多層反饋佇列排程 特殊用途排程 排程評估 摘要

排程方法 一個排程方法決定就緒佇列中那一個行程可以使用 CPU 資源。 常見的排程方法有： 先到先做排程 最短工作優先排程 優先權排程 循環分時排程 多層佇列排程 多層反饋佇列排程

先到先做排程 先到先做（FCFS）為最簡單的不可搶先排程法。 根據行程要求使用 CPU 的順序，來取得 CPU 的使用權。 所產生的平均等待時間經常都很長。 使用先到先做排程法時，若系統中存在一個 CPU 暴衝時間很長的行程時，則會產生護航現象。

先到先做排程 (續) 行程 CPU 暴衝時間（毫秒） P1 20 P2 5 P3 5 P1 P2 P3 20 25 30 20 25 30 平均等待時間：(0 + 20 + 25）/ 3 = 15 毫秒 P2 P3 P1 5 10 30 平均等待時間：(10 + 0 + 5）/ 3 = 5 毫秒

最短工作優先排程 下一次 CPU 暴衝最短的行程可優先取得 CPU 的使用權。 對於平均等待時間而言最短工作優先排程（SJF）為最佳的不可搶先排程法。 若兩個行程下一次的 CPU 暴衝時間等長的話，則可以使用 FCFS 排程方式來排程。

最短工作優先排程 (續) 行程 CPU 暴衝時間（毫秒） P1 15 P2 4 P3 3 P3 P2 P1 3 7 22 3 7 22 平均等待時間：（7 + 3 + 0）/ 3 = 3.3 毫秒 若使用 FCFS 排程法，行程到達的順序為 P1、P2、P3 則平均等待時間：（0 + 15 + 19）/ 3 = 11.3 毫秒 FCFS 的平均等待時間大約為 SJF 的 3.4 倍。

最短工作優先排程 (續) SJF 在實作上有困難，因為很難知道行程下一個 CPU 暴衝時間的確實長度。 使用預估的方法來求得近似的值。行程下一個 CPU 暴衝時間的預估值可以設為前幾次 CPU 暴衝時間的幾何平均值。 tn 為第 n 次 CPU暴衝時間的長度 Tn+1 表示再下一次 CPU 暴衝時間的預估值

下一次 CPU 暴衝時間的預測 12 10 暴衝時間 8 6 4 2 1 2 3 4 時間 i 5 6 7 CPU暴衝（ti） 6 4 6 1 2 3 4 時間 i 5 6 7 CPU暴衝（ti） 6 4 6 4 13 13 13 … 預測（Ti） 10 8 6 6 5 9 11 12 …

最短工作優先排程 (續) SJF 也可以是可搶先的。 可搶先的 SJF 排程又稱為最短剩餘時間優先的排程法。 行程 CPU 暴衝時間（毫秒） 到達時間 P1 6 0 P2 3 1 P3 7 2 P4 4 3 P1 P2 P4 P1 P3 1 4 8 13 22 平均等待時間：（7 + 0 + 11 + 1）/ 4 = 4.75 毫秒

優先權排程 排程器依行程的優先權高低來分配 CPU 的使用順序，優先權愈高的行程可優先使用 CPU。 SJF 也可以視為是一種優先權排程法。 優先權的定義可以分成兩種類型： 內部 - 使用行程內可以測量的項目，如行程使用的記憶體大小。 外部 - 使用如使用者繳費的多寡等外部資訊。 優先權排程可以是不可搶先的或可搶先的。 有可能發生飢餓的現象 可使用老化來解決

優先權排程 (續) 使用不可搶先的優先權排程 優先權數值愈小代表優先權愈高 行程 CPU 暴衝時間（毫秒） 優先權 P1 6 2 5 9 15 18 25 平均等待時間：（9 + 0 + 18 + 5 + 15）/ 5 = 9.4毫秒

循環分時排程 將時間等切成一小片一小片的時間切片，每一個時間切片則為每個行程每次得到 CPU 使用權後可執行的時間。 特別為分時系統所設計，為可搶先的。 行程 CPU 暴衝時間（毫秒） P1 6 P2 5 P3 7 (時間切片為 5 毫秒) P1 P2 P3 P1 P1 5 9 13 18 25 平均等待時間：（8 + 5 + 9）/ 3 = 7.33 毫秒

循環分時排程 (續) RR 排程法的效能與時間切片的長短關係非常密切 使用 RR 排程法時，必須注意內文切換對效能的影響。 太長 - 如同FCFS 排程法 太短 - 產生處理器分享的現象 使用 RR 排程法時，必須注意內文切換對效能的影響。 使用 RR 排程法最重要的一點就是定義時間切片的長短。一般的經驗法則是 80% 行程的 CPU 暴衝時間應該要比一個時間切片要來得短。

時間切片與內文切換 5 1 2 3 4 6 7 8 內文切換 次數 時間切片 長度 10 行程執行時間 = 8 毫秒

多層佇列排程 將行程分類，相同類型的行程分在同一佇列，而每一佇列都有自己的排程方法。 最常見的分類將行程分成 前景（互動）行程 - RR 排程法 背景（批次）行程 - FCFS 排程法 佇列與佇列之間還有優先權的關係，且佇列之間還需要另一個整體排程方法 可搶先的固定優先權排程法 可能會產生飢餓的現象。

多層佇列排程法 高優先權 系統行程 伺服精靈行程 批次行程 使用者行程 低優先權

多層反饋佇列排程 多層反饋佇列排程法允許行程在各個佇列間移動。 CPU 暴衝時間愈長的行程就移到優先權比較低佇列中。 能避免飢餓的現象發生。

多層反饋佇列排程 (續) A: 時間切片 = 5 ms B: 時間切片 = 20 ms C: FCFS

第五章 排程 排程概念 排程方法 特殊用途排程 多處理器排程 即時排程 排程評估 摘要

特殊用途排程 特殊的系統中，需要使用特別的排程方法才能完成系統的特殊需求，如 多處理器的環境 即時系統

多處理器排程 若系統中的處理器皆為相同架構時，此系統稱為同質，反之，稱為異質。 在同質系統中，通常將所有就緒的行程都放置於同一個佇列中，等待著被分派給空閒的處理器執行。 共用就緒佇列的架構下形成了兩種排程方式 對稱式多元處理 - 各處理器自行進行排程 非對稱式多元處理 –由某一顆處理器來幫其他處理器進行排程

即時排程 提高所有工作的可排程性及可預測性，也就是保證最多工作能在所要求的時間限制下完成。 依照系統對時間限制所要求的程度可分為兩類： 硬即時系統 軟即時系統 硬即時系統須保證關鍵工作在一定的時間內能夠完，否則對系統會有負面的影響。 軟即時系統對時間的要求就沒有那麼嚴苛，萬一工作沒有在一定的時間內完成，它還是有部份價值

即時排程 (續) 為了讓即時行程能馬上執行，分派延遲必須很短。 為了縮短分派延遲，系統呼叫必須是可以搶先的： 在系統呼叫中加入可搶先點。 讓整個核心都是可搶先的 整個核心中的資料結構都需要使用同步的機制來保護。 會產生優先權倒轉的狀況。

第五章 排程 排程概念 排程方法 特殊用途排程 排程評估 定性模式 排隊模式 模擬 實作 摘要

排程評估 不同的排程方法，適用於不同的系統。 有幾種不同的評估方法來為系統選擇合適的排程方法： 定性模式 排隊模型 模擬 實作

定性模式 定性模式是一種分析式評估，使用預先選定的行程組合來評估各種不同的排程方法。 例如預先選定一組行程組合，然後分別使用 FCFS、SJF 和 RR 排程法來評估那一種排程法所產生的平均等待時間最短。 定性模式的評估快速簡單，但 需要事先知道很多系統的資訊當作輸入。 只適用於行為比較固定的系統上。

排隊模式 電腦系統可看成是以網路相連的一群伺服器的組合： 佇列中行程的數目隨著時間變化，不適合以定性模式來評估。 CPU 是執行就緒佇列中行程的伺服器 I/O 系統是執行裝置佇列中行程的伺服器 佇列中行程的數目隨著時間變化，不適合以定性模式來評估。 若知道新行程到達的速率與舊行程被處理的速率，就可能求出 CPU 使用率 佇列平均長度 平均等待時間

排隊模式 (續) Little’s formula 系統排程的模型很難以演算法和行程到達的分佈函數完全模擬出來。 排隊模型得到的結果經常只是模擬的近似值。

模擬 透過軟體建立一個電腦系統模型，以軟體的資料結構來模擬系統中的主要元件。 模擬程式在執行時，會產生很多資料與數據，這些資訊通常都被收集起來以備日後分析使用。 模擬時需要有很多資料來當作模擬程式的輸入，通常使用 亂數產生器產生行程和 CPU 的暴衝時間。 追蹤磁帶 模擬可以得到比較準確的評估結果，但它需要花費很大的成本，通常一次模擬都需花上數小時的時間。

實作 要完整地評估一個排程方法最終還是需要實作出排程器。 實作的主要困難點在於所花費的代價太高： 另一個困難點在於評估的環境是變動的。 撰寫排程器與修改作業系統需花費大量的時間 使用者對作業系統經常改變所產生反應的代價 另一個困難點在於評估的環境是變動的。

摘要 (1) 排程的目的是藉由行程在 CPU 之間的切換，增加整體的系統效能。 不同的排程方法對最適當的行程會有不同的定義。 排程方法可以分成可搶先的或是不可搶先的。 FCFS 排程是最簡單排程法，但有可能造成 CPU 暴衝短的行程必須等待 CPU 暴衝很長的行程。

摘要 (2) 對平均等待時間而言，SJF 是最理想的排程法，不過要實作 SJF 排程法是很困難的。 優先權排程法是根據行程優先權的高低來分配 CPU 使用權的順序，高優先權的行程能優先使用 CPU。 優先權與 SJF 排程法都可能會造成飢餓現象，使用老化技術可以避免飢餓現象。 RR 排程法，是特別為分時系統所設計的， 使用 RR 排程法最重要的一點就是定義時間切片的長短。

摘要 (3) 多層佇列排程法將行程分類，相同類別的分在同一佇列，每一佇列都有自己的排程法，行程不可以在各佇列間移動。 多層反饋佇列排程法類似多層佇列排程法，但允許行程在各個佇列間移動。 評估排程方法時通常有幾種方式： 定性模式 排隊模型 模擬 實作