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

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

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

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

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

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

6、類資源的數(shù)目為5，C類資源的數(shù)目為20。在T0時(shí)刻系統(tǒng)狀態(tài)如下表所示。系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。進(jìn)程資源情況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時(shí)刻是否為安全狀態(tài)？若是，給出安全序列。（2）若在T0時(shí)刻進(jìn)程P2請(qǐng)求資源（0，3，4），是否能實(shí)施資源分配？為什么？解答：1）由題目所給出的最大資源需求量和已分配的資源數(shù)量，可以計(jì)算出T0時(shí)刻各進(jìn)程的資源需求量Need，NeedMax-Allocation，

7、利用銀行家算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析，可得此時(shí)的安全性分析情況，如下表：進(jìn)程資源情況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的安全性分析中可以看出，存在一個(gè)安全序列 P5、P4、P3、P2、P1，故T0時(shí)刻的狀態(tài)是安全的。（8分） （2）若在T0時(shí)刻進(jìn)

8、程P2請(qǐng)求資源（0，3，4），因請(qǐng)求資源數(shù)（0，3，4）大于剩余資源數(shù)（2，3， 3），所以不能分配。（2分）14、若系統(tǒng)運(yùn)行中出現(xiàn)如下表所示的資源分配情況，該系統(tǒng)是否安全？若是，給出安全序列；如果進(jìn)程P2此時(shí)提出資源申請(qǐng)（1，2，2，2），系統(tǒng)能否將資源分配給它？為什么？ 資源情況進(jìn)程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）利用安全性算法對(duì)此刻的資源分

9、配情況進(jìn)行如下表的安全性檢：資源情況進(jìn)程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從表中可以看出，此時(shí)存在一個(gè)安全序列P0,P3,P4,P1,P2，故系統(tǒng)是安全的。（7分）（2）P2請(qǐng)求資源（1，2，2，2）<= P2需求資源（2，3，5，6）&&

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

11、equest1(1,0,2)，試用銀行家算法說明系統(tǒng)能否將資源分配給它？ 資源情況進(jìn)程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答：進(jìn)程P1發(fā)出請(qǐng)求向量Request1(1,0,2)，系統(tǒng)按銀行家算法進(jìn)行檢查：（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向量，由此形成的資源變化情況如表所示： 資源情況進(jìn)程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）再利用安全性算法檢查此時(shí)系統(tǒng)是否安全，過程如下所示： 資源情況進(jìn)程WorkNeedAllocationWork+ AllocationFinishA B CA B C