【正文】 r4答：對該圖進(jìn)行化簡，得到如下圖所示的結(jié)果。由于該圖是不可完全簡化的，所以根據(jù)死鎖定理，系統(tǒng)處于死鎖狀態(tài)。P10P0 r1 r2 r3 r4 P3P4P2(22) 簡述解決死鎖的途徑：1）、預(yù)防死鎖——設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件之一。2）、避免死鎖——資源動態(tài)分配過程中，用某方法防止系統(tǒng)進(jìn)入不安全狀態(tài)。3）、檢測死鎖——允許發(fā)生死鎖，但通過系統(tǒng)設(shè)置的檢測機構(gòu)，檢測死鎖的發(fā)生，并精確確定與死鎖有關(guān)的進(jìn)程和資源。4）、解除死鎖——將進(jìn)程從死鎖狀態(tài)下解脫。 (23) 設(shè)有進(jìn)程P1和P2并發(fā)執(zhí)行，都要享用資源R1，R2，使用資源情況如下：進(jìn)程P1：……申請R1……申請R2……釋放R1……進(jìn)程P2：……申請R2……申請R1……釋放R2……判斷是否會產(chǎn)生死鎖，并解釋其原因。答：在不同的運行推進(jìn)速度下，可能產(chǎn)生死鎖。在某時刻，P1占用R1，又去申請R2；而P2占用R2，又去申請R1；互不釋放自己占用的資源，又得不到自己所需的資源，系統(tǒng)處于僵持狀態(tài)，形成死鎖。(24) 簡述死鎖定理。答：用資源分配圖加以簡化的方法來檢測系統(tǒng)是否處于死鎖狀態(tài)。S為死鎖狀態(tài)的充分條件是，當(dāng)且僅當(dāng)s狀態(tài)的資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。四. 應(yīng)用題(1) 請用信號量實現(xiàn)4*100接力賽的同步過程P1P2P4P3解答： S1 S2 S3PPP3和P4分別代表四位運動員，他們的跑步順序受其位置的限制。從上圖表示可以看出，此題相當(dāng)于是用信號量描述前趨關(guān)系。SSSS4的初值均為0。P1：起跑——前進(jìn)100米——V(S1)P2：P(S1)——起跑——前進(jìn)100米——V(S2)P3：P(S2)——起跑——前進(jìn)100米——V(S3)P4：P(S3)——起跑——前進(jìn)100米——到達(dá)終點(2) 有一發(fā)送者進(jìn)程和一接收者進(jìn)程，其流程如下。s是用于實現(xiàn)進(jìn)程同步的信號量，m是用于實現(xiàn)進(jìn)程互斥的信號量。試完成流程圖。假定緩沖區(qū)有無限多個，s和m的初值為多少？發(fā)送者 接收者 申請緩沖區(qū) C 把信息寫入緩沖區(qū) D A 從消息鏈?zhǔn)兹∫粋€緩沖區(qū) 將緩沖區(qū)放到消息鏈尾 V(m) B 從緩沖區(qū)取出消息 V(s) 釋放緩沖區(qū)解答： s=0表示滿緩沖的數(shù)量、即多少緩沖區(qū)里有消息m=1表示互斥信號量A：P(m) B：V(m) C：P(s) D：P(m)由題意，m用于實現(xiàn)進(jìn)程互斥，初值應(yīng)為1，并應(yīng)成對出現(xiàn)，由接收者進(jìn)程的V(m)操作可知，m用于實現(xiàn)消息鏈存、取緩沖區(qū)操作的互斥，故D為P(m)。相應(yīng)的，A為P(m)，B為V(m)。 由發(fā)送者進(jìn)程可知，當(dāng)發(fā)送者將一個消息放入消息鏈尾后，執(zhí)行V(s)操作，故s表示接收者可取消息的數(shù)量，又因s用于實現(xiàn)進(jìn)程同步，所以接收者接受消息前，應(yīng)判斷是否有消息可以取，需對s執(zhí)行P操作，所以C為P(s)，發(fā)送者發(fā)送消息前，接收者無消息可取，s的初值應(yīng)為0。 (3) 桌上有一只盤子，最多允許存放兩只水果，每次只能放入或取出一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，兩個兒子專等吃盤中的蘋果，兩個女兒專等吃盤中的桔子。試用PV操作實現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。解答：由題意，盤中最多可以放兩只水果，而不管放入的是何種水果，故只要盤中有空位置，父母均可執(zhí)行放水果的操作，即父母的放水果（蘋果、桔子）操作僅取決于盤中是否有空位置。只有盤中有蘋果，兒子才能取，只有盤中有桔子，女兒才能取，即兒女取水果的操作取決于相應(yīng)水果是否存在。從另一個角度講，父親放蘋果與兒子取蘋果要同步，母親放桔子與兒子取桔子要同步，分別需要用同步信號量實現(xiàn)。每次只能向盤子放入或從盤中取出一個水果，用互斥信號量實現(xiàn)。設(shè)置信號量 s1=2，表示盤子中可放水果的空位置； s2=1，表示盤中放、取水果的互斥信號量； s3=0，表示盤中蘋果的數(shù)目； s4=0，表示盤中桔子的數(shù)目；父親： 母親： 兒子： 女兒： P(S1) P(S1) P(S3) P(S4) P(S2) P(S2) P(S2) P(S2)放蘋果 放桔子 取蘋果 取桔子V(S2) V(S2) P(S2) P(S2)V(S3) V(S4) V(S1) V(S1)(4) 在公共汽車上，司機和售票員的活動分別是司機：啟動車輛；正常行車；到站停車；售票員：關(guān)車門；售票；開車門；在汽車不斷到站、停車、行駛過程中，這兩個活動存在著同步關(guān)系，試用信號量和P、V操作實現(xiàn)它們的同步。解答：根據(jù)常識，車門關(guān)好后司機方可啟動車輛，到站停車后售票員方可打開車門，即門的開、關(guān)與車的停、開存在著相互制約的同步關(guān)系。定義信號量 run，表示司機是否可以啟動車輛，也就是車門的狀態(tài)（0表示門開，1表示門關(guān)），初值為0。定義信號量stop表示售票員是否可以開車門，即車是否停好（0表示車停，1表示車開），初值為0。初始狀態(tài)為車停門開。售票員： 上乘客； 關(guān)車門； V(run)。 車門關(guān)好后，run 加1，表明司機可以啟動車輛。 售票； P(stop)。 判斷是否可以開車門；若司機已停車，stop為1，繼續(xù)； 開車門； 若司機未停車，stop為0，阻塞，無法開車門。 下乘客； 司機： P(run)。 判斷是否可以啟動車輛；若售票員已關(guān)門run為1，繼續(xù)； 啟動車輛； 若售票員未關(guān)門run為0，阻塞，無法啟動車輛。 正常行車； 到站停車； V(Stop)。 停車后，stop加1，表明售票員可以開車門。(5) 某寺廟，有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚引用。水缸可容12桶水,水取自同一井中。水井徑窄，每次只能容一個桶取水。水桶總數(shù)為4個。每次入、取缸水僅為一桶，且不可同時進(jìn)行。試給出有關(guān)取水、入水的算法描述。解答：分析題目可知，小和尚負(fù)責(zé)用桶到井中取水并將水倒入缸中，其操作依次為拿桶、井中取水、倒水入缸。水桶只有4個，只有拿到桶后方可繼續(xù)，否則需要等桶，因水井徑窄，每次只能容一個桶取水，故取水的小和尚對水井的訪問必須是互斥的。老和尚負(fù)責(zé)用桶從缸中取水，其操作依次為拿桶、缸中取水。只有拿到桶后方可繼續(xù)，否則需要等桶。每次入、取缸水僅為一桶，且不可同時進(jìn)行，表明小和尚倒水入缸、老和尚取水必須互斥。同時，缸中沒水，老和尚不能取水，要等待小和尚倒水入缸；水缸滿，小和尚不能倒水入缸，要等待老和尚取水，也就是說，小和尚倒水入缸和老和尚取水必須同步。設(shè)置互斥信號量和同步信號量： m1=1，表示小和尚從水井取水時，對水井的互斥訪問，即一次只能有一個水桶進(jìn)出水井；m2=1，表示小和尚倒水入缸、老和尚取水時對水缸的互斥訪問，即每次入、取缸水只能一個桶；count=4，表示是否有桶可以供小和尚、老和尚使用； full=0滿緩沖，表示缸內(nèi)有水的桶數(shù)，控制老和尚取水；empty=12，空緩沖，缸內(nèi)還能放水的桶數(shù)，控制小和尚倒水入缸； P(empty) 判斷缸中是否有倒水的位置，若有，水位1，繼續(xù)； P(count) 判斷是否有水桶可以使用，若有，可用水桶數(shù)目1，繼續(xù)； P(m1) 判斷能否對水井訪問，即是否有其他小和尚從水井取水 從井中取水 互斥控制一個水桶從水井取水； V(m1) P(m2) 判斷能否對水缸訪問，即是否有其他和尚取水或倒水 送水入缸 互斥地將水倒入水缸； V(m2) V(count) 水入缸后，水桶空閑，可供其他和尚使用?？捎盟皵?shù)目+1 V(full) 水入缸后可供老和尚取水，可取水的桶數(shù)+1此題特別要注意P操作的次序，例如：如果P(empty)和P(count)操作次序顛倒，就有可能產(chǎn)生死鎖。若某時刻水缸水滿（empty=0。 full=12），而四個小和尚依次拿水桶去井中取水，此時P(count)均執(zhí)行減1操作，count 的值變?yōu)?，但繼續(xù)執(zhí)行P(empty)時，empty1，empty0，阻塞；此時老和尚想取水，執(zhí)行P(full) ，繼續(xù)，執(zhí)行P(count)，此時couunt1，count0，阻塞，即老和尚沒有水桶可以取水。老和尚無法取水，小和尚無法倒水，形成僵局，死鎖發(fā)生。所以，P操作的順序不可顛倒。小和尚從水井取水入缸老和尚從缸中取水 P(full) 缸中是否有水供老和尚取用；若有，可取水的桶數(shù)1，繼續(xù)； P(count) 判斷是否有水桶可以使用，若有，可用水桶數(shù)目1，繼續(xù)； P(m2) 判斷能否對水缸訪問，即是否有其他和尚取水或倒水 從缸中取水 互斥地從水缸中取水； V(m2) V(empty) 取水后，水缸中增加了倒水的位置，水位+1； V(count) 取水后，水桶空閑，可供其他和尚使用。可用水桶數(shù)目+1 (6) 設(shè)系統(tǒng)中有五個進(jìn)程、3種資源，總數(shù)分別為A 17，B 5，C 20，T0時刻系統(tǒng)狀態(tài)如下。最大資源需求已分配資源剩余資源數(shù)ABCABCABCP1559212233P2536402P34011405P4425204P542431415217i. 完成剩余資源數(shù)的計算：ii. T0時刻是否安全？iii. 若P2請求資源（0，3，4），系統(tǒng)如何處理？解答：T0時刻的向量見圖中粗體數(shù)字。need[i,j]=max[i,j]allocation[i,j]利用銀行家算法對此資源分配情況進(jìn)行分析，可得此時刻的安全性分析情況： Work NeedAllocationWork+allocationFinishP4233221204437TrueP54371103147411TrueP174113472129513TrueP2951313440213515TrueP31351500640517520True因為T0時刻存在安全序列p4,p5,p1,p2,p3，故T0時刻安全。按照銀行家算法，在T0時刻P2請求資源（0，3，4），因請求資源數(shù)（0，3，4）最大請求資源數(shù)（1，3，4），繼續(xù)。請求資源數(shù)（0，3，4）剩余資源數(shù)（2，3，3），所以系統(tǒng)沒有足夠的資源，不能分配。(7) P1，P2，P3，P4四個進(jìn)程同時依次進(jìn)入就緒隊列，它們所需要的處理器時間和優(yōu)先數(shù)如下，若不計調(diào)度等所消耗的時間，請回答：進(jìn)程 處理器時間（秒） 優(yōu)先數(shù) P1 20 2 P2 15 3 P3 10 5 P4 12 3（a） 分別寫出采用先來先服務(wù)和非搶占式的優(yōu)先數(shù)調(diào)度算法時進(jìn)程執(zhí)行的次序。（b） 分別計算每個進(jìn)程在就緒隊列中的等待時間和平均等待時間。解答：（a）進(jìn)程執(zhí)行次序為： 先來先服務(wù)法非搶占式的優(yōu)先數(shù)法PPPP4PPPP1 （b） 先來先服務(wù)法： 每個進(jìn)程在就緒隊列的等待時間分別為 P1：0（秒） P2：0+20=20（秒） P3：20+15=35（秒） P4：35+10=45（秒） 平均等待時間為（0+20+35+45）/4=25（秒） 非搶占式的優(yōu)先數(shù)法： 每個進(jìn)程在就緒隊列的等待時間分別為 P1：25+12=37（秒）P2：0+10=10（秒）P3：0（秒）P4：10+15=25（秒）平均等待時間為（37+10+0+25）/4=18（秒）(8) 系統(tǒng)中有四道作業(yè)，分別用先來先服務(wù)、短作業(yè)優(yōu)先調(diào)度方法和最高響應(yīng)比優(yōu)先法調(diào)度，完成表格的計算，并計算平均帶權(quán)周轉(zhuǎn)時間。 單位：小時解答：先來先服務(wù)：作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間11：0021：003：00221：1063：009：007．8332：0029：0011：00942：00111：0012：0010平均帶權(quán)周轉(zhuǎn)時間=（2/2++9/2+10/1）/4= 短作業(yè)優(yōu)先調(diào)度