考研P、V操作习题答案.doc

1、信号量应用问题：1 写出程序描述下列前趋关系。S1-S2, S1-S3, S2-S4, S2-S5 , S3-S6, S4-S7, S5-S7, S6-S7Var s1,s2, s3,s4:semaphore:=0, 0, 0, 0;BeginParbeginP1: begin.;V(s1);V(s1);End;P2: beginP(s1);V(s2); V(s2);End;P3: beginP(s1)V(s3)End;P4: beginP(s2);V(s4);P5: beginP(s2);.;V(s4);End;P6: beginP(s3).V(s4)End;P7:beginP(s4);P(

2、s4);P(s4);End;Parendend2. 请用信号量实现 4100（4 人，每人 100米）接力赛的同步过程。提示：前趋图同步问题，可设 4个进程，三个信号量，进程 1只设 V操作，进程 4只设 P操作，其余进程先做 P操作再做 V操作。Var s1,s2,s3:semaphore:=0, 0, 0;BeginParbeginAthlete1: beginRun 100m;V(s1);End;Athlete2: beginP(s1)Run 100m;V(s2);End;Athlete3: beginP(s2) ;Run 100m;V(s3);End;Athlete4: beginP(

3、s3);Run 100m;End;Parendend3设公共汽车上，司机和售票员的活动分别是：司机： 售票员：启动车辆 上乘客正常行车 关车门到站停车 售票开车门下乘客在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？请用信号量机制实现他们的同步。/-假定初始状态为停车状态，引入信号量 Stop和 Run：BEGINsemaphore Stop,Run;Stop:=Run:=0;CoBeginDriver: BEGINRepeatWait(Run);启动车辆；正常行驶；到站停车；Signal(Stop);Until False;END;Conductor:BEGINRepeat上乘

4、客；关车门；Signal(Run);售票；Wait(Stop);开车门；下乘客；Until False;END;CoEnd;END;生产者消费者问题：1桌上有一个可以容纳两个水果的盘子，每次只能放或取一个水果。爸爸放苹果妈妈放橘子，两个儿子吃苹果，两个女儿吃橘子。试用信号量和 P、V 操作，编写实现爸爸、妈妈、儿子和女儿的并发工作程序。Mutex实现互斥放或取水果。empty盘子可放水果数Apple 盘子中放的苹果数Orange 盘子中放的橘子数Semaphore mutex=1;Semaphore empty=2;Semahpore apple=0;Semahpore orange=0;Ma

5、in()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，最大库容量各为

6、 m个。有一车间不断地取 A和 B进行装配，每次各取一个。为了避免零件锈蚀，遵循线入库者先出库的原则。有两组供应商分别不断地供应 A和 B（每次一个） ，为保证齐套和合理库存，当某种零件的数量比另一种数量超过 n（nm）个时，暂停对数量大的零件的进货，集中补充数量少的零件。试用 P、V 操作正确实现之。semaphore mutex=1, emptya=emptyb=m, fulla=fullb=0, sa=sb=n;main() CoBeginProvider_A(); /零件A供应商Provider_B(); /零件B供应商Assembling_Shop(); /装配车间CoEndProv

7、ider_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两种产品，仓库的存储空间足够大，但要求：每次只能存入一种

8、产品（X 或 Y） ；-NA产品数量-B 产品数量M。其中，N 和 M时正整数。试用“存放 A”、 “存放 B”和 P、V操作描述产品 A与产品 B的入库过程。A-BM说明：如果只放 A不放 B，则A最多可放 M-1个，如果多放一个B，则可以多放一个 A。B-AN说明：如果只放 B不放 A，则B最多可放 N-1个，如果多放一个A，则可以多放一个 B。/2-BEGINMutex,SA,SB:semaphore;Mutex:=1;SA:=M-1;SB:=N-1;parBeginprocess PABeginloop:P(SA);P(Mutex);存放 A;V(Mutex);V(SB);Goto l

9、oop;End;process PBBeginloop:P(SB);P(Mutex);存放 B;V(Mutex);V(SA);Goto loop;End;parEnd;END;/北大 91读者写者问题：1、多个进程共享一个文件，其中只读文件的程值为读者，其余只写文件的称为写者。读者可以同时读，但写者只能独立地写。说明进程间的相互制约关系，应设置哪些信号量？用 P、V 操作写出其同步算法；修改上述算法，使得它对写者优先，即一旦有写者到达，后续的读者都必须等待，而无论是否有读者在读文件。（该问题的又一提法：在一个飞机订票系统中，多个用户共享一个数据库。多用户同时查询是可以接受的，但若一个用户要订票

10、需更新数据库时，其余所有用户都不可以访问数据库。请画出用户查询与订票的逻辑框图(等价于同步进程的描述的图式表示)。为了提高写者的优先级，增加一个信号量 S，用于在写进程到达后封锁后续的读者Semaphore mutex=1;Semaphore write=1;Semahpore s=1;Int count =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

11、);V(mutex);Writer()While(true) p(s);P(write);写文件；V(write);V(s);2某一桥只有一车道，载重为 4辆车，用 P、V 操作实现两方向的车过桥。本题本质上可以认为是读者写者问题，往同一个方向的车可以认为是读者，往相反方向的车可以认为是写者。但是由于桥的重量有限，增加了读者之间的互斥。本题的临界资源显然是单通道的桥，首先如果桥上有向东方向的车，那么向西方向的车一定不能过，如果超过 4辆，同一方向的车也不能过，需要互斥。设信号量 mutex，实现双向车子互斥通行；信号量 sew，swe 表示由西向东与由东向西的负荷数，初值为4；整数型 iew,

12、iwe表示各方向的车子数，初值为 0；siew,siwe 实现对iew,iwe的互斥访问，初值为 1；Process 由东向西的车子；Begin P(sew);P(siew);Iew:=iew+1;If iew=1 then p(mutex);V(siew);过桥；P(siew);Iew:=iew-1;If iew=0 then v(mutex);V(siew);V(sew)EndPorcess 由西向东BeginP(swe);P(siwe);Iwe:=iwe+1;If iwe=1 hten p(mutex);V(siwe);过桥；P(siwe);Iwe:=iwe-1;If iwe=0 the

13、n v(mutex);V(siwe);V(swe)End;理发师睡觉问题：1 （睡眠的理发师问题）理发店有一个等候室（其中有 N把椅子）和一个理发室（一把理发椅组成） 。如果没有顾客来理发，理发时就在理发椅上睡觉，如果一个走进理发店，发现等候室的椅子都坐满就离开理发店；如果理发师正忙于理发，那么该顾客就坐在一把空椅子上等待；若理发师正在睡觉，则顾客就唤醒他。用 P、V操作写出工作流程。 考点： 用 PV原语实现同步Semaphore costomers=0; 等候的顾客数（不包括正在理发的）Semaphore barbers=0; 等候顾客的理发师数Semaphore mutex=1; Int

14、 waiting =0; 等候的顾客数（还没有理发，实际是 customers的备份，为了读取信号量的当前值） ；Void barber(void) while (true) P(customers);P(mutex);waiting = waiting 1 ;V(barbers);V(mutex);cut_hair( );顾客进程Void customers(void)P(mutex);if(waitingchairs) waiting = waiting + 1 ;V(customers);V(mutex);P(barbers);get_hair( );else V(mutex);提示：考

15、虑一下理发师（barber）重复的下列活动：（1）睡觉；（2）为顾客理发；顾客（customers）重复的下列活动：（3）在椅子上等候；（4）理发；离开；显然，理发师在（1）处要考察是否有顾客等候理发，如果没有，理发师睡觉；在（2）处理发师等待最先进入理发店的顾客唤醒，开始理发。顾客在（3）处先看是否有座位，没有则离开；等候理发的顾客在（4）处被理发师唤醒（最先理发的顾客要唤醒理发师） ；理发结束后离开。在这两个活动中，从资源的角度来看，理发师是顾客争用的资源，用信号量 barber表示，初值为 0；除此以外，顾客还要争用 n张椅子，信号量 customers表示等候理发的顾客数，初值为 0；

16、最后设置信号灯变量mutex用于这两个活动对资源barber、customers 的互斥，初值为1。2复印室里有一个操作员为顾客复印资料，有 5把椅子供顾客休息等待复印。如果没有顾客，则操作员休息，当顾客来到复印室时，如果有空椅子则坐下来，并唤醒复印操作员；如果没有空椅子必须离开复印室。试用信号量几 P、V 操作实现顾客和操作员活动的同步。Customers 表示正在等待复印的顾客数Operator 代表操作员的状态，只能取 1或 0；Waiting 表示正在等待的顾客数；Mutex实现对 waiting的互斥访问customers, operator,mutex: semaphore;wai

17、ting: inteter;customers=0;operator=0;mutex=1;process operatorbegin loop:p(customers);复印；V(operator);Goto loop;End;Process coutomeriBeginP(mutex);If waiting 5 then Begin Waiting=waiting+1;V(custormers);V(mutex);P(operator);P(mutex);Waiting=waiting-1;V(mutex);EndElseBeginV(mutex);End;End;4理发师问题：一个理发店有

18、一个入口和一个出口。理发店内有一个可站 5 位顾客的站席 区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等 待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理 发、收银和休息三种活动。理发店的活动满足下列条件： 1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发； 2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发； 3）理发时间长短由理发师决定； 4）在站席区等待时间最长的顾客可坐到空闲的理发上； 5）任何时刻最多只能有一个理发师在收银。 试用信号量机制或管程机制实现理发师进程和顾客进程。原理： (1)cust

19、omer 进程： 首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入 理发店。在站席区等待沙发的空位（信号量 sofa） ，如果沙发已满，则进入阻塞等待队列， 直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity） 。坐到沙 发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现 空位，在沙发上等待时间最长的顾客离开沙发（释放信号量 sofa） 。坐到理发椅上，释放 准备好的信号（customer_ready） ，获得该理发师的编号（01 的数字） 。等待理发师理 发结束（finishe

20、dbarber_number） 。在离开理发椅之前付款（payment） ，等待收据 (receipt)，离开理发椅（leave_barberchair） 。最后离开理发店。 这里需要注意几点： a) 首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅 和付款几个地方。 b) 通过 barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭 baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上， 因此增加信号量 leave_barberchair，让顾客离开理发椅后，释放该信号，而理发 师接收到该信号后才释放 ba

21、rber_chair 等待下一位顾客。 c) 在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活 动。这个机制是通过 customer 进程获得给他理发的理发师编号来实现的，这样，当 该编号的理发师释放对应的 finished信号的时候，该顾客才理发完毕。 d) 理发师是通过 mutex 信号量保证他们每个人同时只进行一项操作（理发或者收款） 。 e) 为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理 发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。在伪码中由以下机制实 现：即顾客在释放离开理发椅的信号前，发出付款的信号。这样该理发

22、师得不到顾客的 离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款 操作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该 理发椅的信号，让下一位等待的顾客坐到理发椅上。 (2)barber 进程 首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量 customer_ready)，开始理发，理发结束后释放结束信号（finished） 。等待顾客 离开理发椅（leave_barberchair） （期间去收银台进行收款活动） ，释放理发椅空闲信 号(barber_chair)，等待下一位顾客坐上来。 (3)cash（收银台）进

23、程 等待顾客付款(payment),执行收款操作，收款操作结束，给付收据（receipt） 。 信号量总表： 信号量 wait signal stand_capacity 顾客等待进入理发店 顾客离开站席区 sofa 顾客等待坐到沙发 顾客离开沙发 barber_chair 顾客等待空理发椅 理发师释放空理发椅 customer_ready 理发师等待，直到一个顾客坐 到理发椅 顾客坐到理发椅上，给理发师 发出信号 mutex 等待理发师空闲，执行理发或 收款操作 理发师执行理发或收款结束， 进入空闲状态 mutex1 执行入队或出队等待 入队或出队结束，释放信号 finished 顾客等待对

24、应编号理发师理 发结束 理发师理发结束，释放信号 leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据，离开 理发椅释放信号 payment 收银员等待顾客付款 顾客付款，发出信号 receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据， 释放信号 伪码： semaphore stand_capacity=5; semaphore sofa=4; semaphore barber_chair=3; semaphore customer_ready=0; semaphore mutex=3; semaphore mutex1=1; semaphore f

25、inished3=0,0,0; semaphore leave_barberchair=0; semaphore payment=0; semaphore receipt=0; void customer() int barber_number; wait(stand_capacity); /等待进入理发店 enter_room(); /进入理发店 wait(sofa); /等待沙发 leave_stand_section(); /离开站席区 signal(stand_capacity); sit_on_sofa(); /坐在沙发上 wait(barber_chair); /等待理发椅 get

26、_up_sofa(); /离开沙发 signal(sofa); wait(mutex1); sit_on_barberchair(); /坐到理发椅上 signal(customer_ready); barber_number=dequeue(); /得到理发师编号 signal(mutex1); wait(finishedbarber_number); /等待理发结束 pay(); /付款 signal(payment); /付款 wait(receipt); /等待收据 get_up_barberchair(); /离开理发椅 signal(leave_barberchair); /发出离

27、开理发椅信号 exit_shop(); /了离开理发店 void barber(int i) while(true) wait(mutex1); enqueue(i); /将该理发师的编号加入队列 signal(mutex1); wait(customer_ready); /等待顾客准备好 wait(mutex); cut_hair(); /理发 signal(mutex); signal(finished); /理发结束 wait(leave_barberchair); /等待顾客离开理发椅信号 signal(barber_chair); /释放 barber_chair 信号 void c

28、ash() /收银 while(true) wait(payment); /等待顾客付款 wait(mutex); /原子操作 get_pay(); /接受付款 give_receipt(); /给顾客收据 signal(mutex); signal(receipt); /收银完毕，释放信号 分析： 在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重 性的,主要包括： （1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动作的话，很 容易造成没有收银员为其收款的情形， 原因是： 为该顾客理发的理发师收到 leave_barbercha

29、ir 信号后，释放 barber_chair 信号，另外一名顾客坐到理发椅上， 该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题， 就是采取在释放 leave_barberchair 信号之前，完成付款操作。这样该理发师无法进入 下一轮循环为另外顾客服务，只能到收银台收款。（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号， 如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号 才会进行付款等操作。这样实现，是为避免这样的错误，即：如果仅用一个 finished 信 号量的话，很容易出现别的理发师理发完毕释放了 finished 信号，把正在理发的这位顾 客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编 号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为 finished 数组不能是无限的。而为理发师编号，则只需要三个元素即可。