Process Scheduling (行程排班) Chapter 5 Process Scheduling (行程排班)

Topic Overview 5.1 基本觀念 (Basic Concepts) 5.2 排班準則 (Scheduling Criteria) 5.3 排班演算法 (Scheduling Algorithms) 5.4 演算法的評估 (Algorithm Evaluation) W.-S. Hsu 2011

5.1 基本觀念 (Basic Concept) 多元程式規劃作業系統 (multiprogrammed OS) 主要目的： 概念： 隨時保有一個 process 在CPU內執行，藉以提高 CPU 使用率。 概念： 一個行程一直執行到它必須等待某一事件 (通常是I/O要求)結束後，在此等待的時候，CPU是閒置的，而多元程式規劃系統 下，此時可以讓其他 process 使用 CPU time，以充份應用CPU。 CPU 排班 (short-term scheduler) 是多元程式規劃作業系統的基礎。 W.-S. Hsu 2011

排班的種類 CPU scheduler 本章的主題 5.1 基本觀念 (Cont.) job queue ready queue  short-term scheduler  long-term scheduler swap space  medium-term scheduler swap-in/swap-out W.-S. Hsu 2011

5.1 基本觀念 (Cont.) 排班的種類 (Cont.) 長程排班 選擇載入 main memory 的 process，藉以控制記憶體中的行程數目(多元程式規劃系統的程度)。 中程排班 Swapping In/Out 的選擇。 短程排班 選擇從 memory 內的 process 在處理機上執行(CPU Scheduler)。 I/O排班 選擇哪一個 process的I/O請求將被I/O裝置處理。 三種排班種類發生的頻率：短程 > 中程 > 長程 W.-S. Hsu 2011

Process排班與process狀態轉換 5.1 基本觀念 (Cont.) Process排班與process狀態轉換 Process排班的Queue圖 結束 新建  CPU排班 長程排班 就緒 執行 swap space 等待  中程排班 job queue ready queue CPU waiting queues W.-S. Hsu 2011

5.1.1 CPU - I/O分割週期 (burst cycle) CPU burst 行程執行一連串CPU動作 I/O burst 行程等待I/O動作 行程的運作 行程的執行是由CPU執行時間及I/O等待時間所組成的週期 (cycle)。行程在這兩個狀態之間交替往返。 行程執行由一個CPU分割 (CPU burst) 開始。跟著是一個I/O分割 (1/O burst)，然後再由另外一個CPU分割跟著，再來又是另一個I/O分割。 W.-S. Hsu 2011

5.1.1 CPU - I/O分割週期 (burst cycle) CPU-I/O bound CPU bound 行程有一些非常長的CPU burst I/O bound 行程有很多很短的CPU burst CPU排班 CPU-I/O bound行程的分佈，對於選擇CPU排班演算法是項非常重要的資料 W.-S. Hsu 2011

5.1.2 CPU排班程式 (CPU scheduler) 使用時機 在多processes的環境下，當CPU閒置時，OS必須從ready queue中選擇一個process進入CPU內執行其工作。此即OS中CPU scheduler (短程排班程式) 的工作 Ready queue 內含所有processes皆排隊以等待機會來執行(使用) CPU 將processes的PCBs，串接在一起 Ready queue的類型： FIFO queue 優先次序queue 樹狀結構queue 無順序關係的linked-list queue W.-S. Hsu 2011

5.1.3 可剝奪式排班 (Preemptive Scheduling) 意義 當一個行程正在CPU內執行時，可以被中斷，以讓其他process使用CPU時間的排班方法 不可剝奪式CPU排班： 一旦CPU被配置一個process時，此process一直保有CPU，直到它以終止或轉換到等待狀態的方式釋放出CPU為止 何時會使用到CPU排班之決策 ?     W.-S. Hsu 2011

分派程式 意義 功能 Dispatch latency (分派延遲) 5.1.4 分派程式 (Dispatcher) 分派程式 意義 將CPU控制權交予CPU Scheduler所選出的行程所使用的模組程式 功能 Context switch (內容轉換) 將系統轉換成使用者模式 (user mode) 跳越至使用者程式的適當位置以重新執行程式 Dispatch latency (分派延遲) Dispatcher 用來停止一個行程，並開始另一行程所花費的時間 W.-S. Hsu 2011

5.2 排班原則 (Scheduling Criteria) CPU排班法則的評估準則： CPU使用率 (utilization)：CPU忙碌所占時間的百分比(40% ~ 90%)。 產能 (throughput)：單位時間內所完成的process數。 回復時間 (turnaround time)：從一個process進入電腦，一直到該process完成離開所花費的時間。 等待時間 (waiting time)：一個process在ready queue中所等待的時間 反應時間 (response time)：在交談式系統中，強調的是『一個process提出要求至第一個反應出現的間隔時間』。 W.-S. Hsu 2011

5.3 排班演算法 (Scheduling Algorithms) 先來先做 (First-Come_First-Served, FCFS) 將CPU分配給第一個要求CPU的行程 使用 FIFO 佇列來執行此工作 範例 Gantt Chart (甘特圖) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 Time 3 P1 W.-S. Hsu 2011

先來先做 (Cont.) Gantt Chart (甘特圖) P1 P2 P3 P4 P5 5.3.1 FCFS 先來先做 (Cont.) Gantt Chart (甘特圖) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 Time 6 8 4 2 P1 3 9 P2 13 P3 18 P4 20 P5 P1 P2 P3 P4 平均等待時間 = (0+1+5+7+10) /5 = 4.6 P5 W.-S. Hsu 2011

先來先做 (Cont.) 練習1 練習2 5.3.1 FCFS (Cont.) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 24 P2 2 3 P3 4 行程 到達ready queue時間 需要CPU時間-Burst Time P1 4 24 P2 3 P3 2 W.-S. Hsu 2011

先來先做 (Cont.) FCFS 結論 平均等待時間並非最小 可能隨 CPU burst-time 之極大變化而差異甚大 5.3.1 FCFS (Cont.) 先來先做 (Cont.) FCFS 結論 平均等待時間並非最小 可能隨 CPU burst-time 之極大變化而差異甚大 可能產生 convoy effect (護送現象，當所有的 processes 都在等待某一個CPU bound的行程之結束時，形成CPU與I/O裝置使用率的降低) 不可剝奪演算法 不適用分時系統 W.-S. Hsu 2011

最短的工作先做 (Shortest-Job-First, SJF) 最短的工作先做。若有兩個行程具有相同的長度，則採用FCFS的方法 最短的下一個 CPU Burst 先做。藉著檢查每個 process 的下一個CPU burst 來作決策 範例 Gantt Chart (甘特圖) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 W.-S. Hsu 2011

最短的工作先做 (Cont.) Gantt Chart (甘特圖) P1 P2 P5 P3 P4 5.3.2 SJF (Cont.) 最短的工作先做 (Cont.) Gantt Chart (甘特圖) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 Time 6 8 4 2 P1 3 9 P2 11 P5 15 P3 20 P4 P1 P2 P3 P4 平均等待時間 = (0+1+7+9+1) /5 = 3.6 P5 W.-S. Hsu 2011

最短的工作先做 (Cont.) 練習1 SJF 結論 可得到最小平均等待時間 困難之處：如何得知下一個CPU要求的時間。 5.3.2 SJF (Cont.) 最短的工作先做 (Cont.) 練習1 SJF 結論 可得到最小平均等待時間 困難之處：如何得知下一個CPU要求的時間。 SJF 經常用在長程排班問題上；但不能用在解決短程(CPU) 排班的問題問題 (無法預知下一個 CPU burst 的長度) 預估下一個 CPU burst 的長度： 利用前幾次 CPU bursts 所測得的值的指數平均數 n+1= tn + (1) n 不可剝奪演算法 長CPU-burst 的 process 可能餓死 (starvation) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 6 P2 9 P3 W.-S. Hsu 2011

最短剩餘時間的工作先做 (Shortest-Remaining-Time First) 5.3.2.1 SRTF 最短剩餘時間的工作先做 (Shortest-Remaining-Time First) 選擇預計最短還需執行CPU時間的行程 當新加一個process進入ready queue時，它可能比正在執行的process所需的時間還短，因此，任何一個process加入到ready queue中，scheduler就會進行剝奪的操作 範例 Gantt Chart (甘特圖) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 W.-S. Hsu 2011

最短剩餘時間的工作先做 (Cont.) Gantt Chart (甘特圖) P5 P2 P4 P1 P3 P3 平均等待時間 = 5.3.2.1 SRTF (Cont.) 最短剩餘時間的工作先做 (Cont.) Gantt Chart (甘特圖) 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 Time 4 8 6 2 3 P1 10 P5 P2 15 20 P4 Remainder time P1 3  1  0 P2 6  5  0 P3 4  2  0 P4 5  0 P5 2  0 P1 P2 P3 P3 P1 P2 P3 P4 平均等待時間 = [(0)+((3-2)+(10-4))+(0)+(15-6)+0] /5 = 3 P5 W.-S. Hsu 2011

最短剩餘時間的工作先做 (Cont.) SRTF 結論 可剝奪演算法 長CPU-burst的process可能餓死 (starvation) 5.3.2.1 SRTF (Cont.) 最短剩餘時間的工作先做 (Cont.) SRTF 結論 可剝奪演算法 長CPU-burst的process可能餓死 (starvation) 已經服務的時間必須記錄下來 (額外的開銷) SRTF 比 SJF 提供較好的 response time 性能 W.-S. Hsu 2011

優先權 (Priority) SJF是一般優先權排班演算法的一個特例 每個 process 給予一個優先順序權 (固定範圍的數字)，CPU scheduler 在ready queue中選擇一個priority最高的process來執行；而相等priority的processes則採用FCFS來排班 範例： 假設各 processes 到達 ready queue 時間為0且依序到達，且低數值的優先次序高 行程 需要CPU時間-Burst Time 優先順序值 P1 10 3 P2 1 P3 2 P4 4 P5 5 W.-S. Hsu 2011

優先權 (Cont.) Gantt Chart (甘特圖) 平均等待時間 = (6+0+16+18+1) /5 = 8.2 P2 P5 P1 行程 需要CPU時間-Burst Time 優先順序值 P1 10 3 P2 1 P3 2 P4 4 P5 5 Time 1 P2 6 P5 16 P1 P3 18 19 P4 平均等待時間 = (6+0+16+18+1) /5 = 8.2 W.-S. Hsu 2011

優先權 (Cont.) Priority 結論： 可/不可剝奪演算法 優先權可由外部或內部定義 內部得出優先權：使用一些可以測得的量值來定義一個process 的 priority。如時間限制、記憶體需求、平均 I/O burst 與 CPU burst 的比率來計算優先權 外部得出優先權：由 OS 外部的標準所決定。如 process 的重要性 最大問題：indefinite blocking 或 starvation 預防 低priority 行程被無限期擱置的方法─ 老化 (aging) (將停留在系統中一段時間的 process 予以提高其優先權) W.-S. Hsu 2011

5.3.4 循環 (Round-Robin, RR) 循環 (Round-Robin, RR) CPU在一個單位時間 (time slice) 後，即在ready queue (環狀queue、FIFO佇列) 轉換給下一個process。此法設定一個 timer 以中斷CPU的執行並轉換process 主要針對 Time-Sharing 的系統所設計 Time-slice 的選擇可能對於系統的效益有著深遠的影響 範例：假設 time-slice = 4 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 W.-S. Hsu 2011

循環 (Cont.) Gantt Chart (甘特圖)  time-slice = 4 P1 P2 P3 P4 P5 P2 5.3.4 RR (Cont.) 循環 (Cont.) Gantt Chart (甘特圖)  time-slice = 4 行程 到達ready queue時間 需要CPU時間-Burst Time P1 3 P2 2 6 P3 4 P4 5 P5 8 Time 4 8 6 2 P1 3 P2 7 P3 11 P4 15 P5 17 P2 19 P4 20 Remainder time P1 3  0 P2 6  2  P3 4  0 P4 5  1 P5 2  P1 P2 P3 P4 平均等待時間 = [(0)+((3-2)+(17-7))+(7-4)+((11-6)+(19-15))+(15-8)] /5 = 6 P5 W.-S. Hsu 2011

5.3.4 RR (Cont.) 循環 (Cont.) RR 結論 可剝奪演算法。 Round-Robin 的效能完全取決於時間量的長短。當 time-slice 無限大時，此法與 FCFS 排班演算法則一樣。而當 slice 極小時 (1微秒)，此法則稱為「處理機共用 (processor sharing，n行程各自擁有1/n個processor的專用處理機)」法則。 Time slice 的大小需考慮 context switch 的時間 (time-slice > context switch)。Time slice 愈短，則 context switch 的負擔越重。 Time slice 的大小也需考慮 turnaround time 的時間 (80%的程式CPU執行時段應小於 time-slice 的大小) W.-S. Hsu 2011

5.3.4 RR (Cont.) 循環 (Cont.) RR 結論 (Cont.) W.-S. Hsu 2011

5.3.5 多層佇列 (Multilevel Queue) 依據 processes 的性質將其分成幾個不同的群組。 Foreground-交談式processes；Background-整批作業processes 前景行程的優先次序應高於背景行程。 將 ready queue 區分成多個 priority 不同的獨立 queues。行程依其特定性質被固定指到某個queue中。 每個獨立佇列可依本身需求或性質，而可採用不同的排班法則。 而這些獨立 queues 間，仍需要一個排班法則。 採用固定的 queue priority 順序的方法。 分配每個 queue 一個固定的CPU時間。 W.-S. Hsu 2011

5.3.5 多層佇列 (Cont.) 多層佇列 (Cont.) W.-S. Hsu 2011

5.3.6 多層回饋佇列 (Multilevel Feedback Queue) 允許 process 在各獨立 queues 間移動 W.-S. Hsu 2011

5.4 演算法的評估 (Algorithm Evaluation) 如何為系統選擇一個 CPU Scheduler ? 標準：CPU 使用率、turnaround time、throughput等 使用各種的評估法： 定量模式 (Deterministic modeling) 佇列模式 (Queuing models) 模擬 (Simulations) 實作 (Implementation) W.-S. Hsu 2011

5.4.1 定量模式 (Deterministic modeling) 使用排班演算法和系統工作量來產生一個公式或數字 (如：平均等待時間) 以評估在那個工作量下該演算法的性能 例子： 假設底下五個 processes 都在時間0時到達，其順序如下，而 CPU burst time 以毫秒為單位 考慮 FCFS、SJF、RR (time slice=10毫秒) 等排班演算法用在這組行程上，試問哪一個演算法的平均等待時間最小 ? 行程 需要的CPU時間 (ms) P1 10 P2 29 P3 3 P4 7 P5 12 FCFS: 28 ms SJF: 13 ms RR: 23 ms W.-S. Hsu 2011

佇列模式 (Queuing models) 描述某個 CPU burst 之機率的數學公式 估算 CPU分割 和 I/O分割 的分佈情形 李特公式 (Little’s formula)： =     = 平均佇列長度  = 佇列中新行程到平均到達比率  = 佇列中的平均等待時間 W.-S. Hsu 2011

5.4.3-4 模擬 (Simulations) & 實作 (Implementation) 設計一套電腦系統模型 Random 產生 processes 的到達時間、離開時間、CPU burst time 和 I/O burst time，並評估各演算法的性能 實作 (Implementation) 將演算法實際撰寫程式並放入 OS 中，並觀察其效能 圖 5.8 W.-S. Hsu 2011

End of Chapter 5 W.-S. Hsu 2011

問題與討論 1.用FCFS、SJF及RR(time-slice=2) 求等待時間及回復時間 W.-S. Hsu 2011