内容发布更新时间 : 2024/12/22 16:53:32星期一 下面是文章的全部内容请认真阅读。

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.