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

经典P、V操作问题详解lionxcat@一、基本概念1. 信号量struct semaphore{ int value; // 仅且必须附初值一次，初值非负 PCBtype* wait_queue; // 在此信号量上阻塞的进程队列} S; // 信号量实例为S2. P、V操作P(S){ S := S-1; if (S<0) 调用进程自己阻塞自己，等待在S的等待队列末尾;}V(S){ S := S+1; if (S≤0) 从S等待队列头释放一进程就绪在就绪队列尾; 调用进程继续执行;}3. 使用方法(i). P、V操作成队出现，处理互斥时出现在同一进程中；处理同步时出现在不同进程中ii). 同步P先于互斥P调用，V的顺序无关4. 另类P、V操作导致的问题(或信号量的栈实现方法或漏斗法)[习题P174-23]某系统如此定义P、V操作：P(S): S = S-1; 若S＜0，本进程进入S信号量等待队列的末尾；否则，继续执行V(S): S＝S+1; 若S≤0，释放等待队列中末尾的进程，否则继续运行1)上面定义的P、V操作是否合理？有什么问题？(2)现有四个进程P1、P2、P3、P4竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面定义的P、V操作正确解决P1、P2、P3、P4对该互斥资源的使用问题。

答：(1)不合理：先进后出；可能“无限等待”，即等待队列头的进程得不到释放2)思路：令每个信号量上的等待队列中始终只有一个进程解决方案如下：(n个进程)n个进程至多有n-1个等待设置n-1个信号量，每个进程阻塞在不同的信号量上，使每个等待队列至多有一个进程等待用循环模拟队列Semaphore S[n-1]; // S[i]的初值为i+1Procedure_i(){int j;DO_PRE_JOB();for(j=n-2; j>=0; j--)P(S[j]);DO_JOB_IN_CRITICAL_SECTION();for(j=0;j<=n-2;j++)V(S[j]);……}二、经典进程同步问题总述：进程同步问题主要分为以下几类：一（生产者－消费者问题）；二（读者写者问题）；三（哲学家就餐问题）；四（爱睡觉的理发师问题）；五（音乐爱好者问题）；六（船闸问题）；七（红黑客问题）等其中前两类都是用于处理进程之间通信的问题：生产者－消费者问题主要实现进程的消息机制，而读者－写者问题用于实现管道通信哲学家就餐问题是经典的互斥转同步防止死锁的多资源争夺理发师问题适合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; // 无穷缓冲区无须’%n’V(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 ; i

同步：发送进程发送消息数量不限，无消息时接收进程不能取信息，故设置当前消息数量(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) // 把消息存到地址A{P(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_send[m](1))；接收者不能从空缓冲区接收信息(mutex_receive[m](0))互斥：设置指示下一个空缓冲区变量(cur(0))，发送进程互斥访问(mutex_cur(1))；　　　设置buffer_count[m](0)记录某个缓冲区被读过几次，若某个缓冲区被读过n2次，则可以释放，接收者互斥访问buffer_count(mutex_count[m](1))阻塞分析：若接收者试图接收空缓冲区被阻塞在mutex_receive[k]上，则其他要访问同一缓冲区的接收者被堵塞在mutex_count[k]上；若此时发送者向缓冲区k写入信息，则由第一个接收者释放其他接收者　　　若有一发送者被阻塞在mutex_send[cur]上，则其他发送者被阻塞在mutex_cur上void send(){while (true){P(mutex_cur);cur = (cur+1)% m;// 若阻塞则表示cur满P(mutex_send[cur]);写入buffer[cur]; // cur内容等待被读取V(mutex_receive[cur]);V(mutex_cur);}}void receive(){While (true){for (int i=0; i

而后者如果没有东西消费，就会阻塞等待第一类(读者优先)[书P121]：问题：写者在写，则其余写者和读者等待；有读者在。