经典PV操作问题详解(最全面的PV资料).doc

经典P、V操作问题详解一、基本概念1. 信号量struct semaphoreint value; / 仅且必须附初值一次，初值非负PCBtype* wait_queue; / 在此信号量上阻塞的进程队列 S; / 信号量实例为S2. P、V操作P(S)S := S-1;if (S=0; j-)P(Sj);DO_JOB_IN_CRITICAL_SECTION();for(j=0;j=n-2;j+)V(Sj);二、经典进程同步问题总述：进程同步问题主要分为以下几类：一（生产者消费者问题）；二（读者写者问题）；三（哲学家就餐问题）；四（爱睡觉的理发师问题）；五（音乐爱好者问题）；六（船闸问题）；七（红黑客问题）等。其中前两类都是用于处理进程之间通信的问题：生产者消费者问题主要实现进程的消息机制，而读者写者问题用于实现管道通信。哲学家就餐问题是经典的互斥转同步防止死锁的多资源争夺。理发师问题适合I/O或外部设备的管理，如打印调度。红黑客问题是解决不同条件触发事件的思想方法。I. 生产者消费者问题(初始缓冲区为空)问题：生产者生产产品放到缓冲区，消费者从缓冲区取产品消费。单缓冲区书P119(适合单或多生产消费者)：同步：生产者不能往满缓冲区放产品(S1(1)；消费者不能从空缓冲区取产品(S2(0)。void Producer()while (true) 生产一个产品; P(S1); 申请一个空的缓冲区 放到缓冲区; V(S2); 返回一个满的缓冲区void Consumer()while (true) P(S2); 申请一个满的缓冲区 从缓冲区取一个产品; V(S1); 返回一个空的缓冲区 消费产品;环行多缓冲区（或无穷缓冲区）单生产消费者习题P173-13：同步：生产者不能往满缓冲区放产品(S1(n)；消费者不能从空缓冲区取产品(S2(0)。n为缓冲区大小。互斥：设置指示下一个空缓冲区的位置变量(i(0)和指示下一个产品在缓冲区的位置变量(j(0)，由于只有一个生产者和消费者，i和j无须互斥访问。此问题无互斥关系。void Producer()while (true)生产了一个产品;P(S1);把产品放入缓冲区; i = (i+1)%n; / 无穷缓冲区无须%nV(S2);void Consumer()while (true) P(S2); 取一个产品; j = (j+1)%n; / 无穷缓冲区无须%n V(S1); 消费产品;环行多缓冲区多生产消费者书P120：同步：生产者不能往满缓冲区放产品(S1(n)；消费者不能从空缓冲区取产品(S2(0)。n为缓冲区大小。互斥：设置指示下一个空缓冲区的位置变量(i(0)，生产者之间互斥(mutex1(1)；设置指示下一个产品在缓冲区的位置变量(j(0)，消费者之间互斥(mutex2(1)。也可以生产者和消费者之间都互斥(把mutex1和mutex2都换成一个mutex(1)。void Producer()while(true) 生产一个产品; P(S1); 申请一个空的缓冲区 P(mutex1); 一个生产者申请制造产品 放到缓冲区; i = (i+1)%n; 指针移动到下一空的缓冲区 V(mutex1); 释放生产者 V(S2); 释放一个满的缓冲区void Consumer()while(true) P(S2); 申请一个满的缓冲区 P(mutex2); 一个消费者申请消费 从第j个缓冲区取一个产品; j = (j+1)%n; 指向下一个满的缓冲区 V(mutex2); 释放消费者 V(S1);释放一个空的缓冲区 消费产品;用进程通信(信箱通信)的方法解决上述问题习题P175-27:void Producer()msgbuff mb; /message bufferwhile (1)generate sth. to send;receive(consumer, &mb); / 取一空缓冲区create_message(&mb); / 放产品到缓冲区send(consumer,&mb); / 生产好的产品发给消费者/ send和receive原语见信箱通信问题void Consumer() msgbuff mb; / empty messagefor(int i=0 ; in; i+)send(producer, &mb); / 初始化，发n个空缓冲区给生产者while (1)receive(producer, &mb); / 收到一个产品extract message; / 把产品保存下来send(producer, &mb); / 把空缓冲区再发给生产者do sth.; / 消费产品进程消息缓冲通信书P128:问题：发送进程把缓冲区中的消息挂到接收进程的消息链上。同步：发送进程发送消息数量不限，无消息时接收进程不能取信息，故设置当前消息数量(m-syn(0)。互斥：发送和接收进程互斥访问消息队列首指针m-q，故设置互斥信号量(m-mutex(1)。空缓冲区个数为(s-b(n)，设置互斥访问信号量(b-mutex(1)。send(R,M) / 把消息M发给R找到接收进程R，否则错误返回;申请缓冲区P(s-b);P(b-mutex); 取一空缓冲区;V(b-mutex);把信息M复制到空缓冲区;P(m-mutex); 把缓冲区挂到m-q上;V(m-mutex);V(m-syn); receive(A) / 把消息存到地址AP(m-syn);P(m-mutex); 取一消息复制到A;V(m-mutex);P(b-mutex); 释放消息缓冲区;V(b-mutex);进程信箱通信书P130，06年秋讲义：问题：发送进程把信息发到信箱中，接收进程随时取信。同步：发送进程不能向满信箱中发信(full(0)；接收进程不能从空信箱中取信(empty(1)。send(N,M) / 把信件M发到信箱N中查找信箱N;P(full); 把M送入信箱N;V(empty);receive(N,X) / 从信箱N中取一封信放到X查找信箱N;P(empty); 从信箱N中取一封信放到X;V(full);进程通信多发送接收者问题习题P174-16：问题：n1个进程通过m个缓冲区向n2个进程发送消息，每个消息所有接收进程都接收一次。同步：发送者不能向满缓冲区发信息(mutex_sendm(1)；接收者不能从空缓冲区接收信息(mutex_receivem(0)。互斥：设置指示下一个空缓冲区变量(cur(0)，发送进程互斥访问(mutex_cur(1)；设置buffer_countm(0)记录某个缓冲区被读过几次，若某个缓冲区被读过n2次，则可以释放，接收者互斥访问buffer_count(mutex_countm(1)。阻塞分析：若接收者试图接收空缓冲区被阻塞在mutex_receivek上，则其他要访问同一缓冲区的接收者被堵塞在mutex_countk上；若此时发送者向缓冲区k写入信息，则由第一个接收者释放其他接收者。若有一发送者被阻塞在mutex_sendcur上，则其他发送者被阻塞在mutex_cur上。void send()while (true)P(mutex_cur);cur = (cur+1)% m;/ 若阻塞则表示cur满P(mutex_sendcur);写入buffercur; / cur内容等待被读取V(mutex_receivecur);V(mutex_cur);void receive()While (true)for (int i=0; im; i+)P(mutex_counti);buffer_counti+;if (buffer_counti=1) / 第一次读，有信息吗？P(mutex_receivei); / 有信息(或已经有人在访问了），释放其他接收者V(mutex_counti);从bufferi中读;P(mutex_counti);if (buffer_counti=n2) / 大家都收过一次了buffer_counti = 0; / buffer_count恢复初值V(mutex_sendi); / 释放此缓冲区V(mutex_counti);II. 读者写者问题读者写者问题与生产者消费者问题最大区别在于前者不存在同步问题，就是说不考虑读者没有东西读的问题，没有可读的直接“走人”。而后者如果没有东西消费，就会阻塞等待。第一类(读者优先)书P121：问题：写者在写，则其余写者和读者等待；有读者在读，则其他读者可读，直到没有读者写者才能写。互斥：写者之间互斥以及所有读者和写者之间互斥(write(0/1)；读者之间不互斥；readcount记录当前读者个数(readcount(0)，多个读者对readcount互斥访问，访问后加上1(mutex(1); readcount是一个可被多个读者进程访问的临界资源，所以需要设置一个互斥信号mutex阻塞分析：当有读者在读时，所有写者堵塞在write上；有写者在写时，第一个读者阻塞在write上，其余的阻塞在mutex上，所有写者阻塞在write上。void Reader()P(mutex);一开始，读者申请一个位置去看书readcount+;然后逐渐有更多的读者读书，自动加上1if (readcount=1) / 第一个读者，可能有写者在写 P(write);为写者申请一个空间写东西V(mutex);读者要释放空间或缓冲区了P(mutex);为读者申请能读书的资源readcount-;读者读不到足够的书 读者逐渐减少if (readcount=0) / 没有读者了，释放写者 V(write);V(mutex);释放读者，让作者写书void Writer()P(write); 写;V(write);/ 释放的可能是读者或写者/*相对读者优先，即写者可以释放写者；也可改为绝对读者优先，即只要有读者在，写者写完优先释放读者。方法类似于写者优先。*/第二类(写者优先)习题P175-24：问题：写者在写，则其余写者和读者等待；写者写完，优先释放下一个写者；读者在读，若无写者等待，则其他读者可读；读者在读，若有写者等待，则其他读者等待。互斥：写者之间互斥(write(1)，读者和写者之间互斥(read(1)；读者之间不互斥；记录当前读者个数(readcount(0)和写者个数(writecount(0)，读者对readcount互斥访问(mutex1(1)，写者对writecount互斥访问(mutex2(1)；为保证在有读者等待的时候，新写者到来也优先释放写者，让等待的读者继续等待，不能将读者和写者阻塞在同一队列上(mutex3(1)。阻塞分析：当有写者在写时，其余写者阻塞在write上，第一个读者阻塞在read上，其他的读者堵塞在mutex3上。当一个写者写完后，若有写者等待，则唤醒一个写者，否则唤醒第一个读者，由第一个读者唤醒其余读者。当有读者在读时，一读者R通过P(read)还未V(read)，此时新到来的第一位写者W阻塞在read上，其余写者阻塞在mutex2上；新到来的第一位读者R1阻塞在read上，其余读者阻塞在mutex3上：（1）若正在等待的第一位写者W先于读者R1到来，则他先被读者R释放，接着W会释放其余写者，使原阻塞在mutex2上的写者通过mutex2，重新阻塞在write上，而所有等待的读者仍然阻塞在原来的地方；（2）否则读者R先释放读者R1，R1代替R的位置，原来等待在mutex3上的第一位读者R2被阻塞在read上，但此时R2在read等待队列上必处于写者W之后，成为情况（1）。因此可以看到，在下面的方案中，新写者到来后，最多再放行一位读者。void Reader()P(mutex3);/若去掉则读者和写者先来后到P(read);P(mutex1);/其实有了read无需mutex1readcount+;if (readcount=1)P(write);V(mutex1);V(read);V(mutex3);reading;P(mutex1);readcount-;if (readcount=0)V(write);V(mutex1);void Writer()P(mutex2);writecount+;if (writecount=1)P(read);V(mutex2);P(write);writing;V(write);P(mutex2);writecount-;if (writecount=0)V(read);V(mutex2);III. 哲学家就餐问题书P122，06年秋讲义问题：n个哲学家，n支筷子，仅当一个哲学家两边的筷子都可用时才可以拿筷子。互斥：设置n个哲学家的状态变量(staten(thinking/hungry/eating)，初始值全thinking)，用于判断一个哲学家的左右筷子是否能用；设置n个信号量(sn，初始全0)，用于判断哲学家是否能吃饭。每个哲学家对state和s互斥访问(mutex(1)。void test()if (statei=hungry &state(i-1)%n!=eating &state(i+1)%n!=eating) / 能吃饭，后面的P(si)不会阻塞statei = eating;V(si);void Philosopher(int i)Thinking;P(mutex); statei = hungry; test(i); / 能吃饭吗？V(mutex);P(si); / 能吃饭！其对应的V操作在test里 拿起左右筷子吃饭；吃完放下左右筷子；P(mutex);statei = thinking;/ 吃完了，帮忙看看左右的能吃饭吗 test(i-1)%n); test(i+1)%n);V(mutex);IV. 爱睡觉的理发师问题单理发师习题P174-18，01、06年试题，06年秋讲义问题：理发师只在理发椅前，要么理发要么睡觉；理发师睡觉时，第一个顾客唤醒理发师；理发师在理发时，其余顾客在n张椅子上等待；椅子不够时，顾客离开。同步：没有顾客时理发师不能理发，只能睡觉(customer(0)；理发师睡觉的时候顾客不能理发，需先唤醒(barber(1)。互斥：设置变量wait_count(0)来记录当前等待的顾客数，理发师和顾客以及顾客之间对其互斥访问(mutex(1)。void Barber()while (true) P(customer); / 有顾客吗？没有就睡觉 P(mutex); / 来顾客了！ / 进私室理发，把椅子让给其他人 wait_count-; V(mutex); cut hair; / 理完了一个，可以理下一个了 V(barber); / 注意：如果barber初值是0，则 / V(barber)在cut hair之前void Costumer()P(mutex); / 防止两顾客同坐最后一个椅子if (wait_countn) wait_count+; / 有椅子做，不走了V(mutex);V(costumer); / 我要理发！叫醒理发师P(barber); / 理发师忙吗？忙就等一会get haircut; else / 没有椅子了，不剪了V(mutex);银行叫号系统或多理发师问题习题P174-20，2000年试题问题：银行有n个柜台，每个顾客进入银行取号，若没有空闲柜台则等待，只要有柜台的人员空闲，就叫号。没有顾客时，柜台人员等待。同步：没有顾客时柜台等待(client(0)，无空闲柜台时顾客持号等待(clerk(n)。互斥：设置各柜台状态变量(staten(available/unavailable)，初始值全available），任何顾客或柜员均对其互斥访问(mutex(1)。void Clerk(int i)while (true) P(client); / 有顾客吗？ 办理业务; P(mutex); / 办理完了，恢复状态 statei=available; V(mutex); V(clerk); / 叫下一位顾客 void Client() P(clerk); / 有空柜台吗？ P(mutex); / 找一个空闲柜台 for (int k=1; k1) / 2红客+2黑客过河wait_count = 4; / 设置等船人数V(red_wait); V(black_wait); V(black_wait); / 释放他们red_count = 0; black_count = black_count-2; /else ifelse / (1红+0/1/2/3黑)or(2红+0/1黑)or(3红+0/1黑)V(mutex); / 在阻塞自己之前先释放两个count的访问权 P(red_wait); / 不能走，自己阻塞自己在己方的等待队列上 /else P(mutex_wait_for_boat); if (wait_count=4) P(boat); / 船回来了吗？ wait_count-; / 此人上船 if (wait_count =0) V(full); / 都上船了，可以走了V(mutex); / 其他人可以开始组成四人组了 V(mutex_wait_for_boat);过河啦！void boat()while (true) P(full); / 客满再走 过河; 返回; V(boat); / 我回来了VIII.红黑客问题变形07年试题问题：n个学生m个网球场k个裁判，两个学生组成一组打网球，每组有一个裁判。同步：没有学生，教练休息(student(0)，没有教练，学生等待(referee(k)。互斥：学生互斥的使用场地(playground(m)；记录学生当前的数目(s_count(0)，所有学生互斥访问它(mutex(1)；若不能组成两人组，则先到的学生自己阻塞自己(s_wait(0)；若组成两人组，则派一个代表去申请场地和教练，其余的人等待(mutex_wait(1)，设置等待计数(wait_count(0)；void student_tenis()P(mutex);s_count+; / 学生数目加1if (s_count=2) / 有2个学生了，可以组队去打球了 wait_count = 2; / 设置等待人数 V(s_wait); / 释放1个等待的学生 s_count = 0; / 重新计数 /ifelse / s_count=1，人不够，等待V(mutex); / 在阻塞自己之前先释放两个count的访问权 P(s_wait); / 自己阻塞自己 /else P(mutex_wait); if (wait_count=2)P(playground); / 有场地吗？ P(referee); / 有教练吗？ wait_count-; if (wait_count =0) V(student)