1、第3章 處理機調(diào)度與死鎖3.1 典型例題解析【例1】（1）3個進程共享4個同種類型的資源，每個進程最大需要2個資源，請問系統(tǒng)是否會因為競爭該資源而死鎖？（2）n個進程共享m個同類資源，若每個進程都需要用該類資源，而且各進程對該類資源的最大需求量之和小于m+n。說明該系統(tǒng)不會因競爭該類資源而阻塞。（3）在（2）中，如果沒有“每個進程都需要用該類資源”的限制，情況又會如何？（西北工業(yè)大學(xué)2000年考題）答：（1）該系統(tǒng)不會因為競爭該類資源而死鎖。因為，必有一個進程可獲得2個資源，故能順利完成，并釋放出其所占用的2個資源給其他進程使用，使它們也順利完成。（2）用Max(i)表示第i個進程的最大資源需

2、求量，need（i）表示第i個進程還需要的資源量，alloc(i)表示第i個進程已分配的資源量。由題中所給條件可知：need（i）0(對所有的i)max(1)+max(i)+max(n) m+n如果在這個系統(tǒng)中發(fā)生了死鎖，則意味著已有一個以上的進程因申請不到該類資源而無限阻塞，而m個資源應(yīng)該全部分配出去，即alloc(1)+alloc(i)+alloc(n)=m 因此need(1)+need(i)+need(n)=max(1)+max(i)+max(n)-alloc(1)+alloc(i)+alloc(n)m+n-m即need(1)+need(i)+need(n)n這樣，至少必須存在一個進程，

3、其need(i)0，這顯然與題意不符，所以該系統(tǒng)不可能因競爭該類資源而進入死鎖狀態(tài)。（3）此時系統(tǒng)可能發(fā)生死鎖，如n=4,m=3時，若P1的Max為0，而其余三個進程的Max都為2，則仍然滿足最大需求量之和（即6）小于m+n（即7）的要求，但當(dāng)除P1以外的其余三個進程各得到一個資源時，這三個進程將進入死鎖狀態(tài)?！纠?】設(shè)系統(tǒng)中有3種類型的資源A、B、C和5個進程P0、P1、P2、P3、P4，A資源的數(shù)量為10，B資源的數(shù)量為5，C資源的數(shù)量為7。在T0時刻系統(tǒng)狀態(tài)如下表所示。系統(tǒng)采用銀行家算法實施死鎖避免策略。MaxAllocationNeedAvailableABCABCABCABCP0P1

4、P2P3P4753010743332322200122902302600222211011433002431（1）T0時刻是否為安全狀態(tài)？若是，請給出安全序列。（2）在T0時刻若進程P1發(fā)出資源請求Request（1，0，2），是否能夠?qū)嵤┵Y源分配？（3）在的基礎(chǔ)上P4發(fā)出資源請求Request（3，3，0），是否能夠?qū)嵤┵Y源分配？（4）在的基礎(chǔ)上P0發(fā)出資源請求Request（0，2，0），是否能夠?qū)嵤┵Y源分配?答：(1) 利用銀行家算法對T0時刻的資源分配情況進行分析，可得此時刻的安全性分析情況:WorkNeedAllocationWork+AllocationFinishABCABCAB

5、CABCP1332122200532TrueP3532011211743TrueP4743431002745TrueP27456003021047TrueP010477430101057True可知，在T0時刻存在著一個安全序列P1、P3、P4、P2、P0，故系統(tǒng)是安全的。（2）P1請求資源Request（1，0，2），系統(tǒng)按銀行家算法進行檢查：Request（1，0，2）Need（1，2，2）Request（1，0，2）Available（3，3，2）系統(tǒng)試探分配，修改相應(yīng)的向量，形成的資源變化情況如下表所示：MaxAllocationNeedAvailableABCABCABCABCP07

6、53010743230P1322302020P2902302600P3222211011P4433002431在利用安全性算法檢查此時系統(tǒng)是否安全，如下表所示：WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532TrueP3532011211743TrueP4743431002745TrueP0745743010755TrueP27556003021057True由安全性算法檢查可知，可以找到一個安全序列P1、P3、P4、P0、P2。因此，系統(tǒng)是安全的，可以立即把P1所申請的資源分配給它。（3）P4發(fā)出資源請求Req

7、uest（3，0，0），系統(tǒng)按照銀行家算法進行檢查：Request（3，3，0）Need（4，3，1）Request（3，3，0）Available（2，3，0），所以讓P4等待。（4）P0發(fā)出資源請求Request（0，2，0），系統(tǒng)按照銀行家算法進行檢查：Request（0，2，0）Need（7，4，3）Request（0，2，0）Available（2，3，0）系統(tǒng)試探分配，修改相應(yīng)的向量，形成的資源變化情況如下表所示：AllocationNeedAvailableABCABCABCP0030723210P1302020P2302600P3211011P4002431進行安全性檢查，可用

8、資源Available（2，1，0）已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。3.2 練習(xí)題一、 單項選擇題1. 任何時刻總是讓具有最高優(yōu)先數(shù)的進程占用處理器，此時采用的進程調(diào)度算法是（）。A.非搶占式的優(yōu)先數(shù)調(diào)度算法B.時間片輪轉(zhuǎn)調(diào)度算法C.先來先服務(wù)調(diào)度算法D.搶占式的優(yōu)先數(shù)調(diào)度算法2. 搶占式的優(yōu)先數(shù)調(diào)度算法在（）中很有用。A.網(wǎng)絡(luò)操作系統(tǒng)B.分布式系統(tǒng)C.批處理系統(tǒng)D.實時系統(tǒng)3. 下列算法中，（）只能采用非搶占調(diào)度方式，（）只能采用搶占調(diào)度方式，而其余的算法既可采用搶占方式，也可采用非搶占方式。A.高優(yōu)先權(quán)優(yōu)先法B.時間片輪轉(zhuǎn)法C.FCFS調(diào)度算法D.短作業(yè)

9、優(yōu)先算法4. 下列進程調(diào)度算法中，綜合考慮進程等待時間和執(zhí)行時間的是（）。A.時間片輪轉(zhuǎn)調(diào)度算法B.短進程優(yōu)先調(diào)度算法 C.先來先服務(wù)調(diào)度算法D.高響應(yīng)比優(yōu)先調(diào)度算法 5. 進程調(diào)度的關(guān)鍵問題是（ ）A.時間片大小B.進程調(diào)度算法C.CPU速度D.內(nèi)存空間利用率6. 下列選項中，降低進程優(yōu)先權(quán)級的合理時機是（）。A.進程的時間片用完B.進程剛完成I/O，進入就緒隊列C.進程長期處于就緒隊列中D.進程從就緒狀態(tài)轉(zhuǎn)為運行態(tài)7. 采用時間片輪轉(zhuǎn)調(diào)度算法是為了（）A.多個終端用戶能得到系統(tǒng)的及時響應(yīng)B.先來先服務(wù)C.CPU最短的進程先執(zhí)行D.優(yōu)先級高的進程能得到及時調(diào)度8. 下面關(guān)于優(yōu)先權(quán)大小的敘述中

10、正確的是（）。A.用戶進程的優(yōu)先權(quán)，應(yīng)高于系統(tǒng)進程的優(yōu)先權(quán)B.在動態(tài)優(yōu)先權(quán)中，隨著作業(yè)的等待時間的增加，其優(yōu)先權(quán)將隨之增加C.資源要求多的作業(yè)，其優(yōu)先權(quán)應(yīng)高于資源要求少的作業(yè)D.長作業(yè)的優(yōu)先權(quán)，應(yīng)高于短作業(yè)的優(yōu)先權(quán)9. 作業(yè)調(diào)度算法的選擇常考慮的因素之一是使系統(tǒng)有最高的吞吐量，為此應(yīng)（）。A.不讓處理機空閑B.能夠處理盡可能多的作業(yè)C.使用戶們都滿意D.不使磁頭過于復(fù)雜10. 在各種作業(yè)調(diào)度算法中，若所有作業(yè)同時到達，則平均等待時間最短的算法是（）。A.先來先服務(wù)B.高優(yōu)先權(quán)優(yōu)先C.短作業(yè)優(yōu)先D.高響應(yīng)比優(yōu)先11. 作業(yè)調(diào)度程序從（）隊列中選取適當(dāng)?shù)淖鳂I(yè)投入運行。A.就緒 B.提交 C.運行

11、D.后備12. 在批處理系統(tǒng)中，用戶的作業(yè)是由（）組成的。A.程序 B.程序+數(shù)據(jù)+作業(yè)說明書 C.程序+作業(yè)說明書D.程序+數(shù)據(jù)13. 假設(shè)下述四個作業(yè)同時到達，當(dāng)使用最高優(yōu)先數(shù)優(yōu)先調(diào)度算法時，作業(yè)的平均周轉(zhuǎn)時間為（）。作業(yè)所需運行時間優(yōu)先數(shù)124259381438A. 4.5B. 10.5C. 4.75D. 10.2514. 一作業(yè)8：00到達系統(tǒng)，估計運行時間為1小時，若10：00開始執(zhí)行該作業(yè)，其響應(yīng)比是（）。A. 2B. 1C. 3D. 0.515. 下面哪個算法適用于分時系統(tǒng)中的進程調(diào)度（）。A.FCFSB.時間片輪轉(zhuǎn)C.CPU為主的優(yōu)先D.動態(tài)優(yōu)先數(shù)法16. 在多道批處理系統(tǒng)中，

12、為充分利用各種資源，運行的程序應(yīng)具備的條件是（）。A.適應(yīng)于內(nèi)存分配的B.計算量大的 C.I/O量大的D.計算型和I/O型均衡的17. 下面的敘述中正確的是（）。A.安全狀態(tài)是沒有死鎖的狀態(tài)，非安全狀態(tài)是有死鎖的狀態(tài)。 B.安全狀態(tài)是可能有死鎖的狀態(tài)，非安全狀態(tài)也是可能有死鎖的狀態(tài)C.安全狀態(tài)是可能沒有死鎖的狀態(tài)，非安全狀態(tài)是有死鎖的狀態(tài)D.安全狀態(tài)是沒有死鎖的狀態(tài)，非安全狀態(tài)是可能有死鎖的狀態(tài)18. 除了進程競爭資源，因為資源不足可能出現(xiàn)死鎖以外，不適當(dāng)?shù)模ǎ┮部赡墚a(chǎn)生死鎖。A.進程優(yōu)先權(quán)B.資源的線性分配C.進程推進順序D.分配隊列優(yōu)先權(quán)19. 發(fā)生死鎖的必要條件有四個，要防止死鎖的發(fā)生，

13、可以破壞這四個必要條件，但破壞（）條件是不太實際的。A.互斥B.請求和保持C.不剝奪D.環(huán)路等待20. 除了可以采用資源剝奪法解除死鎖，還可以采用（）方法解除死鎖。A.修改信號量 B.拒絕分配新的資源C.撤銷進程 D.執(zhí)行并行操作21. 資源的按序分配策略可以破壞（）條件。A.互斥 B.請求和保持C.不剝奪 D.環(huán)路等待22. 在（）的情況下，系統(tǒng)出現(xiàn)死鎖。A.計算機系統(tǒng)發(fā)生了重大故障B.有多個阻塞的進程存在C.若干個進程因競爭資源而無休止地相互等待他方釋放已占有的資源D.資源數(shù)大大小于進程數(shù)或進程同時申請的資源數(shù)大大超過資源總數(shù)23. 某系統(tǒng)中有3個并發(fā)進程，都需要同類資源4個，試問該系統(tǒng)不

14、會發(fā)生死鎖的最少資源數(shù)是（）。A. 9 B. 10C. 11 D. 1224. 某計算機系統(tǒng)中有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該系統(tǒng)可能會發(fā)生死鎖的K的最小值是（）。A. 2 B. 3 C. 4 D. 5 解析：3k k4（n個進程共享m個同類資源，若每個進程都需要用該類資源，而且各進程對該類資源的最大需求量之和小于m+n。則該系統(tǒng)不會因競爭該類資源而阻塞。）25. 銀行家算法是一種（）算法。A.解除死鎖 B.避免死鎖C.預(yù)防死鎖 D.檢測死鎖二、填空題1進程調(diào)度程序按_從_中選擇一個進程; 從而使之占用處理器運行。2進程調(diào)度算法常用的有_、_ 、_ 、高優(yōu)先權(quán)優(yōu)

15、先等幾種。3進程的調(diào)度方式有兩種，一種是_，另一種是_。4在_調(diào)度算法中，按照進程進入就緒隊列的先后順序來分配處理機。5死鎖是指在系統(tǒng)中的多個_無限期等待永遠(yuǎn)也不會發(fā)生的條件。6死鎖產(chǎn)生的四個必要條件是_、_、_和_ 。7銀行家算法中，當(dāng)一個進程提出的資源請求將導(dǎo)致系統(tǒng)從_ 狀態(tài)進入_狀態(tài)時，系統(tǒng)就拒絕它的資源請求。8對待死鎖，一般應(yīng)考慮死鎖的預(yù)防、避免、檢測和解除四個問題。典型的銀行家算法是屬于_，破壞環(huán)路等待條件是屬于_，而剝奪資源是_的基本方法。三、計算題1、有4個進程P1，P2，P3，P4，它們進入就緒隊列的先后次序為P1、P2、P3、P4，它們的優(yōu)先數(shù)和需要的處理器時間如下表所示。假

16、定這四個進程執(zhí)行過程中不會發(fā)生等待事件，忽略進行調(diào)度等所花費的時間，從某個時刻開始進程調(diào)度，請回答下列問題：寫出分別采用“先來先服務(wù)”調(diào)度算法選中進程執(zhí)行的次序、計算出各進程在就緒隊列中的等待時間以及的平均等待時間；寫出分別采用“非搶占式的優(yōu)先數(shù)”（固定優(yōu)先數(shù)）調(diào)度算法選中進程執(zhí)行的次序、計算出各進程在就緒隊列中的等待時間以及平均等待時間；寫出分別采用“時間片輪轉(zhuǎn)”（時間片大小為5）調(diào)度算法選中進程執(zhí)行的次序、計算出各進程在就緒隊列中的等待時間以及平均等待時間。進 程處理器時間優(yōu)先數(shù)P183P261P3225P4442、在一個批處理單道系統(tǒng)中，采用響應(yīng)比高者優(yōu)先的作業(yè)調(diào)度算法。當(dāng)一個作業(yè)進入系

17、統(tǒng)后就可以開始調(diào)度，假定作業(yè)都是僅計算，忽略調(diào)度花費的時間。現(xiàn)有三個作業(yè)，進入系統(tǒng)的時間和需要計算的時間如表所示：作業(yè)進入系統(tǒng)時間需要計算時間開始時間完成時間周轉(zhuǎn)時間19:0060分鐘29:1045分鐘39:2525分鐘（1）求出每個作業(yè)的開始時間、完成時間及周轉(zhuǎn)時間并填入表中。（2）計算三個作業(yè)的平均周轉(zhuǎn)時間應(yīng)為多少？3、一系統(tǒng)具有150個存儲單元，在T0時刻系統(tǒng)按下表所示分配給3個進程。T0時刻系統(tǒng)資源分配狀態(tài)表進程Maximum demandCurrent allocationP17025P26040P36045對下列請求應(yīng)用銀行家算法分別分析判定是否安全？（1）第4個進程P4到達，最大

18、需求60個存儲單元，當(dāng)前請求分配25個單元。（2）第4個進程P4到達，最大需求50個存儲單元，當(dāng)前請求分配35個單元。如果是安全的，請給出一個可能的進程安全執(zhí)行序列；如果是不是安全的，請說明原因。四、問答題1、何謂死鎖？產(chǎn)生死鎖的原因和必要條件是什么？2、下列程序執(zhí)行結(jié)果中a=？為什么？a=55;pid=fork();if (pid= =0)a=99;exit(0);elsewait(NULL);printf(“a=%dn”,a);參考答案一、 單項選擇題1-5: DD CB DB6-10: AABBC11-15: DBDCB16-20: DDCAC21-25: DCBCB二、填空題 1某種調(diào)度算法 就緒隊列2先來先服務(wù) 短進程優(yōu)先 時間片輪轉(zhuǎn)調(diào)度算法3剝奪式 非剝奪式4先來先服務(wù)5進程6互斥 請求和保持 不剝奪 環(huán)路等待7安全狀態(tài) 不安全狀態(tài)8避免死鎖 預(yù)防死鎖 解除死鎖三、計算題1、答：先來先服務(wù)算法選擇進程的順序依次為P1、P2、P3、P4。進程P1等待時間為0；進程P2等待時間為8；進程P3等待時間為8+6=14；進程P4等待時間為8+6+22=36。平均等待時間為（0+8+14+36）/4=14.5非搶占式的優(yōu)先數(shù)算法選擇進程的順序依次為P3、P4、P1、P2。進程P1等待時間