CPU調度

• 進程執行的過程是一個CPU執行和等待I/O的cycle
• 一個進程在執行I/O操作的時候，另外一個進程可以開始用CPU
• CPU-bound：多數時間執行計算，比較少地執行I/O操作；它可能有很多很長的CPU burst
• I/O-bound：執行I/O操作的時間多於執行計算的時間；它由很多很短的CPU burst
• CPU空閑的時候，操作系統要選擇一個進程去執行；做出這個選擇的是短期調度器（short-term scheduler）也叫作CPU調度器（CPU scheduler）。
• CPU調度器從ready queue裡面選擇一個進程執行，給它分配CPU
• 一共有以下4種情況可以進行調度：

1. 進程從running變成waiting（等待I/O或者event）
2. 進程從running變成ready（發生了中斷）
3. 進程從waiting變成ready（I/O或者event完成）
4. 進程結束（從running變成terminated）

• 不可搶佔調度（Non-preemptive scheduling）：發生在進程從running進入waiting或者從running進入terminated的時候。比較簡單，但是效率不高。
• 可搶佔調度（Preemptive scheduling）：可以發生在上面的任意一個情況下。但是這對kernel的要求很高。
• 分配器將CPU交給被調度到的進程，包括了：
• 上下文切換
• 切換到用戶態（說明調度發生在核心態）
• 跳到用戶程序的某個位置以重新啟動程序
• dispatch latency：dispatcher停止一個進程且啟動另一個進程的所需時間
• 調度標準：
• CPU利用率：儘可能大
• 吞吐量（Throughput）：定義是number of processes completed per time unit；也是要儘可能大
• 周轉時間（Turnaround Time）：Turnaround Time = Waiting time before entering the system + Waiting time in the ready queue + Waiting time in all events + Executing Time on the CPU
• 等待時間（Waiting Time）：進程在ready queue裡面的時間；CPU調度演算法只會影響進程在ready queue的時間
• 響應時間（Response Time）：從申請提交到第一次響應的時間，不包括output這個響應的時間
• FCFS（First-Come, First-Served）：
• 先提出申請的進程先執行
• FCFS是不可搶佔的
• 會有護航效應（Convoy Effect）：時間短的進程可能會待在時間長的進程的後面，導致平均等待時間變長，也可能會導致CPU利用率不高
• SJF（Shortest-Job-First）：
• 當在ready queue裡面選擇進程的時候，next CPU burst越短的進程越先執行
• 在ready queue內的進程是按照CPU burst的長度排序的
• 不可搶佔版本：只要進程在CPU中執行了，那麼就要一直等它執行完
• 可搶佔版本：如果一個新的進程進入ready queue了，且它的CPU burst長度比當前在執行的進程的剩餘CPU burst長度要短，那麼就搶佔當前的進程。（這也被稱為SRTF（Shortest-Remaining-Time-First））
• SJF是最優的：對於一堆給定的進程集合來說， 它有著最短的平均等待時間
• 如何正面SJF是最優的呢？因為當我們把一個短進程放在一個長進程的前面，我們就能減少平均等待時間。我們可以將進程集合調成成有序的。
• 但是問題是，我們不能知道next CPU burst的長度。所以我們只能預測這個長度。

• SJF調度演算法也有問題：
• next CPU burst難以預測准
• 因為SJF總是選擇短的進程，所以長進程可能就沒機會運行。這個問題也被稱作Starvation（餓死）。
• Priority Scheduling（優先順序調度演算法）：
• 每個進程都被賦予一個優先順序
• 優先順序可以被內部決定或者外部決定：
• 內部的優先順序：time limit, memory requirement等等
• 外部的優先順序：不由操作系統控制（進程的重要性）
• 調度器每次從ready queue中選擇最高優先順序的進程
• FCFS和SJF可以被看作是優先順序調度演算法的特例
• 也有可搶佔版本和不可搶佔版本
• Indefinite block(or starvation) may occur
• 解決starvation的辦法：Aging：逐漸提高等待在系統中的進程的優先順序
• RR（Round Robin）：
• RR和FCFS很像，但是每個進程會被分配給一個time quantum
• 在ready queue中的進程是FIFO
• CPU空閑的時候，調度器選擇第一個進程，分配給它一個time quantum
• 如果執行完了，那麼就把它放在tail
• 同樣的，如果time quantum用完，也把它放在tail，調度器分配下一個進程
• 如果time quantum非常大，那麼RR就變成了FCFS
• 如果time quantum非常小，那麼RR就變成了processor sharing
• 上下文切換時間會影響RR的performance
• time quantum短意味著上下文切換的次數多
• 80%的CPU burst要比time quantum短
• 一般來說，它與SJF相比有著更長的平均周轉時間，但是有更好的響應性
• Multilevel Queue：
• ready queue被分成兩個單獨的隊列：foreground和background
• 每個進程（permanently）被分配給一個隊列（基於這個進程的各個特性）
• foreground: RR; background: FCFS
• 每個隊列有不同的優先順序。一個進程能被運行只有在它之上（優先順序比它高）的那些隊列都為空。
• 如果一個進程在運行，同時在比它所處的隊列優先順序更高的隊列中有進程到來了，那麼這個運行中的進程就被搶佔了。
• 調度是在隊列之間進行的。
• 如果規定先執行foreground再執行background，那麼可能會starvation
• 可以規定time slice，就是每個隊列被給予一定量的CPU time（比如給80% foreground, 20% background）
• Multilevel Feedback Queue：
• 跟multilevel queue很像，但是可以允許進程在隊列間切換
• If a process uses more CPU time, it is moved to a queue of lower priority.
• I/O-bound processes will be in higher priority queues.
• CPU-bound processes will be in lower priority queues.

推薦閱讀：