第三章 同步、通讯与死锁
1、 有三个并发进程:R 负责从输入设备读入信息块,M 负责对信息块加工处理;P 负责打印输出信息块。今提供; l )一个缓冲区,可放置K 个信息块; 2 )二个缓冲区,每个可放置K 个信息块;
试用信号量和P 、V 操作写出三个进程正确工作的流程。 答:
1 ) var B : array [ 0 , k-1 ] of item ; sread : semaPhore : = k ; smanage : semaPhore : = 0 ; swrite : semaphore : = 0 ; rptr : integer : = O ; mptr : integer : = O ; wptr :integer : = 0 ; x : item cobegin
process reader ; process manager ; process writer ; begin begin begin
LI : read a message intox ; L2 : P ( smanage ) ; L3 : P ( swnte ) ; P ( sread ) ; x:=B[mptr]; x:=B[swrite];
B[rptr]:=x; mptr:=(mptr+1) mod k; wptr:=(wptr+1) mod k; Rptr:=(rptr+1) mod k; manage the message in x; V(sread); V(smanage); B[mptr]:=x; print the message in x; Goto L1; V(swrite); goto L3; End; goto L2; end; End; coend
2 ) var A , B :array [ 0 , k -l ] of item ; sPut1 : semaphore:=k; SPut2: semaPhore:=k;
sget1 : semaPhore : = 0 ; sget2 : semaphore : = 0 ; put1 :integer :=O ; put2:integer : = 0 ; get1 :integer :=O ; get2 : integer : = O ; cobegin
process reader ; processn manager; process Writer ;
begin begin begin
Ll : read a message into x ; L2 : P ( sgetl ) ; L3 : P ( sgetZ ) ; P ( SPut1 ) ; x : = A [ get1] ; x : = B [get2];
A [put1]:=x ; get1 :(get1+1 ) mod k ; get2:=(get2 + l ) mod k ; Put1:=(put1+1) mod k; V(sput1); V(sput2);
V(sget1); manage the message into x; print the message in x; Goto L1; P(sput2); goto L3; Put2:=(put2+1) mod k; V(sget2); Goto L2; End; Coend
2 设有n 个进程共享一个互斥段,如果: ( 1 )每次只允许一个进程进入互斥段;
( 2 )每次最多允许m 个进程(m 簇n )同时进入互斥段。
试问:所采用的信号量初值是否相同?信号量值的变化范围如何? 答:所采用的互斥信号量初值不同。
1 )互斥信号量初值为1 ,变化范围为[-n+l , 1 ]。
当没有进程进入互斥段时,信号量值为1 ;当有1 个进程进入互斥段但没有进程等待进入互斥段时,信号量值为O ;当有1 个进程进入互斥段且有一个进程等待进入互斥段时,信号量值为-1 ;最多可能有n -1 个进程等待进入互斥段,故此时信号量的值应为-(n - 1 )也就是-n+1 。
2 )互斥信号量初值为m ,变化范围为[-n+m , m ]。
当没有进程进入互斥段时,信号量值为m ;当有1 个进程进入互斥段但没有进程等待进入互斥段时,信号量值为m - 1 :当有m 个进程进入互斥段且没有一个进程等待进入互斥段时,信号量值为0 :当有m 个进程进入互斥段且有一个进程等待进入互斥段时,信号量值为一l ;最多可能有n - m 个进程等待进入互斥段,故此时信号量的值应为-(n-m)也就是-n+m.
3 有两个优先级相同的进程P1和P2,各自执行的操作如下,信号量S1和S2初值均为0。试问Pl 、P2 并发执行后,x 、y 、z 的值各为多少? P1: P2:
Begin begin Y:=1; x:=1; Y:=y+3; x:=x+5; V(S1); P(S1); Z:=Y+1; X:X+Y; P(s2); V(S2); Y:=z+y; z:=z+x; End end
答:现对进程语句进行编号,以方便描述. P1 : P2 : begin begin
y : = 1 ;① x :=1 ; ⑤
y :=y+3 ;② x :x+5 ; ⑥ V(S1); P(S1);
Z:Y+1 ;③ x :X+Y ;⑦ P(s2); V(S2);
Y:=z+y; ④ z:=Z+X;⑧ End end
① 、② 、⑤ 和⑥ 是不相交语句,可以任何次序交错执行,而结果是唯一的。接着无论系统如何调度进程并发执行,当执行到语句⑦ 时,可以得到x = 10 , y = 4 。按Bernstein 条件,语句③ 的执行结果不受语句⑦ 的影响,故语句③ 执行后得到z = 5 。最后,语句④ 和⑧ 并发执行,这时得到了两种结果为: 语句④ 先执行:x =10 , y =9 , z= 150 语句⑧ 先执行:x =10 , y =19 , z =15
此外,还有第三种情况,语句③ 被推迟,直至语句⑧ 后再执行,于是依次执行以下三个语句: 7 :二z + X : z : = y + 1 ; y : =Z十y ;
这时z 的值只可能是y +1=5 ,故y =Z+Y=5 + 4=9,而x = 10 。 第三种情况为:x = 10 ,Y=9 , Z = 5 。 4 有一阅览室,读者进入时必须先在一张登记表上登记,该表为每一座位列出一个表目,包括座号、姓名,读者离开时要注销登记信息;假如阅览室共有100 个座位。试用:l )信号量和P 、V 操作;2 )管程,来实现用户进程的同步算法。 答:1 )使用信号量和P 、v 操作: var name :array [ l …100]of A ; A = record
number :integer ; name:string ; end
for i : = 1 to 100 do {A [ i ].number :i;A [ i ].name :null;} mutex , seatcount : semaphore ;
i : integer ;mutex : = l ; seatcount : = 100 ; cobegin {
process readeri ( var readename:string ) (i=1 , 2 …) {
P ( seatcount ) ; P (mutex ) ;
for i : = 1 to 100 do i++
if A [ i ].name=null then A [ i ].name:readername; reader get the seat number=i;/*A[I].number V ( mutex )
进入阅览室,座位号i ,座下读书; P ( mutex ) ; A[i]name:null ;
V (mutex ) ; V(seatcount); 离开阅览室; } } coend
2 )使用管程操作: TYPE readbook=monitor VAR R: condition ; I,seatcount :integer;
name:array [ l:100] of string ; DEFINE rcadercome, readerleave ;
USE check , wait , signal , release ; Procedure readercome ( readername ) begin
check ( IM ) ;
if seatcount≥100 wait ( R,IM ) seatcount : = seatcount + 1 ; for i=1 to 100 do i++
if name[i] ==null then name[i]:= readername; get the seat number = i ; release ( IM ) ; end
procedure readerleave ( readername ) begin
check ( IM ) ; seatcount--;
for i = 1 to 1 00 do i++
if name[i ]readername then name[i]:null; release ( IM ) ; end begin
seatcount : = 1OO ; name:=null ; end
cobegin {
process readeri ( i = 1 , 2 .… ) begin
readercome ( readername); read the book ;
readerleave ( readername); leave the readroom; end }
coend.
5. 在一个盒子里,混装了数量相等的黑白围棋子· 现在用自动分拣系统把黑子、白子分开,设分拣系统有二个进程P1 和P2 ,其中P1 拣白子;P2 拣黑子。规定每个进程每次拣一子;当一个进程在拣时,不允许另一个进程去拣;当一个进程拣了一子时,必须让另一个进程去拣.试写出两进程P1 和P2 能并发正确执行的程序。
答1 :实质上是两个进程的同步问题,设信号量s1 和s2 分别表示可拣白子和黑子,不失一般性,若令先拣白子。 var S1 , S2 : semaphore; S1 : = l; S2 :=0; cobegin {
process P1 begin repeat P( S1 ) ; 拣白子
V ( S2 ) ; until false ; end
process P2 begin repeat
P ( S2 ) ; 拣黑子
V (S1 ) ; until false ; end }
coend . 答2 :
TYPE pickup-chess = MONITOR VAR flag : boolean ;
S-black , s-white : codition ;
DEFINE pickup-black , pickup-white ; USE wait,signal , check , release ; procedure pickup-black ; begin
check(IM ) ;
if flag then wait(s-black,IM ) ; flag : =true; pickup a black;
signal(S-white,IM); release ( IM ) ;