第三章 處理機調(diào)度與死鎖習題課

1、第三章 處理機調(diào)度與死鎖1、系統(tǒng)出現(xiàn)死鎖是因為 (若干進程因競爭資源而無休止的等待著其他進程釋放已占有的資源)。2、某系統(tǒng)中有5個并發(fā)進程，都需要同類資源3個，試問該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是（ 11 ）。3、發(fā)生死鎖現(xiàn)象的原因有_競爭資源_和_進程推進順序非法_。通常不采用( 從非死鎖進程處搶奪資源 )方法來解除死鎖。4、某系統(tǒng)中有4個并發(fā)進程，都需要同類資源3個，試問該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是( 9 )。5、死鎖產(chǎn)生的4個必要條件是： 互斥 、 不可剝奪 、_請求和保持_ 和環(huán)路等待條件。6、作業(yè)在系統(tǒng)中存在與否的唯一標志是作業(yè)控制塊7、某計算機系統(tǒng)中有8臺打印機,有K個進程競爭

2、使用,每個進程最多需要3臺打印機.該系統(tǒng)可能會發(fā)生死鎖的K的最小值是( 4 )8、產(chǎn)生系統(tǒng)死鎖的原因可能是由于 （多個進程競爭資源出現(xiàn)了循環(huán)等待）9、系統(tǒng)中有3個進程，每個進程需2臺打印機，如果系統(tǒng)配有4臺打印機，則系統(tǒng)_不可能_出現(xiàn)死鎖的情況（本題要判斷出現(xiàn)死鎖的可能性：可能或不可能）。10、什么是死鎖？產(chǎn)生死鎖的必要條件是什么？處理死鎖的基本方法有哪些？ 答：死鎖是兩個或兩個以上進程由于競爭資源而處于的僵持狀態(tài)，在這種僵持狀態(tài)下若沒有外力作用，所有進程都無法正常向前推進。（ 必要條件：（1）互斥條件（2）請求和保持條件（3）不剝奪條件（4）環(huán)路等待條件 處理方法：預防死鎖、避免死鎖、檢測死

3、鎖、解除死鎖。11、死鎖定理的含義是什么？試簡化下圖進程資源圖，并利用死鎖定理給出相應的結(jié)論。P1P2R1R2答：死鎖定理：當且僅當資源分配圖是不可完全簡化的。 R1資源有3個，R2資源有2個；P1進程：占有2個R1，申請1個R2；P2進程占有1個R1，1個R2，申請1個R1；目前系統(tǒng)只有一個R2空閑；P1是一個既不孤立又不阻塞的進程，消去P1的邊，有2個R1,1個R2空閑，能滿足P2申請，使P2成為既不孤立又不阻塞的進程，所以消去P2的邊，由死鎖定理知，不會產(chǎn)生死鎖。12、4個進程的提交、運行時間如下表所示。若采用（1）先來先服務算法；（2）最高響應比優(yōu)先調(diào)度算法，試求出進程的執(zhí)行順序，進程

4、的開始時間、完成時間、周轉(zhuǎn)時間及進程的平均周轉(zhuǎn)時間。進程的提交與運行時間表（十進制） 進程提交時間運行時間P18.02.0P28.40.3P38.60.1P49.00.2答：（1）先來先服務算法進程提交時間運行時間開始時間完成時間周轉(zhuǎn)時間P18.02.08.010.02.0P28.40.310.010.31.9P38.60.110.310.41.8P49.00.210.410.63分1.6平均周轉(zhuǎn)時間=（2+1.9+1.8+1.6）/41.825（1分）（2）最高響應比優(yōu)先調(diào)度算法進程提交時間運行時間開始時間完成時間周轉(zhuǎn)時間P18.02.08.010.02.0P28.40.310.110.42

5、.0P38.60.110.010.11.5P49.00.210.410.63分1.6a. P2響應比=1+(10-8.4)/0.3=6.3 P3響應比=1+（10-8.6）/0.1=15 P4響應比=1+(10-9)/0.2=6因為P3響應比最高，所以執(zhí)行進程3； b.P2響應比=1+(10.1-8.4)/0.3=6.7 P4響應比=1+(10.1-9)/0.2=6.5因為P2響應比最高，所以執(zhí)行進程2； （2分）平均周轉(zhuǎn)時間=（2.0+2.0+1.5+1.6）/4=1.775 （1分）13、設系統(tǒng)中有3中類型的資源（A,B,C）和5個進程P1、P2、P3、P4、P5，A類資源的數(shù)目為17，B

6、類資源的數(shù)目為5，C類資源的數(shù)目為20。在T0時刻系統(tǒng)狀態(tài)如下表所示。系統(tǒng)采用銀行家算法實施死鎖避免策略。進程資源情況Max A B CAllocation A B CAvailable A B CP15 5 92 1 22 3 3P25 3 64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 0 4（1）T0時刻是否為安全狀態(tài)？若是，給出安全序列。（2）若在T0時刻進程P2請求資源（0，3，4），是否能實施資源分配？為什么？解答：1）由題目所給出的最大資源需求量和已分配的資源數(shù)量，可以計算出T0時刻各進程的資源需求量Need，NeedMax-Allocation，

7、利用銀行家算法對T0時刻的資源分配情況進行分析，可得此時的安全性分析情況，如下表：進程資源情況WorkA B CNeedA B CAllocationA B CWork+AllocationA B CFinishP52 3 31 1 03 1 45 4 7TP45 4 72 2 12 0 47 4 11TP37 4 110 0 64 0 511 4 16TP211 4 161 3 44 0 215 4 18TP115 4 183 4 72 1 217 5 20T從T0的安全性分析中可以看出，存在一個安全序列 P5、P4、P3、P2、P1，故T0時刻的狀態(tài)是安全的。（8分） （2）若在T0時刻進

8、程P2請求資源（0，3，4），因請求資源數(shù)（0，3，4）大于剩余資源數(shù)（2，3， 3），所以不能分配。（2分）14、若系統(tǒng)運行中出現(xiàn)如下表所示的資源分配情況，該系統(tǒng)是否安全？若是，給出安全序列；如果進程P2此時提出資源申請（1，2，2，2），系統(tǒng)能否將資源分配給它？為什么？ 資源情況進程Allocation(已分配資源數(shù))Need(還需要資源數(shù))Available(系統(tǒng)可以分配資源數(shù))P00 0 3 20 0 1 21 6 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6答：（1）利用安全性算法對此刻的資源分

9、配情況進行如下表的安全性檢：資源情況進程WorkNeedAllocationWork+AllocationP01 6 2 20 0 1 20 0 3 21 6 5 4P31 6 5 40 6 5 20 3 3 21 9 8 6P41 9 8 60 6 5 60 0 1 41 9 9 10P11 9 9 101 7 5 01 0 0 02 9 9 10P22 9 9 102 3 5 61 3 5 43 12 14 14從表中可以看出，此時存在一個安全序列P0,P3,P4,P1,P2，故系統(tǒng)是安全的。（7分）（2）P2請求資源（1，2，2，2）<= P2需求資源（2，3，5，6）&&

10、lt;=剩余資源數(shù)（1，6， 2，2）資源情況進程AllocationNeedAvailableP00 0 3 20 0 1 20 4 0 0P11 0 0 01 7 5 0P22 5 7 61 1 3 4P30 3 3 20 6 5 2P40 0 1 40 6 5 6此時，可利用資源（0，4，0，0）已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，故不能將資源分配給P2。15、系統(tǒng)中有四個進程 P0 , P1 , P2 , P3 和三類資源A , B , C，各種資源的數(shù)量分別為10，5，5，在T0時刻的資源分配情況如圖所示，且已知T0時刻處于安全狀態(tài)。在T1時刻，如果進程P1發(fā)出請求向量R

11、equest1(1,0,2)，試用銀行家算法說明系統(tǒng)能否將資源分配給它？ 資源情況進程MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P37 5 33 2 29 0 22 2 20 1 02 0 03 0 22 1 1 7 4 31 2 26 0 00 1 13 3 2答：進程P1發(fā)出請求向量Request1(1,0,2)，系統(tǒng)按銀行家算法進行檢查：（1）Request1(1,0,2)Need1(1,2,2)；（1分）（2）Request1(1,0,2)Available(3,3,2)；（1分）（3）系統(tǒng)先假定可為P1分配資源，并修改Available1，Allocation，Need1向量，由此形成的資源變化情況如表所示： 資源情況進程MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P37 5 33 2 29 0 22 2 20 1 03 0 23 0 22 1 1 7 4 30 2 06 0 00 1 12 3 0（3分）（4）再利用安全性算法檢查此時系統(tǒng)是否安全，過程如下所示： 資源情況進程WorkNeedAllocationWork+ AllocationFinishA B CA B C