目錄

一、處理機調度概述

1.基本準則

（1）CPU利用率

（2）系統吞吐量?

（3）周轉時間

（4）等待時間

（5）響應時間

2.進程調度方式

（1）非剝奪調度方式（非搶占方式）

（2）剝奪調度方式（搶占方式）

二、調度算法

1.FCFS算法（先來先服務）

（1）算法規則:

?（2）適用情況:

（3）優缺點

2.SJF算法（短作業優先）

（1）算法規則:

（2）適用情況:

（3）優缺點：

3.優先級算法

（1）算法規則:

（2）使用情況：

（3）類型：

（4）優先級的類型：

（5）優缺點：

4.RR算法（時間片輪轉）

（1）算法思想：

（2）算法規則：

（3）適用情況：

（4）類型：

（5）優缺點:

5.HRRN算法（高響應比優先）

（1）算法思想：

（2）算法規則：

（3）適用情況：

（4）優缺點：

6.多級反饋隊列調度算法

（1）算法思想：

（2）算法規則：

（3）適用情況：

（4）類型：

（5）優缺點：

總結

---

一、處理機調度概述

1.基本準則

不同的調度算法具有不同的特性，在選擇調度算法時，必須考慮算法的特性。為了比較處理機調度算法的性能，人們提出了很多評價準則，下面介紹其中主要的幾種。

（1）CPU利用率

CPU是計算機系統中最重要和昂貴的資源之一，所以應盡可能使保持“忙”的狀態， 使這一資源利用率最高。

（2）系統吞吐量?

• 表示單位時間內CPU完成作業的數量。?
• 長作業需要消耗較長的處理機時間，因此會降低系統的吞吐量。?
• 短作業需要消耗的處理機時間較短，因此能提高系統的吞吐量。?
• 調度算法和方式的不同，也會對系統的吞量產生較大的影響。?

（3）周轉時間

周轉時間是指從作業提交到作業完成所經歷的時間，是作業等待、在就緒隊列中排隊、在處理機上運行及進行輸入/輸出操作所花費時間的總和。?

• 作業的周轉時間:

周轉時間 = 作業完成時間 - 作業提交時間

• 平均周轉時間:?

平均周轉時間 = (作業1的周轉時間 + ...... + 作業n的周轉時間)/n

• 帶權周轉時間（作業周轉時間與作業實際運行時間的比值）:

帶權周轉時間 = 作業周轉時間 / 作業實際運行時間

• 平均帶權周轉時間（多個作業帶權周轉時間的平均值）:

平均帶權周轉時間 = (作業1的帶權周轉時間 + ...... + 作業n的帶權周轉時間) / n?

（4）等待時間

等待時間指進程處于等待處理機狀態的時間之和，等待時間越長，用戶滿意度越低。

（5）響應時間

響應時間指從用戶提交請求到系統首次產生響應所用的時間。

2.進程調度方式

是指當某個進程正在處理機上執行時，若有某個更為重要或緊迫的進程需要處理，即優先權更高的進程進入就緒隊列，此時應如何分配處理機的方式。?通常有以下兩種進程調度方式:?

（1）非剝奪調度方式（非搶占方式）

非剝奪調度方式是指當一個進程正在處理機上執行時，即使有某個更為重要或緊迫的進程進入就緒隊列，仍然讓正在執行的進程繼續執行，直到該進程完成或發生某種事件而進入阻塞態時，才把處理機分配給更為重要或緊迫的進程。

（2）剝奪調度方式（搶占方式）

采用剝奪式的調度，對提高系統吞吐率和響應效率都有明顯的好處。但“剝奪”?不是一種任意性行為，必須遵循一定的原則，主要有優先權、短進程優先和時間片原則等。

---

二、調度算法

1.FCFS算法（先來先服務）

（1）算法規則:

先來先服務算法(first come first server,FCFS)按照作業/進程到達的先后順序來進行調度。

?（2）適用情況:

可用于作業調度也可用于進程調度。?

（3）優缺點

• 優點:算法實現簡單。?
• 缺點:對長作業有利，對短作業不利。

2.SJF算法（短作業優先）

（1）算法規則:

短作業優先調度算法(short job first,SJF)以作業的長短來計算優先級，作業越短，其優先級越高。?

（2）適用情況:

可用于作業調度及進程調度。?

（3）優缺點：

• 優點:“最短的”平均等待時間及平均周轉時間。?
• 缺點:①必須先知道作業的運行時間。?
• ②對長作業不利，會出現饑餓現象。
• ③沒有考慮作業的緊迫程度。

3.優先級算法

（1）算法規則:

基于進程(作業)的緊迫程度，由外部賦予進程相應的優先級，根據優先級進行調度。?

（2）使用情況：

可用于作業調度也可用于進程調度甚至I/O調度。

（3）類型：

搶占式優先級調度算法:只需出現另一個優先級更高的進程，調度就會發生變化非搶占式優先級調度算法:主動放棄。

（4）優先級的類型：

①靜態優先級:在創建進程時確定，其在進程的整個運行期間不變。?

②動態優先級:在創建進程之初，先賦予進程一個優先級，然后動態的調整優先級。

（5）優缺點：

• 優點:用優先級區分緊急程度，運用于實時os。
• 缺點:可能導致饑餓(低優先級進程的饑餓)。

4.RR算法（時間片輪轉）

（1）算法思想：

時間片輪轉算法(Round-Robin)公平地、輪流地為各個進程服務， 讓每個進程在一定時間間隔內都可以得到響應。

（2）算法規則：

按照各進程到達就緒隊列的順序， 輪流讓各個進程執行一個時間片。 若進程未到一個時間片內執行完，則剝奪處理機，將進程重新放到就緒隊列隊尾重新排隊。

（3）適用情況：

可用于進程調度。

（4）類型：

屬于搶占式算法。 由時鐘裝置發出時鐘中斷來通知CPU時間片已到。?

（5）優缺點:

• 優點：公平，響應快，適用于分時操作系統。
• 缺點:不能區分任務的緊急程度，需要進程切換，消耗較大。

5.HRRN算法（高響應比優先）

（1）算法思想：

高響應比優先調度算法(Highest Respomse Ratio Nex,HRRN )綜合考慮作業或進程的等待時間和要求服務的時間。?

（2）算法規則：

每次調度前先計算各個作業或進程的響應比(優先級)，選擇響應比最高的作業或進程為其服務。

?響應比(R)=(等待時間+要求服務時間)/要求服務時間=響應時間/要求服務時間

（3）適用情況：

可用于作業調度及進程調度。

（4）優缺點：

• 優點:綜合考慮了等待時間和運行時間，較好的實現了折中。?
• 缺點:每次調度前都要算響應比，會增加系統的開銷。?
• 注意:不會導致饑餓現象。高響應比優先算法

6.多級反饋隊列調度算法

（1）算法思想：

對其他調度算法的折中權衡。?

（2）算法規則：

• 設置多個就緒隊列.各級隊列優先級從高到低，時間片從小到大。
• 每個隊列都采用FCFS調度算法。?
• 按隊列優先級調度。只有當第1~i一1隊列均空時，才會調度第i隊列中的進程。

（3）適用情況：

可用于進程調度

（4）類型：

屬于搶占式的算法。

（5）優缺點：

• 優點:用優先級區分緊急程度，運用于實時OS 。?
• 缺點:可能導致饑餓(低優先級進程的饑餓)。

（6)圖示

---

總結

本篇對操作系統處理機調度的內容進行了概括梳理，便于理解和復習。部分內容源自網絡，如有侵權請聯系作者刪除處理，謝謝！