【正文】 ：如果進(jìn)程資源分配圖中有環(huán)路，且每個(gè)資源類(lèi)中僅有一個(gè)資源，則系統(tǒng)中發(fā)生死鎖。（3）：如果進(jìn)程資源分配圖中有環(huán)路，且所涉及的資源類(lèi)中有多個(gè)資源，則環(huán)路的存在只是系統(tǒng)發(fā)生死鎖的必要條件而不是充分條件，系統(tǒng)不一定會(huì)發(fā)生死鎖。29：系統(tǒng)有輸入及和打印機(jī)各一臺(tái)，現(xiàn)有兩個(gè)進(jìn)程都要使用他們，采用PV操作實(shí)現(xiàn)請(qǐng)求使用和歸還資源后還會(huì)產(chǎn)生死鎖嗎？說(shuō)明理由，若是，則給出防止死鎖的方法。34：什么是競(jìng)爭(zhēng)條件？答：多個(gè)進(jìn)程并發(fā)訪問(wèn)和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與訪問(wèn)的特定順序有關(guān)，稱(chēng)為競(jìng)爭(zhēng)條件35：什么是忙式等待？答：不進(jìn)入等待狀態(tài)的等待稱(chēng)為忙式等待。答：應(yīng)用題：1：有三個(gè)并發(fā)進(jìn)程：R負(fù)責(zé)從輸入設(shè)備讀入信息塊，M負(fù)責(zé)對(duì)信息塊加工處理；P負(fù)責(zé)打印輸出信息塊。答： 2：設(shè)有n個(gè)進(jìn)程共享一個(gè)互斥段，如果：(1)每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；(2)每次最多允許m個(gè)進(jìn)程（m≤n）同時(shí)進(jìn)入互斥段。當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為1；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為1；最多可能有n1個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為(n1)也就是n+1。當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為m；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為m1；當(dāng)有m個(gè)進(jìn)程進(jìn)入互斥段且沒(méi)有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0；當(dāng)有m個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為1；最多可能有nm個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為(nm)也就是n+m。試問(wèn)PP2并發(fā)執(zhí)行后，x、y、z的值各為多少？P1： P2：begin beginy:=1。y:=y+3。V(S1)。z:=y+1。P(S2)。y:=z+y z:=z+x。試用：1）信號(hào)量和P、V操作；2）管程，來(lái)實(shí)現(xiàn)用戶進(jìn)程的同步算法。使用信號(hào)量和P、V操作： 6：在一個(gè)盒子里，混裝了數(shù)量相等的黑白圍棋子。規(guī)定每個(gè)進(jìn)程每次揀一子；當(dāng)一個(gè)進(jìn)程在揀時(shí)，不允許另一個(gè)進(jìn)程去揀；當(dāng)一個(gè)進(jìn)程揀了一子時(shí)，必須讓另一個(gè)進(jìn)程去揀。答：實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問(wèn)題，設(shè)信號(hào)量S1和S2分別表示可揀白子和黑子，不失一般性，若令先揀白子。售票員的活動(dòng)：關(guān)車(chē)門(mén)；售票；開(kāi)車(chē)門(mén)。答：在汽車(chē)行駛過(guò)程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：售票員關(guān)車(chē)門(mén)后，向司機(jī)發(fā)開(kāi)車(chē)信號(hào)，司機(jī)接到開(kāi)車(chē)信號(hào)后啟動(dòng)車(chē)輛，在汽車(chē)正常行駛過(guò)程中售票員售票，到站時(shí)司機(jī)停車(chē)，售票員在車(chē)停后開(kāi)門(mén)讓乘客上下車(chē)。用P、V原語(yǔ)描述如下：9：一個(gè)快餐廳有4類(lèi)職員：（1）領(lǐng)班：接受顧客點(diǎn)菜；（2）廚師：準(zhǔn)備顧客的飯菜；（3）打包工：將做好的飯菜打包；（4）出納員：收款并提交食品。答：S的值表示它代表的物理資源的使用狀態(tài)：S0表示還有共享資源可供使用。S0表示資源已被分配完，還有進(jìn)程等待使用資源。Process P Process Qbegin beginA； C；B； D；C； end；end；16：另一個(gè)經(jīng)典同步問(wèn)題：吸煙者問(wèn)題(patil，1971)。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。供應(yīng)者隨機(jī)地將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對(duì)健康不利的吸煙。試采用：(1)信號(hào)量和P、V操作；(2)管程編寫(xiě)他們同步工作的程序。當(dāng)mn時(shí)，如果m/n不整除，每個(gè)進(jìn)程最多可以請(qǐng)求”商+1”個(gè)這類(lèi)資源，否則為”商”個(gè)資源，使系統(tǒng)一定不會(huì)發(fā)生死鎖。答：設(shè)max（i）表示第i個(gè)進(jìn)程的最大資源需求量，need(i)表示第i個(gè)進(jìn)程還需要的資源量，alloc(i)表示第i個(gè)進(jìn)程已分配的資源量。max(1)+┅+max(n)=(need(1)+┅+need(n))+((alloc(1)+┅+alloc(n))m+n如果在這個(gè)系統(tǒng)中發(fā)生了死鎖，那么一方面m個(gè)資源應(yīng)該全部分配出去，alloc(1)+┅+alloc(n)=m,另一方面所有進(jìn)程將陷入無(wú)限等待狀態(tài)。┅+need(n)n上式表示死鎖發(fā)生后，n個(gè)進(jìn)程還需要的資源量之和小于n，這意味著此刻至少存在一個(gè)進(jìn)程i,need(i)=0,即它已獲得了所需要的全部資源。21：Jurassic公園有一個(gè)恐龍博物館和一個(gè)花園，有m個(gè)旅客和n輛車(chē)，每輛車(chē)僅能乘一個(gè)旅客。若n輛車(chē)都已被旅客乘坐游玩，則想坐車(chē)的旅客需要等待。試用信號(hào)量和P、V操作同步m個(gè)旅客和n輛車(chē)子。P1，P2，P3，P4的CkiAki分別為：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0)系統(tǒng)處于安全狀態(tài)，存在安全序：P2，P1，P3，P4可以分配，存在安全序列：P2，P1，P3，P4。(4)不可以分配。25：把死鎖檢測(cè)算法用于下面的數(shù)據(jù)，并請(qǐng)問(wèn)：Available=(1，0，2，0)1 1 0 03 0 1 10 1 1 2 Allocation= 0 1 0 0Need=3 1 1 1 1 0 0 01 1 0 10 0 1 0=2 1 1 0 0 0 0 0(1)此時(shí)系統(tǒng)此時(shí)處于安全狀態(tài)嗎？(2)若第二個(gè)進(jìn)程提出資源請(qǐng)求request2(0，0，1，0)，系統(tǒng)能分配資源給它嗎？(3)若第五個(gè)進(jìn)程提出資源請(qǐng)求request5(0，0，1，0)，系統(tǒng)能分配資源給它嗎？答：(1)此時(shí)可以找出進(jìn)程安全序列：P4，P1，P5，P2，P3。(3)不可分配，系統(tǒng)進(jìn)入不安全狀態(tài)。使用銀行家算法，以確定下面的任何一個(gè)請(qǐng)求是否安全。(2)P4進(jìn)程到達(dá)，P4最大需求60,最初請(qǐng)求35。答：29：進(jìn)程AA…、An1通過(guò)m個(gè)緩沖區(qū)向進(jìn)程BB…、Bn2不斷地發(fā)送消息。試用信號(hào)量和PV操作編制正確控制消息的發(fā)送和接收的程序。答：39：一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程共享九個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)可以存放一個(gè)整數(shù)。請(qǐng)用：(1)信號(hào)量和P、V操作；(2)管程，寫(xiě)出能夠正確執(zhí)行的程序。試從“互斥”(mutual exclusion)、“空閑讓進(jìn)”(progress)、“有限等待”(bounded waiting)等三方面討論它的正確性。program attemp。procedure p1。repeatc1:=1c2until c20。 (/* 臨界區(qū) */)c1:=1until falseend。 (/* 對(duì)另一個(gè)進(jìn)程p2 */)beginrepeatRemain Section 2。Critical Section。begin (/* 主程序 */)c1:=1。cobeginp1。當(dāng)free[index]=true時(shí)，表示第index個(gè)頁(yè)框空閑，free[index]=false時(shí)，表示第index個(gè)頁(yè)框。59：試?yán)靡话阈盘?hào)量機(jī)制解決讀者寫(xiě)者問(wèn)題。readcount :integer :=0 。 readcount=readcount+1。 if readcount=0 then V(wmutex)。 write text。 until false end parendend60：試?yán)枚敌盘?hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題。buffer: array[0,...,n1] of item。beginparbeginproducer: beginrepeat.produce an item in nextp。 wait(s1,s2,s3,...,sn)。buffer(in):=nextp。signal(mutex)。signal(s1,s2,s3,...,sn)。endconsumer: beginrepeatwait(full)。 //k1,k2,...,kn為執(zhí)行消費(fèi)者進(jìn)程除full外其余的條件wait(mutex)。out:=(out+1) mod n。signal(empty)。consume the item in nextc。endparendend 專(zhuān)業(yè)整理分享