习题课（一） PV操作的应用.ppt

《习题课（一） PV操作的应用.ppt》由会员分享，可在线阅读，更多相关《习题课（一） PV操作的应用.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题课（一）PV操作的应用PV原语的含义原语的含义nP:passeren pass V:verhoog incrementnP操作和V操作是不可中断的程序段，称为原语。nPV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。在PV原语执行期间不允许有中断的发生。PV原语的含义原语的含义n信号量S是一整数nP(S)原语操作的动作是：原语操作的动作是：（1）S减1；（2）若S减1后仍大于或等于零，则进程继续执行；（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。nV(S)原语操作的动作是：原语操作的动作是：（1）S加1；（2）若相加结果大于零，则进程继续执

2、行；（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。用PV操作实现进程的互斥与同步解决此类问题的一般方式：q根据问题给出的条件，确定进程有几个或几类；确定进程间的制约关系是互斥，还是同步；q各相关进程间通过什么信号量实现彼此的制约，标明信号量的含义和初值；q用PV操作写出相应的代码段q验证代码的正确性：设以不同的次序运行各进程，是否能保证问题的圆满解决，切忌按固定顺序执行各进程。苹果桔子问题苹果桔子问题 桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的

3、桔子，一个女儿专等吃盘子里的苹果。请用、操作实现爸爸、妈妈、儿子、女儿四个并发进程的同步与互斥。苹果桔子问题苹果桔子问题解：sp:semaphore；/*盘子里可以放几个水果盘子里可以放几个水果*/sg1:semaphore;/*盘子里有桔子盘子里有桔子*/sg2:semaphore;/*盘子里有苹果盘子里有苹果*/sp:=1;/*盘子里允许放一个水果盘子里允许放一个水果*/Sg1:=0;/*盘子里没有桔子盘子里没有桔子*/sg2:=0;/*盘子里没有苹果盘子里没有苹果*/cobegin苹果桔子问题苹果桔子问题process father beginL1:削一个苹果；削一个苹果；盘子为空吗？盘

4、子为空吗？把苹果放入把苹果放入plate；女儿可以拿苹果；女儿可以拿苹果；goto L1;end;process daughter beginL4:盘子里有苹果吗？盘子里有苹果吗？从从plate中取苹果；中取苹果；盘子又为空；盘子又为空；吃苹果；吃苹果；goto L4;end;V(sg2);P(sp);P(sg2);V(sp);苹果桔子问题苹果桔子问题process mother beginL2:剥一个桔子；剥一个桔子；盘子为空吗？盘子为空吗？把桔子放入把桔子放入plate；儿子可以拿桔子；儿子可以拿桔子；goto L2;end;process son beginL3:盘子里有桔子吗？盘子里有

5、桔子吗？从从plate中取桔子；中取桔子；盘子又为空；盘子又为空；吃桔子；吃桔子；goto L3;end;V(sg1);P(sp);P(sg1);V(sp);苹果桔子问题：苹果桔子问题：process father beginL1:削一个苹果；削一个苹果；P(sp);把苹果放入把苹果放入plate；V(sg2);goto L1;end;process mother beginL2:剥一个桔子；剥一个桔子；P(sp);把桔子放入把桔子放入plate；V(sg1);goto L2;end;苹果桔子问题：苹果桔子问题：process son beginL3:P(sg1);从从plate中取桔子；中取

6、桔子；V(sp);吃桔子；吃桔子；goto L3;end;process daughter beginL4:P(sg2);从从plate中取苹果；中取苹果；V(sp);吃苹果；吃苹果；goto L4;end;coend缓冲问题（一）有三个并发进程R,M和P，它们共享一个缓冲区B。进程R负责从输入设备读入一条记录，每读一条记录后把它存放在缓冲区B中；进程M在缓冲区B中加工进程R存入的记录；进程P把加工后的记录打印输出。缓冲区B每次只能存放一条记录，当记录被加工输出后，缓冲区B中才可存放另一条新记录。请用P,V操作作为同步机制来描述它们并发执行时能正确工作的程序。缓冲问题（一）解：beginR,M

7、,P:semaphore;R:=1;M:=P:=0;cobegin进程R L1：从输入设备中读取一条记录；P(R)；将读入记录存入缓冲区；V(M)；goto L1进程M L2:P(M);对缓冲区中的数据信息进行加工，并将其存入缓冲区中；V(P)；goto L2进程P L3:P(P)输出缓冲区的信息；V(R)goto L3 coend;end;缓冲问题（一）缓冲问题（二）若有三个进程A，B和C协作解决文件打印问题：A将文件记录从磁盘读入主存的缓冲区buffer1，每执行一次读一个记录；B将缓冲区buffer1的内容复制到缓冲区buffer2，每执行一次复制一个记录；C打印缓冲区buffer2的内

8、容，每执行一次打印一个记录。缓冲区的大小和一个记录大小一样。请用P、V操作来保证文件的正确打印。缓冲问题（二）注意：B既是生产者，也是消费者解：设置信号量初值：mutex1:=mutex2:=1；empty1:=empty2:=1;full1:=full2:=0begincobegin缓冲问题（二）进程AL1:read from disk;P(empty1);/*申请空缓冲区申请空缓冲区buffer1*/P(mutex1);/*进程进程A和和B要互斥的访问要互斥的访问buffer1*/put to buffer 1;/*向向buffer1输入数据输入数据*/V(full1);/*释放满缓冲区释

9、放满缓冲区buffer1*/V(mutex1);/*进程进程A对对buffer1的访问结束的访问结束*/Goto L1;缓冲问题（二）进程BL2：P（full1）;P(mutex1);Get from buffer1;V(empty1);V(mutex1);P(emmty2);P(mutex2);Put to buffer 2;V(full2);V(mutex2);Goto L2;缓冲问题（二）进程CL3:P(full2)P(mutex2);Get from buffer2;V(empty2);V(mutex2);Print record;Goto L3;CoendEnd总结：以上三个题目均为

10、生产者消费者问题的变型，在处理这类问题时，应注意生产者消费者问题里的两个条件：n对缓冲区的读、写要互斥进行n不能从空的缓冲区中读数据，不能向满缓冲区中写数据。通过以上三个题目，加深对PV操作的理解，掌握用PV操作解决进程同步和互斥问题的方法。重点：找出进程间的制约关系嗜睡的理发师问题嗜睡的理发师问题一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发室便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在

11、理发完成后，顾客必须付费，知道理发师收费后才能离开理发店。试用信号量实现这一同步问题。嗜睡的理发师问题嗜睡的理发师问题解：Var count:integer:=0;Mutex,sofa,empty,full:semaphore:=1,n,1,0;Cut,payment,receipt;semaphore:=0,0,0;BeginParbegin嗜睡的理发师问题嗜睡的理发师问题Guest:beginWait(mutex);If(countN)thenbegin Signal(mutex);Exit shop;endelsebegin count:=count+1;if(count1)then b

12、egin wait(sofa)sit on sofa;wait(empty);get up from sofa;signal(sofa);end嗜睡的理发师问题嗜睡的理发师问题else /*count=1*/wait(empty);sit on the baber_chair;signal(full);wait(cut);pay;signal(payment);wait(receipt);get up from the baber_chair;signal(empty);wait(mutex);count:=count-1;signal(mutex);exit shop;endend嗜睡的理发

13、师问题嗜睡的理发师问题barber:begin repeat wait(full);cut hair;signal(cut);wait(payment);accept payment;signal(receipt);until false;endparend end仓库问题仓库问题设有两个生产者进程A，B和一个销售者进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库；而且要求生产和销售A产品和B产品的件数都满足以下关系：-n=A的件数的件数-B的件数的件数=m，其中n、m是正整

14、数。请用信号量机制写出A，B，C三个进程的工作流程。仓库问题仓库问题解：var difference:integer:=0;SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,0,0,0,1;Begin Parbegin仓库问题仓库问题 Process A:begin Repeat Wait(SAB);Procedure a product A;Signal(SBA);Wait(mutex);Add the product A to the storehouse;Signal(mutex);Signal(SA);Signal(S);until false;end仓库问题仓

15、库问题process B:begin repeat wait(SBA);produce a product B;signal(SAB);wait(mutex);add the product B to the storehouse;signal(mutex);signal(SB);signal(S);until false;end仓库问题仓库问题process C:begin repeat wait(S);if difference=m then begin wait(SB);wait(mutex);take a product B from storehouse;signal(mutex);difference:=difference-1;end仓库问题仓库问题 else begin wait(mutex);take a product A or B from storehouse;signal(mutex);if(product_type=A)then begin /*取走的是A产品*/wait(SA);difference:=difference+1;endelse begin /*取走的是B产品*/wait(SB);difference:=difference-1;end sell the product;until false;endparendend