• 進程執行的過程是一個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）

CPU調度發生時機概括圖

  • 不可搶佔調度（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的長度。所以我們只能預測這個長度。

用來預測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.

multilevel feedback queue例子

推薦閱讀：

相关文章