习题课一V操作应用

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

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

3、 苹果桔子问题苹果桔子问题 桌上有一只盘子，每次只能放入一只水果；爸爸专 向盘子中放苹果(apple)，妈妈专向盘子中放桔子 (orange)，一个儿子专等吃盘子中的桔子，一个女 儿专等吃盘子里的苹果。请用、操作实现爸爸、 妈妈、儿子、女儿四个并发进程的同步与互斥。 习题课一V操作应用 苹果桔子问题苹果桔子问题 解： sp:semaphore； /* 盘子里可以放几个水果盘子里可以放几个水果 */ sg1:semaphore; /* 盘子里有桔子盘子里有桔子 */ sg2:semaphore; /* 盘子里有苹果盘子里有苹果 */ sp := 1; /* 盘子里允许放一个水果盘子里允许放一个水

4、果*/ Sg1:= 0; /* 盘子里没有桔子盘子里没有桔子 */ sg2 := 0; /* 盘子里没有苹果盘子里没有苹果*/ cobegin 习题课一V操作应用 苹果桔子问题苹果桔子问题 process father begin L1:削一个苹果；削一个苹果； 盘子为空吗？盘子为空吗？ 把苹果放入把苹果放入plate； 女儿可以拿苹果；女儿可以拿苹果； goto L1; end; process daughter begin L4:盘子里有苹果吗？盘子里有苹果吗？ 从从plate中取苹果；中取苹果； 盘子又为空；盘子又为空； 吃苹果；吃苹果； goto L4; end; V(sg2); P(

5、sp); P(sg2); V(sp); 习题课一V操作应用 苹果桔子问题苹果桔子问题 process mother begin L2:剥一个桔子；剥一个桔子； 盘子为空吗？盘子为空吗？ 把桔子放入把桔子放入plate； 儿子可以拿桔子；儿子可以拿桔子； goto L2; end; process son begin L3:盘子里有桔子吗？盘子里有桔子吗？ 从从plate中取桔子；中取桔子； 盘子又为空；盘子又为空； 吃桔子；吃桔子； goto L3; end; V(sg1); P(sp); P(sg1); V(sp); 习题课一V操作应用 苹果桔子问题：苹果桔子问题： process fath

6、er begin L1:削一个苹果；削一个苹果； P(sp); 把苹果放入把苹果放入plate； V(sg2); goto L1; end; process mother begin L2:剥一个桔子；剥一个桔子； P(sp); 把桔子放入把桔子放入plate； V(sg1); goto L2; end; 习题课一V操作应用 苹果桔子问题：苹果桔子问题： process son begin L3: P(sg1); 从从plate中取桔子；中取桔子； V(sp); 吃桔子；吃桔子； goto L3; end; process daughter begin L4: P(sg2); 从从plate中

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

8、egin 习题课一V操作应用 进程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; 缓 冲 问 题 （一） 习题课一V操作应用 缓冲问题（二） 若有三个进程A，B和C协作解决文件打印问题：A 将文件记录从磁盘读入主存的缓冲区buffer1，每执 行一次读一个记录；B将缓冲区buffer1的内容复制到 缓冲区buffer2，每执行一次复制一个记

9、录；C打印缓 冲区buffer2的内容，每执行一次打印一个记录。缓 冲区的大小和一个记录大小一样。请用P、V操作来 保证文件的正确打印。 习题课一V操作应用 缓冲问题（二） 注意：B既是生产者，也是消费者 解：设置信号量初值： mutex1:=mutex2:=1； empty1:=empty2:=1; full1:=full2:=0 begin cobegin 习题课一V操作应用 缓冲问题（二） 进程A L1:read from disk; P(empty1); /* 申请空缓冲区申请空缓冲区buffer1 */ P(mutex1); /* 进程进程A和和B要互斥的访问要互斥的访问buffer

10、1 */ put to buffer 1; /*向向buffer1输入数据输入数据*/ V(full1); /*释放满缓冲区释放满缓冲区buffer1*/ V(mutex1); /* 进程进程A对对buffer1的访问结束的访问结束 */ Goto L1; 习题课一V操作应用 缓冲问题（二） 进程B L2：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; 习题课一V操作应用 缓冲问题（二

11、） 进程C L3:P(full2) P(mutex2); Get from buffer2; V(empty2); V(mutex2); Print record; Goto L3; Coend End 习题课一V操作应用 总结： 以上三个题目均为生产者消费者问题的变型，在 处理这类问题时，应注意生产者消费者问题里的 两个条件： n对缓冲区的读、写要互斥进行 n不能从空的缓冲区中读数据，不能向满缓冲区中 写数据。 通过以上三个题目，加深对PV操作的理解，掌握用 PV操作解决进程同步和互斥问题的方法。 重点：找出进程间的制约关系 习题课一V操作应用 嗜睡的理发师问题嗜睡的理发师问题 一个理发店由

12、一个有N张沙发的等候室和一个放有 一张理发椅的理发室组成。没有顾客要理发时，理 发室便去睡觉。当一个顾客走进理发店时，如果所 有的沙发都已被占用，他便离开理发店；否则，如 果理发师正在为其他顾客理发，则该顾客就找一张 空沙发坐下等待；如果理发师因无顾客正在睡觉， 则由新到的顾客唤醒理发师为其理发。在理发完成 后，顾客必须付费，知道理发师收费后才能离开理 发店。试用信号量实现这一同步问题。 习题课一V操作应用 嗜睡的理发师问题嗜睡的理发师问题 解： Var count: integer:=0; Mutex,sofa,empty,full:semaphore:=1,n,1,0; Cut,payme

13、nt,receipt;semaphore:=0,0,0; Begin Parbegin 习题课一V操作应用 嗜睡的理发师问题嗜睡的理发师问题 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 sofa; signal(sofa); end 习题课一V操作应用 嗜睡的理发师问题嗜睡的理发师问题 e

14、lse /*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 习题课一V操作应用 嗜睡的理发师问题嗜睡的理发师问题 barber:begin repeat wait(full); cut hair; signal(cu

15、t); wait(payment); accept payment; signal(receipt); until false; end parend end 习题课一V操作应用 仓库问题仓库问题 设有两个生产者进程A，B和一个销售者进程C，他 们共享一个无限大的仓库，生产者每次循环生产一 个产品，然后入库供销售者销售；销售者每次循环 从仓库中取出一个产品进行销售。如果不允许同时 入库，也不允许边入库边出库；而且要求生产和销 售A产品和B产品的件数都满足以下关系：-n = A 的件数的件数-B的件数的件数 = m，其中n、m是正整数。请用 信号量机制写出A，B，C三个进程的工作流程。 习题课一

16、V操作应用 仓库问题仓库问题 解： var difference:integer:=0; SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,0,0,0,1; Begin Parbegin 习题课一V操作应用 仓库问题仓库问题 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 习题课一V操作应用 仓库问题仓库问题 process B:begin repeat wait(SBA); produce a product B; signal(SAB); wait(mutex); add the produc