经典的PV问题

1、精选优质文档-倾情为你奉上PV问题：1 生产-消费模型，推广到多个生产者，多个消费者的生产消费模型；设一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来，缓冲区只能容纳一个产品，生产者不断的生产产品，然后往空缓冲区送产品；消费者不断的从缓冲区中取出产品，并消费。1.1 一个生产者、一个消费者、一个缓冲区的模型：信号量empty=0 full=0专心-专注-专业P：Repeat生产一个产品送产品到缓冲区V(full);P(empty);Until false;Q：Repeat：P(full);从缓冲区拿走一个产品V(empty);消费产品Until false;1.2 一个生产者、一

2、个消费者、一个缓冲区的第二种解法：信号量empty=1 full=0P:RepeatP(empty);生产一个产品送产品到缓冲区V(full);Until false;Q:RepeatP(full);从缓冲区取产品V(empty);消费产品Until false;1.3 一个生产者、一个消费者、n个缓冲区的模型：(不需要考虑互斥)信号量empty=n 空缓冲区的数目full=0 满缓冲区的数目P:i:=0Repeat生产产品P(empty);送产品到缓冲池bufferiV(full);i:=(i+1)mod n;Until false;Q:j:=0RepeatP(full);从缓冲池buffe

3、ri中取产品V(empty);消费产品j:=(j+1)mod n;Until false;1.4 m个生产者、k个消费者、n个缓冲区的模型：（需要考虑互斥）信号量：empty=n 空缓冲区的数目full=0 满缓冲区的数目mutex1(P进程互斥),mutex2(Q进程互斥)=1 互斥信号量，实现临界区（缓冲池）的互斥P:i:=0Repeat生产产品P(empty);P(mutex1);添加产品到缓冲区bufferii:=(i+1)mod n;V(mutex1);V(full);Until false;Q:j:=0RepeatP(full);P(mutex2);从缓冲区bufferj中取产品j

4、:=(j+1)mod n;V(mutex2);V(empty);消费产品Until false;2 读者-写者模型，分两种：读者优先，写着优先；某个共享文件F，系统允许若干进程对文件F读或写，但规定：1、多个进程可以同时读文件F；2、任一个进程在对文件F进行写时不允许其他进程对文件进行读或写；3、当有进程在读文件是不允许任何进程去写文件。2.1 第一类读者-写者问题：读者优先除非有写者在写文件，否则没有一个读者需要等待。分析思想：读者到：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等写者到：1）无读者，新写者可以写2）有读者，新写者等待3

5、）有其它写者，新写者等待信息量：readcount = 0 记录当前正在读的读者进程数，这是一个共享变量，需要互斥使用mutex = 1 互斥信息量write = 1 用于写者互斥，或第一个读者和最后一个读者与写者互斥READ：Repeat;P(mutex);readcount:=readcount+1;if(readcount=1)P(write);V(mutex);读文件P(mutex);readcount:=readcount-1;if(readcount=0)V(write);V(mutex);Until falseWRITE:RepeatP(write);写文件V(write);Un

6、til false;2.2 第二类读者-写者问题：写者优先一旦一个写者到来，它应该尽快对文件进行写操作。则新来到的读者不允许进行读操作。分析思想：读者到：1） 无读者且无写者，新读者读2） 有读者但无写者等待，新读者读3） 有读者但有写着等待，读者等待4） 有写者在写，新读者等待写者到：1） 无读者且无写者，新写者写2） 有读者在读，新写者等待3） 有写者写，新写者等待信息量：read:=1 读者信息量，用于第一个写者与读者互斥readcount:=0 记录当前读者的进程数mutex:=1 互斥信息量writecount:=0 记录当前写者排队的进程数write:=1 写者信息量，用于写者互斥

7、，第一个读者与写者互斥mutex2:=1 互斥信息量P:RepeatP(read)P(mutex)V(read)readcount:=readcount+1;if(readcount=1)P(write)V(mutex)读文件P(mutex)readcount:=readcount-1if(readcount=0)V(write)V(mutex)Until falseQ:RepeatP(mutex2)writecount:= writecount+1if(writecount=1)P(read)V(mutex2)P(write)写文件V(write)P(mutex2)writecount:=w

8、ritecount-1if(writecount=0)V(read)V(mutex2)Until false;3 哲学家就餐模型，共3种解法；哲学家就餐问题Dijkstra，1965 问题描述：有五个哲学家以思考、用餐交替进行的方式生活，他们坐在一张圆桌边，桌子上有5个盘子和5只筷子。当一个哲学家思考时，他不与邻座的哲学家发生联系，当一个哲学家感觉到饿了，他就试图拿起他左右两边的筷子用餐。如果该哲学家的邻座已经拿到筷子，则他可能只能拿到一只甚至一支筷子都拿不到。当一个饥饿的哲学家得到了两只筷子，他就可以用餐。当他用餐完毕，就放下筷子再次进行思考。一般解法：#define chopstick5v

9、oid philosopher (int i)whileP(chopsticki);P(chopstick(i+1)%5);用餐;V(chopsticki);V(chopstick(i+1)%5);思考;3.1 改进解法1最多允许4个哲学家同时坐在桌子周围。分析思想：1） 当有哲学家进程启动时，检查有几个哲学家进程已经启动，如果已经启动四个，则等待。信息量：personcount:=4 记录已经坐下的哲学家人数，即启动进程的数量chopstick0-4:=1 筷子的信息量解法：#define chopstick5#define personcountvoid philosopher (int

10、i)P(personcount);whileP(chopsticki);P(chopsticki+1);用餐;V(chopsticki);P(chopsticki+1);思考;V(personcount);3.2 改进解法2仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子参照讲义#define N 5#define THINKING 0#define HUNGRY 1#define EATING 2#typedef int semaphore;int stateNsemaphore mutex=1semaphore sNvoid test(int i)if(statei=HUNGRY)&a

11、mp;&(state(i-1)%5!=EATING)&&(state(i+1)%5!=EATING)statei=EATING;V(si);void philosopher(int i)while(true)思考;P(mutex);statei=HUNGRY;test(i);V(mutex);P(si);P(chopsticki);P(chopstick(i+1)%5);用餐;V(chopsticki);V(chopstick(i+1)%5);P(mutex);statei=THINKING;test(i-1)%5);test(i+1)%5);V(mutex);stat

12、ei=THINKING;si=0;3.3 改进解法3给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之信号量：mutex:=1 互斥信息量chopstick5:=1 筷子的信息量void philosopher(int i)while(true)思考;P(mutex);if(0=i%2)P(chopstick(i+1)%5);P(chopsticki);elseP(chopsticki);P(chopstick(i+1)%5);V(mutex);用餐;P(mutex);V(chopsticki);V(chopstick(i+1)%5;V(mutex);4 吸烟者问题，1

13、种解法；吸烟者问题（Patil, 1971) 吸烟者问题或者说是酒吧听音乐问题三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。酒吧听音乐问题：在一件酒吧里有三个音乐爱好者队列，第一队的音乐爱好者只有随身听，第二队只有音乐磁带，第三队只有电池，而要听音乐就必须

14、随身听，磁带和电池这三种物品俱全。酒吧老板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种。于是第二名音乐爱好者得到这三种物品，并开始听音乐。全部买卖就这样进行下去。以吸烟者问题为例：分析思想：供应者每次供应两种物品，并根据这两种物品叫相应的吸烟者拿走物品吸烟，其他没有叫到的吸烟者继续等待。吸烟者吸完烟后叫醒供应者再次供应物品。信息量：tobacco:=0paper:=0match:=0smoker1:=0smoker2:=0smoker3:=0seller:=0程序：semaphore tobacco=0,paper

15、=0,match=0;semaphore smoker1=0,smoker2=0,smoker3=0,seller=0;int casevoid seller()while(1)P(seller);Randomnize;case = random(0,2);if(case=0)V(tobacco);V(paper);V(smoker1);else if(case=1)V(tobacco);V(match);V(smoker2);else if(cass=2)V(paper);V(match);V(smoker3);void smoker1()while(1)P(smoker1);V(match

16、);P(tobacco);P(paper);P(match);/吸烟V(seller)void smoker2()while(1)P(smoker2);V(paper);P(tobacco);P(paper);P(match);/吸烟V(seller)void smoker3()while(1)P(smoker3);V(tobacco);P(tobacco);P(paper);P(match);/吸烟V(seller)5 面包师问题，1种解法；银行问题某银行有人民币储蓄业务，由n个柜员负责。每个顾客进入银行后先取一个号，并且等着叫号。当一个柜员人员空闲下来，就叫下一个号。试用PV操作编写柜员人

17、员和顾客进程的程序。分析思想：1） 分成两部分进程，柜员进程和顾客进程2） 顾客进门后P信息量，相当于进入等待队列。3） 柜员间互斥。当柜员空闲时，进入互斥操作部分，放入一个等待的顾客，推出互斥操作。4） 设置柜员状态变量，空闲为1，忙碌为0，顾客进入后扫描状态变量，找到空闲的柜员后过去办理业务。当顾客扫描空闲柜员的时候互斥。虽然这样能保证顾客到空闲的柜员处办理业务，但不能保证他所去的柜员是叫他号的柜员。5） 需要考虑当没有顾客，但所有柜员进程都启动的时候，柜员需要等待顾客的到来信息量：ClientQueue:=0 记录顾客等待的队列Clerkmutex:=1 柜员的互斥信息量Clientmu

18、tex:=1 顾客的互斥信息量Customer:=0 记录提供给柜员可以办理业务的客户的数量，同时在客户少于n时表示等待客户的柜员的数量。程序：#typedef int semaphoresemaphore ClientQueue=0;semaphore Customer=0;semaphore Clerkmutex=1;semaphore Clientmutex=1;int ClerkStaten;for(int i=0;i<n;i+)ClerkStatei=1;void Client()P(ClientQueue);/每个顾客不是循环不停的办理业务，所以认为不需要循环语句P(Clie

19、ntmutex);/扫描柜员期间互斥，以防与后面的顾客同时扫描到同一柜员V(Customer);/表示提供一个可供服务的客户for(int i=0;i<n;i+)/扫描到第一个空闲的柜员后推出，即到该柜员出办理if(ClerkStatei=1)ClerkStatei=0;break;V(Clientmutex);到第i个柜员处办理业务;void Clerk(int i)while(1)P(mutex);ClerkStatei=1;V(ClientQueue)V(mutex);P(Customer);/等待可供服务的客户，如果客户数量少于n，柜员在此排队办理业务;6 类似面包师的理发师问题

20、，可以推广到多个理发师问题；爱睡觉的理发师问题Dijkstra，1968一个理发店有两间相连的屋子，一间是私室，里面有一把理发椅，另一件是等候室，有一个滑动门和N把椅子。理发师忙的时候，通向私室的门被关闭，新来的顾客找一把空椅子坐下，如果椅子都被占满了，则顾客只好离去。如果没有顾客，则理发师在理发椅上睡觉，并打开通向私室的门。理发师睡觉时，顾客可以叫醒他理发。请编写理发师和顾客的程序，正确实现同步互斥问题。分析思想：1） 当没有顾客，理发师休息，当有顾客，理发师对最先来的顾客理发。2） 顾客进入理发师有3种状况：1、理发店没人，直接进里屋理发，2、理发店有人，找个凳子等，3、理发店有人，n个凳

21、子被占满，顾客离开。3） 理发师给一个顾客理完发后，打开滑门，即V操作信息量，顾客进入后关上滑门，即P操作信息量，在理发过程中，顾客是互斥的4） 一个顾客进入，即等待室中的凳子空出一把。每个顾客进入理发店需要判断是否n把椅子满，即判断变量chair=n or not。如果椅子满顾客进程需要退出。信息量：barber:=1 理发师的信息量，同时也是顾客的排队度队列Customer:=0 顾客的数量mutex:=1 顾客互斥信息量程序：#define int semaphoresemaphore waiting=0;semaphore cutHair=0;semaphore mutex=1;int

22、 count=0;void Customer()P(mutex);if(count>n)V(mutex);return false;else count+;V(mutex);if(count>1)/got a chair;P(waiting);/等待V(cutHair);/顾客叫醒理发师理发;P(mutex);count-;if(count>0)V(waiting);V(mutex);void Barber()while(true)P(cutHair);/等待顾客理发;解法二：加入了占用椅子资源，顾客付钱理发师收钱的同步过程。from 计算机操作系统课程及考研辅导semaph

23、ore mutex=1,empty=1;semaphore chair=n;semaphore full=0;semaphore cut=0,payment=0,receipt=0;int count=0;guest()P(mutex);if(count>n)V(mutex);return false;elsecount+;V(mutex);if(count>1)P(chair);/sit on a chairP(empty);/on queueV(chair);/get up from a chairelse P(empty);sit on the barbers chair;V

24、(full);P(cut);pay;V(payment);P(receipt);get up from barbers chair;V(empty);P(mutex);count-;V(mutex);exit shop;barber()while(1)P(full);cut hair;V(cut);P(payment);accept payment;V(receipt);/V(empty);二者有一即可7 狒狒过河问题；巴拿马运河问题巴拿马运河建在太平洋和大西洋之间，由于太平洋和大西洋水面高度不同，有巨大落差，所以运河中建有T(T2)级船闸，并且只能允许单向通行，船闸依次编号为1,2,T，由大

25、西洋来的船需要经过船闸T,T-1.,2,1通过运河到达太平洋，由太平洋来的船需要经由船闸1,2,T-1,T通过运河到达大西洋。使用P,V操作正确解决大西洋和太平洋的船只通航问题。分析思想：1） 巴拿马运河大西洋，太平洋两个方向的船设置为两个进程。Atlantic(),Pacific();2） 当一侧船来到运河，如果另一侧船在过河，则等待；如果自己方船在过河，同时己方船只的总过河船数小于T，则过河；如果己方船在过河，同时己方船只过河总数大于T，则等待。3） 为了避免饥饿和死锁，必须控制一次过河的船数T。信息量：A,P:=1 代表两边的船只是否允许通过的闸门。mutex1,mutex2:=1 互斥

26、信息量程序：semaphore A=1;semaphore P=1;semaphore mutex1=1;semaphore mutex2=1;int PshipSum=0,AshipSum=0;int PshipCur=0,AshipCur=0;Pacific()P(P);P(mutex1);PshipSum+; PshipCur+;if(PshipCur=1)P(A);if(PshipSum=T)P(P);V(P);V(mutex1)过河；P(mutex1);PshipCur-;if(PshipCur=0)V(A);PshipSum=0;if(PshipSum=T)V(P);V(mutex

27、1);Atlantic()P(A);P(mutex2);AshipSum+; AshipCur+;if(AshipCur=1)P(P);if(AshipSum=T)P(A);V(A);V(mutex2);过河；P(mutex2);AshipCur-;if(AshipCur=0)V(P);AshipSum=0;if(AshipSum=T)V(A);V(mutex2);8 另类P，V问题。红客黑客过河问题有红客和黑客两组人员需要过河。河上有船，但是每次只能乘坐4人，且每次乘客满员时才能开船，到河对岸后空船返回。但船上乘客不能同时有3个红客 、1个黑客 或者 1个红客 、 3个黑客的组合。（其他组合

28、安全）。请编写程序，用pv操作解决红客、黑客过河的问题。并说明所设置的信号量及其初值。分析思想：(from 计算机科学论坛-北大必考题，PV经典案例分析)对同步与互斥的分析： 同步关系：1. 满员才能开船；2. 红黑客满足一定的组合规则,才能有四人上船 互斥关系：红黑客对请求上船的控制 显然，此题难点在对同步关系的解决。 下面给出所写程序的算法思想： Red():每个红客到来请求上船时执行该程序； 1. 请求进入临界区； 2. 首先检查本人的到来是否满足上船的组合(即4个红客或2个红客与2个黑客); 3. 如果满足2个红客和2和黑客的组合，则看是否有船可上，有的话该红客上船并通知另外1个红客和

29、2个黑客上船，然后通知船满员，并退出临界区； 4. 如果满足4个红客的组合，则看是否有船可上，有的话该红客上船并通知另外3个红客上船，然后通知船满员，并退出临界区； 5. 不符合上船的组合，则先退出临界区，然后在信号量S_red上等待，直到当条件满足时，有人通知其上船。 6. 完毕。 Black():每个黑客到来请求上船时执行该程序,其算法与Red()完全一致； Boat():河上的船执行该程序； 1.等待满员后开船过河； 2.空船返回，通知可以上船了，转而执行1。信息量：mutex:=1S_red,S_black:=0ready:=1 船是否靠岸board:=0上船shipping:=0 程

30、序：semaphore mutex=1;semaphore S_red=0;semaphore S_black=0;semaphore board=0;semaphore shipping=0;int RedCount=0,BlackCount=0;Red()P(mutex);RedCount+;if(RedCount>1 && BlackCount>1)P(ready);V(S_red);V(S_black);V(S_black);上船;V(board);P(shipping);RedCount-=2;BlackCount-=2;开船;V(mutex);else

31、if(RedCount=4)P(ready);V(S_red);V(S_red);V(S_red);上船;V(board);P(shipping);RedCount-=4;开船;V(mutex);else V(mutex);P(S_red);上船;开船;Black()P(mutex);BlackCount+;if(RedCount>1 && BlackCount>1)P(ready);V(S_black);V(S_red);V(S_red);上船;V(board);P(shipping);RedCount-=2;BlackCount-=2;开船;V(mutex);else if(BlackCount=4)P(ready);V(S_black);V(S_black);V(S_black);上船;V(board);