【正文】 ger 。 tune:0 or 1 or … or , n1 。 process Pi(i=0,1，…,n1) var j 。 integer 。 begin repeat repeat flag [i] :want_in 。 while turn≠1 do if flag[turn]==idle then turn:=i 。 flag[i]:= ip_cs 。 j:=0 。 while (j n ) amp。 (j==1 or flag[j] ≠in_cs ) do j:=j + 1 。 until j≥n : critical section 。 flag [i]:=idle ?！?until false 。 end . 試說明該算法滿足臨界區(qū)原則。 答：為方便描述，把Dijkstra 程序的語句進行編號：repeat flag[i]:=want_in ；① while turn≠i do ② if flag[trun]==idle then turn:=i ；③ flag[i]: = in_cs ；④ j:= O 。 while(j n ) amp。 (j==1 or flag[j] ≠in_cs ）⑤ do j:=j + 1 。 @ until j≥n 。 critical section 。 flag[i] :=idle ；⑦ … ( l ）滿足互斥條件當所有的巧都不在臨界區(qū)中，滿足flag[j]≠in_cs（對于所有j , j≠i ）條件時，Pi 才能進入它的臨界區(qū)，而且進程Pi 不會改變除自己外的其他進程所對應(yīng)的flag[j]的值。另外，進程Pi 總是先置自己的flag[j]為in_cs后，才去判別Pj進程的flag[j]的值是否等于in_cs 所以，此算法能保證n 個進程互斥地進入臨界區(qū)。( 2 ）不會發(fā)生無休止等待進入臨界區(qū)由于任何一個進程Pi 在執(zhí)行進入臨界區(qū)代碼時先執(zhí)行語句① ，其相應(yīng)的flag[i]的值不會是idle 。注意到flag[i]＝in_cs 并不意味著turn的值一定等于i 。我們來看以下情況，不失一般性，令turn 的初值為0，且P0不工作，所以，flag[turn]=flag[0]=idle。但是若干個其他進程是可能同時交替執(zhí)行的，假設(shè)讓進程Pj(j=l , 2 , …nl）交錯執(zhí)行語句① 后（這時flag[j]=want_in），再做語句② （第一個while 語句），來查詢flag[turn]的狀態(tài)。顯然，都滿足turn≠i ，所以，都可以執(zhí)行語句③ ，讓自己的turn 為j 。但turn僅有一個值，該值為最后一個執(zhí)行此賦值語句的進程號，設(shè)為k 、即turn=k (1≤k≤n 1 ）。接著，進程Pj(j=1,2,…nl ) 交錯執(zhí)行語句④ ，于是最多同時可能有n1 個進程處于in_cs 狀態(tài)，但不要忘了僅有一個進程能成功執(zhí)行語句④ ，將加m 置為自己的值。 假設(shè)｛P1 , P2 ，… Pm ｝是一個己將flag[i] 置為in_cs ( i =1,2,…,m ) ( m ≤n 1）的進程集合，并且已經(jīng)假設(shè)當前turn=k ( 1≤k≤m ) ，則Pk 必將在有限時間內(nèi)首先進入臨界區(qū)。因為集合中除了Pk 之外的所有其他進程終將從它們執(zhí)行的語句⑤ （第二個while 循環(huán)語句）退出，且這時的j 值必小于n ，故內(nèi)嵌until 起作用，返回到起始語句① 重新執(zhí)行，再次置flag [ i ] = want_in ，繼續(xù)第二輪循環(huán)，這時的情況不同了，flag[turn] =flag[ k] 必定≠idle （而為in_cs ）。而進程Pk 發(fā)現(xiàn)最終除自身外的所有進程Pj 的flag[j]≠in_cs ，并據(jù)此可進入其臨界區(qū)。17 另一個經(jīng)典同步問題：吸煙者問題(patil , 1971 ）。三個吸煙者在一個房間內(nèi)，還有一個香煙供應(yīng)者。為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。供應(yīng)者隨機地將兩樣東西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣東西放在桌子上，喚醒另一個吸煙者。試采用：( 1 ）信號量和P 、v 操作，( 2 ）管程編寫他們同步工作的程序。答：( 1 ）用信號量和P 、v 操作。vars , S1 ,S2 , S3 。 semaphore 。 S:=1 。 S1:=S2:=S3:=0 。 fiag1 , flag2 , fiag3 : Boolean 。 fiag1:=flag2:=flag3:=true。cobegin { process 供應(yīng)者begin repeat P(S) 。 取兩樣香煙原料放桌上，由flagi標記； / * nago1 、nage2 、nage3 代表煙草、紙、火柴if flag2 amp。 flag3 then V(S1) 。 / ＊供紙和火柴else if flag1 amp。 fiag3 then V(S2 ) 。 / ＊供煙草和火柴else V(S3) 。 / ＊供煙草和紙untile false 。 end process 吸煙者1 begin repeat P(S1) 。 取原料；做香煙；V(S) 。 吸香煙；untile false 。process 吸煙者2begin repeat P (S2 ) 。 取原料； 做香煙； V(S) 。 吸香煙； untile false 。process 吸煙者3 begin repeat P (S3 ) 。 取原料； 做香煙； V ( S ) 。 吸香煙； untile false 。 coend .( 3 ）用管程。TYPE mskesmoke=moonitor VAR S, S1 ,S2 ,S3 : condition 。 flag1 , flag2, flag3 : boolean DEFINE give , take1 , take2 , take3 。 USE check , wait , signal , release 。 procedure give begin check ( IM ) 。 準備香煙原料；if 桌上有香煙原料then wait( S , IM ) 。 把準備的香煙原料放桌上；if fiag2 amp。 flag3 then signal ( S1 ,IM）。if flag1 amp。 flag3 then signal ( S2 ,IM ) 。 else signal (S3 , IM ) 。 release ( IM ) 。 end procedure take1 begin check(IM):if 桌上沒有香煙原料then wait ( S1 ,IM）。 else 取原料；signal ( S , IM ) 。 release ( IM ) 。 end procedure take2begin check ( IM ) : if 桌上沒有香煙原料 then wait(S2,IM)。else 取原料；signal ( S , IM ) 。 release （IM）。 end procedure take3 begin check ( IM ) : if 桌上沒有香煙原料then wait(S3,IM)。else 取原料 signal ( S ,IM ) 。 release ( IM ) 。 end begin flag1:=flag2:=flag3:=true。end.cobegin { process 供應(yīng)者begin repeat Call ()。 …… until false 。 end process 吸煙者1 beginrepeat Call () 。做香煙，吸香煙； until false 。 end process 吸煙者2 begin repeat Call () 。 做香煙，吸香煙； until false 。 end process 吸煙者3 begin repeat Call ()。 做香煙，吸香煙； until false 。 end } coend . 1 如圖所示，四個進程Pi （i=0… 3 ）和四個信箱Mj (j=0… 3 ) ，進程間借助相鄰信箱傳遞消息，即Pi 每次從Mi中取一條消息，經(jīng)加工后送入M(i + 1) mod4 ，其中M0 、M1 、M2 、M3 ?？纱娣? 、3 、2 、2 個消息。初始狀態(tài)下，MO 裝了三條消息，其余為空。試以P 、V 為操作工具，寫出Pi（i=0…3）的同步工作算法答：var mutexl , mutexZ , mutex3 ，mutex0 :semaphore。 Mutex1＝nutex2:=mutex3:=mutex0:=1。Empty0,empty1,empty2, empty3。 semaphore。empty:=0 。 empty1:=3 。 empty:=2:=empty3:=2。full0 , full1 , full2 , full3:semphore 。 full0:=3。full1:=full2:=full3:=0。in0,in1,in2,in3,out0 ,out2,out3,。intger。in0:=in1:＝in2:＝in3:=out0:=out1:=out2:=out3:=0。cobegin{ process P0 begin repeat P(full0)。 P(mutex0)。 從M0[out0]取一條消息；out0:=(out0+1) mod 3 。 V(mutex0)。 V(empty0) 。 加工消息；P(empty1) 。 P(mutex1) 。 消息已M1[in1]。In1:=(in1+1) mod 3。V(mutex1) 。 V(full1 ) 。 untile false 。 end process P1 begin repeat P ( full1 ) 。 P ( mutex1 ) 。 從M1[out1]取一條消息； Out1:=(out1+1) mod 3 。V(mutex1)。 V(empty1)。 加工消息。P(empty2)。 P(mutex2 ) 。 消息己M2[in2]。In2:=(in2+1) mod 2。V(mutex2 ) 。 v ( full2 ) 。 untile false 。 end process P2begin repeat P(full2) 。 P(mutex2 ) 。 從M2[out2]取一條消息； out2:=(out2 + l ) mod 2。V(mutex2) 。 V(empty2) 。 加工消息；P(empty3) 。 P(mutex3) 。 消息己M3[in3]。in3:=(in3+1) mod 2 。V(mutex3) 。 V(full3) 。 untile false 。 endprocess P3 begin repeat P(full3) 。 P(mutex3) 。 從M3[out3] 取一條消息。out3:=(out3+1)mod 2。V (mutex3) 。 V (empty3) 。 加工消息；P ( empty0 ) 。 P ( mutex0 ) 。 消息己MO[in0]。In0:=(in0+1) mod 3 。V(mutex0) 。 V(full0) 。 untile false 。 end { coend 1有三組進程Pi 、Qj、Rk ，其中Pi 、Qj構(gòu)成一對生產(chǎn)者和消費者，共享一個由M1個緩區(qū)構(gòu)成的循環(huán)緩沖池buf1 。Qj、Rk凡構(gòu)成另一對生產(chǎn)者和消費者，共享一個由M2 個緩沖區(qū)構(gòu)成的循環(huán)緩沖池buf2 。如果Pi每次生產(chǎn)一個產(chǎn)品投入buf1,Qj每次從中取兩個產(chǎn)品組裝成一個后并投入buf2，Rk每次從中取三個產(chǎn)品包裝出廠. 試用信號量和P 、V操作寫出它們同步工作的程序。答：var mutex1 , mutex2 , mutex3 : semaphore。 empty1 , empty2 , full1 , full2 。 semaphore 。 in1 , in2 , out1 , out2 : integer 。 counter1 , counter2:integer 。 buffer1:array[0…M11] of item 。 buffer2:array[0…M21]of item 。empty1:=M1 。 empty:=M2。 in1 : = in2 :=out1:=out2:=0 。 counter1:=counter2:=0 。fun1:=full2:＝mutex1:=mutex2:=mutex3:=1。cobegin { process Pi begin L1: P(empty1) 。 P(mutex1 ) 。 put an item into buffer [in1] 。 in1:=(in1+1) mod M1 。 counter++。if counter1 = 2 then { counter1:=0。