take an item from buffer1[out1] ; out1:=(out1 + 1) mod M1 ; V ( mutex1 ) ; V ( empty1 ) ; V ( empty1 ) ;
Process the products ; P ( emPty2) ; P ( mutex2 ) ;
put an item into buffer2 [ in2 ] ; in2:=( in2 + l ) mod M2 ; counter2 + + ;
if counter2 = 3 then { counter2:=0 ;V( full2 ) ; } V ( mutex2) ; goto L2 ; process Rk begin L3 : P ( full2 ) ; P ( mutex2 ) ;
take an item from buffer2 [out2]; out2: = ( out2 + 1 ) mod M2 ;
take an item from buffer2 [out2] ; out2:=( out2 + 1) mod M2 ;
take an item from buffer2 [out2]; out2:=(out2 + 1 ) mod M2 ; v ( mutex2 ) ; V ( empty2 ) ; V ( empty2 ) ; V ( empty2 ) ;
packet the products ; goto L3 ; end } coend
20 在一个实时系统中，有两个进程P 和Q ，它们循环工作。P 每隔1 秒由脉冲寄存器获得输入，并把它累计到整型变量W 上，同时清除脉冲寄存器。Q 每隔1 小时输出这个整型变量的内容并将它复位。系统提供了标准例程创PUT 和OUT 卫UT 供拍，提供了延时系统调用Delay ( seconds ）。试写出两个并发进程循环工作的算法。 答：
Var W ,V:integer; Mutex:semaphore;
W:=0 ; V:=0 ;mutex:1; cobegin { process P
begin repeat
P(mutex) ; delay (1) ; V＝INPUT ; W:=W + V ;
清除脉冲寄存器；
V (mutex) ; untile false ; end
process Q begin repeat
P ( mutex ) ; delay ( 60 ) ; OUTPUT ( W ) ; W : = 0 ; V ( mutex ) ; untile false ; }
coend .
21 系统有同类资源m 个，被n 个进程共享，问：当m > n 和m≤n 时，每个进程最多可以请求多少个这类资源时，使系统一定不会发生死锁？
答：当m≤n 时，每个进程最多请求1 个这类资源时，系统一定不会发生死锁。当m > n 时，如果m/n 不整除，每个进程最多可以请求”商＋1 ”个这类资源，否则为”商”个资源，使系统一定不会发生死锁？
22 N个进程共享M 个资源，每个进程一次只能申请释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N 个，证明该系统此时不会产生死锁。
答卜设max ( i ）表示第i 个进程的最大资源需求量，need ( i ）表示第i 个进程还需要的资源量，alloc ( i ）表示第i 个进程已分配的资源量。由题中所给条件可知：
max ( 1 ）+?+max( n ) = ( need (1)+?+need( n ))+((alloc(1)+?+alloc(n)) 如果在这个系统中发生了死锁，那么一方面m 个资源应该全部分配出去，alloc (1) ＋?+alloc ( n ）=m 另一方面所有进程将陷入无限等待状态。可以推出 need(1)+?+need (n)< n 上式表示死锁发生后，n 个进程还需要的资源量之和小于n ，这意味着此刻至少存在一个进程i , need ( i ) = 0 ，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。 答2 ：由题意知道，n×m < m + n 是成立的， 等式变换n×( m - 1 ) + n < n + m 即n×(m-1) < m 于是有n×( m-1 ) + 1 这说明当n 个进程都取得了最大数减1 个即（m- 1 ）个时，这时至少系统还有一个资源可分配。故该系统是死锁无关的。 23 一条公路两次横跨运河，两个运河桥相距100 米，均带有闸门，以供船只通过运河桥。运河和公路的交通均是单方向的。运河上的运输由驳船担负。在一驳船接近吊桥A 时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾P 通过此桥为止。对吊桥B 也按同样次序处理。一般典型的驳船长度为200 米，当它在河上航行时是否会产生死锁？若会，说明理由，请提出一个防止死锁的办法，并用信号量来实现驳船的同步。 答：当汽车或驳船未同时到达桥A 时，以任何次序前进不会产生死锁。但假设汽车驶过了桥A ，它在继续前进，并且在驶过桥B 之前，此时有驳船并快速地通过了桥A ，驳船头到达桥B ，这时会发生死锁。因为若吊起吊桥B 让驳船通过，则汽车无法通过桥B ；若不吊起吊桥B 让汽车通过，则驳船无法通过桥B 。可用两个信号量同步车、船通过两座桥的动作。 var Sa , Sb : semaphore ; Sa:=Sb:=1 ; cobegin { process 驳船 begin P(Sa ) ; P(Sb ) ; 船过桥A 、B ; V(Sa ) ; V(Sb ) ; end process 汽车 begin P ( Sa ) ; P ( Sb ) ; 车过桥A 、B ; V ( Sa ) ; V ( Sb ) ; end } coend 24 Jurassic公园有一个恐龙博物馆和一个花园，有m 个旅客租卫辆车，每辆车仅能乘一个一旅客。旅客在博物馆逛了一会，然后，排队乘坐旅行车，挡一辆车可用喊飞它载入一个旅客，再绕花园行驶任意长的时间。若n 辆车都己被旅客乘坐游玩，则想坐车的旅客需要等待。如果一辆车己经空闲，但没有游玩的旅客了，那么，车辆要等待。试用信号量和P 、V 操作同步m 个旅客和n 辆车子。 答：这是一个汇合机制，有两类进程：顾客进程和车辆进程，需要进行汇合、即 顾客要坐进车辆后才能游玩，开始时让车辆进程进入等待状态 var sc1 , sck , sc ，Kx,xc ，mutex : semaphore ; sck:=kx:=sc:=xc:=0； sc1:=n ；mutex : = 1 ; sharearea ：一个登记车辆被服务乘客信息的共享区； cobegin process 顾客i ( i = 1 , 2 ，? ） begin P ( sc1 ) ; / ＊车辆最大数量信号量 P ( mutex ) ; / ＊封锁共享区，互斥操作 在共享区sharearea 登记被服务的顾客的信息：起始和到达地点，行驶时间 V ( sck ) ; /* 释放一辆车 ,即顾客找到一辆空车 P （Kx）; /* 待游玩结束之后，顾客等待下车 V ( sc1 ) ; /*空车辆数加1 End Process 车辆j(j=1,2,3?) Begin L:P(sck); /*车辆等待有顾客来使用 在共享区sharearea登记那一辆车被使用，并与顾客进程汇合； V(mutex); /*这时可开放共享区，让另一顾客雇车 V(kx); /*允许顾客用此车辆 车辆载着顾客开行到目的地； V(xc); /*允许顾客下车 Goto L; End coend 25 今有k 个进程，它们的标号依次为1 、2 、? 、k ，如果允许它们同时读文件file ，但必须满足条件：参加同时读文件的进程的标号之和需小于K ，请使用：1 ）信号量与P 、v 操作，2 ）管程，编写出协调多进程读文件的程序。 答1 : l ）使用信号量与P 、v 操作 var waits , mutex :semphore ; numbersum:integer:=0 ; wait:=0；mutex:=1 ; cobegin { process readeri ( var number:integer ; ) begin P(mutex ) ; L:if numbersum+number≥ K then { V ( mutex ) ; P ( waits ) ; goto L ; } Then numbersum:numbersum+number; V (mutex ) ; Read file ; P(mutex ) ; numbersum: = numbersum-number ; V(waits ) ; V(mutex ) ; 2 ）使用管程： TYPE sharefile = MONITOR VAR numbersum ,n : integer ; SF : codition ; DEFINE startread , endread ; USE wait , signal , check , release ; procedure startread ( var number ：integer : ) ; begin check (IM ) ; L :if（number + numbersum )≥ K then {wait(SF,IM) ; goto L ; } Numbersum:=numbersum+number; release (IM ) ; end procedure endread (var number:integer ; ) ; begin check(IM ) ; numbersum : = numbersum - number ; signal ( SF , IM ) ; release ( IM ) ; end begin numbersum:=0 end . main() { cobegin process-i() ; coend } process-i() var number : integer ; begin number : ＝进程读文件编号； startread(number);; read F ; endread(number) ; end 26、设当前的系统状态如下：系统此时Available=(1,1,2):