CPU Scheduling

• CPU 排程簡介
• Decision Mode
• Dispatcher
• Scheduling Criteria
• Starvation
• Scheduling Algorithms

在 Process 章節，我們提到系統中包含 Long-term, Short-term, Medium-term 等多種排程

在本章節，我們會針對 Short-term Scheduling，也就是 CPU Scheduling 詳細說明

作業系統採用 multiprogramming 方法得到 CPU 最大使用率，一般 process 一開始都是 CPU Burst，交由 CPU 去處理該 process，接著是 I/O Burst，做 I/O 資料的傳送。在正常的狀況下，process 就在這兩個狀態間一直循環，最後會呼叫一個終止行程執行的 system call 作為行程的結束

排成進行的時機是由 Decision Mode 決定的，一般分為 Non-preemptive 與 Preemptive 兩種

進行 CPU scheduling 的可能時機有下列四種:

1. 當一個 process 的狀態由 running 轉為 waiting 時
2. 當一個 process 的狀態由 running 轉為 ready 時 e.g. time sharing 因為 timeout 回到 ready
3. 當一個 process 的狀態由 waiting 轉為 ready 時
4. 當一個 process 的狀態由 running 轉為 terminate 時

Non-preemptive:

Non-preemptive 不可搶奪型，又稱 cooperative scheduling 合作式排程

• 一個 Process 除非自行放棄 CPU 的使用權，否則其他 Processes 不能奪取其 CPU 使用權
  • process 等待 I/O, semaphore wait
  • process terminates
• Non-preemptive scheduling 只可能發生在上面的 1. 4. 兩個時機點

Preemptive:

Preemptive 可搶奪型

• 不論正在執行的 process 是否可繼續執行，必要時 CPU 使用權可能被搶奪
• Preemptive scheduling 在上述的四個時間點皆會發生
• 適用於 real-time system, time sharing system
• context switch 次數較多，overhead 較大

分派程式 Dispatcher 主要負責將 CPU 控制權交給經由 CPU Scheduling 所挑選出來的 process

主要工作有三:

• Context switch
• Change to user mode from monitor mode
• Jumping to the proper location in the user program to restart that program

Dispatch Latency 是指 Dispatcher 停止一個 process 並開始另一個 process 所耗的時間，這個時間越短越好

衡量排班效能的準則:

• CPU utilization: CPU 花在 process 執行的時間
• Throughput: 單位時間內完成的 process 數目
• Waiting time: process 待在 ready queue 等待獲取 CPU 的時間總和
• Turnaround time: 一個 process 進入系統，到其完成工作的這段時間
• Response time: 自 user 下命令進入系統，到系統產生第一個回應的時間

Starvation 飢餓現象: 某些 process 因長期無法取得足夠資源來完成工作，造成自身無窮停滯的情況 (Infinite Blocking)

解決方式: Aging Technique (老化技術)

系統每隔一段時間，便將待在系統內時間很長卻未完成工作的 process 逐步提高其 priority value

Soft Real-Time system 不採用

First Come First Served Scheduling, FCFS

Arrival time 越早的 process 越優先取得 CPU 控制權

• 易於實作
• 排班效益最差，Average waiting time, Average turnaround time 最長
• 會有 Convoy Effect (護衛現象)
  • 多個 process 均在等待一個需要很長時間 CPU Time 來完成工作的 process，造成平均等待時間大幅增加
• 公平排班演算法
• No Starvation
• Non-preemptive

Shortest Job First Scheduling, SJF

Process 的 CPU Burst Time 越少，越優先取得 CPU 控制權

• 排班效益最佳
• 不會有 Convoy Effect
• 不公平的排班演算法
• 可能 Starvation
• Non-preemptive

Shortest Remaining Time First Scheduling, SRTF

Process 的 Remaining Time 越小，越優先取得 CPU 控制權

• Preemptive
• Context Switch 次數多
• 不公平的排班演算法
• 可能 Starvation

Priority Scheduling

Process 的 優先權越高，越優先取得 CPU 控制權

• 不公平的排班演算法
• 可能 Starvation
• 可以是 Preemptive 或 Non-preemptive

Round Robin Scheduling

作業系統會規定一個 CPU Time Slice (Time Quantum)，當 process 獲取 CPU 執行，若未能在 CPU Time Slice 內完成，則 process 會被迫放棄 CPU，狀態從 Running → Ready，等候下一輪 CPU 使用權

• 公平的排班演算法
• No Starvation
• Preemptive
• 適用於 Time-Sharing System