《经典的PV问题(共17页).doc》由会员分享，可在线阅读，更多相关《经典的PV问题(共17页).doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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)&(
11、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);statei=THINKING;si=0;3
12、.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种解法；吸烟者问题（Patil, 1
13、971) 吸烟者问题或者说是酒吧听音乐问题三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。酒吧听音乐问题：在一件酒吧里有三个音乐爱好者队列，第一队的音乐爱好者只有随身听，第二队只有音乐磁带，第三队只有电池，而要听音乐就必须随身听，磁带和电池这三种物品俱全。酒
14、吧老板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种。于是第二名音乐爱好者得到这三种物品，并开始听音乐。全部买卖就这样进行下去。以吸烟者问题为例：分析思想：供应者每次供应两种物品，并根据这两种物品叫相应的吸烟者拿走物品吸烟，其他没有叫到的吸烟者继续等待。吸烟者吸完烟后叫醒供应者再次供应物品。信息量：tobacco:=0paper:=0match:=0smoker1:=0smoker2:=0smoker3:=0seller:=0程序：semaphore tobacco=0,paper=0,match=0;semapho
15、re 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);P(tobacco);P(pap
16、er);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操作编写柜员人员和顾客进程的程序。分析思想：1）
17、分成两部分进程，柜员进程和顾客进程2） 顾客进门后P信息量，相当于进入等待队列。3） 柜员间互斥。当柜员空闲时，进入互斥操作部分，放入一个等待的顾客，推出互斥操作。4） 设置柜员状态变量，空闲为1，忙碌为0，顾客进入后扫描状态变量，找到空闲的柜员后过去办理业务。当顾客扫描空闲柜员的时候互斥。虽然这样能保证顾客到空闲的柜员处办理业务，但不能保证他所去的柜员是叫他号的柜员。5） 需要考虑当没有顾客，但所有柜员进程都启动的时候，柜员需要等待顾客的到来信息量：ClientQueue:=0 记录顾客等待的队列Clerkmutex:=1 柜员的互斥信息量Clientmutex:=1 顾客的互斥信息量Cus
18、tomer:=0 记录提供给柜员可以办理业务的客户的数量，同时在客户少于n时表示等待客户的柜员的数量。程序：#typedef int semaphoresemaphore ClientQueue=0;semaphore Customer=0;semaphore Clerkmutex=1;semaphore Clientmutex=1;int ClerkStaten;for(int i=0;in;i+)ClerkStatei=1;void Client()P(ClientQueue);/每个顾客不是循环不停的办理业务，所以认为不需要循环语句P(Clientmutex);/扫描柜员期间互斥，以防与
19、后面的顾客同时扫描到同一柜员V(Customer);/表示提供一个可供服务的客户for(int i=0;in)V(mutex);return false;else count+;V(mutex);if(count1)/got a chair;P(waiting);/等待V(cutHair);/顾客叫醒理发师理发;P(mutex);count-;if(count0)V(waiting);V(mutex);void Barber()while(true)P(cutHair);/等待顾客理发;解法二：加入了占用椅子资源，顾客付钱理发师收钱的同步过程。from 计算机操作系统课程及考研辅导semaph
20、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(countn)V(mutex);return false;elsecount+;V(mutex);if(count1)P(chair);/sit on a chairP(empty);/on queueV(chair);/get up from a chairelse P(empty);sit on the barbers chair;V(full);P
21、(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，由大西洋来的船需要经
22、过船闸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 互斥信息量程序：se
23、maphore 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(mutex1);Atlan
24、tic()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个黑客的组合。（其他组合安全）。请编写程
25、序，用pv操作解决红客、黑客过河的问题。并说明所设置的信号量及其初值。分析思想：(from 计算机科学论坛-北大必考题，PV经典案例分析)对同步与互斥的分析： 同步关系：1. 满员才能开船；2. 红黑客满足一定的组合规则,才能有四人上船 互斥关系：红黑客对请求上船的控制 显然，此题难点在对同步关系的解决。 下面给出所写程序的算法思想： Red():每个红客到来请求上船时执行该程序； 1. 请求进入临界区； 2. 首先检查本人的到来是否满足上船的组合(即4个红客或2个红客与2个黑客); 3. 如果满足2个红客和2和黑客的组合，则看是否有船可上，有的话该红客上船并通知另外1个红客和2个黑客上船，然
26、后通知船满员，并退出临界区； 4. 如果满足4个红客的组合，则看是否有船可上，有的话该红客上船并通知另外3个红客上船，然后通知船满员，并退出临界区； 5. 不符合上船的组合，则先退出临界区，然后在信号量S_red上等待，直到当条件满足时，有人通知其上船。 6. 完毕。 Black():每个黑客到来请求上船时执行该程序,其算法与Red()完全一致； Boat():河上的船执行该程序； 1.等待满员后开船过河； 2.空船返回，通知可以上船了，转而执行1。信息量：mutex:=1S_red,S_black:=0ready:=1 船是否靠岸board:=0上船shipping:=0 程序：semaph
27、ore 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(RedCount1 & BlackCount1)P(ready);V(S_red);V(S_black);V(S_black);上船;V(board);P(shipping);RedCount-=2;BlackCount-=2;开船;V(mutex);else if(RedCount=4)P(ready);V(
28、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(RedCount1 & BlackCount1)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(
29、S_black);V(S_black);上船;V(board);P(shipping);BlackCount-=4;开船;V(mutex);else V(mutex);P(S_black);上船;开船;Ship()while(1)V(ready);上船;P(board);V(shipping);开船;某系统如此定义p,v操作： p(s) s=s-1; 若s0，本进程进入s信号量等待队列的末尾；否则，继续执行。 v(s) s=s+1; 若s=0,释放等待队列中末尾的进程，否则，继续执行。现有4个进程p1,p2,p3,p4竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面的定义的p,v操
30、作正确解决p1,p2,p3,p4对该互斥资源的使用问题。在标准PV操作定义下，四个进程竞争使用一个互斥资源可以用这样的程序。semaphore s=1;Pi(int i)while(true)P(s);使用资源；V(s);思想&解法from: 计算机科学论坛-北大必考题，PV操作中的疑惑 Thank to Supremgoooo题目的重点在于：若s=0,释放等待队列中末尾的进程，在标准定义下是随机从等候队列中释放进程。所以当两个进程竞争资源是，用上面的程序没有问题，两个进程将循环使用资源。当多个进程竞争资源时，最后队列尾部的两个进程使用资源。前面的进程形成饥饿。解决方法：使进程两两竞争使用资源
31、。1、 漏斗解法：用队列来实现这个过程，就是把进程对资源的请求排队，首先要占到队尾，然后向前移动一位。直到站到队首。2、 倒立二叉树解法：相邻的两个进程先两两竞争，优胜者进入下一轮竞争。最后得出优胜者使用资源。程序1：semaphore mutex1=1,mutex2=2,mutex3=3;void Pi()/i1,2,3,4whiles(true)P(mutex3);/挡住最后的一个进程，即最后面的进程在这里等待排队P(mutex2);P(mutex1);/最后剩下的两个进程竞争资源使用资源;V(mutex1);/让mutex1的竞争失败者向前一步使用资源V(mutex2);/让mutex2的竞争失败者前进一步到mutex1等待V(mutex3);程序2：semaphore s1=1,s2=1,s=1;void Pi()/i=1或2while(1)P(s1);P(s);使用资源;V(s);V(s1);void Pi()/i=3或4while(1)P(s2);P(s);使用资源；V(s);V(s2);