《习题课（一）+pv操作的应用》由会员分享，可在线阅读，更多相关《习题课（一）+pv操作的应用（30页珍藏版）》请在金锄头文库上搜索。
1、习题课（一） PV操作的应用,PV原语的含义,P:passeren pass V:verhoog increment P操作和V操作是不可中断的程序段，称为原语。 PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。在PV原语执行期间不允许有中断的发生。,PV原语的含义,信号量S是一整数 P(S)原语操作的动作是： （1）S减1； （2）若S减1后仍大于或等于零，则进程继续执行； （3）若S减1后小于零，则该进程被阻塞后进入与该 信号相对应的队列中，然后转进程调度。 V(S)原语操作的动作是： （1）S加1； （2）若相加结果大于零，则进程继续执行； （3）若相加结果小于或等于零，则
2、从该信号的等待 队列中唤醒一等待进程，然后再返回原进程继续执 行或转进程调度。,用PV操作实现进程的互斥与同步,解决此类问题的一般方式： 根据问题给出的条件，确定进程有几个或几类； 确定进程间的制约关系是互斥，还是同步； 各相关进程间通过什么信号量实现彼此的制约，标明信号量的含义和初值； 用PV操作写出相应的代码段 验证代码的正确性：设以不同的次序运行各进程，是否能保证问题的圆满解决，切忌按固定顺序执行各进程。,苹果桔子问题,桌上有一只盘子，每次只能放入一只水果；爸爸专 向盘子中放苹果(apple)，妈妈专向盘子中放桔子 (orange)，一个儿子专等吃盘子中的桔子，一个女 儿专等吃盘子里的苹
3、果。请用、操作实现爸爸、 妈妈、儿子、女儿四个并发进程的同步与互斥。,苹果桔子问题,解： sp:semaphore； /* 盘子里可以放几个水果 */ sg1:semaphore; /* 盘子里有桔子 */ sg2:semaphore; /* 盘子里有苹果 */ sp := 1; /* 盘子里允许放一个水果*/ Sg1:= 0; /* 盘子里没有桔子 */ sg2 := 0; /* 盘子里没有苹果*/ cobegin,苹果桔子问题,process father begin L1:削一个苹果； 盘子为空吗？ 把苹果放入plate； 女儿可以拿苹果； goto L1; end;,process d
4、aughter begin L4: 盘子里有苹果吗？ 从plate中取苹果； 盘子又为空； 吃苹果； goto L4; end;,V(sg2);,P(sp);,P(sg2);,V(sp);,苹果桔子问题,process mother begin L2:剥一个桔子； 盘子为空吗？ 把桔子放入plate； 儿子可以拿桔子； goto L2; end;,process son begin L3: 盘子里有桔子吗？ 从plate中取桔子； 盘子又为空； 吃桔子； goto L3; end;,V(sg1);,P(sp);,P(sg1);,V(sp);,苹果桔子问题：,process father beg
5、in L1:削一个苹果； P(sp); 把苹果放入plate； V(sg2); goto L1; end;,process mother begin L2:剥一个桔子； P(sp); 把桔子放入plate； V(sg1); goto L2; end;,苹果桔子问题：,process son begin L3: P(sg1); 从plate中取桔子； V(sp); 吃桔子； goto L3; end;,process daughter begin L4: P(sg2); 从plate中取苹果； V(sp); 吃苹果； goto L4; end;,coend,缓冲问题（一）,有三个并发进程R,M和
6、P，它们共享一个缓冲区B。 进程R负责从输入设备读入一条记录，每读一条记 录后把它存放在缓冲区B中；进程M在缓冲区B中加 工进程R存入的记录；进程P把加工后的记录打印输 出。缓冲区B每次只能存放一条记录，当记录被加 工输出后，缓冲区B中才可存放另一条新记录。请 用P,V操作作为同步机制来描述它们并发执行时能正 确工作的程序。,缓冲问题（一）,解： begin R,M,P:semaphore; R:=1;M:=P:=0; cobegin,进程R L1： 从输入设备中读取一条记录； P(R)； 将读入记录存入缓冲区； V(M)； goto L1 进程M L2: P(M); 对缓冲区中的数据信息进行
7、加工，并将其存入缓冲区中； V(P)； goto L2 进程P L3: P(P) 输出缓冲区的信息； V(R) goto L3 coend;end;,缓冲问题,（一）,缓冲问题（二）,若有三个进程A，B和C协作解决文件打印问题：A 将文件记录从磁盘读入主存的缓冲区buffer1，每执 行一次读一个记录；B将缓冲区buffer1的内容复制到 缓冲区buffer2，每执行一次复制一个记录；C打印缓 冲区buffer2的内容，每执行一次打印一个记录。缓 冲区的大小和一个记录大小一样。请用P、V操作来 保证文件的正确打印。,缓冲问题（二）,注意：B既是生产者，也是消费者 解：设置信号量初值： mute
8、x1:=mutex2:=1； empty1:=empty2:=1; full1:=full2:=0 begin cobegin,缓冲问题（二）,进程A L1:read from disk; P(empty1); /* 申请空缓冲区buffer1 */ P(mutex1); /* 进程A和B要互斥的访问buffer1 */ put to buffer 1; /*向buffer1输入数据*/ V(full1); /*释放满缓冲区buffer1*/ V(mutex1); /* 进程A对buffer1的访问结束 */ Goto L1;,缓冲问题（二）,进程B L2：P（full1）; P(mutex1
9、); Get from buffer1; V(empty1); V(mutex1);,P(emmty2); P(mutex2); Put to buffer 2; V(full2); V(mutex2); Goto L2;,缓冲问题（二）,进程C L3:P(full2) P(mutex2); Get from buffer2; V(empty2); V(mutex2); Print record; Goto L3; Coend End,总结：,以上三个题目均为生产者消费者问题的变型，在 处理这类问题时，应注意生产者消费者问题里的 两个条件： 对缓冲区的读、写要互斥进行 不能从空的缓冲区中读数据
10、，不能向满缓冲区中写数据。 通过以上三个题目，加深对PV操作的理解，掌握用 PV操作解决进程同步和互斥问题的方法。 重点：找出进程间的制约关系,嗜睡的理发师问题,一个理发店由一个有N张沙发的等候室和一个放有 一张理发椅的理发室组成。没有顾客要理发时，理 发室便去睡觉。当一个顾客走进理发店时，如果所 有的沙发都已被占用，他便离开理发店；否则，如 果理发师正在为其他顾客理发，则该顾客就找一张 空沙发坐下等待；如果理发师因无顾客正在睡觉， 则由新到的顾客唤醒理发师为其理发。在理发完成 后，顾客必须付费，知道理发师收费后才能离开理 发店。试用信号量实现这一同步问题。,嗜睡的理发师问题,解： Var c
11、ount: integer:=0; Mutex,sofa,empty,full:semaphore:=1,n,1,0; Cut,payment,receipt;semaphore:=0,0,0; Begin Parbegin,嗜睡的理发师问题,Guest:begin Wait(mutex); If (countN) then begin Signal(mutex); Exit shop; end else,begin count:=count+1; if (count1) then begin wait(sofa) sit on sofa; wait(empty); get up from s
12、ofa; 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; end end,嗜睡的理发师问题,barber:begin repeat wait(full); cut
13、hair; signal(cut); wait(payment); accept payment; signal(receipt); until false;,end parend end,仓库问题,设有两个生产者进程A，B和一个销售者进程C，他 们共享一个无限大的仓库，生产者每次循环生产一 个产品，然后入库供销售者销售；销售者每次循环 从仓库中取出一个产品进行销售。如果不允许同时 入库，也不允许边入库边出库；而且要求生产和销 售A产品和B产品的件数都满足以下关系：-n = A 的件数-B的件数 = m，其中n、m是正整数。请用 信号量机制写出A，B，C三个进程的工作流程。,仓库问题,解： v
14、ar 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,仓库问题,process B:begin repeat wait(
15、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=-n then begin wait(SA); wait(mutex); take a product A from storehouse; signal(mutex); difference:=differ
16、ence+1; end,else 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; end,else begin /*取走的是B产品*/ wait(SB); difference:=difference-1; end sell the product
