send 操作。
3 ）接收消息是一个出队操作，当队列存储区空时，设计另一个同步信号量阻塞receive 操作。
( 2 ）用消息传递实现信号量。
l ）为每一个信号量建立一个同步管理进程，它包含了一个计数器，记录信号量值；还为此信号量设立一个等待进程队列
2 ）应用进程执行P 或V操作时，将会调用相应P 、V库过程。库过程的功能是：把应用进程封锁起来，所执行的P 、V 操作的信息组织成消息，执行send 发送给与信号量对应的同步管理进程，之后，再执行receive 操作以接收同步管理进程的应答。
3 ）当消息到达后，同步管理进程计数并查看信号量状态。如果信号量的值为负的话，执行P 操作的应用进程被阻塞，挂到等待进程队列，所以，不再要送回答消息。此后，当V 操作执行完后，同步管理进程将从信号量相应队列中选取一个进程唤醒，并回送一个应答消息。正常情况下，同步管理进程回送一个空应答消息，然后，解锁执行P 、V 操作的应用程序。 14 使用（1）消息传递，( 2 ）管程，实现生产者和消费者问题。答：( 1 ）见课文ch3 3.5.4 节。（2 ）见课文Ch3 3.4.3 节。
15 试利用记录型信号量和P 、V 操作写出一个不会出现死锁的五个哲学家进餐问题的算法。答：
var forki:array [0?4] of semaphore ; forki:=1 ; cobegin {
process Pi /* i = 0 , 1 , 2 , 3 */ begin L1 : 思考：
P(fork[i]) ; / * i =4,P(fork [0]) * /
P(fork[i+1] mod 5) / * i =4P（fork [4]）* / 吃通心面； V (fork[i] ;
V (fork([i+1] mod 5 ) ; goto L1 ; end ; }
coend ;
16 Dijkstra 临界区软件算法描述如下：
var flag ：array[0?n] of (idle,want-in ，in_cs ) ; turn:integer ; tune:0 or 1 or ? or , n-1 ; process Pi(i=0,1，?,n-1) 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 ) & (j==1 or flag[j] ≠in_cs ) do j:=j + 1 ; until j≥n :
critical section ; flag [i]:=idle ; ??
until false ; end .
试说明该算法满足临界区原则。
答：为方便描述，把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 ) & (j==1 or flag[j] ≠in_cs ）⑤ do j:=j + 1 ; @ until j≥n ;
critical section ; flag[i] :=idle ；⑦ ?
( l ）满足互斥条件
当所有的巧都不在临界区中，满足flag[j]≠in_cs（对于所有j , j≠i ）条件时，Pi 才能进入它的临界区，而且进程Pi 不会改变除自己外的其他进程所对应的flag[j]的值。另外，进程Pi 总是先置自己的flag[j]为in_cs后，才去判别Pj进程的flag[j]的值是否等于in_cs 所以，此算法能保证n 个进程互斥地进入临界区。
( 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 ) :