【文章內(nèi)容簡介】 設(shè){P1,P2,…Pm}是一個已將flag[i]置為in_cs(i=1,2,…,m)(m≤n1)的進(jìn)程集合，并且已經(jīng)假設(shè)當(dāng)前turn=k(1≤k≤m)，則Pk必將在有限時間內(nèi)首先進(jìn)入臨界區(qū)。因為集合中除了Pk之外的所有其他進(jìn)程終將從它們執(zhí)行的語句⑤(第二個while循環(huán)語句)退出，且這時的j值必小于n，故內(nèi)嵌until起作用，返回到起始語句①重新執(zhí)行，再次置flag[i]=want_in，繼續(xù)第二輪循環(huán)，這時的情況不同了，flag[turn]=flag[k]必定≠idle(而為in_cs)。而進(jìn)程Pk發(fā)現(xiàn)最終除自身外的所有進(jìn)程Pj的flag[j]≠in_cs，并據(jù)此可進(jìn)入其臨界區(qū)。17 另一個經(jīng)典同步問題：吸煙者問題(patil，1971)。三個吸煙者在一個房間內(nèi)，還有一個香煙供應(yīng)者。為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。供應(yīng)者隨機(jī)地將兩樣?xùn)|西放在桌子上，允許一個吸煙者進(jìn)行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個吸煙者。試采用：(1)信號量和P、V操作，(2)管程編寫他們同步工作的程序。答：(1)用信號量和P、V操作。var S,S1,S2,S3。semaphore。 S:=1。S1:=S2:=S3:=0。 flag1,flag2,flag3:Boolean。 flag1:=flag2:=flag3:=true。cobegin{ process 供應(yīng)者begin repeat P(S)。 取兩樣香煙原料放桌上，由flagi標(biāo)記。 /*flageflageflage3代表煙草、紙、火柴 if flag2amp。flag3 then V(S1)。 /*供紙和火柴 else if flag1amp。flag3 then V(S2)。 /*供煙草和火柴 else V(S3)。 /*供煙草和紙 untile false。 end process 吸煙者1begin repeat P(S1)。 取原料。 做香煙。 V(S)。 吸香煙。 untile false。process 吸煙者2begin repeat P(S2)。 取原料。 做香煙。 V(S)。 吸香煙。 untile false。process 吸煙者3begin repeat P(S3)。 取原料。 做香煙。 V(S)。 吸香煙。 untile false。}coend.(3) 用管程。TYPE mskesmoke=monitorVAR S,S1,S2,S3:condition。flag1,flag2,flag3:booleanDEFINE give, take1, take2, take3。USE check,wait,signal,release。procedure give begin check(IM)。 準(zhǔn)備香煙原料。 if 桌上有香煙原料 then wait(S,IM)。 把準(zhǔn)備的香煙原料放桌上。 if flag2amp。flag3 then signal(S1,IM)。 if flag1amp。flag3 then signal(S2,IM)。 else signal(S3,IM)。 release(IM)。endprocedure take1begin check(IM): if 桌上沒有香煙原料 then wait(S1,IM)。 else 取原料。 signal(S,IM)。 release(IM)。endprocedure take2begin check(IM): if 桌上沒有香煙原料 then wait(S2,IM)。 else 取原料。 signal(S,IM)。 release(IM)。endprocedure take3begin check(IM): if 桌上沒有香煙原料 then wait(S3,IM)。 else 取原料。 signal(S,IM)。 release(IM)。endbegin flag1:=flag2:=flag3:=true。end.cobegin{ process 供應(yīng)者begin repeat Call ()。 … until false。end process 吸煙者1begin repeat Call ()。 做香煙，吸香煙。 until false。end process 吸煙者2begin repeat Call ()。 做香煙，吸香煙。 until false。end process 吸煙者3begin repeat Call ()。 做香煙，吸香煙。 until false。end}coend.18 如圖所示，四個進(jìn)程Pi（i=0…3）和四個信箱Mj（j=0…3），進(jìn)程間借助相鄰信箱傳遞消息，即Pi每次從Mi中取一條消息，經(jīng)加工后送入M(i+1)mod4，其中M0、MMM3分別可存放2個消息。初始狀態(tài)下，M0裝了三條消息，其余為空。試以P、V操作為工具，寫出Pi（i=0…3）的同步工作算法。P0P1P2P3M1M2M3M0答：var mutex1,mutex2,mutex3,mutex0:semaphore。mutex1:=mutex2:=mutex3:=mutex0:=1。empty0,empty1,empty2,empty3:semaphore。empty:=0。empty1:=3。empty:=2:=empty3:=2。full0,full1,full2,full3:semaphore。full0:=3。full1:=full2:=full3:=0。in0,in1,in2,in3,out0,out1,out2,out3。integer。in0:=in1:=in2:=in3:=out0:=out1:=out2:=out3:=0。cobegin{process P0begin 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。 endprocess P1begin 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。 endprocess P2begin repeat P(full2)。 P(mutex2)。 從M2[out2]取一條消息。 out2:=(out2+1) mod 2。 V(mutex2)。 V(empty2)。 加工消息。 P(empty3)。 P(mutex3)。 消息已M3[in3]。 in3:=(in3+1) mod 2。 V(mutex3)。 V(full3)。 untile false。 endprocess P3begin repeat P(full3)。 P(mutex3)。 從M3[out3]取一條消息。 out3:=(out3+1) mod 2。 V(mutex3)。 V(empty3)。 加工消息。 P(empty0)。 P(mutex0)。 消息已M0[in0]。 in0:=(in0+1) mod 3。 V(mutex0)。 V(full0)。 untile false。 end}coend.19 設(shè)有三組進(jìn)程Pi、Qj、Rk，其中Pi、Qj構(gòu)成一對生產(chǎn)者和消費(fèi)者，共享一個由M1個緩沖區(qū)構(gòu)成的循環(huán)緩沖池buf1。Qj、Rk構(gòu)成另一對生產(chǎn)者和消費(fèi)者，共享一個由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:arrar[0..M11] of item。buffer2:array[0..M21] of item。empty1:=M1。empty:=M2。in1:=in2:=out1:=out2:=0。 counter1:=counter2:=0。full1:=full2:=0。mutex1:=mutex2:=mutex3:=1。cobegin{ process Pibegin L1: P(empty1)。 P(mutex1)。 put an item into buffer[in1]。 in1:=(in1+1) mod M1。 counter++。 if counter1=2 then {counter1:=0。V(full1)。} V(mutex)。goto L1。 end process Qjbegin L2: P(full1)。 P(mutex1)。 take an item from buffer1[out1]。 out1:=(out1+1) mod M1。take an item from buffer1[out1]。 out1:=(out1+1) mod M1。 V(mutex1)。V(empty1)。V(empty1)。Process the products。P(empty2)。 P(mutex2)。put an item into buffer2[in2]。 in2:=(in2+1) mod M2。 counter2++。 if counter2=3 then {counter2:=0。 V(full2)。} V(mutex2)。goto L2。 endprocess Rkbegin L3: P(full2)。 P(mutex2)。 take an item from buffer2[out2]。 out2:=(out2+1) mod M2。 take an item from buffer2[out2]。 out2:=(out2+1) mod M2。 take an item from buffer2[out2]。 out2:=(out2+1) mod M2。 V(mutex2)。V(empty2)。V(empty2)。V(empty2)。packet the products。goto L3。 end}coend20 在一個實時系統(tǒng)中，有兩個進(jìn)程P和Q，它們循環(huán)工作。P每隔1秒由脈沖寄存器獲得輸入，并把它累計到整型變量W上，同時清除脈沖寄存器。Q每隔1小時輸出這個整型變量的內(nèi)容并將它復(fù)位。系統(tǒng)提供了標(biāo)準(zhǔn)例程INPUT和OUTPUT供I/O，提供了延時系統(tǒng)調(diào)用Delay（seconds）。試寫出兩個并發(fā)進(jìn)程循環(huán)工作的算法。答：var W，V:integer。 mutex:semaphore。W:=0。V:=0。mutex:1。c