LQ:QGET(x); 加工处理 X; QPUT(x); Goto LQ; End
Process R X:=integer; Begin
LR:RGET(X); 打印X; Goto LR; End } Coend 41、下述流程是解决两进程互斥访问临界区问题的一种方法。试从“互斥”（mutual exclusinn ）、“空闲让进(progress ）、“有限等待(bounded waiting ）等三方面讨论它的正确性。如果它是正确的，则证明之；如果它不正确，请说明理由。
Program attemp; Var c1,c2:integer;
Procedure p1; (/*对第一个进程P1*/) Begin Repeat
Remain section 1; Repet
C1:=1-c2; Until c2<>0;
Critical section; (/*临界区*/) C1:=1;
Until false End;
Procedure p2; (/*对 另一个进程p2*/) Begin Repet
Remain section 2; Repeat C2:=1-c1
Until c1<>0;
Critical section; (/* 临界区*/) C2:=1
Until false End;
Begin (/*主程序*/) C1:=1;
C2:=1; Cobegin
P1;P2 (/*两进程P1,P2开始执行*/) Coend End
答：( 1 ）互斥
己知cl 和c2 的初值为1 ，若进程P1 执行到c1: = 1-c2 时，进程P2 也同时执行c2 : = 1-c1 ．这样一来，c1和c2 的值都变为0，接着再各自执行，repeat---untile循环语句c1: = 1-c2 和c2 :=1-c1 时， c1 和c2 就又都变回了1。于是，P1 和P2 会同时进入临界区，不满足互斥条件。 ( 2 ）有空让进
设开始无进程在临界区中，进程P1 执行了c1 :=1-c2 ，由于c2 的初值为1 ，这使得c1 的值变为0 但c2 仍为1 ，从而保证了P1进入临界区。当P1退出临界区时，执行了c1 :=1，使得P2 就可进入临界区。进程P2先执行的情况相似，能保证有空让进的原则。 ( 3 ）有限等待
假定进程P1在临界区执行，进程P2 申请进入临界区，则因进程P1会在有限时间内执行完并退出临界区，然后，将执行c1 : = 1 ，这使得进程P2 因c1 值为1 而立即可进入临界区。因而，能满足有限等待的原则。 42 分析下列算法是否正确，为什么？ repeat key:=true; repeat
swap ( lock , key ) : until key=false;
Critical section （/＊临界区*/） Lock:=false; Other code ; Until false; 答：由于lock 的初值未定，如果它的值false ，则可通过swap 实现上锁操作。但如果lock 的初值为true，那么，进程会永远等待而进不了临界区． 43 以下并发执行的程序，仅当数据装入寄存器后才能加1 Const n =50；
var tally :integer : procedure total ( ) var count ：integer ; Begin
For count:=1 to n do tally:=tally+1 End;
Begin (/*main program*/) Tally:=0; Cobegin
Total();total() Coend;
Writeln(tally); End.
给出该并发程序输出的tally值的上限和下限． 答：tally 值的上限和下限为100 和50 . 44 举例说明下列算法不能解决互斥问题。 var balocked ：array[ O?1] of boolean ; turn:0?1;
procedure P[id:integer]; begin repeat
blocked[id]:=true; while turn≠id do begin
while blocked [1-id] do Skip; turn: = id ; end;
{critical section } blocked[id]:＝false : {remainder } until false end; begin
blocked [ 0 ]: blocked[1]:=false ; turn:=0; cobegin P[0] ;P[1] coend ; end.
答：为方便描述，把程序语句进行编号： Blocked[id]:=true; ① while turn≠id do ② begin
while blocked[1-id] do skip; ③ Turn:=id; ④ End;
假设id=0，则1-id =1 ，并且turn = 1 ．当进程P[id] 先执行① 置
blocked[id]=true ：接着执行② 时，因为turn≠id 而进入到③ 执行．此时，因blocked[1-id]为false （初值），故在③ 上不做空操作而打算去做④ 。麻烦的事情发生了，如果在P[ id ] 执行④ 之前，系统又调度执行P[1-id ] , 而P [ 1-id] 在执行了① 置blocked[1-id]=true 之后，在执行② 时，因发现turn =1-id ，故退出了while ，直接进入临界区。而这时P[id ]继续执行④ ，虽然置turn=id 但已无法挡住P[1-id] 先己进入了临界区的事实，此后，P[ id ]也进入临界区。
所以，该算法不能解决互斥问题，它会让两个进程同时进入临界区。
45 现有三个生产者P1 、P2 、P3 ，他们都要生产水，每个生产者都已分别购得两种不同原料，待购得第三种原料后就可配制成桔子水，装瓶出售。有一供应商能源源不断地供应糖、水、桔子精，但每次只拿出一种原料放入容器中供给生产者。当容器中有原料时需要该原料的生产者可取走，当容器空时供应商又可放入一种原料。假定：生产者P1已购得糖和水； 生产者P2 已购得水和桔子精； 生产者P3 已购得糖和桔子精；
试用：1 ）管程，2)信号量与P 、v 操作，写出供应商和三个生产者之间能正确同步的程序． 答：1 ）管程．
TYPE makedrink = monitor
VAR S , S1 , S2 , S3 : condition ; container:item ;
DEFINE give , produce1 , produce2 , produce3 ; USE check , wait , signal , re lease ; procedure give begin
Check ( IM ) ;
take raw material ;
ifcontainer≠null then wait ( S , IM ) ; else container : = rawn materiai ;
if （container）=桔子精then singal ( s1 , IM ) ; eise if ( container)=糖 then signal(S2 ，IM）; else signal ( S3 , IM ) ; release ( IM ) ; end
procrdure produce1 begin
check ( IM ) ;
if ( c ontainer ）≠桔子精 then wait ( s1 , IM ) ; else { take the 桔子精 from container ；做桔子水；} signal ( S ，IM）; re1ease ( IM ) ; end
procrdure produce2 begin
check(IM);
IF(CONTAINER)≠糖 then wait(S2,IM);
Else{take the 糖 from container;做橘子水；} Signal(S,IM); Release(IM); End
Procrdure produce3 Begin
Check(IM);
If(container)≠水 then wait(S3,IM);
Else{take the 水 from container;做橘子水;} Signal(S,IM); Release(IM); End Begin
Container{糖，水，橘子精}; End
Cobegin {
Process 供应商 Begin Repeat ?
Call makedrink.give(); ?
Until false; End
Process P1 Begin repeat ?
Call makedrink.produce1(); ?
Until false; End
Process P2 Begin Repeat ?
Call makedrink.produce2(); ?
Until false; End
Process P3 Begin Repeat ?
Call makedrink,produce3(); ?
Until false; End }
Coend.