排程 – 行程的執行順序安排問題 日期 : 2018/11/14

排程 背景知識 排程的主要問題 如何排程是影響作業系統效能最重要的因素。 有了行程切換的概念，就可以介紹排程了。 很多個程式在記憶體當中，下一個應該誰來執行呢？ 如何排程是影響作業系統效能最重要的因素。 排程的目的就是將 CPU 資源作更有效的利用。 2 陳鍾誠 - 2018/11/14

排程的背景知識 背景知識一： 背景知識二： 背景知識三： 內文切換的方法與意義 CPU 暴衝與 IO 暴衝 排程佇列的概念 3 陳鍾誠 - 2018/11/14

背景知識一:內文切換 通常用組合語言撰寫 用來將暫存器、檔案資源等儲存的函數 該函數稱為內文切換函數 4 陳鍾誠 - 2018/11/14

背景知識二：CPU 與 IO 暴衝 行程一開始都是 CPU 暴衝，接著是 I/O 暴衝，然後再回到 CPU 暴衝和 I/O 暴衝。在正常的狀況下，行程就在這兩個狀態間一直循環，最後以 CPU 暴衝作為結束。 5 陳鍾誠 - 2018/11/14

CPU 暴衝與 I/O 暴衝 - 圖示 load store add store read from file CPU暴衝 等待 I/O store increment index write to file CPU暴衝 等待 I/O I/O暴衝 load store add store read from file CPU暴衝 … 6 陳鍾誠 - 2018/11/14

CPU 暴衝時間統計示意圖 160 140 120 頻率 100 80 60 40 20 8 16 24 32 40 暴衝時間（毫秒） 8 16 24 32 40 暴衝時間（毫秒） 7 陳鍾誠 - 2018/11/14

背景知識三：排程佇列 一個行程在執行期間會在各種不同的佇列中進出。 一個系統中通常有 工作佇列 就緒佇列 等待佇列 裝置佇列 8 陳鍾誠 - 2018/11/14

就緒佇列與裝置佇列 head tail 暫存器 … 就緒佇列 磁碟1 佇列 磁碟2 佇列 PCB7 PCB2 PCB5 PCB1 PCB9 陳鍾誠 - 2018/11/14

Linux 行程串列的資料結構 prev_task next_task init_task 10 陳鍾誠 - 2018/11/14

Linux 的就緒佇列 在就緒佇列中的所有行程，其狀態皆為TASK_RUNNING。 行程描述器中實作就緒佇列的 run_list 欄位： 就緒佇列的開頭 struct list_head run_list; static LIST_HEAD(runqueue_head); 11 陳鍾誠 - 2018/11/14

排程的方法 先到先做排程 (First-Come, First Served) 最短工作優先排程 (Shortest Job First) 可搶先版：最短剩餘優先排程 優先權排程 – Priority Scheduling 循環分時排程 – Round Robin Scheduling (大輪迴的排法) 多層佇列排程 – Multilevel Queue Scheduling 多層反饋佇列排程 – Multilevel Feedback Queue Scheduling 12 陳鍾誠 - 2018/11/14

先到先做排程法 First Come, First Served 方法： 簡稱 FCFS Scheduling 先進入的行程先執行。 13 陳鍾誠 - 2018/11/14

先到先做排程法 - 範例圖示 行程 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 毫秒 14 陳鍾誠 - 2018/11/14

最短工作優先排程 Shortest Job First 方法 簡稱 SJF Scheduling 需要的時間最短者先執行。 15 陳鍾誠 - 2018/11/14

最短工作優先排程– 範例圖示 行程 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 倍。 16 陳鍾誠 - 2018/11/14

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

下一次 CPU 暴衝時間的預測 12 10 暴衝時間 8 6 4 2 時間 i 1 2 3 4 5 6 7 CPU暴衝（ti） 6 4 6 時間 i 1 2 3 4 5 6 7 CPU暴衝（ti） 6 4 6 4 13 13 13 … 預測（Ti） 10 8 6 6 5 9 11 12 … 18 陳鍾誠 - 2018/11/14

最短剩餘優先排程 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 毫秒 19 陳鍾誠 - 2018/11/14

優先權排程 Priority Scheduling 方法： 最高優先權的行程先執行 Highest Priority First 20 陳鍾誠 - 2018/11/14

優先權排程 – 圖示 使用不可搶先的優先權排程 優先權數值愈小代表優先權愈高 行程 CPU 暴衝時間（毫秒） 優先權 P1 6 2 5 9 15 18 25 平均等待時間：（9 + 0 + 18 + 5 + 15）/ 5 = 9.4毫秒 21 陳鍾誠 - 2018/11/14

循環分時排程 Round-Robin Scheduling 將時間等切成一小片一小片的時間切片，每一個時間切片則為每個行程每次得到 CPU 使用權後可執行的時間。 特別為分時系統所設計，為可搶先的。 22 陳鍾誠 - 2018/11/14

循環分時排程 – 圖示 行程 CPU 暴衝時間（毫秒） P1 6 P2 5 P3 7 (時間切片為 5 毫秒) P1 P2 P3 P1 P1 5 9 13 18 25 平均等待時間：（8 + 5 + 9）/ 3 = 7.33 毫秒 23 陳鍾誠 - 2018/11/14

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

時間切片的影響 5 1 2 3 4 6 7 8 內文切換 次數 時間切片 長度 10 行程執行時間 = 8 毫秒 內文切換 次數 時間切片 長度 10 行程執行時間 = 8 毫秒 注意：時間切片若太短，則會一值在做內文切換，很少在真正執行程式。 25 陳鍾誠 - 2018/11/14

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

多層佇列排程法 – 圖示 高優先權 系統行程 伺服精靈行程 批次行程 使用者行程 低優先權 27 陳鍾誠 - 2018/11/14

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

多層反饋佇列排程 – 圖示 A: 時間切片 = 5 ms B: 時間切片 = 20 ms C: FCFS 陳鍾誠 - 2018/11/14 29 陳鍾誠 - 2018/11/14

常見作業系統的排程方法 Linux, (UNIX, FreeBSD) : Micro C/ OS2 (uCOS2) First-Come, First-Serve Scheduling Round – Robin Scheduling Micro C/ OS2 (uCOS2) Highest Priority First – Preemptive 特色： 每個行程都有唯一的優先順序，可搶先。 切換的速度超快，因為使用了特殊的位元導向資料結構作排程。 在嵌入式系統領域相當的火紅。 30 陳鍾誠 - 2018/11/14

評估排程優劣的方法 定性模式 排隊模型 模擬 實作 31 陳鍾誠 - 2018/11/14

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

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

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

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

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