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.