第三章處理器管理

要求：

?:?掌握作業調度、進程調度的功能。

?:?掌握常用調度算法的基本思想，會評價

其性能（如用平均周轉時間和平均等待

時間）。

處理器管理的任務

所謂進程的運行，就是給進程分配處理

器，也就是將進程調度到處理器上執行程序。

在進程管理中，負責進程運行的部分稱

為進程調度，或CPU調度或處理器管理。

從進程的角度來看，它關心如下問題：

1、進程被創建以后，何時能夠開始運行?

也就是說何時能夠獲得處理器？

2、獲得處理器后，能運行多久？何時會

失去處理器？以何種方式失去？（自愿放

棄或被搶占）

3、在失去處理器時，應保存什么信息？

誰來保存？

4、在多個進程競爭處理器的情況下，

需要滿足什么條件才可以再次獲得處理

器？誰來作這種裁決？是否公平？

5、當再次獲得處理器時，如何繼續上

次的工作？

CPU是一種資源。從資源管理的角度來看，關心的

問題如下：

1、按照何種策略，根據什么條件，選擇下一個應

該獲得處理器的進程。

2、如何實現進程的切換？包括：

■如何將處理器的現場信息保存在當前進程的PCB

中？

■如何根據新選中進程的PCB恢復處理器的現場？

3、如何回收處理器資源？即如何再次獲得處理器

的控制權？

處理器管理的任務

回答進程所關心問題的程序叫進程調度。

回答資源管理所關心問題的程序CPU調度。

操作系統是一個資源管理者，包括處理器

資源。因此，操作系統的設計者關心的是CPU調

度，它要解決的問題是：進程選擇算法、進程

切換方法、處理器回收方法。

從資源管理的角度來看，所謂處理器管理

就是對處理器資源的分配和回收。

處理器資源只能分配給進程。

從進程管理的角度來看，所謂處理器管理

就是在所有就緒的進程中，找一個最值得運

行的進程，讓它占用處理器。

現實社會中，這類工作稱為調度。所以處

理器管理又叫CPU調度，或進程調度。

3.1作業調度

在早期批處理時代，調度是以作業為單

位的。因此，那時的處理器管理又稱為作業

倜度。

作業調度的任務是：從處于后備狀態的

作業中選擇一個作業，為其分配資源，讓它

進入主機運行。

此時的作業調度程序非常簡單，運行頻

率也很低，不存在作業切換，也不用擔心處

理器資源的回收問題。

為了提高處理器的利用率，人們提出了

多道程序的概念，允許在系統中同時存在

多個作業。

這時作業調度的任務是：從處于后備

狀態的作業中選擇一個或一批作業，讓它

（它們）進入主機，為它們創建進程，準

備運行。

多道批處理系統中，作業調度的主

要工作是選擇作業、創建進程。

為了充分發揮資源的作用，應合理

搭配作業，并控制系統中作業的數量。

3.1作業調度

進入主機的作業并不一定能夠立刻運行,

還需要另外一個調度程序為它們分配CPU,這

就是CPU調度。

作業調度又稱為高級調度、宏調度、長

調度等，它選擇的作業具有了獲得處理器的

資格。

CPU調度又稱為低級調度、微調度、短調

度等，它選擇能夠立刻投入運行的進程，并

將處理器分配給它。

兩者的關系如下圖:

時間片用完

備

后

業

作

列

隊

等待

隊列

作業調度與CPU調度的關系

作業調度與進程調度的關系

1）功能不同

2）執行頻率不同

作業調度執行的次數很少，進程調

度執行頻繁。

作業的概念主要用于批處理系統，這

類系統的設計目標是最大限度地發揮各種

資源的利用率和保持系統內各種活動的充

分并行。

批處理系統既需要作業調度，也需要

進程調度程序。

分時系統中，用戶與系統直接交互,

通過鍵盤、鼠標等直接創建和啟動進程,

不再需要作業調度。

類似地，實時系統也不需要作業調

度。

3.2進程調度

進程調度是玩魔術的程序，它讓處理器在各個進程之間飛

快地輪轉，從而給每個進程都造成一個假象，認為自己在獨占

實際的CPU

e工幡/，3.2進程調度

進程調度要解決的問題是：進程選擇算法、進

程切換方法、處理器回收方法。首先考慮處理器的

回收問題。

在下面幾種情況下，操作系統會再次獲得CPU

的控制權。

1、進程請求操作系統服務

2、進程終止,中斷

3、進程運行出錯

4、外部中斷>

操作系統在獲得處理器控制器權后，首先

完成相應的中斷處理，而后根據情況決定：

(1)把處理器的控制權還給被中斷的進程。

(2)產生一次調度，將處理器的控制權交

給另一個進程。

即使進程不作系統調用、不產生異常操作,

即使所有的外部設備都不產生中斷，因為有時

鐘的存在，操作系統也會周期性地回收到處理

器的控制權。

再考慮進程的切換問題。

所謂進程的切換就是處理器現場的切換。

就是將處理器當前的現場保存起來，而后用

另一個進程的信息重新設置處理器的現場。

切換在調度程序中完成。

不同處理器提供了不同的進程切換機

制，包括需要保存的內容及切換的方法。

如InteI處理器需要保存的內容大致是

TSS（任務狀態段），切換的方法包括：

1、直接caII或jmp一個TSS。

2、切換系統堆棧，而后通過指令正常返回

剩下的問題是：如何選擇下一個運行

的進程？

進程選擇算法的好壞直接影響到處理

器管理的好壞，進程管理的好壞，甚至一

個操作系統的好壞，因此，需要很仔細地

選擇、設計進程選擇算法。

在選擇、設計具體的調度算法之前，先確

定調度的時機。

下列情況會觸發進程調度：

1、正在運行的進程需要等待某些資源或

某個事件，國而自原放棄CPU。

2、正在運行的進程用完了自己的時間片。

3、系統中發生了某個事件（I/O、同步信

號等），使得某個正在等待的進程變成

就緒或有新創建進程，而且其優先級高

于當前進程。

4、當前進程終止。

第1和第4是進程本身自愿放棄處理器的

控制權，屬于非搶占式調度

(nonpreemptive)。

第2和第3是搶占式調度(preemptive)

因為當前進程的CPU是被強行收回的，并非

出于進程的自愿。

非搶占式調度比較容易設計，它不需

要考慮太多的保護。

而搶占式調度卻要考慮各種數據結構

的保護問題，考慮資源的互斥即死鎖問題,

所以搶占式調度的設計更加困難。

但搶占式調度會改善系統的響應能力,

使系統反應速度更快。

如果整個操作系統內核都不允許搶占，

那么該系統稱為非搶占式操作系統。

Linux2.6之前的版本是非搶占式的，它

的搶占只發生在由內核切換回用戶空間之前。

如果當前進程的時間片用完，或剛就緒進程

的優先級較高，當前進程只是收到一個標志

(need_resched)。

即使內核允許搶占，搶占的動作也會被

推遲到中斷處理完成之后。如Linux2.6版、

Windows2000等。

3.3性能評價標準

確定調度策略時考慮的主要因素：

1、應保證實現系統的設計目標。

2、公平對待所有作業或進程。

3、均衡使用資源，盡量使系統中各種資

源都同時得到利用。

4、兼顧響應時間和資源利用率。

5、基于相對優先級，但避免無限延期。

6、系統開銷不應太大。

算法的評價標準

可以將評價標準分為面向用戶的和面向系

統的。

1、面向用戶的評價標準

(1)響應時間。從用戶提交請求到收到

第一個應答所需要的時間。

響應時間=進程等待運行的時間+產生第一個

輸出的時間。

(2)周轉時間。從進程創建到終止之間

的時間間隔，包括進程實際的運行時間、等

待資源的時間、等待調度的時間等。

好的調度算法應盡量減少進程等待調度

的時間，從而減少其周轉時間。

(3)死線(DeadIine)。一個進程最后

完成的期限。如果允許進程聲明自己的死線,

那么好的調度算法應盡可能的滿足各進程的

死線要求，并支持盡可能多的進程。

(4)可預言性(PredictabiIity)。同

一個程序(作業)的每次運行應該花費大致

相同的時間和代價，不管系統的負載情況如

何。

e工幡/，

2、面向系統的評價標準

(1)吞吐量。單位時間內完成的任務

(進程)數量。

從系統角度來看，處理器調度的目的是

最大化處理器的利用率。

吞吐量取決于每個進程的運行長度，但

它也受調度算法的影響。

e工幡/，

(2)處理器利用率。百分比，表示處理

器有多忙。

對于大型計算機系統，這是一個重要指

標，但對PC機、實時系統等來說，并不太重

要。

(3)就緒等待時間。進程在就緒隊列中

的等待時間。

調度算法不真正影響進程的執行時間或

I/O操作的時間，它僅影響進程在就緒隊列中

的等待時間。

(4)公平。公平對待各個進程，不會

出現餓死現象。

(5)優先級。高優先級的進程應該受

到照顧。

(6)均衡利用資源。保證系統中的資

源都處于忙狀態。不太使用緊缺資源的進

程應該受到重視，從而平衡資源的使用。

3.4常用的調度算法

下面列舉幾種常用的調度算法(主要是進

程選擇算法)。

一、先來先服務(FCFS)

數據結構：一個單就緒隊列，新就緒的進

程被加入到就緒隊列的隊尾。

選擇算法：就緒隊列的隊頭就是下一個要

運行的進程。

例：有三個進程PI、P2、P3,它們順序

排在就緒隊列中。各進程下一次的運行時間分

別為24、3、3o

FCFS調度的執行順序如下：

PlP2P3

0242730

各進程的就緒等待時間為：0、24、27o

平均等待時間為：（0+24+27）/3=

17o

3.4常用的調度算法

FCFS算法偏愛長進程，因為平均來說，

長進程的等待時間較少，而短進程的等待時

間較長。或者說，短進程得到的服務要比長

進程差。

如上例，各進程得到的服務時間與等待

時間的比(滿意度)分別是：8、0.125、

0.11(3/27)o

3.4常用的調度算法

另外，FCFS算法偏愛處理器繁忙型進

程。與I/O繁忙型進程相比，處理器繁忙

型進程會占用更長的時間，它得到的服務

要優于I/O繁忙型進程。

如I/O繁忙型進程通常在等待I/O,此

時處理器繁忙型進程會占用CPU。當I/O繁

忙型進程就緒時，通常還要等待處理器繁

忙型進程。

3.4常用的調度算法

換一種調度方式:

P2P3P1

03630

各進程的就緒等待時間為：0、3、6o

平均等待時間為：(0+3+6)/3=3o

此時，各進程得到的服務時間與等待時間的

比為：8、1、4,要優于FCFS算法。

回顧

處理機管理

作業調度

從后備隊列中選擇一批作業，創建進程,

準備運行。

進程調度

從就緒進程中選擇一個，將處理器分配

給它。

回顧

常用調度算法：

1、先來先服務(FCFS)

2、短進程優先(SPN)

3、輪轉法(RR)

4、可變時間片輪轉

5、優先級算法

6、多級隊列法

7、多級反饋隊列法

3.4常用的調度算法

二、短進程優先（SPN）

數據結構：單就緒隊列。

算法思想：選擇就緒隊列中下一次運

行時間最短的進程。

3.4常用的調度算法

如有4個就緒進程Pl、P2、P3、P4,

其預計運行時間是6、3、8、7,貝IJSPN算法

的調度順序如下：

P2PlP4P3

0391624

3.4常用的調度算法

優點：平均等待時間最短，周轉時間最短。

通常I/O繁忙型進程的運行時間都很短，

這類進程又需要盡快得到服務，使用SPN算法

可以縮短系統的響應時間，改善服務質量。

缺點：如果就緒隊列中持續出現短進程，

可能會餓死長進程。

e工幡/，3.4常用的調度算法

問題：當一個進程正在運行時，如果一

個新的進程進入就緒隊列，而且它的估算時

間比當前進程的剩余時間還要短，應該如何

處理？

1、搶占。立刻調度，將處理器交給新

就緒的進程。

2、非搶占。當前進程繼續運行，直到

完成其預計工作，而后再調度。

3.4常用的調度算法

SPN算法又分為搶占式SPN和非搶占

式SPN。

搶占式SPN有時又叫最短剩余時間

優先(ShortestRemainingTime

First)o

3.4常用的調度算法

例：四個進程P1、P2、P3、P4,其到達就

緒隊列的時間和期望的運行時間如下：

進程到達時間期望運行時間

P108

P214

P329

P435

非搶占式SPN：

PlP2P4P3

搶占式SPN：

PlP2P4PlP3

3.4常用的調度算法

三、輪轉法(RR)

輪轉法(RoundRobin)是加了時間片限

制的FCFS算法。

數據結構與FCFS相同：單就緒隊列。

基本思想：調度程序從就緒隊列中的第一

個進程開始，輪流把CPU分配給隊列中的每個

進程，每個進程每次可以運行一個時間片。

3.4常用的調度算法

在三種情況下，當前進程會讓出CPU：

1、當前進程在未用完時間片之前就已完成

工作。

2、當前進程在未用完時間片之前就已進入

等待狀態。

3、當前進程用完了時間片，仍未完成工作,

它的CPU被剝奪。

輪轉法是搶占式的算法。

e工幡/，3.4常用的調度算法

例：有三個進程PI、P2、P3,它們順序排在

就緒隊列中。各進程下一次的運行時間分別為24、

3、3o

假定時間片是4,貝URR調度的執行順序如下：

PlP2P3PlPlPlPlPl

047101418222630

各進程的就緒等待時間是（10-4）、4、7o

平均就緒等待時間為：（6+4+7）/3=

5.666o

3.4常用的調度算法

主要設計問題：如何確定時間片的長度？

時間片越長，CPU的輪轉就越慢，新就緒

進程的等待時間就越長。如果時間片無限長，

輪轉法就退變成了FCFS。

時間片過短，會導致調度次數的增加，從

而增加系統開銷。另外，過短的時間片會將短

進程的處理分割成幾部分，會延長其周轉時間。

3.4常用的調度算法

桌面系統的時間片應短，保證短的響應

時間；服務器系統的時間片應長，減少額

外開銷。

Linux的時間片是210ms,2.6改為21ms。

Windows的時間片是20ms（桌面）、

120ms（服務器）o

時間片的長度應稍大于一次典型交互

的時間。

3.4常用的調度算法

時間片的長短由以下因素決定：

(1)系統的響應時間。進程數目一定

時，與響應時間成正比。

(2)就緒隊列的長度。響應時間一定

時，與就緒進程數目成反比。

3.4常用的調度算法

(3)進程的切換時間。若進程切換時間

為t,時間片為q,貝h/q應不大于某一數值,

如1/10。即相對于進程的轉換時間，時間

片不能太短。

(4)CPU運行速度。CPU速度快則時間片

可以短。

3.4常用的調度算法

需求：I/O繁忙型進程（如交互式程序）

的大部分時間都在等待I/O,需要的處理器時

間較少。但一旦其I/O操作完成，就希望能立

刻投入運行，否則會給用戶造成系統反映遲鈍

的感覺。

輪轉法的問題：將就緒的I/O進程加入到

就緒隊列的隊尾，無法立刻投入運行。

e工幡/，3.4常用的調度算法

改進方法一：增加一個輔助隊列，將

剛就緒的I/O進程加入到此隊列中。調度程

序先從輔助隊列中選擇進程，只有當輔助

隊列空時，才從就緒隊列中選擇進程。

改進方法二：將剛就緒的I/O進程加入

到就緒隊列的隊頭。

3.4常用的調度算法

I/O

兀

成

I/O隊列n

3.4常用的調度算法

四、可變時間片輪轉法

調整的方法是：在每一輪周期開始時，根據就緒

隊列中進程的數目計算出這一輪的時間片，并開始輪

轉。

在輪轉開始之后，新就緒的進程不允許加入就緒

隊列，因而也不參加輪轉。

輪轉一周以后，新就緒進程加入隊列，再根據就

緒隊列中進程的數目重新計算時間片，開始下一輪輪

轉。對長進程，可以適當增加其時間片的長度。

3.4常用的調度算法

五、優先級

基本思想：根據進程的緊急程度給進程

指定優先級，如給希望盡快得到CPU服務的

進程以較高的優先級。指定進程的優先級后,

可以根據優先級選擇進程。

3.4常用的調度算法

選擇方法：選擇優先級最高的就緒進

程；如有多個優先級最高的進程，則選最

早到達者(FCFS)o

數據結構：單就緒隊列，也可以采用

多就緒隊列。

新就緒的進程加入到隊尾。

調度程序遍歷就緒隊列，選擇遇到的

第一個具有最高優先級的進程。

3.4常用的調度算法

優先級調度的關鍵是：如何確定進程的優

先級？

確定優先級的方法有兩種：靜態和動態。

工、靜態。在進程創建時確定其優先級，

一旦確定就不再改變。

靜態優先級難以反映進程動態的變化。

e工幡/，3.4常用的調度算法

靜態優先級分內部定義和外部指定。

內部定義：利用某些可度量的量一次

性地計算進程的優先級。如預計的進程運

行時間、需要的內存量、工/O操作的次數

等。

外部指定：按OS以外的標準設置，如

由用戶指定。

3.4常用的調度算法

2、動態。在進程運行過程中，根據某些條件的

變化動態地調整進程的優先級。

調整優先級的條件包括：進程已運行的時間、已

等待的時間、預計的執行時間、進程的重要程度等。

如指定進程的優先級是它預計的運行時間的倒數,

則優先級調度就是SPN。

如指定進程的優先級是它在就緒隊列中的等待時

間，則優先級調度就是FCFS。

3.4常用的調度算法

優先級調度算法可以是搶占的，也可以是

非搶占的。

搶占：在進程進入就緒隊列時，與當前進

程比較優先級。如果新就緒進程的優先級高于

當前進程，則觸發調度，搶占當前進程的處理

珀奧tro

基于優先級的搶占式調度可以保證盡快地

運行高優先級進程，縮短其響應時間。

3.4常用的調度算法

非搶占：在進程進入就緒隊列時，不

比較其優先級。不管新就緒進程的優先級

是否高于當前進程，都不觸發調度，而是

靜靜地等待。

非搶占式調度實現簡單，但會出現優

先級倒掛現象。

e工幡/，3.4常用的調度算法

優先級調度的問題：可能會出現低優先級進程餓

死的現象。

解決辦法一：按照進程的年齡（在就緒隊列中等

待的時間）調整其優先級，即隨著進程年齡的增大，

逐步調高它的優先級，從而獲得運行機會。

解決辦法二：當進程在就緒隊列中等待足夠長后,

躍遷其優先級，讓它運行，而后再將其優先級降低到

原來的水平。

3.4常用的調度算法

例：Windows的線程有兩個優先級：

BasePriority和CurrentPriority,其中

BasePriority是從進程中繼承來的，但可

以通過系統調用修改；CurrentPriority

是動態變化的，從工到工5。

3.4常用的調度算法

Windows的線程調度程序采用多級就緒隊列。

Windows提供了32個優先級，因而有32個就緒隊列。

其中0到15用于普通線程，16到31用于實時進程。

在下列情況下，線程的優先級會躍遷：

等待的I/。操作完成、等待的事件（如信號量）發

生、前臺線程就緒、GUI線程被喚醒、線程過分饑

餓。

3.4常用的調度算法

六、多級隊列法

系統中的進程對調度的要求是不一樣的O

如在前臺運行的進程通常是交互式的，需要短的

響應時間；而在后臺運行的進程通常是服務器進程，

需要短的周轉時間。所以，前臺進程的輪轉應快，時

間片應短；而后臺進程的輪轉可慢，時間片應長。

因此，應根據進程的實際情況將其分組，每組進

程采用適當的調度算法。

3.4常用的調度算法

基本思想：

1、提供幾個就緒隊列，每個隊列有自己

獨立的調度算法。

2、根據進程的某些特性，如類型、優先

級等，永久性地把進程鏈入某一隊列。

3、整個系統（隊列之間）采用另外的調

度算法，如固定優先級的搶占式調度或

規定各個隊列占用CPU的比例。

3.4常用的調度算法

高優先級輪轉

------?系統進程-----

---------1交互進程-----

低優先級程FCFS

3.4常用的調度算法

七、多級反饋隊列法

基本思想：給剛就緒的進程以最高的優先

級，讓它盡快投入運行；在進程的運行過程中

不斷地降低其優先級，即進程運行時間越長，

它的優先級就越低。

提供多個就緒隊列。每個就緒隊列的時間片

長度不同，采用的調度算法也可不同。

第一級隊列（高）

RR終止

>

第二級隊列

RR終止

第N級隊列（低）FCFS

，處理器?終止

3.4常用的調度算法

將就緒隊列分為N個，每個就緒隊列一個優先級。

給每個就緒隊列分配不同的時間片。隊列的優先

級越高，時間越短；優先級越低，時間片越長。

最低優先級隊列采用FCFS調度算法，其它隊列采

用時間片輪轉調度算法。

第一次就緒的進程進入第一級隊列（優先級最

高）；等待進程被喚醒后，進入原來的就緒隊列。

系統從第一級隊列開始調度，當第一級為空時，

轉向第二個隊列，依次類推。

運行進程用完一個時間片后，進入下一級就緒隊

列。

高優先級進程就緒時，可以搶占CPU,被搶占的

進程回到原就緒隊列的隊尾。

3.4常用的調度算法

多級反饋隊列法特點：

允許進程在各隊列之間移動。

比較照顧新的、小的進程，小進程能盡快得到處

理器。

進程等待的時間不計算在內，因此等待工/O操作

的進程不會被降級。

長進程的優先級會被逐漸降低，因而獲得處理器

的機會會減少。但長進程的時間片被延長，它每次獲

得處理器后，可以運行更長的時間。

進程之間允許搶占，所以短進程的響應時間不會

太長。

3.5多處理器調度

多處理器系統的調度有自己獨特的要求。

有多種形式的多處理器系統，如：

工、松散耦合的多處理器。每個處理器都有自己

的內存、I/O通道等。

2、主從形式的多處理器。處理器有分工，如

工/O處理器等，處理器之間有主從關系。

3、緊密耦合的多處理器。各處理器共享同一個

物理內存，由一個操作系統集中控制。

考慮第三種形式的多處理器系統。

e工幡/，3.5多處理器調度

多處理器調度時需要考慮如下問題：

1、如何為進程指派處理器？

2、是否允許在單處理器上運行多道程序?

3、如何調度和切換進程？

3.5多處理器調度

把處理器看成處理器池。

如何指派處理器？

(1)靜態。在進程創建時為其指派處理

器，此后該進程就在指派的處理器上運行。

(2)動態。進程可以在任意一個空閑的

處理器上運行。

3.5多處理器調度

誰來指派處理器？

(1)主從。操作系統運行在一臺處理器上,

它負責處理器的指派。簡單。

(2)同等。操作系統運行在所有處理器上,

每個處理器自己選擇進程。復雜。

3.5多處理器調度

是否允許多道程序？

(1)如果進程之間的關系松散，允許在單處理器

上運行多道程序會提高處理器的利用率。

(2)如果進程之間的關系很密切(有大量的交

互)，如只有當它們同時運行時才能獲得最佳的性能,

此時，允許在單處理器上運行多道程序反而會降低應

用程序的性能。

在這種情況下，較好的方法是不支持多道程序。

浪費部分處理器資源以獲得較高的性能。

3.5多處理器調度

如何選擇下一個運行的進程？

(1)所有處理器共用