PV操作习题答案说课材料.docx

PV操作习题答案说课材料.docx

《PV操作习题答案说课材料.docx》由会员分享，可在线阅读，更多相关《PV操作习题答案说课材料.docx（21页珍藏版）》请在冰点文库上搜索。

PV操作习题答案说课材料

信号量应用问题：

1．写出程序描述下列前趋关系。

S1->S2,S1->S3,S2->S4,S2->S5,S3->S6,S4->S7,S5->S7,S6->S7

Vars1,s2,s3,s4:

semaphore:

=0,0,0,0;

Begin

Parbegin

P1:

begin

….;

V（s1）;

V（s1）;

End;

P2:

begin

P（s1）;

…;

V（s2）;

V（s2）;

End;

P3:

begin

P（s1）

…

V（s3）

End;

P4:

begin

P（s2）;

…

V（s4）;

P5:

begin

P（s2）;

..;

V（s4）;

End;

P6:

begin

P（s3）

..

V（s4）

End;

P7:

begin

P（s4）;

P（s4）;

P（s4）;

…

End;

Parend

end

2.请用信号量实现4×100（4人，每人100米）接力赛的同步过程。

提示：

前趋图同步问题，可设4个进程，三个信号量，进程1只设V操作，进程4只设P操作，其余进程先做P操作再做V操作。

Vars1,s2,s3:

semaphore:

=0,0,0;

Begin

Parbegin

Athlete1:

begin

Run100m;

V（s1）;

End;

Athlete2:

begin

P（s1）

Run100m;

V（s2）;

End;

Athlete3:

begin

P（s2）;

Run100m;

V（s3）;

End;

Athlete4:

begin

P（s3）;

Run100m;

End;

Parend

end

3．设公共汽车上，司机和售票员的活动分别是：

 司机：

    售票员：

  启动车辆   上乘客

  正常行车   关车门

  到站停车   售票

         开车门

         下乘客

 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？

请用信号量机制实现他们的同步。

/-假定初始状态为停车状态，引入信号量Stop和Run：

 BEGIN

  semaphoreStop,Run;

  Stop:

=Run:

=0;

  CoBegin

   Driver:

 BEGIN

         Repeat

          Wait（Run）;

          启动车辆；

          正常行驶；

          到站停车；

          Signal（Stop）;

         UntilFalse;

        END;

   Conductor:

BEGIN

         Repeat

          上乘客；

          关车门；

          Signal（Run）;

          售票；

          Wait（Stop）;

          开车门；

          下乘客；

         UntilFalse;

        END;

  CoEnd;

 END;

生产者消费者问题：

1．桌上有一个可以容纳两个水果的盘子，每次只能放或取一个水果。

爸爸放苹果妈妈放橘子，两个儿子吃苹果，两个女儿吃橘子。

试用信号量和P、V操作，编写实现爸爸、妈妈、儿子和女儿的并发工作程序。

Mutex实现互斥放或取水果。

empty盘子可放水果数

Apple盘子中放的苹果数

Orange盘子中放的橘子数

Semaphoremutex=1;

Semaphoreempty=2;

Semahporeapple=0;

Semahporeorange=0;

Main（）

{

Cobegin

Father（）;

Mother（）;

Son（）;

Daughter（）;

;

Coend）

}

Father（）

{

While（true）

{p（empty）

P（mutex）

放苹果

V（mutex）

V（apple）}

}

Mother（）

{

While（true）

{p（empty）

P（mutex）

放橘子

V（mutex）

V（orange）}

}

Son（）

{

While（true）

{p（apple）

P（mutex）

取苹果

V（mutex）

V（empty）}

}

Daughter（）

{

While（true）

{p（orange）

P（mutex）

取橘子

V（mutex）

V（empty）}

}

2、有一个仓库存放两种零件A和B，最大库容量各为m个。

有一车间不断地取A和B进行装配，每次各取一个。

为了避免零件锈蚀，遵循线入库者先出库的原则。

有两组供应商分别不断地供应A和B（每次一个），为保证齐套和合理库存，当某种零件的数量比另一种数量超过n（n

试用P、V操作正确实现之。

 semaphoremutex=1,emptya=emptyb=m,fulla=fullb=0,sa=sb=n;

 main（）

 {CoBegin

   Provider_A（）;   //零件A供应商

   Provider_B（）;   //零件B供应商

   Assembling_Shop（）;//装配车间

  CoEnd

 }

 Provider_A（）

 {while（true）

  {p（emptya）;

   p（sa）;

   p（mutex）;

   将零件A放入仓库;

   v（mutex）;

   v（fulla）;

   v（sb）;

  }

 }

 Provider_B（）

 {while（true）

  {p（emptyb）;

   p（sb）;

   p（mutex）;

   将零件B放入仓库;

   v（mutex）;

   v（fullb）;

   v（sa）;

  }

 }

 Assembling_Shop（）

 {while（true）

  {p（fulla）;

   p（fullb）;

   p（mutex）;

   装配零件;

   v（mutex）;

   v（emptya）;

   v（emptyb）;

  }

 }

3、有一个仓库，可以存放A和B两种产品，仓库的存储空间足够大，但要求：

 每次只能存入一种产品（X或Y）；

 -N

 其中，N和M时正整数。

 试用“存放A”、“存放B”和P、V操作描述产品A与产品B的入库过程。

A-B

如果只放A不放B，则A最多可放M-1个，如果多放一个B，则可以多放一个A。

B-A

如果只放B不放A，则B最多可放N-1个，如果多放一个A，则可以多放一个B。

/2-BEGIN

  Mutex,SA,SB:

semaphore;

  Mutex:

=1;

  SA:

=M-1;

  SB:

=N-1;

  parBegin

   processPA

    Begin

loop:

     P（SA）;

     P（Mutex）;

     存放A;

     V（Mutex）;

     V（SB）;

Gotoloop;

    End;

    processPB

    Begin

    loop:

 P（SB）;

     P（Mutex）;

     存放B;

     V（Mutex）;

     V（SA）;

Gotoloop;

    End;

   parEnd;

 END;

/北大91

读者写者问题：

1、多个进程共享一个文件，其中只读文件的程值为读者，其余只写文件的称为写者。

读者可以同时读，但写者只能独立地写。

 说明进程间的相互制约关系，应设置哪些信号量？

 用P、V操作写出其同步算法；

 修改上述算法，使得它对写者优先，即一旦有写者到达，后续的读者都必须等待，而无论是否有读者在读文件。

（该问题的又一提法：

在一个飞机订票系统中，多个用户共享一个数据库。

多用户同时查询是可以接受的，但若一个用户要订票需更新数据库时，其余所有用户都不可以访问数据库。

请画出用户查询与订票的逻辑框图（等价于同步进程的描述的图式表示）。

为了提高写者的优先级，增加一个信号量S，用于在写进程到达后封锁后续的读者

Semaphoremutex=1;

Semaphorewrite=1;

Semahpores=1;

Intcount=0;

Main（）

{

Cobegin

Reader（）;

Writer（）;

Coend；

}

Reader（）

{while（true）

{

P（s）;

P（mutex）;

If（count==0）p（write）;

Count++;

V（s）;

读文件；

P（mutex）

Count--;

If（count==0）v（write）;

V（mutex）;

}

}

Writer（）

{

While（true）

{p（s）;

P（write）;

写文件；

V（write）;

V（s）;

}

}

2．某一桥只有一车道，载重为4辆车，用P、V操作实现两方向的车过桥。

本题本质上可以认为是读者写者问题，往同一个方向的车可以认为是读者，往相反方向的车可以认为是写者。

但是由于桥的重量有限，增加了读者之间的互斥。

本题的临界资源显然是单通道的桥，首先如果桥上有向东方向的车，那么向西方向的车一定不能过，如果超过4辆，同一方向的车也不能过，需要互斥。

设信号量mutex，实现双向车子互斥通行；信号量sew，swe表示由西向东与由东向西的负荷数，初值为4；整数型iew,iwe表示各方向的车子数，初值为0；siew,siwe实现对iew,iwe的互斥访问，初值为1；

Process由东向西的车子；

Begin

P（sew）;

P（siew）;

Iew:

=iew+1;

Ifiew=1thenp（mutex）;

V（siew）;

过桥；

P（siew）;

Iew:

=iew-1;

Ifiew=0thenv（mutex）;

V（siew）;

V（sew）

End

Porcess由西向东

Begin

P（swe）;

P（siwe）;

Iwe:

=iwe+1;

Ifiwe=1htenp（mutex）;

V（siwe）;

过桥；

P（siwe）;

Iwe:

=iwe-1;

Ifiwe=0thenv（mutex）;

V（siwe）;

V（swe）

End;

理发师睡觉问题：

1．（睡眠的理发师问题）理发店有一个等候室（其中有N把椅子）和一个理发室（一把理发椅组成）。

如果没有顾客来理发，理发时就在理发椅上睡觉，如果一个走进理发店，发现等候室的椅子都坐满就离开理发店；如果理发师正忙于理发，那么该顾客就坐在一把空椅子上等待；若理发师正在睡觉，则顾客就唤醒他。

用P、V操作写出工作流程。

考点：

用PV原语实现同步

Semaphorecostomers=0;等候的顾客数（不包括正在理发的）

Semaphorebarbers=0;等候顾客的理发师数

Semaphoremutex=1;

Intwaiting=0;等候的顾客数（还没有理发，实际是customers的备份，为了读取信号量的当前值）；

Voidbarber（void）

{while（true）

{P（customers）;

P（mutex）;

waiting=waiting–1;

V（barbers）;

V（mutex）;

cut_hair（）;

}

顾客进程

Voidcustomers（void）

{P（mutex）;

if（waiting

{waiting=waiting+1;

V（customers）;

V（mutex）;

P（barbers）;

get_hair（）;}

else{V（mutex）;}

}

提示：

考虑一下理发师（barber）重复的下列活动：

（1）睡觉；

（2）为顾客理发；

顾客（customers）重复的下列活动：

（3）在椅子上等候；（4）理发；离开；

显然，理发师在

（1）处要考察是否有顾客等候理发，如果没有，理发师睡觉；在

（2）处理发师等待最先进入理发店的顾客唤醒，开始理发。

顾客在（3）处先看是否有座位，没有则离开；等候理发的顾客在（4）处被理发师唤醒（最先理发的顾客要唤醒理发师）；理发结束后离开。

在这两个活动中，从资源的角度来看，理发师是顾客争用的资源，用信号量barber表示，初值为0；除此以外，顾客还要争用n张椅子，信号量customers表示等候理发的顾客数，初值为0；最后设置信号灯变量mutex用于这两个活动对资源barber、customers的互斥，初值为1。

2．复印室里有一个操作员为顾客复印资料，有5把椅子供顾客休息等待复印。

如果没有顾客，则操作员休息，当顾客来到复印室时，如果有空椅子则坐下来，并唤醒复印操作员；如果没有空椅子必须离开复印室。

试用信号量几P、V操作实现顾客和操作员活动的同步。

Customers表示正在等待复印的顾客数

Operator代表操作员的状态，只能取1或0；

Waiting表示正在等待的顾客数；

Mutex实现对waiting的互斥访问

customers,operator,mutex:

semaphore;

waiting:

inteter;

customers=0;

operator=0;

mutex=1;

processoperator

begin

loop:

据统计，上海国民经济持续快速增长。

03全年就实现国内生产总值（GDP）6250.81亿元，按可比价格计算，比上年增长11.8%。

第三产业的增速受非典影响而有所减缓，全年实现增加值3027.11亿元，增长8%，增幅比上年下降2个百分点。

p（customers）;

复印；

V（operator）;

10元以下□10～50元□50～100元□100元以上□Gotoloop;

（2）东西全End;

为了解目前大学生对DIY手工艺品制作的消费情况，我们于己于人2004年3月22日下午利用下课时间在校园内进行了一次快速抽样调查。

据调查本次调查人数共50人，并收回有效问卷50份。

调查分析如下：

Processcoutomeri

（六）DIY手工艺品的“创作交流性”Begin

P（mutex）;

我们熟练的掌握计算机应用，我们可以在网上搜索一些流行因素，还可以把自己小店里的商品拿到网上去卖，为我们小店提供了多种经营方式。

Ifwaiting<5then

Begin

据调查，大学生对此类消费的态度是：

手工艺制品消费比“负债”消费更得人心。

Waiting=waiting+1;

标题：

上海发出通知为大学生就业—鼓励自主创业，灵活就业2004年3月17日V（custormers）;

图1-4大学生购买手工艺制品目的V（mutex）;

P（operator）;

P（mutex）;

Waiting=waiting-1;

V（mutex）;

（3）优惠多End

Else

Begin

V（mutex）;

End;

End;

4．理发师问题：

一个理发店有一个入口和一个出口。

理发店内有一个可站5位顾客的站席

区、4个单人沙发、3个理发师及其专用理发工具、一个收银台。

新来的顾客坐在沙发上等

待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。

理发师可从事理

发、收银和休息三种活动。

理发店的活动满足下列条件：

1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；

2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；

3）理发时间长短由理发师决定；

4）在站席区等待时间最长的顾客可坐到空闲的理发上；

5）任何时刻最多只能有一个理发师在收银。

试用信号量机制或管程机制实现理发师进程和顾客进程。

原理：

（1）customer进程：

首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入

理发店。

在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列，

直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。

坐到沙

发上，等待理发椅（barber_chair），如果理发椅已满，则进入阻塞等待队列，直到出现

空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。

坐到理发椅上，释放

准备好的信号（customer_ready），获得该理发师的编号（0~1的数字）。

等待理发师理

发结束（finished[barber_number]）。

在离开理发椅之前付款（payment），等待收据

（receipt），离开理发椅（leave_barberchair）。

最后离开理发店。

这里需要注意几点：

a）首先是几个需要进行互斥处理的地方，主要包括:

进入站席区、进入沙发、进入理发椅

和付款几个地方。

b）通过barber_chair保证一个理发椅上最多只有一名顾客。

但这也不够，因为单凭

baber_chair无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上，

因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该信号，而理发

师接收到该信号后才释放barber_chair等待下一位顾客。

c）在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活

动。

这个机制是通过customer进程获得给他理发的理发师编号来实现的，这样，当

该编号的理发师释放对应的finished信号的时候，该顾客才理发完毕。

d）理发师是通过mutex信号量保证他们每个人同时只进行一项操作（理发或者收款）。

e）为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理

发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。

在伪码中由以下机制实

现：

即顾客在释放离开理发椅的信号前，发出付款的信号。

这样该理发师得不到顾客的

离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款

操作。

直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该

理发椅的信号，让下一位等待的顾客坐到理发椅上。

（2）barber进程

首先将该理发师的编号压入队列，供顾客提取。

等待顾客坐到理发椅坐好（信号量

customer_ready），开始理发，理发结束后释放结束信号（finished）。

等待顾客

离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信

号（barber_chair），等待下一位顾客坐上来。

（3）cash（收银台）进程

等待顾客付款（payment）,执行收款操作，收款操作结束，给付收据（receipt）。

信号量总表：

信号量waitsignal

stand_capacity顾客等待进入理发店顾客离开站席区

sofa顾客等待坐到沙发顾客离开沙发

barber_chair顾客等待空理发椅理发师释放空理发椅

customer_ready理发师等待，直到一个顾客坐

到理发椅

顾客坐到理发椅上，给理发师

发出信号

mutex等待理发师空闲，执行理发或

收款操作

理发师执行理发或收款结束，

进入空闲状态

mutex1执行入队或出队等待入队或出队结束，释放信号

finished顾客等待对应编号理发师理

发结束

理发师理发结束，释放信号

leave_barberchair理发师等待顾客离开理发椅顾客付款完毕得到收据，离开

理发椅释放信号

payment收银员等待顾客付款顾客付款，发出信号

receipt顾客等待收银员收、开具收据收银员收款结束、开具收据，

释放信号

伪码：

semaphorestand_capacity=5;

semaphoresofa=4;

semaphorebarber_chair=3;

semaphorecustomer_ready=0;

semaphoremutex=3;

semaphoremutex1=1;

semaphorefinished[3]={0,0,0};

semaphoreleave_barberchair=0;

semaphorepayment=0;

semaphorereceipt=0;

voidcustomer（）

{

intbarber_number;

wait（stand_capacity）;//等待进入理发店

enter_room（）;//进入理发店

wait（sofa）;//等待沙发

leave_stand_section（）;//离开站席区

signal（stand_capacity）;

sit_on_sofa（）;//坐在沙发上

wait（barber_chair）;//等待理发椅

get_up_sofa（）;//离开沙发

signal（sofa）;

wait（mutex1）;

sit_on_barberchair（）;//坐到理发椅上

signal（customer_ready）;

barber_number=dequeue（）;//得到理发师编号

signal（mutex1）;

wait（fini