使用银行家算法，以确定下面的任何一个请求是否安全。（l ) P4 进程到达，P4 最大需求60 ，最初请求25 个。（2 ) P4 进程到达，P4 最大需求60 ，最初请求35 。如果安全，找出安全序列；如果不安全，给出结果分配情况。 答：

( l ）由于系统目前还有150-25-40-45=40 个单元，P4 进程到达，把25 个单元分给它。这时系统还余15 个单元，可把15 个单元分给P3 ，它执行完后会释放60 个单元。于是可供P1 （还要45 个单元）, P2 （还要20 个单元）, P4(还要35 个单元)任何一个执行。 安全序列为：

（1）P4进程到达，P4最大需求60，最初请求35 。如果把35 个单元分给P4 ，系统还余5个单元，不再能满足任何一个进程的需求，系统进入不安全状态。 30 有一个仓库，可存放X 、Y 两种产品，仓库的存储空间足够大，但要求：( l ）每次只能存入一种产品X或Y , ( 2 ）满足-N＜X 产品数量-Y 产品数量＜M 。其中，N 和M 是正整数，试用信号量与P 、V 操作实现产品X 与Y 的入库过程。 答：本题给出的表达式可分解为制约条件： -N < X 产品数量-Y 产品数量 X 产品数量-Y 产品数量＜M

也就是说，X 产品的数量不能比Y 产品的数量少N 个以上，X 产品的数量不能比Y 产品的数量多M 个以上。可以设置两个信号量来控制X 、Y 产品的存放数量： SX 表示当前允许X 产品比Y 产品多入库的数量，即在当前库存量和Y 产品不入库的情况下，还可以允许SX个X产品入库；初始时，若不放Y而仅放X产品，则SX最多为M-1个。

sy 表示当前允许Y 产品比x 产品多入库的数量，即在当前库存量和x 产品不入库的情况下，还可以允许sy 个Y 产品入库．初始时，若不放X 而仅放Y 产品，则sy 最多为N -1 个。当往库中存放入一个X 产品时，则允许存入Y 产品的数量也增加1 ，故信号量sy 应加1 ：当往库中存放入一个Y 产品时，则允许存入X 产品的数量也增加1 ，故信号量sx 应加1 . var mutex : semaphore = 1 /*互斥信号量＊/ sx , sy : semaphore;

sx = M-1 ; sy = = N - l ; cobegin {

process X ｛repeat P(sx ) ;

P （mutex ) ;

将X 产品入库； V(mutex ) ; V ( sy ) ; until false }

process Y { repeat P ( sy ) ; P （mutex ) ; 将Y 产品入库； V （mutex ) ; V ( px ) ; until false } }

coend .

31 有一个仓库可存放A 、B 两种零件，最大库容量各为m 个。生产车间不断地取A 和B 进行装配，每次各取一个．为避免零件锈蚀，按先入库者先出库的原则。有两组供应商分别不断地供应A 和B ，每次一个。为保证配套和合理库存，当某种零件比另一种零件超过n ( n < m ）个时，暂停对数量大的零件的进货，集中补充数量少的零件．试用信号量与P 、V 操作正确地实现它们之间的同步关系。 答：按照题意，应满足以下控制关系：A 零件数量-B 零件数量≤n ; B 零件数量-A 零件数量≤n : A 零件数量≤m ; B 零件数量≤m ．四个控制关系分别用信号量sa 、sb 、empty1 和empty2 实施。为遵循先入库者先出库的原则，A 、B 零件可以组织成两个循形队列，并增加入库指针in1 、in2 和出库指针out1 、out2 来控制顺序。并发程序编制如下：

Var empty1,empty2,full1,full2:semaphore; Mutex ,sa,sb:semaphore; In1,in2,out1,out2:integer;

Buffer1,buffer2:array[0…m-1]of item; Empty1:=empty2:=m; Sa:=sb:=n;

In1:=in2=out1:=out2:=0; Cobegin {

Process producerA {repeat P(empty1); P(sa); P(mutex);

Buffer1[in1]:=A零件; In1:=(in1+1)mod m; V(mutex);

V(sb); V(full1); Untile false; }

Process producer B {repeat P(empty2); P(sb); P(mutex);

Buffer2[in2]:=B零件; In2:=(in2+1)mod m; V(mutex); V(sa); V(full2); Untile false; }

Process take {repeat P(full1); P(full2); P(mutex);

Take from buffer1[out1] and buffer2[out2]中的A，B零件； Out1:=(out1+1)mod m; Out2:=(out2+1)mod m; V(mutex); V(empty1); V(empty2);

把A和B装配成产品； Until false } }

Coend.

32 进程Al 、A2 、…、An1 通过m 个缓冲区向进程B1 、B2 、… 、Bn2 不断地发送消息．发送和接收工作符合以下规则： ( l ）每个发送进程每次发送一个消息，写进一个缓冲区，缓冲区大小与消息长度相等；

( 2 ）对每个消息，Bl 、BZ 、二、BnZ 都需接收一次，并读入各自的数据区内； ( 3 ）当M 个缓冲区都满时，则发送进程等待，当没有消息可读时，接收进程等待．

试用信号量和PV 操作编制正确控制消息的发送和接收的程序。

答：本题是生产者一消费者问题的一个变形，一组生产者A1 , A2 ，… An1 和一组消费者B1 , B2 ，… Bn2 共用m 个缓冲区，每个缓冲区只要写一次，但需要读n2 次。因此，可以把这一组缓冲区看成n2 组缓冲区，每个发送者需要同时写n2 组

缓冲区中相应的n2 个缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。

应设置一个信号量mutex 实现诸进程对缓冲区的互斥访问；两个信号量数组empty[n2]和full[n2]描述n2 组缓冲区的使用情况．其同步关系描述如下： var mutex , empty[n2],full[n2]:semaphore ; i :integer ; mutex=1 ; for(i=0;i<=n2-1;i++) {

empty[i]=m; Full[i]=0; }

main ( ) {

cobegin A1 ( ) ; A2 ( ) ; …

An1 ( ) ; B1 ( ) ; B2 ( ) ; …

Bn2 ( ) ; coend

send ( ) / ＊进程Ai 发送消息＊/ { int i ;

for （i=0;i<=n2-1;i++）; P(empty[i]); P (mutex ) ;

将消息放入缓冲区； V （mutex ) ;

for(i=0；i<=n2-1;i++) V(full[i]); }

receive (i) /＊进程Bi 接收消息＊/ {

P(full[i]); P(mutex);

将消息从缓冲区取出； v （mutex ) ; v ( empy[i]) ;

Ai ( ) / ＊发送进程A1 , A2 ，… An1 的程序类似，这里给出进程Ai 的描述＊l { {

While(1) { …

send ( ) ; … } }

Bi ( ) /＊接收进程Bl , B2 ，… BnZ 的程序类似，这里给出进程Bi 描述＊/ {

while(i) ( …

receive ( i ) ; … } }

某系统有R1 设备3 台，R2 设备4 台，它们被Pl 、PZ 、P3 和P4 进程共享，且己知这4 个进程均按以下顺序使用设备：

一申请Rl 一申请R2 一申请RI ～释放Rl 一释放R2 一释放Rl ( 1 ）系统运行中可能产生死锁吗？为什么？

( 2 ）若可能的话，请举出一种情况，并画出表示该死锁状态的进程一资源图． 答：( l ）系统四个进程需要使用的资源数为Rl 各2 台，R2 各1 台。可见资源数不足，同时各进程申请资源在先，有可能产生死锁发生的四个条件，故系统可能产生死锁。( 2 ）当三个进程执行完申请资源Rl ，开始执行申请资源R2 时，第四个进程会因没有资源Rl 而被阻塞。当三个进程执行完申请资源R2 后，系统还剩1 个R2 资源。而这三个进程因执行申请第二个资源Rl 而全部被阻塞，系统进入死锁。

34 如图所示，左右两队杂技演员过独木桥，为了保证安全，请用PV 操作和信号量来解决过独木桥问题。只要桥上无人，则允许一方的人过桥，待一方的人全部过完后，另一方的人才允许过桥。