目錄

• 1 CPU調(diào)度基本概念
• • 1.1 基本概念
  • 1.2 CPU調(diào)度的時機
  • 1.3 CPU調(diào)度方案
• 2 CPU調(diào)度算法
• • 2.1 先來先服務(FCFS)
  • 2.2 短作業(yè)優(yōu)先(SJF)
  • 2.3 優(yōu)先級
  • 2.4 RR時間片輪轉(zhuǎn)
  • 2.5 多級隊列和多級反饋隊列

1 CPU調(diào)度基本概念

1.1 基本概念

CPU調(diào)度就是就從就緒隊列中選擇一個進程來分配CPU的過程，進行CPU調(diào)度的原因是為了實現(xiàn)多道，使得CPU有更高的利用率，之所以進程能夠進行CPU調(diào)度是因為進程的特點，進程執(zhí)行過程中分為兩個脈沖一個是CPU脈沖 (CPU Burst)，一個是 I/O 脈沖 (I/O Burst)，即在 CPU 上執(zhí)行和等待 I/O ，進程的執(zhí)行以 CPU 脈沖開始，其后跟著 I/O 脈沖，進程的執(zhí)行就是在這兩個狀態(tài)之間進行轉(zhuǎn)換，如下圖所示：

觀察CPU脈沖的統(tǒng)計后發(fā)現(xiàn)，CPU 脈沖的分布，在系統(tǒng)中存在許多短 CPU 脈沖，只有少量的長 CPU 脈沖，比如 I/O 型作業(yè)具有許多短 CPU 脈沖，而 CPU 型作業(yè)則會有幾個長 CPU 脈沖，這個分布規(guī)律對CPU 調(diào)度算法的選擇是非常重要的，下圖是對CPU脈沖的統(tǒng)計直方圖，橫軸是時間，豎軸是頻率，可以發(fā)現(xiàn)頻率在0~8ms的高頻脈沖是比較多的：

1.2 CPU調(diào)度的時機

當CPU空閑時，OS就選擇內(nèi)存中的某個就緒進程，并給其分配CPU，以下是進程狀態(tài)轉(zhuǎn)換圖，當某個進程從running狀態(tài)離開時，就代表當前CPU就空閑了，圖中紅色和藍色的箭頭都代表著會發(fā)生CPU調(diào)度：

CPU的調(diào)度可能發(fā)生在以下情況：

• 從運行轉(zhuǎn)到等待 (Switches from running to waiting state)：非搶占式調(diào)度；
• 從運行轉(zhuǎn)到就緒 (Switches from running to ready state)：搶占式調(diào)度，時間片到；
• 從等待轉(zhuǎn)到就緒 (Switches from waiting to ready)：搶占式調(diào)度，若某個在就緒隊列的進程優(yōu)先級較高，則會搶占CPU，所以是搶占式調(diào)度；
• 終止運行 (Terminates)：非搶占式調(diào)度。

1.3 CPU調(diào)度方案

CPU調(diào)度方案分為以下兩種：

• 非搶占方式 (nonpreemptive)：把處理機分配給某進程后，便讓其一直執(zhí)行，直到該進程完成或發(fā)生某事件而被阻塞時，才把處理機分配給其它進程，不允許其他進程搶占已經(jīng)分配出去的處理機，其優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)環(huán)境，缺點是難以滿足緊急任務的要求，不適用于實時、分時系統(tǒng)要求
• 搶占方式（Preemptive mode）：允許調(diào)度程序根據(jù)某個原則，去停止某個正在執(zhí)行的進程，將處理機重新分配給另一個進程

對于搶占方式，搶占有如下的原則：

• 時間片原則：各進程按時間片運行，當一個時間片用完后，便停止該進程的執(zhí)行而重新進行調(diào)度。這個原則適用于分時系統(tǒng)；
• 優(yōu)先權(quán)原則：通常對一些重要的和緊急的進程賦予較高的優(yōu)先權(quán)。當這種進程進入就緒隊列時，如果其優(yōu)先權(quán)比正在執(zhí)行的進程優(yōu)先權(quán)高，便停止正在執(zhí)行的進程，將處理機分配給優(yōu)先權(quán)高的進程，使之執(zhí)行；
• 短作業(yè)優(yōu)先原則：當新到達的作業(yè)比正在執(zhí)行的作業(yè)明顯短時，將暫停當前長作業(yè)的執(zhí)行，將處理機分配給新到的短作業(yè)，使之執(zhí)行。

2 CPU調(diào)度算法

設計CPU調(diào)度算法的性能指標有如下幾點：

• CPU利用率：使CPU盡可能的忙碌；
• 吞吐量：單位時間內(nèi)運行完的進程數(shù)；
• 周轉(zhuǎn)時間：進程從提交到運行結(jié)束的全部時間 ；
• 等待時間：進程在就緒隊列中等待調(diào)度的時間片總和；
• 響應時間 ：從進程提出請求到首次被響應的時間段，在分時系統(tǒng)環(huán)境下不是輸出完結(jié)果的時間

注：調(diào)度算法影響的是等待時間 ， 而不能影響進程真正使用CPU 的時間和 I/O 時間

2.1 先來先服務(FCFS)

先來先服務 (First-Come-First-Served)，其算法思想和字面意思一樣，就是先到來的進程，先被調(diào)度，這是最簡單的調(diào)度算法，FCFS屬于非搶占方式，一旦一個進程占有處理機，它就一直運行下去，直到該進程完成或者因等待某事件而不能繼續(xù)運行時才釋放處理機。FCFS 算法易于實現(xiàn)，表面上很公平 ，實際上有利于長作業(yè)，不利于短作業(yè)；有利于 CPU 繁忙型，不利于 I/O 繁忙型，可以看下面的例子。

假設有 $P_1$，$P_2$，$P_3$ 三個進程，所需的CPU脈沖時間分別為24，3，3，如下表：

進程CPU脈沖時間

$P_1$	24
$P_2$	3
$P_3$	3

現(xiàn)設三個進程到來的順序是 $P_1$，$P_2$，$P_3$，那么該調(diào)度的Gantt圖如下：

各個進程的等待時間如下表：

進程等待時間

$P_1$	0
$P_2$	24
$P_3$	27

平均等待時間為 $t=\frac{0+24+27}{3}=17$。

現(xiàn)假設三個進程到來的順序是 $P_2$，$P_3$，$P_1$，那么該調(diào)度的Gantt圖如下：

各進程的等待時間如下表：

進程等待時間

$P_1$	6
$P_2$	0
$P_3$	3

平均等待時間為 $t=\frac{6+0+3}{3}=3$。

由上面兩個例子可以看出，在先來先服務算法中，進程到來的次序?qū)ζ骄却龝r間的影響是很大的，這里有個專業(yè)名詞叫做 護航效應 (Convoy effect)

護航效應 (Convoy effect)：

• 假設有一個CPU進程和許多I/O型進程
• 當CPU進程占用CPU運行時， I/O型進程可能完成了其I/O操作，回到就緒隊列等待CPU， I/O設備空閑
• CPU進程釋放CPU后， I/O型進程陸續(xù)使用CPU，并很快轉(zhuǎn)為I/O操作，CPU空閑

在這種情況下，CPU和 I/O 設備并沒有得到有效的利用。

2.2 短作業(yè)優(yōu)先(SJF)

短作業(yè)優(yōu)先 (Shortest-Job-First)，其算法思想是關聯(lián)到每個進程下次運行的 CPU 脈沖長度，調(diào)度最短的進程，由于進程是不斷調(diào)入到就緒隊列中的，其整個就緒隊列中的最短作業(yè)，也是動態(tài)變化的，此時就要面臨一個問題了，若現(xiàn)在到來了一個所需CPU脈沖時間最短的一個進程，那么是讓當前執(zhí)行的進程讓位，還是等當前進程執(zhí)行完再執(zhí)行，所以有如下兩種策略：

• 非搶占式調(diào)度：一旦進程擁有 CPU ， 它的使用權(quán)限只能在該 CPU 脈沖結(jié)束后讓出；
• 搶占式調(diào)度 ：發(fā)生在有比當前進程剩余時間片更短的進程到達時，也稱為最短剩余時間優(yōu)先調(diào)度

短作業(yè)優(yōu)先SJF算法是最優(yōu)的，因為對一組指定的進程而言，它給出了最短的平均等待時間，如下面的例子：

現(xiàn)有四個進程 $P_1$，$P_2$，$P_3$，$P_4$，他們的到達時間和所需CPU脈沖時間如下表：

進程到達時間CPU脈沖時間

$P_1$	0	7
$P_2$	2	4
$P_3$	4	1
$P_4$	5	4

若采用搶占式的調(diào)度，其調(diào)度Gantt圖如下：

平均等待時間為 $t=\frac{9+1+0+2}{4}=3$。

若采用非搶占式的調(diào)度，其調(diào)度Gantt圖如下：

平均等待時間為 $t=\frac{0+6+3+7}{4}=4$。

---

雖說短作業(yè)優(yōu)先算法是最優(yōu)的算法，但是實際上在實現(xiàn)起來確實很難的，因為要不斷的統(tǒng)計各個進程所需的CPU脈沖時間，這顯然實現(xiàn)難度高，就算能實現(xiàn)，其開銷也會非常大，所以實際應用中是估計進程所需時間，可以通過先前的CPU脈沖長度及計算指數(shù)均值進行估計。

綜上所述，采用SJF有利于系統(tǒng)減少平均周轉(zhuǎn)時間,提高系統(tǒng)吞吐量，一般情況下SJF調(diào)度算法比FCFS調(diào)度算法的效率要高一些, 但實現(xiàn)相對要困難些。如果作業(yè)的到來順序及運行時間不合適，會出現(xiàn)饑餓現(xiàn)象，例如，系統(tǒng)中有一個運行時間很長的作業(yè)JN，和幾個運行時間小的作業(yè)，然后，不斷地有運行時間小于JN的作業(yè)的到來，這樣，作業(yè)JN就因得不到調(diào)度而餓死。另外，作業(yè)運行的估計時間也有問題。

2.3 優(yōu)先級

上面所講的短作業(yè)優(yōu)先算法實際上是優(yōu)先級算法的一個特例，短作業(yè)優(yōu)先算法將作業(yè)所需時間定為衡量優(yōu)先級的量，表示優(yōu)先級的量一般為一個整數(shù)，這里假定越小的數(shù)優(yōu)先級越高，下面 $P_1$，$P_2$，$P_3$，$P_4$，$P_5$ 五個進程的調(diào)度狀況如下：

進程CPU脈沖時間優(yōu)先級

$P_1$	10	3
$P_2$	1	1
$P_3$	2	4
$P_4$	1	5
$P_5$	5	2

根據(jù)優(yōu)先級，其調(diào)度順序為 $P_2$，$P_5$，$P_1$，$P_3$，$P_4$，平均等待時間為 8.2 。

那么進程的優(yōu)先級如何確定呢？通常在進程創(chuàng)建時確定，且在整個生命期中保持不變，這種叫靜態(tài)優(yōu)先級，靜態(tài)優(yōu)先級就會出現(xiàn)饑餓問題，即某個進程若優(yōu)先級非常低，它幾乎永遠得不到CPU調(diào)度。

一個很有意思的例子：當MIT的IBM7094機器于1973年關掉時，人們發(fā)現(xiàn)一個于1967年提交的一個低優(yōu)先權(quán)的進程還沒有得到運行。

解決方法是老化，根據(jù)進程等待時間的延長提高其優(yōu)先數(shù)，也就是動態(tài)優(yōu)先級，優(yōu)先級會根據(jù)等待時間不斷調(diào)整。考慮改變優(yōu)先級的因素通常有進程的等待時間，已使用CPU的時間，資源使用情況等。

2.4 RR時間片輪轉(zhuǎn)

RR (Round Robin)，這個算法主要用在分時系統(tǒng)里，這個算法的思想是每個進程將得到小單位的 CPU 時間 (時間片)，通常為 10-100 毫秒 。時間片用完后，該進程將被搶占并插入就緒隊列末尾。

例如有四個進程 $P_1$，$P_2$，$P_3$，$P_4$ 如下表，設時間片大小為 20：

進程CPU脈沖時間

$P_1$	53
$P_2$	17
$P_3$	68
$P_4$	24

其調(diào)度Gantt圖如下：

一般來說，RR的平均周轉(zhuǎn)時間比SJF長，但響應時間要短一些。

對于時間片輪轉(zhuǎn)算法，確定時間片大小是非常重要的，若時間片過大，則每個進程都能在單個時間片能完成，則時間片輪轉(zhuǎn)等價于先來先服務算法，若時間片過小，則各個進程要頻繁的切換，造成大量的資源開銷。

2.5 多級隊列和多級反饋隊列

多級隊列的意思是把進程根據(jù)其某種屬性進行分類，每一類的進程都會組成一個就緒隊列，也就是說在操作系統(tǒng)中會有多個就緒隊列，每個進程固定的處在自己所屬的隊列中，對于不同的隊列，也可以有自己專屬的調(diào)度算法，那么此時就要進行隊列的調(diào)度，可以給每個隊列設置不同的優(yōu)先級，若是固定優(yōu)先級，則會產(chǎn)生饑餓問題。那么另一種解決方案就是基于時間片的算法，給定 時間片調(diào)度，即個隊列得到一定的 CPU 時間，進程在給定時間內(nèi)執(zhí)行，如下圖：

若某個進程在一個優(yōu)先級較低的隊列中，那么它就會一直處于饑餓狀態(tài)，解決方案是多級反饋隊列調(diào)度，存在多個就緒隊列，具有不同的優(yōu)先級，各自按時間片輪轉(zhuǎn)法調(diào)度，它與多級隊列的不同是它允許進程在隊列之間移動，當一個進程執(zhí)行完一個完整的時間片后被搶占處理器，被搶占的進程優(yōu)先級降低一級而進入下級就緒隊列，如此繼續(xù)，直至降到進程的基本優(yōu)先級。而一個進程從阻塞態(tài)變?yōu)榫途w態(tài)時要提高優(yōu)先級，最后會將I/O型和交互式進程留在較高優(yōu)先級隊列，如下圖：

總結(jié)

以上是生活随笔為你收集整理的操作系统原理第五章：CPU调度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。