【正文】 態(tài)。30 有一個(gè)倉(cāng)庫(kù)，可存放X、Y兩種產(chǎn)品，倉(cāng)庫(kù)的存儲(chǔ)空間足夠大，但要求：(1) 每次只能存入一種產(chǎn)品X或Y， (2) 滿足NX產(chǎn)品數(shù)量 Y 產(chǎn)品數(shù)量M。其中，N和M是正整數(shù)，試用信號(hào)量與P、V操作實(shí)現(xiàn)產(chǎn)品X與Y的入庫(kù)過(guò)程。答：本題給出的表達(dá)式可分解為制約條件： －N＜X產(chǎn)品數(shù)量－Y產(chǎn)品數(shù)量 X產(chǎn)品數(shù)量－Y產(chǎn)品數(shù)量＜M也就是說(shuō)，X產(chǎn)品的數(shù)量不能比Y產(chǎn)品的數(shù)量少N個(gè)以上，X產(chǎn)品的數(shù)量不能比Y產(chǎn)品的數(shù)量多M個(gè)以上?？梢栽O(shè)置兩個(gè)信號(hào)量來(lái)控制X、Y產(chǎn)品的存放數(shù)量：sx表示當(dāng)前允許X產(chǎn)品比Y產(chǎn)品多入庫(kù)的數(shù)量，即在當(dāng)前庫(kù)存量和Y產(chǎn)品不入庫(kù)的情況下，還可以允許sx個(gè)X產(chǎn)品入庫(kù)；初始時(shí)，若不放Y而僅放X產(chǎn)品，則sx最多為M－1個(gè)。sy表示當(dāng)前允許Y產(chǎn)品比X產(chǎn)品多入庫(kù)的數(shù)量，即在當(dāng)前庫(kù)存量和X產(chǎn)品不入庫(kù)的情況下，還可以允許sy個(gè)Y產(chǎn)品入庫(kù)。初始時(shí)，若不放X而僅放Y產(chǎn)品，則sy最多為N－1個(gè)。當(dāng)往庫(kù)中存放入一個(gè)X產(chǎn)品時(shí)，則允許存入Y產(chǎn)品的數(shù)量也增加1，故信號(hào)量sy應(yīng)加1；當(dāng)往庫(kù)中存放入一個(gè)Y產(chǎn)品時(shí)，則允許存入X產(chǎn)品的數(shù)量也增加1，故信號(hào)量sx應(yīng)加1。var mutex：semaphore=1。/*互斥信號(hào)量*/ sx，sy：semaphore； sx=M1。 sy=N1。cobegin{ process X { repeat P(sx)。 P(mutex)。 將X產(chǎn)品入庫(kù)； V(mutex)。 V(sy)。 until false } process Y { repeat P(sy)。 P(mutex)。 將Y產(chǎn)品入庫(kù)； V(mutex)。 V(px)。 until false}}coend.31 有一個(gè)倉(cāng)庫(kù)可存放A、B兩種零件，最大庫(kù)容量各為m個(gè)。生產(chǎn)車間不斷地取A和B進(jìn)行裝配，每次各取一個(gè)。為避免零件銹蝕，按先入庫(kù)者先出庫(kù)的原則。有兩組供應(yīng)商分別不斷地供應(yīng)A和B，每次一個(gè)。為保證配套和合理庫(kù)存，當(dāng)某種零件比另一種零件超過(guò)n(nm)個(gè)時(shí)，暫停對(duì)數(shù)量大的零件的進(jìn)貨，集中補(bǔ)充數(shù)量少的零件。試用信號(hào)量與P、V操作正確地實(shí)現(xiàn)它們之間的同步關(guān)系。答：按照題意，應(yīng)滿足以下控制關(guān)系：A零件數(shù)量 B零件數(shù)量≤n；B零件數(shù)量 A零件數(shù)量≤n；A零件數(shù)量≤m；B零件數(shù)量≤m。四個(gè)控制關(guān)系分別用信號(hào)量sa、sb、empty1和empty2實(shí)施。為遵循先入庫(kù)者先出庫(kù)的原則，A、B零件可以組織成兩個(gè)循形隊(duì)列，并增加入庫(kù)指針inin2和出庫(kù)指針outout2來(lái)控制順序。并發(fā)程序編制如下：var empty1，empty2，full1，full2：semaphore；mutex，sa，sb：semaphore；in1，in2，out1，out2：integer；buffer1，buffer2 ：array [0..m1] of item； empty1：=empty2：=m； sa：=sb：=n； in1：=in2：=out1：=out2：=0；cobegin{process producerA{ repeat P(empty1)； P(sa)； P(mutex)； buffer1[in1] ：=A零件； in1：=(in1+1) mod m； V(mutex)； V(sb)； V(full1)； untile false；}process producerB{ repeat P(empty2)； P(sb)； P(mutex)； Buffer2[in2] ：=B零件； in2：=(in2+1) mod m； V(mutex)； V(sa)； V(full2)； untile false；}process take { repeatP(full1)；P(full2)；P(mutex)；Take from buffer1[out1] and buffer2[out2]中的A、B零件；out1：=(out1+1) mod m；out2：=(out2+1) mod m；V(mutex)；V(empty1)；V(empty1)；把A和B裝配成產(chǎn)品；until false}}coend.32 進(jìn)程AA…、An1通過(guò)m個(gè)緩沖區(qū)向進(jìn)程BB…、Bn2不斷地發(fā)送消息。發(fā)送和接收工作符合以下規(guī)則：(1) 每個(gè)發(fā)送進(jìn)程每次發(fā)送一個(gè)消息，寫進(jìn)一個(gè)緩沖區(qū)，緩沖區(qū)大小與消息長(zhǎng)度相等；(2) 對(duì)每個(gè)消息，BB…、Bn2都需接收一次，并讀入各自的數(shù)據(jù)區(qū)內(nèi)；(3) 當(dāng)M個(gè)緩沖區(qū)都滿時(shí)，則發(fā)送進(jìn)程等待，當(dāng)沒(méi)有消息可讀時(shí)，接收進(jìn)程等待。試用信號(hào)量和PV操作編制正確控制消息的發(fā)送和接收的程序。答：本題是生產(chǎn)者－消費(fèi)者問(wèn)題的一個(gè)變形，一組生產(chǎn)者A1，A2，…An1和一組消費(fèi)者B1，B2，…Bn2共用m個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只要寫一次，但需要讀n2次。因此，可以把這一組緩沖區(qū)看成n2組緩沖區(qū)，每個(gè)發(fā)送者需要同時(shí)寫n2組緩沖區(qū)中相應(yīng)的n2個(gè)緩沖區(qū)，而每一個(gè)接收者只需讀它自己對(duì)應(yīng)的那組緩沖區(qū)中的對(duì)應(yīng)單元。應(yīng)設(shè)置一個(gè)信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖區(qū)的互斥訪問(wèn)；兩個(gè)信號(hào)量數(shù)組empty[n2]和full[n2]描述n2組緩沖區(qū)的使用情況。其同步關(guān)系描述如下：var mutex,empty[n2],full[n2]：semaphore。i:integer。mutex=1。for(i=0。i=n21。i++) { empty[i]=m。 full[i]=0。 }main (){ cobegin A1( )。 A2( )。 ┋ An1 ()。 B1 ()。 B2 ()。 ┋ Bn2( )。coend }send ( ) /*進(jìn)程Ai發(fā)送消息*/{ int i。for (i=0。i=n21。i++) p(empty[i])。 p(mutex)。 將消息放入緩沖區(qū)； V（mutex）。for(i=0。i=n21。i++) V(full[i])。}receive(i) /*進(jìn)程Bi接收消息*/{ p(full[i])。 p(mutex)。 將消息從緩沖區(qū)取出； V(mutex)。 V(emtpy[i])。}Ai ( ) /*發(fā)送進(jìn)程A1,A2,…An1的程序類似，這里給出進(jìn)程Ai的描述*/{while (1) { ┋ send ( )。 ┋ }}Bi ( ) /*接收進(jìn)程B1,B2,…Bn2的程序類似，這里給出進(jìn)程Bi描述*/{while (1){ ┋ receive(i)。 ┋ }}33 某系統(tǒng)有R1設(shè)備3臺(tái)，R2設(shè)備4臺(tái)，它們被PPP3和P4進(jìn)程共享，且已知這4個(gè)進(jìn)程均按以下順序使用設(shè)備： →申請(qǐng)R1→申請(qǐng)R2→申請(qǐng)R1→釋放R1→釋放R2→釋放R1(1) 系統(tǒng)運(yùn)行中可能產(chǎn)生死鎖嗎？為什么？(2) 若可能的話，請(qǐng)舉出一種情況，并畫(huà)出表示該死鎖狀態(tài)的進(jìn)程—資源圖。答：(1)系統(tǒng)四個(gè)進(jìn)程需要使用的資源數(shù)為R1各2臺(tái)，R2各1臺(tái)?？梢?jiàn)資源數(shù)不足，同時(shí)各進(jìn)程申請(qǐng)資源在先，有可能產(chǎn)生死鎖發(fā)生的四個(gè)條件，故系統(tǒng)可能產(chǎn)生死鎖。(2) 當(dāng)三個(gè)進(jìn)程執(zhí)行完申請(qǐng)資源R1，開(kāi)始執(zhí)行申請(qǐng)資源R2時(shí)，第四個(gè)進(jìn)程會(huì)因沒(méi)有資源R1而被阻塞。當(dāng)三個(gè)進(jìn)程執(zhí)行完申請(qǐng)資源R2后，系統(tǒng)還剩1個(gè)R2資源。而這三個(gè)進(jìn)程因執(zhí)行申請(qǐng)第二個(gè)資源R1而全部被阻塞，系統(tǒng)進(jìn)入死鎖。● ● ●●●●●P1P2P3P434 如圖所示，左右兩隊(duì)雜技演員過(guò)獨(dú)木橋，為了保證安全，請(qǐng)用PV操作和信號(hào)量來(lái)解決過(guò)獨(dú)木橋問(wèn)題。只要橋上無(wú)人，則允許一方的人過(guò)橋，待一方的人全部過(guò)完后，另一方的人才允許過(guò)橋。答：var wait,mutex1,mutex2,bridge1,bridge2:semaphore。 mutex1:=mutex2:=bridge1:=bridge2:=1。wait:=0。 counter1,counter2:integer。cobegin{ process P左 process P右 begin begin P(mutex1)。 P(mutex2)。 count1++。 count2++。 if count1=1 then P(wait)。 if count2=1 then P(wait)。 V(mutex1)。 V(mutex2)。 P(bridge1)。 P(bridge2)。 過(guò)獨(dú)木橋。 過(guò)獨(dú)木橋。 V(bridge1)。 V(bridge2)。 P(mutex1)。 P(mutex2)。 Count1 count2。 if count1=0 then V(wait)。 if count2=0 then P(wait)。 V(mutex1)。 V(mutex2)。 end end}coend35 修改讀者寫者的同步算法，使它對(duì)寫者優(yōu)先，即一旦有寫者到達(dá)，后續(xù)的讀者必須等待，而無(wú)論是否有讀者在讀文件。(1)用信號(hào)量和P、V操作實(shí)現(xiàn)；(2)用管程實(shí)現(xiàn)。答：(1) 用信號(hào)量和P、V操作實(shí)現(xiàn)。為了提高寫者的優(yōu)先級(jí)，增加一個(gè)信號(hào)量s，用于在寫進(jìn)程到達(dá)后封鎖后續(xù)的讀者。其控制流程如下：var rmutex，wmutex，S：semaphore； rmutex=1。wmutex=1。 S=1。 count:integer:=0。main ( ){ cobegin reader ( )。 writer ( )。 coend}reader ( ) begin while (1) { P(S)。 P(rmutex)。 if (count==0) p(wmutex)。 count++。 V(rmutex)。 V(S)。 讀文件； p(rmutex)。 count。 if (count==0) v(wmutex)。 V(rmutex)。 }endwriter( ) begin while(1) { P(S)。 P(wmutex)。 寫文件； V(wmutex)。 V(S)。 }end.(2)用管程實(shí)現(xiàn)。TYPE readwrite=monitorVAR rc, wc : integer。 R, W : condition。DEFINE startread, endread, startwriter, endwriter。USE wait,signal,check,release。procedure startread。begin check(IM)。 if wc0 then wait(R,IM)。 rc := rc + 1。 signal(R, IM)。 release(IM)。end。procedure endread。begin check(IM)。 rc := rc 1。 if rc=0 then signal(W,IM)。 release(IM)。end。procedure startwrite。begin check(IM)。 wc := wc + 1。 if rc0 or wc1 then wait(W,IM)。 release(IM)。end。procedure endwrite。begin