操作系統(tǒng)第3章處理器管理

第三章處理器管理

要求：

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

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

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

時間）。

處理器管理的任務

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

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

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

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

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

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

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

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

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

棄或被搶占）

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

誰來保存？

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

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

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

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

次的工作？

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

問題如下：

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

該獲得處理器的進程。

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

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

中？

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

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

的控制權(quán)？

處理器管理的任務

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

倜度。

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

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

進入主機運行。

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

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

理器資源的回收問題。

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

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

多個作業(yè)。

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

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

（它們）進入主機，為它們創(chuàng)建進程，準

備運行。

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

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

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

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

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

進入主機的作業(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)

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

將處理器分配給它。

兩者的關系如下圖:

時間片用完

備

后

業(yè)

作

列

隊

等待

隊列

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

作業(yè)調(diào)度與進程調(diào)度的關系

1）功能不同

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

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

度執(zhí)行頻繁。

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

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

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

分并行。

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

進程調(diào)度程序。

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

通過鍵盤、鼠標等直接創(chuàng)建和啟動進程,

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

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

度。

3.2進程調(diào)度

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

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

實際的CPU

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

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

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

回收問題。

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

的控制權(quán)。

1、進程請求操作系統(tǒng)服務

2、進程終止,中斷

3、進程運行出錯

4、外部中斷>

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

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

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

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

給另一個進程。

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

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

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

器的控制權(quán)。

再考慮進程的切換問題。

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

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

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

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

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

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

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

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

1、直接caII或jmp一個TSS。

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

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

的進程？

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

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

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

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

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

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

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

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

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

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

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

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

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

于當前進程。

4、當前進程終止。

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

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

(nonpreemptive)。

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

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

出于進程的自愿。

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

要考慮太多的保護。

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

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

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

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

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

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

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

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

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

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

的優(yōu)先級較高，當前進程只是收到一個標志

(need_resched)。

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

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

Windows2000等。

3.3性能評價標準

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

1、應保證實現(xiàn)系統(tǒng)的設計目標。

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

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

源都同時得到利用。

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

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

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

算法的評價標準

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

統(tǒng)的。

1、面向用戶的評價標準

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

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

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

輸出的時間。

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

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

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

好的調(diào)度算法應盡量減少進程等待調(diào)度

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

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

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

那么好的調(diào)度算法應盡可能的滿足各進程的

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

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

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

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

何。

e工幡/，

2、面向系統(tǒng)的評價標準

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

(進程)數(shù)量。

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

最大化處理器的利用率。

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

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

e工幡/，

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

器有多忙。

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

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

要。

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

的等待時間。

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

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

的等待時間。

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

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

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

到照顧。

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

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

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

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

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

程選擇算法)。

一、先來先服務(FCFS)

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

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

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

運行的進程。

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

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

別為24、3、3o

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

PlP2P3

0242730

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

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

17o

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

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

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

間較長?；蛘哒f，短進程得到的服務要比長

進程差。

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

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

0.11(3/27)o

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

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

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

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

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

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

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

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

忙型進程。

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

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

P2P3P1

03630

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

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

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

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

回顧

處理機管理

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

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

準備運行。

進程調(diào)度

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

給它。

回顧

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

1、先來先服務(FCFS)

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

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

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

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

6、多級隊列法

7、多級反饋隊列法

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

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

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

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

行時間最短的進程。

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

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

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

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

P2PlP4P3

0391624

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

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

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

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

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

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

可能會餓死長進程。

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

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

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

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

處理？

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

就緒的進程。

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

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

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

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

式SPN。

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

優(yōu)先(ShortestRemainingTime

First)o

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

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

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

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

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)度程序從就緒隊列中的第一

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

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

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

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

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

工作。

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

等待狀態(tài)。

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

它的CPU被剝奪。

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

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

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

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

3、3o

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

PlP2P3PlPlPlPlPl

047101418222630

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

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

5.666o

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

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

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

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

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

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

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

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

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

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

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

外開銷。

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

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

120ms（服務器）o

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

的時間。

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

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

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

時，與響應時間成正比。

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

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

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

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

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

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

片不能太短。

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

可以短。

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

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

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

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

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

的感覺。

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

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

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

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

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

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

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

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

到就緒隊列的隊頭。

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

I/O

兀

成

I/O隊列n

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

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

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

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

轉(zhuǎn)。

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

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

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

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

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

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

五、優(yōu)先級

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

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

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

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

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

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

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

早到達者(FCFS)o

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

多就緒隊列。

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

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

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

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

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

先級？

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

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

一旦確定就不再改變。

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

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

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

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

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

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

等。

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

由用戶指定。

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

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

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

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

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

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

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

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

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

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

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

非搶占的。

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

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

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

珀奧tro

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

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

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

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

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

是否高于當前進程，都不觸發(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)先級進程餓

死的現(xiàn)象。

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

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

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

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

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

原來的水平。

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

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

BasePriority和CurrentPriority,其中

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

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

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

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

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

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

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

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

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

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

餓。

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

六、多級隊列法

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

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

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

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

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

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

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

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

基本思想：

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

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

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

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

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

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

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

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

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

------?系統(tǒng)進程-----

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

低優(yōu)先級程FCFS

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

七、多級反饋隊列法

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

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

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

它的優(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)度算法。

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

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

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

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

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

列。

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

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

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

多級反饋隊列法特點：

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

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

理器。

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

的進程不會被降級。

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

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

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

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

太長。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

把處理器看成處理器池。

如何指派處理器？

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

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

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

處理器上運行。

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

誰來指派處理器？

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

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

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

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

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

是否允許多道程序？

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

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

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

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

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

用程序的性能。

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

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

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

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

(1)所有處理器共用