经典的PV问题

PV问题：1 生产-消费模型，推广到多个生产者，多个消费者的生产消费模型；设一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来，缓冲区只能容纳一个产品，生产者不断的生产产品，然后往空缓冲区送产品；消费者不断的从缓冲区中取出产品，并消费1.1 一个生产者、一个消费者、一个缓冲区的模型：信号量empty=0 full=017__________________________________________________ P： Repeat 生产一个产品 送产品到缓冲区 V(full); P(empty); Until false; Q： Repeat： P(full); 从缓冲区拿走一个产品 V(empty); 消费产品 Until false;1.2 一个生产者、一个消费者、一个缓冲区的第二种解法：信号量empty=1 full=0 P: Repeat P(empty); 生产一个产品 送产品到缓冲区 V(full); Until false; Q: Repeat P(full); 从缓冲区取产品 V(empty); 消费产品 Until false;1.3 一个生产者、一个消费者、n个缓冲区的模型：(不需要考虑互斥)信号量empty=n ——空缓冲区的数目full=0 ——满缓冲区的数目P: i:=0 Repeat 生产产品 P(empty); 送产品到缓冲池buffer[i] V(full); i:=(i+1)mod n; Until false;Q: j:=0 Repeat P(full); 从缓冲池buffer[i]中取产品 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:=0 Repeat 生产产品 P(empty); P(mutex1); 添加产品到缓冲区buffer[i] i:=(i+1)mod n;V(mutex1); V(full); Until false;Q: j:=0 Repeat P(full); P(mutex2); 从缓冲区buffer[j]中取产品 j:=(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）有其它写者，新写者等待信息量：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: Repeat P(write); 写文件 V(write); Until false;2.2 第二类读者-写者问题：写者优先一旦一个写者到来，它应该尽快对文件进行写操作。

则新来到的读者不允许进行读操作分析思想：读者到：1） 无读者且无写者，新读者读2） 有读者但无写者等待，新读者读3） 有读者但有写着等待，读者等待4） 有写者在写，新读者等待写者到：1） 无读者且无写者，新写者写2） 有读者在读，新写者等待3） 有写者写，新写者等待信息量：read:=1 ——读者信息量，用于第一个写者与读者互斥readcount:=0 ——记录当前读者的进程数mutex:=1 ——互斥信息量writecount:=0 ——记录当前写者排队的进程数write:=1 ——写者信息量，用于写者互斥，第一个读者与写者互斥mutex2:=1 ——互斥信息量P: Repeat P(read) P(mutex) V(read) readcount:=readcount+1; if(readcount=1) P(write) V(mutex) 读文件 P(mutex) readcount:=readcount-1 if(readcount=0) V(write) V(mutex) Until falseQ: Repeat P(mutex2) writecount:= writecount+1 if(writecount=1) P(read) V(mutex2) P(write) 写文件 V(write) P(mutex2) writecount:=writecount-1 if(writecount=0) V(read) V(mutex2) Until false;3 哲学家就餐模型，共3种解法；哲学家就餐问题[Dijkstra，1965] 问题描述：有五个哲学家以思考、用餐交替进行的方式生活，他们坐在一张圆桌边，桌子上有5个盘子和5只筷子。

当一个哲学家思考时，他不与邻座的哲学家发生联系，当一个哲学家感觉到饿了，他就试图拿起他左右两边的筷子用餐如果该哲学家的邻座已经拿到筷子，则他可能只能拿到一只甚至一支筷子都拿不到当一个饥饿的哲学家得到了两只筷子，他就可以用餐当他用餐完毕，就放下筷子再次进行思考一般解法：#define chopstick[5]void philosopher (int i){ while{ P(chopstick[i]); P(chopstick[(i+1)%5]); 用餐; V(chopstick[i]); V(chopstick[(i+1)%5]); 思考; }}3.1 改进解法1最多允许4个哲学家同时坐在桌子周围分析思想：1） 当有哲学家进程启动时，检查有几个哲学家进程已经启动，如果已经启动四个，则等待信息量：personcount:=4 ——记录已经坐下的哲学家人数，即启动进程的数量chopstick[0-4]:=1 ——筷子的信息量解法：#define chopstick[5]#define personcountvoid philosopher (int i){ P(personcount); while{ P(chopstick[i]); P(chopstick[i+1]); 用餐; V(chopstick[i]); P(chopstick[i+1]); 思考; } V(personcount);}3.2 改进解法2仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子参照讲义#define N 5#define THINKING 0#define HUNGRY 1#define EATING 2#typedef int semaphore;int state[N]semaphore mutex=1semaphore s[N]void test(int i){ if((state[i]==HUNGRY)&&(state[(i-1)%5]!=EATING)&&(state[(i+1)%5]!=EATING)){ state[i]=EATING; V(s[i]); } } void philosopher(int i){ while(true){ 思考; P(mutex); state[i]=HUNGRY; test(i); V(mutex); P(s[i]); P(chopstick[i]); P(chopstick[(i+1)%5]); 用餐; V(chopstick[i]); V(chopstick[(i+1)%5]); P(mutex); state[i]=THINKING; test((i-1)%5); test((i+1)%5); V(mutex); } } state[i]=THINKING; s[i]=0;3.3 改进解法3给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 信号量： mutex:=1 ——互斥信息量 chopstick[5]:=1 ——筷子的信息量 void philosopher(int i){ while(true){ 思考; P(mutex); if(0==i%2){ P(chopstick[(i+1)%5]); P(chopstick[i]); }else{ P(chopstick[i]); P(chopstick[(i+1)%5]); } V(mutex); 用餐; P(mutex); V(chopstick[i]); V(chopstick[(i+1)%5]; V(mutex); } } 4 吸烟者问题，1种解法；吸烟者问题（Patil, 1971) 吸烟者问题或者说是酒吧听音乐问题三个吸烟者在一间房间内，还有一个香烟供应者。

为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴供应者有丰富的货物提供三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者试为吸烟者和供应者编写程序解决问题酒吧听音乐问题：在一件酒吧里有三个音乐爱好者队列，第一队的音乐爱好者只有随身听，第二队只有音乐磁带，第三队只有电池，而要听音乐就必须随身听，磁带和电池这三种物品俱全酒吧老板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种于是第二名音乐爱好者得到这三种物品，并开始听音乐全部买卖就这样进行下去以吸烟者问题为例：分析思想：供应者每次供应两种物品，并根据这两种物品叫相应的吸烟者拿走物品吸烟，其他没有叫到的吸烟者继续等待吸烟者吸完烟后叫醒供应者再次供应物品信息量：tobacco:=0paper:=0match:=0smoker1:=0smoker2:=0smoker3:=0seller:=0程序：semaphore tobacco=0,paper=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); 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操作编写柜员人员和顾客进程的程序分析思想：1） 分成两部分进程，柜员进程和顾客进程2） 顾客进门后P信息量，相当于进入等待队列3） 柜员间互斥当柜员空闲时，进入互斥操作部分，放入一个等待的顾客，推出互斥操作4） 设置柜员状态变量，空闲为1，忙碌为0，顾客进入后扫描状态变量，找到空闲的柜员后过去办理业务当顾客扫描空闲柜员的时候互斥虽然这样能保证顾客到空闲的柜员处办理业务，但不能保证他所去的柜员是叫他号的柜员5） 需要考虑当没有顾客，但所有柜员进程都启动的时候，柜员需要等待顾客的到来信息量：ClientQueue:=0 ——记录顾客等待的队列Clerkmutex:=1 ——柜员的互斥信息量Clientmutex:=1 ——顾客的互斥信息量Customer:=0 ——记录提供给柜员可以办理业务的客户的数量，同时在客户少于n时表示等待客户的柜员的数量程序：#typedef int semaphoresemaphore ClientQueue=0;semaphore Customer=0;semaphore Clerkmutex=1;semaphore Clientmutex=1;int ClerkState[n];for(int i=0;i

理发师忙的时候，通向私室的门被关闭，新来的顾客找一把空椅子坐下，如果椅子都被占满了，则顾客只好离去如果没有顾客，则理发师在理发椅上睡觉，并打开通向私室的门理发师睡觉时，顾客可以叫醒他理发请编写理发师和顾客的程序，正确实现同步互斥问题分析思想：1） 当没有顾客，理发师休息，当有顾客，理发师对最先来的顾客理发2） 顾客进入理发师有3种状况：1、理发店没人，直接进里屋理发，2、理发店有人，找个凳子等，3、理发店有人，n个凳子被占满，顾客离开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 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 《计算机操作系统课程及考研辅导》semaphore 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; } else{ count++; V(mutex); if(count>1){ P(chair); //sit on a chair P(empty); //on queue V(chair); //get up from a chair } else P(empty); sit on the barber’s chair; V(full); P(cut); pay; V(payment); P(receipt); get up from barber’s 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(T≥2)级船闸，并且只能允许单向通行，船闸依次编号为1,2,…,T，由大西洋来的船需要经过船闸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 ——互斥信息量程序：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(mutex1);}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个黑客的组合其他组合安全）请编写程序，用pv操作解决红客、黑客过河的问题并说明所设置的信号量及其初值分析思想：(from 计算机科学论坛--北大必考题，PV经典案例分析)对同步与互斥的分析： 同步关系：1. 满员才能开船；2. 红黑客满足一定的组合规则,才能有四人上船 互斥关系：红黑客对请求上船的控制 显然，此题难点在对同步关系的解决 下面给出所写程序的算法思想： Red():每个红客到来请求上船时执行该程序； 1. 请求进入临界区； 2. 首先检查本人的到来是否满足上船的组合(即4个红客或2个红客与2个黑客); 3. 如果满足2个红客和2和黑客的组合，则看是否有船可上，有的话该红客上船并通知另外1个红客和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 程序：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 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); 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; 若s<0，本进程进入s信号量等待队列的末尾；否则，继续执行。

v(s) s=s+1; 若s<=0,释放等待队列中末尾的进程，否则，继续执行现有4个进程p1,p2,p3,p4竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面的定义的p,v操作正确解决p1,p2,p3,p4对该互斥资源的使用问题在标准PV操作定义下，四个进程竞争使用一个互斥资源可以用这样的程序semaphore s=1;Pi(int i){ while(true){ P(s); 使用资源； V(s); }}思想&解法from: 计算机科学论坛--北大必考题，PV操作中的疑惑 Thank to Supremgoooo题目的重点在于：若s<=0,释放等待队列中末尾的进程，在标准定义下是随机从等候队列中释放进程所以当两个进程竞争资源是，用上面的程序没有问题，两个进程将循环使用资源当多个进程竞争资源时，最后队列尾部的两个进程使用资源前面的进程形成饥饿解决方法：使进程两两竞争使用资源1、 漏斗解法：用队列来实现这个过程，就是把进程对资源的请求排队，首先要占到队尾，然后向前移动一位直到站到队首2、 倒立二叉树解法：相邻的两个进程先两两竞争，优胜者进入下一轮竞争。

最后得出优胜者使用资源程序1： semaphore mutex1=1,mutex2=2,mutex3=3;void Pi(){ //i∈{1,2,3,4} whiles(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或2 while(1){ P(s1); P(s); 使用资源; V(s); V(s1); }}void Pi(){ //i=3或4 while(1){ P(s2); P(s); 使用资源； V(s); V(s2); }}。