【正文】 V(fu。 counter++。 put an item into buffer [in1] 。cobegin { process Pi begin L1: P(empty1) 。 counter1:=counter2:=0 。 empty:=M2。 buffer2:array[0…M21]of item 。 counter1 , counter2:integer 。 semaphore 。答：var mutex1 , mutex2 , mutex3 : semaphore。Qj、Rk凡構(gòu)成另一對生產(chǎn)者和消費(fèi)者，共享一個(gè)由M2 個(gè)緩沖區(qū)構(gòu)成的循環(huán)緩沖池buf2 。 untile false 。V(mutex0) 。 消息己MO[in0]。 加工消息；P ( empty0 ) 。V (mutex3) 。 從M3[out3] 取一條消息。 endprocess P3 begin repeat P(full3) 。 V(full3) 。in3:=(in3+1) mod 2 。 P(mutex3) 。 V(empty2) 。 從M2[out2]取一條消息； out2:=(out2 + l ) mod 2。 end process P2begin repeat P(full2) 。 v ( full2 ) 。In2:=(in2+1) mod 2。 P(mutex2 ) 。 加工消息。V(mutex1)。 P ( mutex1 ) 。 untile false 。V(mutex1) 。 消息已M1[in1]。 加工消息；P(empty1) 。 V(mutex0)。 P(mutex0)。in0:=in1:＝in2:＝in3:=out0:=out1:=out2:=out3:=0。in0,in1,in2,in3,out0 ,out2,out3,。 full0:=3。 empty:=2:=empty3:=2。empty:=0 。Empty0,empty1,empty2, empty3。試以P 、V 為操作工具，寫出Pi（i=0…3）的同步工作算法答：var mutexl , mutexZ , mutex3 ，mutex0 :semaphore?？纱娣? 、3 、2 、2 個(gè)消息。 做香煙，吸香煙； until false 。 做香煙，吸香煙； until false 。做香煙，吸香煙； until false 。 …… until false 。 end begin flag1:=flag2:=flag3:=true。else 取原料 signal ( S ,IM ) 。 release （IM）。 end procedure take2begin check ( IM ) : if 桌上沒有香煙原料 then wait(S2,IM)。 else 取原料；signal ( S , IM ) 。 release ( IM ) 。 flag3 then signal ( S2 ,IM ) 。 flag3 then signal ( S1 ,IM）。 準(zhǔn)備香煙原料；if 桌上有香煙原料then wait( S , IM ) 。 USE check , wait , signal , release 。TYPE mskesmoke=moonitor VAR S, S1 ,S2 ,S3 : condition 。 吸香煙； untile false 。process 吸煙者3 begin repeat P (S3 ) 。 取原料； 做香煙； V(S) 。 吸香煙；untile false 。 end process 吸煙者1 begin repeat P(S1) 。 / ＊供煙草和火柴else V(S3) 。 / ＊供紙和火柴else if flag1 amp。 取兩樣香煙原料放桌上，由flagi標(biāo)記； / * nago1 、nage2 、nage3 代表煙草、紙、火柴if flag2 amp。 fiag1:=flag2:=flag3:=true。 S1:=S2:=S3:=0 。 semaphore 。答：( 1 ）用信號量和P 、v 操作。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個(gè)吸煙者。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙和第三個(gè)有自己的火柴。三個(gè)吸煙者在一個(gè)房間內(nèi)，還有一個(gè)香煙供應(yīng)者。而進(jìn)程Pk 發(fā)現(xiàn)最終除自身外的所有進(jìn)程Pj 的flag[j]≠in_cs ，并據(jù)此可進(jìn)入其臨界區(qū)。 假設(shè)｛P1 , P2 ，… Pm ｝是一個(gè)己將flag[i] 置為in_cs ( i =1,2,…,m ) ( m ≤n 1）的進(jìn)程集合，并且已經(jīng)假設(shè)當(dāng)前turn=k ( 1≤k≤m ) ，則Pk 必將在有限時(shí)間內(nèi)首先進(jìn)入臨界區(qū)。但turn僅有一個(gè)值，該值為最后一個(gè)執(zhí)行此賦值語句的進(jìn)程號，設(shè)為k 、即turn=k (1≤k≤n 1 ）。但是若干個(gè)其他進(jìn)程是可能同時(shí)交替執(zhí)行的，假設(shè)讓進(jìn)程Pj(j=l , 2 , …nl）交錯(cuò)執(zhí)行語句① 后（這時(shí)flag[j]=want_in），再做語句② （第一個(gè)while 語句），來查詢flag[turn]的狀態(tài)。注意到flag[i]＝in_cs 并不意味著turn的值一定等于i 。另外，進(jìn)程Pi 總是先置自己的flag[j]為in_cs后，才去判別Pj進(jìn)程的flag[j]的值是否等于in_cs 所以，此算法能保證n 個(gè)進(jìn)程互斥地進(jìn)入臨界區(qū)。 critical section 。 (j==1 or flag[j] ≠in_cs ）⑤ do j:=j + 1 。 答：為方便描述，把Dijkstra 程序的語句進(jìn)行編號：repeat flag[i]:=want_in ；① while turn≠i do ② if flag[trun]==idle then turn:=i ；③ flag[i]: = in_cs ；④ j:= O ?！?until false 。 until j≥n : critical section 。 while (j n ) amp。 flag[i]:= ip_cs 。 begin repeat repeat flag [i] :want_in 。 process Pi(i=0,1，…,n1) var j 。 turn:integer 。 } coend 。 goto L1 。 / * i =4,P(fork [0]) * / P(fork[i+1] mod 5) / * i =4P（fork [4]）* / 吃通心面；V (fork[i] 。 forki:=1 。15 試?yán)糜涗浶托盘柫亢蚉 、V 操作寫出一個(gè)不會出現(xiàn)死鎖的五個(gè)哲學(xué)家進(jìn)餐問題的算法。答：( 1 ）見課文ch3 節(jié)。正常情況下，同步管理進(jìn)程回送一個(gè)空應(yīng)答消息，然后，解鎖執(zhí)行P 、V 操作的應(yīng)用程序。如果信號量的值為負(fù)的話，執(zhí)行P 操作的應(yīng)用進(jìn)程被阻塞，掛到等待進(jìn)程隊(duì)列，所以，不再要送回答消息。庫過程的功能是：把應(yīng)用進(jìn)程封鎖起來，所執(zhí)行的P 、V 操作的信息組織成消息，執(zhí)行send 發(fā)送給與信號量對應(yīng)的同步管理進(jìn)程，之后，再執(zhí)行receive 操作以接收同步管理進(jìn)程的應(yīng)答。( 2 ）用消息傳遞實(shí)現(xiàn)信號量。答：( l ）用信號量實(shí)現(xiàn)消息傳遞；1 ）把消息隊(duì)列組織成一個(gè)共享隊(duì)列，用一個(gè)互斥信號量管理對該隊(duì)列的入隊(duì)操作和出隊(duì)操作.2 ）發(fā)送消息是一個(gè)入隊(duì)操作，當(dāng)隊(duì)列存儲區(qū)滿時(shí)，設(shè)計(jì)一個(gè)同步信號量阻塞send 操作。 count:=0 。 end begin r:= 0 。 if count＝n1 then signal ( full , IM ) 。 if count = 0 then wait ( empty , IM ) 。 end procedure get ( m ) 。 if count = 1 then sighal ( empty , IM ) 。 buffer [r]:=message 。 begin check ( IM ) 。 USE check , wait , signal , release 。 full , empty:condition 。TYPE mailbox=monitor VAR r , k , count:integer 。答：( 1 ）用消息傳遞實(shí)現(xiàn)管程；用消息傳遞可以實(shí)現(xiàn)信號量（見13 ( 2 ) ) ，用信號量可以實(shí)現(xiàn)管程（見11 (1 ) ) ，那么，把兩種方法結(jié)合起來，就可以用用消息傳遞實(shí)現(xiàn)管程。 end begin C:=初值。 if C≤0 then signal ( S,IM ) 。 release ( IM ) 。 procedure P begin check ( IM ) 。 DEFINE P , V 。 condition 。 } ( 2 ）用管程實(shí)現(xiàn)信號量。 } void wait(c) /*等待條件c ，開放管程{ V ( mutex ) 。｛注意這時(shí)沒有開放管程，因?yàn)閯倓偙会尫诺倪M(jìn)程己在管程中。 } void leavemonitornormally ( )/*不發(fā)信號退出管程{ V ( mutex ) 。 c:=0 。相應(yīng)的用信號量實(shí)現(xiàn)的管程庫過程為： Var mutex,c:semaphore 。下面介紹另一種簡單方法：每一個(gè)管程都對應(yīng)一個(gè)mutex ，其初值為1 ，用來控制進(jìn)程互斥調(diào)用管程。11 證明信號量與管程的功能是等價(jià)的： ( l ）用信號量實(shí)現(xiàn)管程； ( 2 ）用管程實(shí)現(xiàn)信號量。 l ) K 的初值為5 ，故P1 執(zhí)行兩個(gè)循環(huán)后，K = 23 。 ( 2 ）把語句編號，以便于描述：P1 P2 repeat repeat k:=k2 ；① printk ；③ k:=k+l ；② k:=0 ；④ until false 。 D 、A 、E 、B 、C 。 D 、A 、B 、E 、C。 A 、D 、B 、C 、E。 A 、B 、D 、C 、E 。答： ( 1 ）共有10 種交錯(cuò)執(zhí)行的路徑：A 、B 、C 、D 、E。 until false 。 k:=0 。 print k 。 end : end 。 E 。 D 。10 ( 1 ）兩個(gè)并發(fā)進(jìn)程并發(fā)執(zhí)行，其中，A 、B 、C 、D 、E 是原語，試給出可能的并發(fā)執(zhí)行路徑。S 閱表示共享資源正被進(jìn)程使用但沒有進(jìn)程等待使用資源。 ufltile false 。 end process P4 begin repeat P( 54 ) 。 將做好的飯菜打包； V ( S4 ) 。 untile false 。cobegin { process P1begin repeat 有顧客到來；P ( S1 )； 接受顧客點(diǎn)菜；V ( 52 )；untile false； end process P2 begin repeat P (S2 ) 。S1 : = 1 。答：典型的進(jìn)程同步問題，可設(shè)四個(gè)信號量51 、S2 、S3 和S4 來協(xié)調(diào)進(jìn)程工作。P ( S2 ) 開車門； 上下乘客； } end 一個(gè)快餐廳有4 類職員：( l ）領(lǐng)班：接受顧客點(diǎn)菜；( 2 ）廚師：準(zhǔn)備顧客的飯菜；( 3 ) 包工：將做好的飯菜打包；( 4 ）出納員：收款并提交食品。 } coend driver ( ) begin while ( 1 ) { P ( S1 )啟動車輛；正常行車；到站停車； V ( S2 ) 。 S1=0；S2=0；cobegin { driver ( ) 。S2 表示是否允許售票員開門（其初值為0 ）。應(yīng)設(shè)置兩個(gè)信號量：S1 、S2 。答：在汽車行駛過程中，司機(jī)活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后，向司機(jī)發(fā)開車信號，司機(jī)接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開門讓乘客上下車。售票員的活動：關(guān)車門；售票；開車門。答：可以采用形如waituntil ＜條件表達(dá)式＞的同步原語。other 。other 。 process W ( ) 。 end begin flag:=true 。 signal ( Sblack,IM ) 。flag :=false 。 begin check ( IM ) 。 release ( IM ) 。pickup a black。 if flag then wait(sblack,IM ) 。 procedure pickupblack 。DEFINE pickupblack , pickupwhite 。 end } coend . 答2 : TYPE pickupchess = MONITOR VAR flag : boolean 。 揀黑子V (S1 ) 。 until false 。cobegin { process P1 begin repeat P( S1 ) 。 S1 : = l。答1 ：實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問題，設(shè)信號量s1 和s2 分別表示可揀白子和黑子，不失一般性，若令先揀白子。 現(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設(shè)分揀系統(tǒng)有二個(gè)進(jìn)