【正文】 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)者和消費者，共享一個由M2 個緩沖區(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 個消息。 做香煙，吸香煙； 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）。 準備香煙原料；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標記； / * nago1 、nage2 、nage3 代表煙草、紙、火柴if flag2 amp。 fiag1:=flag2:=flag3:=true。 S1:=S2:=S3:=0 。 semaphore 。答：( 1 ）用信號量和P 、v 操作。當吸煙者完成吸煙后喚醒供應者，供應者再把兩樣東西放在桌子上，喚醒另一個吸煙者。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。三個吸煙者在一個房間內(nèi)，還有一個香煙供應者。而進程Pk 發(fā)現(xiàn)最終除自身外的所有進程Pj 的flag[j]≠in_cs ，并據(jù)此可進入其臨界區(qū)。 假設｛P1 , P2 ，… Pm ｝是一個己將flag[i] 置為in_cs ( i =1,2,…,m ) ( m ≤n 1）的進程集合，并且已經(jīng)假設當前turn=k ( 1≤k≤m ) ，則Pk 必將在有限時間內(nèi)首先進入臨界區(qū)。但turn僅有一個值，該值為最后一個執(zhí)行此賦值語句的進程號，設為k 、即turn=k (1≤k≤n 1 ）。但是若干個其他進程是可能同時交替執(zhí)行的，假設讓進程Pj(j=l , 2 , …nl）交錯執(zhí)行語句① 后（這時flag[j]=want_in），再做語句② （第一個while 語句），來查詢flag[turn]的狀態(tài)。注意到flag[i]＝in_cs 并不意味著turn的值一定等于i 。另外，進程Pi 總是先置自己的flag[j]為in_cs后，才去判別Pj進程的flag[j]的值是否等于in_cs 所以，此算法能保證n 個進程互斥地進入臨界區(qū)。 critical section 。 (j==1 or flag[j] ≠in_cs ）⑤ do j:=j + 1 。 答：為方便描述，把Dijkstra 程序的語句進行編號：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 試利用記錄型信號量和P 、V 操作寫出一個不會出現(xiàn)死鎖的五個哲學家進餐問題的算法。答：( 1 ）見課文ch3 節(jié)。正常情況下，同步管理進程回送一個空應答消息，然后，解鎖執(zhí)行P 、V 操作的應用程序。如果信號量的值為負的話，執(zhí)行P 操作的應用進程被阻塞，掛到等待進程隊列，所以，不再要送回答消息。庫過程的功能是：把應用進程封鎖起來，所執(zhí)行的P 、V 操作的信息組織成消息，執(zhí)行send 發(fā)送給與信號量對應的同步管理進程，之后，再執(zhí)行receive 操作以接收同步管理進程的應答。( 2 ）用消息傳遞實現(xiàn)信號量。答：( l ）用信號量實現(xiàn)消息傳遞；1 ）把消息隊列組織成一個共享隊列，用一個互斥信號量管理對該隊列的入隊操作和出隊操作.2 ）發(fā)送消息是一個入隊操作，當隊列存儲區(qū)滿時，設計一個同步信號量阻塞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 ）用消息傳遞實現(xiàn)管程；用消息傳遞可以實現(xiàn)信號量（見13 ( 2 ) ) ，用信號量可以實現(xiàn)管程（見11 (1 ) ) ，那么，把兩種方法結(jié)合起來，就可以用用消息傳遞實現(xiàn)管程。 end begin C:=初值。 if C≤0 then signal ( S,IM ) 。 release ( IM ) 。 procedure P begin check ( IM ) 。 DEFINE P , V 。 condition 。 } ( 2 ）用管程實現(xiàn)信號量。 } void wait(c) /*等待條件c ，開放管程{ V ( mutex ) 。｛注意這時沒有開放管程，因為剛剛被釋放的進程己在管程中。 } void leavemonitornormally ( )/*不發(fā)信號退出管程{ V ( mutex ) 。 c:=0 。相應的用信號量實現(xiàn)的管程庫過程為： Var mutex,c:semaphore 。下面介紹另一種簡單方法：每一個管程都對應一個mutex ，其初值為1 ，用來控制進程互斥調(diào)用管程。11 證明信號量與管程的功能是等價的： ( l ）用信號量實現(xiàn)管程； ( 2 ）用管程實現(xiàn)信號量。 l ) K 的初值為5 ，故P1 執(zhí)行兩個循環(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 種交錯執(zhí)行的路徑：A 、B 、C 、D 、E。 until false 。 k:=0 。 print k 。 end : end 。 E 。 D 。10 ( 1 ）兩個并發(fā)進程并發(fā)執(zhí)行，其中，A 、B 、C 、D 、E 是原語，試給出可能的并發(fā)執(zhí)行路徑。S 閱表示共享資源正被進程使用但沒有進程等待使用資源。 ufltile false 。 end process P4 begin repeat P( 54 ) 。 將做好的飯菜打包； V ( S4 ) 。 untile false 。cobegin { process P1begin repeat 有顧客到來；P ( S1 )； 接受顧客點菜；V ( 52 )；untile false； end process P2 begin repeat P (S2 ) 。S1 : = 1 。答：典型的進程同步問題，可設四個信號量51 、S2 、S3 和S4 來協(xié)調(diào)進程工作。P ( S2 ) 開車門； 上下乘客； } end 一個快餐廳有4 類職員：( l ）領班：接受顧客點菜；( 2 ）廚師：準備顧客的飯菜；( 3 ) 包工：將做好的飯菜打包；( 4 ）出納員：收款并提交食品。 } coend driver ( ) begin while ( 1 ) { P ( S1 )啟動車輛；正常行車；到站停車； V ( S2 ) 。 S1=0；S2=0；cobegin { driver ( ) 。S2 表示是否允許售票員開門（其初值為0 ）。應設置兩個信號量：S1 、S2 。答：在汽車行駛過程中，司機活動與售票員活動之間的同步關系為：售票員關車門后，向司機發(fā)開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開門讓乘客上下車。售票員的活動：關車門；售票；開車門。答：可以采用形如waituntil ＜條件表達式＞的同步原語。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 ：實質(zhì)上是兩個進程的同步問題，設信號量s1 和s2 分別表示可揀白子和黑子，不失一般性，若令先揀白子。 現(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設分揀系統(tǒng)有二個進