第三章處理器管理

要求：

?:?掌握作業(yè)調(diào)度、進(jìn)程調(diào)度的功能。

?:?掌握常用調(diào)度算法的基本思想，會評價

其性能（如用平均周轉(zhuǎn)時間和平均等待

時間）。

處理器管理的任務(wù)

所謂進(jìn)程的運行，就是給進(jìn)程分配處理

器，也就是將進(jìn)程調(diào)度到處理器上執(zhí)行程序。

在進(jìn)程管理中，負(fù)責(zé)進(jìn)程運行的部分稱

為進(jìn)程調(diào)度，或CPU調(diào)度或處理器管理。

從進(jìn)程的角度來看，它關(guān)心如下問題：

1、進(jìn)程被創(chuàng)建以后，何時能夠開始運行?

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

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

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

棄或被搶占）

3、在失去處理器時，應(yīng)保存什么信息？

誰來保存？

4、在多個進(jìn)程競爭處理器的情況下，

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

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

5、當(dāng)再次獲得處理器時，如何繼續(xù)上

次的工作？

CPU是一種資源。從資源管理的角度來看，關(guān)心的

問題如下：

1、按照何種策略，根據(jù)什么條件，選擇下一個應(yīng)

該獲得處理器的進(jìn)程。

2、如何實現(xiàn)進(jìn)程的切換？包括：

■如何將處理器的現(xiàn)場信息保存在當(dāng)前進(jìn)程的PCB

中？

■如何根據(jù)新選中進(jìn)程的PCB恢復(fù)處理器的現(xiàn)場？

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

的控制權(quán)？

處理器管理的任務(wù)

回答進(jìn)程所關(guān)心問題的程序叫進(jìn)程調(diào)度。

回答資源管理所關(guān)心問題的程序CPU調(diào)度。

操作系統(tǒng)是一個資源管理者，包括處理器

資源。因此，操作系統(tǒng)的設(shè)計者關(guān)心的是CPU調(diào)

度，它要解決的問題是：進(jìn)程選擇算法、進(jìn)程

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

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

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

處理器資源只能分配給進(jìn)程。

從進(jìn)程管理的角度來看，所謂處理器管理

就是在所有就緒的進(jìn)程中，找一個最值得運

行的進(jìn)程，讓它占用處理器。

現(xiàn)實社會中，這類工作稱為調(diào)度。所以處

理器管理又叫CPU調(diào)度，或進(jìn)程調(diào)度。

3.1作業(yè)調(diào)度

在早期批處理時代，調(diào)度是以作業(yè)為單

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

倜度。

作業(yè)調(diào)度的任務(wù)是：從處于后備狀態(tài)的

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

進(jìn)入主機運行。

此時的作業(yè)調(diào)度程序非常簡單，運行頻

率也很低，不存在作業(yè)切換，也不用擔(dān)心處

理器資源的回收問題。

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

多道程序的概念，允許在系統(tǒng)中同時存在

多個作業(yè)。

這時作業(yè)調(diào)度的任務(wù)是：從處于后備

狀態(tài)的作業(yè)中選擇一個或一批作業(yè)，讓它

（它們）進(jìn)入主機，為它們創(chuàng)建進(jìn)程，準(zhǔn)

備運行。

多道批處理系統(tǒng)中，作業(yè)調(diào)度的主

要工作是選擇作業(yè)、創(chuàng)建進(jìn)程。

為了充分發(fā)揮資源的作用，應(yīng)合理

搭配作業(yè)，并控制系統(tǒng)中作業(yè)的數(shù)量。

3.1作業(yè)調(diào)度

進(jìn)入主機的作業(yè)并不一定能夠立刻運行,

還需要另外一個調(diào)度程序為它們分配CPU,這

就是CPU調(diào)度。

作業(yè)調(diào)度又稱為高級調(diào)度、宏調(diào)度、長

調(diào)度等，它選擇的作業(yè)具有了獲得處理器的

資格。

CPU調(diào)度又稱為低級調(diào)度、微調(diào)度、短調(diào)

度等，它選擇能夠立刻投入運行的進(jìn)程，并

將處理器分配給它。

兩者的關(guān)系如下圖:

時間片用完

備

后

業(yè)

作

列

隊

等待

隊列

作業(yè)調(diào)度與CPU調(diào)度的關(guān)系

作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系

1）功能不同

2）執(zhí)行頻率不同

作業(yè)調(diào)度執(zhí)行的次數(shù)很少，進(jìn)程調(diào)

度執(zhí)行頻繁。

作業(yè)的概念主要用于批處理系統(tǒng)，這

類系統(tǒng)的設(shè)計目標(biāo)是最大限度地發(fā)揮各種

資源的利用率和保持系統(tǒng)內(nèi)各種活動的充

分并行。

批處理系統(tǒng)既需要作業(yè)調(diào)度，也需要

進(jìn)程調(diào)度程序。

分時系統(tǒng)中，用戶與系統(tǒng)直接交互,

通過鍵盤、鼠標(biāo)等直接創(chuàng)建和啟動進(jìn)程,

不再需要作業(yè)調(diào)度。

類似地，實時系統(tǒng)也不需要作業(yè)調(diào)

度。

3.2進(jìn)程調(diào)度

進(jìn)程調(diào)度是玩魔術(shù)的程序，它讓處理器在各個進(jìn)程之間飛

快地輪轉(zhuǎn)，從而給每個進(jìn)程都造成一個假象，認(rèn)為自己在獨占

實際的CPU

e工幡/，3.2進(jìn)程調(diào)度

進(jìn)程調(diào)度要解決的問題是：進(jìn)程選擇算法、進(jìn)

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

回收問題。

在下面幾種情況下，操作系統(tǒng)會再次獲得CPU

的控制權(quán)。

1、進(jìn)程請求操作系統(tǒng)服務(wù)

2、進(jìn)程終止,中斷

3、進(jìn)程運行出錯

4、外部中斷>

操作系統(tǒng)在獲得處理器控制器權(quán)后，首先

完成相應(yīng)的中斷處理，而后根據(jù)情況決定：

(1)把處理器的控制權(quán)還給被中斷的進(jìn)程。

(2)產(chǎn)生一次調(diào)度，將處理器的控制權(quán)交

給另一個進(jìn)程。

即使進(jìn)程不作系統(tǒng)調(diào)用、不產(chǎn)生異常操作,

即使所有的外部設(shè)備都不產(chǎn)生中斷，因為有時

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

器的控制權(quán)。

再考慮進(jìn)程的切換問題。

所謂進(jìn)程的切換就是處理器現(xiàn)場的切換。

就是將處理器當(dāng)前的現(xiàn)場保存起來，而后用

另一個進(jìn)程的信息重新設(shè)置處理器的現(xiàn)場。

切換在調(diào)度程序中完成。

不同處理器提供了不同的進(jìn)程切換機

制，包括需要保存的內(nèi)容及切換的方法。

如InteI處理器需要保存的內(nèi)容大致是

TSS（任務(wù)狀態(tài)段），切換的方法包括：

1、直接caII或jmp一個TSS。

2、切換系統(tǒng)堆棧，而后通過指令正常返回

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

的進(jìn)程？

進(jìn)程選擇算法的好壞直接影響到處理

器管理的好壞，進(jìn)程管理的好壞，甚至一

個操作系統(tǒng)的好壞，因此，需要很仔細(xì)地

選擇、設(shè)計進(jìn)程選擇算法。

在選擇、設(shè)計具體的調(diào)度算法之前，先確

定調(diào)度的時機。

下列情況會觸發(fā)進(jìn)程調(diào)度：

1、正在運行的進(jìn)程需要等待某些資源或

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

2、正在運行的進(jìn)程用完了自己的時間片。

3、系統(tǒng)中發(fā)生了某個事件（I/O、同步信

號等），使得某個正在等待的進(jìn)程變成

就緒或有新創(chuàng)建進(jìn)程，而且其優(yōu)先級高

于當(dāng)前進(jìn)程。

4、當(dāng)前進(jìn)程終止。

第1和第4是進(jìn)程本身自愿放棄處理器的

控制權(quán)，屬于非搶占式調(diào)度

(nonpreemptive)。

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

因為當(dāng)前進(jìn)程的CPU是被強行收回的，并非

出于進(jìn)程的自愿。

非搶占式調(diào)度比較容易設(shè)計，它不需

要考慮太多的保護。

而搶占式調(diào)度卻要考慮各種數(shù)據(jù)結(jié)構(gòu)

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

所以搶占式調(diào)度的設(shè)計更加困難。

但搶占式調(diào)度會改善系統(tǒng)的響應(yīng)能力,

使系統(tǒng)反應(yīng)速度更快。

如果整個操作系統(tǒng)內(nèi)核都不允許搶占，

那么該系統(tǒng)稱為非搶占式操作系統(tǒng)。

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

的搶占只發(fā)生在由內(nèi)核切換回用戶空間之前。

如果當(dāng)前進(jìn)程的時間片用完，或剛就緒進(jìn)程

的優(yōu)先級較高，當(dāng)前進(jìn)程只是收到一個標(biāo)志

(need_resched)。

即使內(nèi)核允許搶占，搶占的動作也會被

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

Windows2000等。

3.3性能評價標(biāo)準(zhǔn)

確定調(diào)度策略時考慮的主要因素：

1、應(yīng)保證實現(xiàn)系統(tǒng)的設(shè)計目標(biāo)。

2、公平對待所有作業(yè)或進(jìn)程。

3、均衡使用資源，盡量使系統(tǒng)中各種資

源都同時得到利用。

4、兼顧響應(yīng)時間和資源利用率。

5、基于相對優(yōu)先級，但避免無限延期。

6、系統(tǒng)開銷不應(yīng)太大。

算法的評價標(biāo)準(zhǔn)

可以將評價標(biāo)準(zhǔn)分為面向用戶的和面向系

統(tǒng)的。

1、面向用戶的評價標(biāo)準(zhǔn)

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

第一個應(yīng)答所需要的時間。

響應(yīng)時間=進(jìn)程等待運行的時間+產(chǎn)生第一個

輸出的時間。

(2)周轉(zhuǎn)時間。從進(jìn)程創(chuàng)建到終止之間

的時間間隔，包括進(jìn)程實際的運行時間、等

待資源的時間、等待調(diào)度的時間等。

好的調(diào)度算法應(yīng)盡量減少進(jìn)程等待調(diào)度

的時間，從而減少其周轉(zhuǎn)時間。

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

完成的期限。如果允許進(jìn)程聲明自己的死線,

那么好的調(diào)度算法應(yīng)盡可能的滿足各進(jìn)程的

死線要求，并支持盡可能多的進(jìn)程。

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

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

相同的時間和代價，不管系統(tǒng)的負(fù)載情況如

何。

e工幡/，

2、面向系統(tǒng)的評價標(biāo)準(zhǔn)

(1)吞吐量。單位時間內(nèi)完成的任務(wù)

(進(jìn)程)數(shù)量。

從系統(tǒng)角度來看，處理器調(diào)度的目的是

最大化處理器的利用率。

吞吐量取決于每個進(jìn)程的運行長度，但

它也受調(diào)度算法的影響。

e工幡/，

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

器有多忙。

對于大型計算機系統(tǒng)，這是一個重要指

標(biāo)，但對PC機、實時系統(tǒng)等來說，并不太重

要。

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

的等待時間。

調(diào)度算法不真正影響進(jìn)程的執(zhí)行時間或

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

的等待時間。

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

出現(xiàn)餓死現(xiàn)象。

(5)優(yōu)先級。高優(yōu)先級的進(jìn)程應(yīng)該受

到照顧。

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

源都處于忙狀態(tài)。不太使用緊缺資源的進(jìn)

程應(yīng)該受到重視，從而平衡資源的使用。

3.4常用的調(diào)度算法

下面列舉幾種常用的調(diào)度算法(主要是進(jìn)

程選擇算法)。

一、先來先服務(wù)(FCFS)

數(shù)據(jù)結(jié)構(gòu)：一個單就緒隊列，新就緒的進(jìn)

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

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

運行的進(jìn)程。

例：有三個進(jìn)程PI、P2、P3,它們順序

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

別為24、3、3o

FCFS調(diào)度的執(zhí)行順序如下：

PlP2P3

0242730

各進(jìn)程的就緒等待時間為：0、24、27o

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

17o

3.4常用的調(diào)度算法

FCFS算法偏愛長進(jìn)程，因為平均來說，

長進(jìn)程的等待時間較少，而短進(jìn)程的等待時

間較長?；蛘哒f，短進(jìn)程得到的服務(wù)要比長

進(jìn)程差。

如上例，各進(jìn)程得到的服務(wù)時間與等待

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

0.11(3/27)o

3.4常用的調(diào)度算法

另外，F(xiàn)CFS算法偏愛處理器繁忙型進(jìn)

程。與I/O繁忙型進(jìn)程相比，處理器繁忙

型進(jìn)程會占用更長的時間，它得到的服務(wù)

要優(yōu)于I/O繁忙型進(jìn)程。

如I/O繁忙型進(jìn)程通常在等待I/O,此

時處理器繁忙型進(jìn)程會占用CPU。當(dāng)I/O繁

忙型進(jìn)程就緒時，通常還要等待處理器繁

忙型進(jìn)程。

3.4常用的調(diào)度算法

換一種調(diào)度方式:

P2P3P1

03630

各進(jìn)程的就緒等待時間為：0、3、6o

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

此時，各進(jìn)程得到的服務(wù)時間與等待時間的

比為：8、1、4,要優(yōu)于FCFS算法。

回顧

處理機管理

作業(yè)調(diào)度

從后備隊列中選擇一批作業(yè)，創(chuàng)建進(jìn)程,

準(zhǔn)備運行。

進(jìn)程調(diào)度

從就緒進(jìn)程中選擇一個，將處理器分配

給它。

回顧

常用調(diào)度算法：

1、先來先服務(wù)(FCFS)

2、短進(jìn)程優(yōu)先(SPN)

3、輪轉(zhuǎn)法(RR)

4、可變時間片輪轉(zhuǎn)

5、優(yōu)先級算法

6、多級隊列法

7、多級反饋隊列法

3.4常用的調(diào)度算法

二、短進(jìn)程優(yōu)先（SPN）

數(shù)據(jù)結(jié)構(gòu)：單就緒隊列。

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

行時間最短的進(jìn)程。

3.4常用的調(diào)度算法

如有4個就緒進(jìn)程Pl、P2、P3、P4,

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

的調(diào)度順序如下：

P2PlP4P3

0391624

3.4常用的調(diào)度算法

優(yōu)點：平均等待時間最短，周轉(zhuǎn)時間最短。

通常I/O繁忙型進(jìn)程的運行時間都很短，

這類進(jìn)程又需要盡快得到服務(wù)，使用SPN算法

可以縮短系統(tǒng)的響應(yīng)時間，改善服務(wù)質(zhì)量。

缺點：如果就緒隊列中持續(xù)出現(xiàn)短進(jìn)程，

可能會餓死長進(jìn)程。

e工幡/，3.4常用的調(diào)度算法

問題：當(dāng)一個進(jìn)程正在運行時，如果一

個新的進(jìn)程進(jìn)入就緒隊列，而且它的估算時

間比當(dāng)前進(jìn)程的剩余時間還要短，應(yīng)該如何

處理？

1、搶占。立刻調(diào)度，將處理器交給新

就緒的進(jìn)程。

2、非搶占。當(dāng)前進(jìn)程繼續(xù)運行，直到

完成其預(yù)計工作，而后再調(diào)度。

3.4常用的調(diào)度算法

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

式SPN。

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

優(yōu)先(ShortestRemainingTime

First)o

3.4常用的調(diào)度算法

例：四個進(jìn)程P1、P2、P3、P4,其到達(dá)就

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

進(jìn)程到達(dá)時間期望運行時間

P108

P214

P329

P435

非搶占式SPN：

PlP2P4P3

搶占式SPN：

PlP2P4PlP3

3.4常用的調(diào)度算法

三、輪轉(zhuǎn)法(RR)

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

制的FCFS算法。

數(shù)據(jù)結(jié)構(gòu)與FCFS相同：單就緒隊列。

基本思想：調(diào)度程序從就緒隊列中的第一

個進(jìn)程開始，輪流把CPU分配給隊列中的每個

進(jìn)程，每個進(jìn)程每次可以運行一個時間片。

3.4常用的調(diào)度算法

在三種情況下，當(dāng)前進(jìn)程會讓出CPU：

1、當(dāng)前進(jìn)程在未用完時間片之前就已完成

工作。

2、當(dāng)前進(jìn)程在未用完時間片之前就已進(jìn)入

等待狀態(tài)。

3、當(dāng)前進(jìn)程用完了時間片，仍未完成工作,

它的CPU被剝奪。

輪轉(zhuǎn)法是搶占式的算法。

e工幡/，3.4常用的調(diào)度算法

例：有三個進(jìn)程PI、P2、P3,它們順序排在

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

3、3o

假定時間片是4,貝URR調(diào)度的執(zhí)行順序如下：

PlP2P3PlPlPlPlPl

047101418222630

各進(jìn)程的就緒等待時間是（10-4）、4、7o

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

5.666o

3.4常用的調(diào)度算法

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

時間片越長，CPU的輪轉(zhuǎn)就越慢，新就緒

進(jìn)程的等待時間就越長。如果時間片無限長，

輪轉(zhuǎn)法就退變成了FCFS。

時間片過短，會導(dǎo)致調(diào)度次數(shù)的增加，從

而增加系統(tǒng)開銷。另外，過短的時間片會將短

進(jìn)程的處理分割成幾部分，會延長其周轉(zhuǎn)時間。

3.4常用的調(diào)度算法

桌面系統(tǒng)的時間片應(yīng)短，保證短的響應(yīng)

時間；服務(wù)器系統(tǒng)的時間片應(yīng)長，減少額

外開銷。

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

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

120ms（服務(wù)器）o

時間片的長度應(yīng)稍大于一次典型交互

的時間。

3.4常用的調(diào)度算法

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

(1)系統(tǒng)的響應(yīng)時間。進(jìn)程數(shù)目一定

時，與響應(yīng)時間成正比。

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

時，與就緒進(jìn)程數(shù)目成反比。

3.4常用的調(diào)度算法

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

為t,時間片為q,貝h/q應(yīng)不大于某一數(shù)值,

如1/10。即相對于進(jìn)程的轉(zhuǎn)換時間，時間

片不能太短。

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

可以短。

3.4常用的調(diào)度算法

需求：I/O繁忙型進(jìn)程（如交互式程序）

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

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

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

的感覺。

輪轉(zhuǎn)法的問題：將就緒的I/O進(jìn)程加入到

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

e工幡/，3.4常用的調(diào)度算法

改進(jìn)方法一：增加一個輔助隊列，將

剛就緒的I/O進(jìn)程加入到此隊列中。調(diào)度程

序先從輔助隊列中選擇進(jìn)程，只有當(dāng)輔助

隊列空時，才從就緒隊列中選擇進(jìn)程。

改進(jìn)方法二：將剛就緒的I/O進(jìn)程加入

到就緒隊列的隊頭。

3.4常用的調(diào)度算法

I/O

兀

成

I/O隊列n

3.4常用的調(diào)度算法

四、可變時間片輪轉(zhuǎn)法

調(diào)整的方法是：在每一輪周期開始時，根據(jù)就緒

隊列中進(jìn)程的數(shù)目計算出這一輪的時間片，并開始輪

轉(zhuǎn)。

在輪轉(zhuǎn)開始之后，新就緒的進(jìn)程不允許加入就緒

隊列，因而也不參加輪轉(zhuǎn)。

輪轉(zhuǎn)一周以后，新就緒進(jìn)程加入隊列，再根據(jù)就

緒隊列中進(jìn)程的數(shù)目重新計算時間片，開始下一輪輪

轉(zhuǎn)。對長進(jìn)程，可以適當(dāng)增加其時間片的長度。

3.4常用的調(diào)度算法

五、優(yōu)先級

基本思想：根據(jù)進(jìn)程的緊急程度給進(jìn)程

指定優(yōu)先級，如給希望盡快得到CPU服務(wù)的

進(jìn)程以較高的優(yōu)先級。指定進(jìn)程的優(yōu)先級后,

可以根據(jù)優(yōu)先級選擇進(jìn)程。

3.4常用的調(diào)度算法

選擇方法：選擇優(yōu)先級最高的就緒進(jìn)

程；如有多個優(yōu)先級最高的進(jìn)程，則選最

早到達(dá)者(FCFS)o

數(shù)據(jù)結(jié)構(gòu)：單就緒隊列，也可以采用

多就緒隊列。

新就緒的進(jìn)程加入到隊尾。

調(diào)度程序遍歷就緒隊列，選擇遇到的

第一個具有最高優(yōu)先級的進(jìn)程。

3.4常用的調(diào)度算法

優(yōu)先級調(diào)度的關(guān)鍵是：如何確定進(jìn)程的優(yōu)

先級？

確定優(yōu)先級的方法有兩種：靜態(tài)和動態(tài)。

工、靜態(tài)。在進(jìn)程創(chuàng)建時確定其優(yōu)先級，

一旦確定就不再改變。

靜態(tài)優(yōu)先級難以反映進(jìn)程動態(tài)的變化。

e工幡/，3.4常用的調(diào)度算法

靜態(tài)優(yōu)先級分內(nèi)部定義和外部指定。

內(nèi)部定義：利用某些可度量的量一次

性地計算進(jìn)程的優(yōu)先級。如預(yù)計的進(jìn)程運

行時間、需要的內(nèi)存量、工/O操作的次數(shù)

等。

外部指定：按OS以外的標(biāo)準(zhǔn)設(shè)置，如

由用戶指定。

3.4常用的調(diào)度算法

2、動態(tài)。在進(jìn)程運行過程中，根據(jù)某些條件的

變化動態(tài)地調(diào)整進(jìn)程的優(yōu)先級。

調(diào)整優(yōu)先級的條件包括：進(jìn)程已運行的時間、已

等待的時間、預(yù)計的執(zhí)行時間、進(jìn)程的重要程度等。

如指定進(jìn)程的優(yōu)先級是它預(yù)計的運行時間的倒數(shù),

則優(yōu)先級調(diào)度就是SPN。

如指定進(jìn)程的優(yōu)先級是它在就緒隊列中的等待時

間，則優(yōu)先級調(diào)度就是FCFS。

3.4常用的調(diào)度算法

優(yōu)先級調(diào)度算法可以是搶占的，也可以是

非搶占的。

搶占：在進(jìn)程進(jìn)入就緒隊列時，與當(dāng)前進(jìn)

程比較優(yōu)先級。如果新就緒進(jìn)程的優(yōu)先級高于

當(dāng)前進(jìn)程，則觸發(fā)調(diào)度，搶占當(dāng)前進(jìn)程的處理

珀奧tro

基于優(yōu)先級的搶占式調(diào)度可以保證盡快地

運行高優(yōu)先級進(jìn)程，縮短其響應(yīng)時間。

3.4常用的調(diào)度算法

非搶占：在進(jìn)程進(jìn)入就緒隊列時，不

比較其優(yōu)先級。不管新就緒進(jìn)程的優(yōu)先級

是否高于當(dāng)前進(jìn)程，都不觸發(fā)調(diào)度，而是

靜靜地等待。

非搶占式調(diào)度實現(xiàn)簡單，但會出現(xiàn)優(yōu)

先級倒掛現(xiàn)象。

e工幡/，3.4常用的調(diào)度算法

優(yōu)先級調(diào)度的問題：可能會出現(xiàn)低優(yōu)先級進(jìn)程餓

死的現(xiàn)象。

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

待的時間）調(diào)整其優(yōu)先級，即隨著進(jìn)程年齡的增大，

逐步調(diào)高它的優(yōu)先級，從而獲得運行機會。

解決辦法二：當(dāng)進(jìn)程在就緒隊列中等待足夠長后,

躍遷其優(yōu)先級，讓它運行，而后再將其優(yōu)先級降低到

原來的水平。

3.4常用的調(diào)度算法

例：Windows的線程有兩個優(yōu)先級：

BasePriority和CurrentPriority,其中

BasePriority是從進(jìn)程中繼承來的，但可

以通過系統(tǒng)調(diào)用修改；CurrentPriority

是動態(tài)變化的，從工到工5。

3.4常用的調(diào)度算法

Windows的線程調(diào)度程序采用多級就緒隊列。

Windows提供了32個優(yōu)先級，因而有32個就緒隊列。

其中0到15用于普通線程，16到31用于實時進(jìn)程。

在下列情況下，線程的優(yōu)先級會躍遷：

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

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

餓。

3.4常用的調(diào)度算法

六、多級隊列法

系統(tǒng)中的進(jìn)程對調(diào)度的要求是不一樣的O

如在前臺運行的進(jìn)程通常是交互式的，需要短的

響應(yīng)時間；而在后臺運行的進(jìn)程通常是服務(wù)器進(jìn)程，

需要短的周轉(zhuǎn)時間。所以，前臺進(jìn)程的輪轉(zhuǎn)應(yīng)快，時

間片應(yīng)短；而后臺進(jìn)程的輪轉(zhuǎn)可慢，時間片應(yīng)長。

因此，應(yīng)根據(jù)進(jìn)程的實際情況將其分組，每組進(jìn)

程采用適當(dāng)?shù)恼{(diào)度算法。

3.4常用的調(diào)度算法

基本思想：

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

獨立的調(diào)度算法。

2、根據(jù)進(jìn)程的某些特性，如類型、優(yōu)先

級等，永久性地把進(jìn)程鏈入某一隊列。

3、整個系統(tǒng)（隊列之間）采用另外的調(diào)

度算法，如固定優(yōu)先級的搶占式調(diào)度或

規(guī)定各個隊列占用CPU的比例。

3.4常用的調(diào)度算法

高優(yōu)先級輪轉(zhuǎn)

------?系統(tǒng)進(jìn)程-----

---------1交互進(jìn)程-----

低優(yōu)先級程FCFS

3.4常用的調(diào)度算法

七、多級反饋隊列法

基本思想：給剛就緒的進(jìn)程以最高的優(yōu)先

級，讓它盡快投入運行；在進(jìn)程的運行過程中

不斷地降低其優(yōu)先級，即進(jìn)程運行時間越長，

它的優(yōu)先級就越低。

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

長度不同，采用的調(diào)度算法也可不同。

第一級隊列（高）

RR終止

>

第二級隊列

RR終止

第N級隊列（低）FCFS

，處理器?終止

3.4常用的調(diào)度算法

將就緒隊列分為N個，每個就緒隊列一個優(yōu)先級。

給每個就緒隊列分配不同的時間片。隊列的優(yōu)先

級越高，時間越短；優(yōu)先級越低，時間片越長。

最低優(yōu)先級隊列采用FCFS調(diào)度算法，其它隊列采

用時間片輪轉(zhuǎn)調(diào)度算法。

第一次就緒的進(jìn)程進(jìn)入第一級隊列（優(yōu)先級最

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

系統(tǒng)從第一級隊列開始調(diào)度，當(dāng)?shù)谝患墳榭諘r，

轉(zhuǎn)向第二個隊列，依次類推。

運行進(jìn)程用完一個時間片后，進(jìn)入下一級就緒隊

列。

高優(yōu)先級進(jìn)程就緒時，可以搶占CPU,被搶占的

進(jìn)程回到原就緒隊列的隊尾。

3.4常用的調(diào)度算法

多級反饋隊列法特點：

允許進(jìn)程在各隊列之間移動。

比較照顧新的、小的進(jìn)程，小進(jìn)程能盡快得到處

理器。

進(jìn)程等待的時間不計算在內(nèi)，因此等待工/O操作

的進(jìn)程不會被降級。

長進(jìn)程的優(yōu)先級會被逐漸降低，因而獲得處理器

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

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

進(jìn)程之間允許搶占，所以短進(jìn)程的響應(yīng)時間不會

太長。

3.5多處理器調(diào)度

多處理器系統(tǒng)的調(diào)度有自己獨特的要求。

有多種形式的多處理器系統(tǒng)，如：

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

的內(nèi)存、I/O通道等。

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

工/O處理器等，處理器之間有主從關(guān)系。

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

物理內(nèi)存，由一個操作系統(tǒng)集中控制。

考慮第三種形式的多處理器系統(tǒng)。

e工幡/，3.5多處理器調(diào)度

多處理器調(diào)度時需要考慮如下問題：

1、如何為進(jìn)程指派處理器？

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

3、如何調(diào)度和切換進(jìn)程？

3.5多處理器調(diào)度

把處理器看成處理器池。

如何指派處理器？

(1)靜態(tài)。在進(jìn)程創(chuàng)建時為其指派處理

器，此后該進(jìn)程就在指派的處理器上運行。

(2)動態(tài)。進(jìn)程可以在任意一個空閑的

處理器上運行。

3.5多處理器調(diào)度

誰來指派處理器？

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

它負(fù)責(zé)處理器的指派。簡單。

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

每個處理器自己選擇進(jìn)程。復(fù)雜。

3.5多處理器調(diào)度

是否允許多道程序？

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

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

(2)如果進(jìn)程之間的關(guān)系很密切(有大量的交

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

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

用程序的性能。

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

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

3.5多處理器調(diào)度

如何選擇下一個運行的進(jìn)程？

(1)所有處理器共用