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