内容发布更新时间 : 2024/5/9 4:02:18星期一 下面是文章的全部内容请认真阅读。

地进入临界区。

( 2 ）不会发生无休止等待进入临界区

由于任何一个进程Pi 在执行进入临界区代码时先执行语句① ，其相应的flag[i]的值不会是idle 。注意到flag[i]＝in_cs 并不意味着turn的值一定等于i 。我们来看以下情况，不失一般性，令turn 的初值为0，且P0不工作，所以，flag[turn]=flag[0]=idle。但是若干个其他进程是可能同时交替执行的，假设让进程Pj(j=l , 2 , ?n-l）交错执行语句① 后（这时flag[j]=want_in），再做语句② （第一个while 语句），来查询flag[turn]的状态。显然，都满足turn≠i ，所以，都可以执行语句③ ，让自己的turn 为j 。但turn仅有一个值，该值为最后一个执行此赋值语句的进程号，设为k 、即turn=k (1≤k≤n -1 ）。接着，进程Pj(j=1,2,?n-l ) 交错执行语句④ ，于是最多同时可能有n-1 个进程处于in_cs 状态，但不要忘了仅有一个进程能成功执行语句④ ，将加m 置为自己的值。

假设｛P1 , P2 ，? Pm ｝是一个己将flag[i] 置为in_cs ( i =1,2,?,m ) ( m ≤n -1）的进程集合，并且已经假设当前turn=k ( 1≤k≤m ) ，则Pk 必将在有限时间内首先进入临界区。因为集合中除了Pk 之外的所有其他进程终将从它们执行的语句⑤ （第二个while 循环语句）退出，且这时的j 值必小于n ，故内嵌until 起作用，返回到起始语句① 重新执行，再次置flag [ i ] = want_in ，继续第二轮循环，这时的情况不同了，flag[turn] =flag[ k] 必定≠idle （而为in_cs ）。而进程Pk 发现最终除自身外的所有进程Pj 的flag[j]≠in_cs ，并据此可进入其临界区。

17 另一个经典同步问题：吸烟者问题(patil , 1971 ）。三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试采用：( 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 供应者 begin repeat P(S) ;

取两样香烟原料放桌上，由flagi标记； / * nago1 、nage2 、nage3 代表烟草、纸、火柴

if flag2 & flag3 then V(S1) ; / ＊供纸和火柴

else if flag1 & fiag3 then V(S2 ) ; / ＊供烟草和火柴 else V(S3) ; / ＊供烟草和纸 untile false ; end

process 吸烟者1 begin repeat P(S1) ; 取原料； 做香烟； V(S) ; 吸香烟； untile false ; process 吸烟者2 begin 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 & flag3 then signal ( S1 ,IM）;

if flag1 & 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 take2 begin

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 供应者 begin repeat

Call makesmoke.give(); ??

until false ; end

process 吸烟者1 begin repeat

Call makesmoke.take1() ; 做香烟，吸香烟；

until false ; end

process 吸烟者2 begin repeat

Call makesmoke.take2() ; 做香烟，吸香烟； until false ; end

process 吸烟者3 begin repeat

Call makesmke.take3();

做香烟，吸香烟； until false ; end }

coend .

18、 如图所示，四个进程Pi （i=0? 3 ）和四个信箱Mj (j=0? 3 ) ，进程间借助相邻信箱传递消息，即Pi 每次从Mi中取一条消息，经加工后送入M(i + 1) mod4 ，其中M0 、M1 、M2 、M3 ;可存放3 、3 、2 、2 个消息。初始状态下，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];