PV操作详解（附详细例题解析和总结）

PV操作详解

写在前面：本文主要讲解PV操作与信息量结合，实现进程的同步与互斥

文章目录

1. PV操作定义

信号量是一类特殊的变量，程序对其访问都是原子 操作，且只允许对它进行P(信号变量)和V(信号变量) 操作。

• 二元信号量：取值仅为“0”或“1”，主要用作实现互斥；

• 一般信号量：初值为可用物理资源的总数，用于进程间的协作同步问题

• 一个信号量可能被初始化为一个非负整数.
• semWait 操作（P操作）使信号量减1。若值为负，则执行 semWait的进程被阻塞。否则进程继续执行。
• semSignal操作（V操作）使信号量加1。若值小于或等于零， 则被semWait操作阻塞的进程被解除阻塞

总而言之：P操作负责分配资源，没有资源的时候就等着（进入阻塞队列）。V操作负责释放资源，在阻塞队列不为空的时候唤醒某个进程进入临界区。

2. 信号量的应用

注意进程同步和互斥的区别！

（更正：进程同步最后应该是进行signal操作，而不是wait操作，表格有误）

3. 经典问题分析

3.1 课上例题

• 生产者－消费者问题(the producer-consumer problem）> 问题描述：若干进程通过有限的共享缓冲区交 换数据。其中，“生产者”进程不断写入，而 “消费者”进程不断读出；共享缓冲区共有N个 ；任何时刻只能有一个进程可对共享缓冲区进 行操作。分析交互关系：生产者：共享缓存区有货物且与消费者、其余生产者操作互斥消费者：共享缓存区有空位且与生产者、其余消费者操作互斥共享对象：缓存区semaphore space;//初值为N，缓冲区内的空位数量semaphore product;//初值为0，缓冲区内的产品数量semaphore mutex=1;//用于形成互斥 main(){ Cobegin produce();consumer(); Coend}voidproduce(){while(true){p(space);//关于mutex和space的p顺序，可以颠倒，最后会导致运行速度不一样，//联系java多线程可以理解p(mutex); 进入临界区 v(mutex);v(product);}}voidconsumer(){while(true){p(product);p(mutex); 进入临界区 v(mutex);v(space);}}
• 读者－写者问题> 问题描述：对共享资源的读写操作，任一时刻“写者 ”最多只允许一个，而“读者”则允许多个。即： “读－写”互斥，“写－写”互斥，“读－读”允许。

分析交互关系：

读者-读者:共享Data, 互斥访问readcount

读者-写者:互斥访问Data

写者-写者:互斥访问Data

所以必须建立读写锁和写写锁(这个读写锁特殊在第一个读的时候得设置互斥，之后进入的读进程不必如此，最后一个读进程负责释放互斥)

int readcount=0;//读进程数目 
semaphore rmutex=1;//对read count的互斥
semaphore fmutex=1;//对data访问的互斥 voidwrite(){while(true){p(fmutex);
    进入临界区
    v(fmutex);}}voidread(){while(true){p(rmutex);if(readcount==0)p(fmutex);//需要特别谨慎：在有关共享对象的操作，一定要使用pv操作保证正确性，在必要时应借助一些全局变量来帮助实现pv操作
    readcount++;v(rmutex);
    进入data临界区
    p(rmutex);
    readcount--;if(rmutex==0)v(fmutex);v(rmutex);}}

（补充：这种模式下，当系统负载很高时，写者基本无机会，因为读者源源不断地进来，把锁牢牢掌握在自己手中，后续会提到写者优先的写法）

• 哲学家进餐问题> 问题描述： （由Dijkstra首先提出并解决）5个哲学家围绕一 张圆桌而坐，桌子上放着5支筷子，每两个哲学家 之间放一支；哲学家的动作包括思考和进餐，进餐 时需要同时拿起他左边和右边的两支筷子，思考时 则同时将两支筷子放回原处。如何保证哲学家们的 动作有序进行？如：不出现相邻者同时要求进餐； 不出现有人永远拿不到筷子；交互性分析：筷子与人绑定，并且互斥Var chopstick : array[0..4] of semaphore;P(chopstick[i]);P(chopstick[(i+1)mod 5]);eatingV(chopstick[i]);V(chopstick [(i+1)mod 5]);thinking这道题还有其他的解答：> 至多只允许四个哲学家同时（尝试）进餐,以保证 至少有一个哲学家能够进餐,最终总会释放出他所 使用过的两支筷子,从而可使更多的哲学家进餐。 设置信号量room=4。（破除资源互斥）> >  对筷子进行编号，奇数号先拿左，再拿右；偶数 号相反。（破除循环等待）> >  同时拿起两根筷子，否则不拿起。（破除保持等待）

3.2 课下习题分析

• 三个进程 P1、P2、P3 互斥使用一个包含 N（N>0）个单元的缓冲区。P1 每次用 produce() 生成一个正整数并用 put()送入缓冲区某一个空单元中；P2 每次用 getodd()从该缓冲区中 取出一个奇数并用 countodd()统计奇数个数；P3 每次用 geteven()从该缓冲区中取出一个 偶数并用 counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动， 并说明所定义的信号量的含义。分析交互性：全部都是互斥的，共享资源为缓冲区（注意细分奇数偶数即可）semaphore mutex=1;//为了形成互斥 semaphore odd=0;//奇数计数 semaphore even=0;//偶数计数 semaphore empty=N;//缓冲区计数main() cobegin{p1(){while(true){p(empty);p(mutex);produce();put();v(mutex);if(num%2==1)//生成的正整数为奇数{v(odd);}else{v(even);}}}p2(){while(true){p(odd);p(mutex);getodd();countodd()++;v(empty);v(mutex);}}P3(){while(true){p(even);p(mutex);geteven();counteven()++;v(empty);v(mutex);}}} coend注意书写格式：while-true、cobegin-coend

• 一个野人部落从一个大锅中一起吃炖肉，这个大锅一次可以存放 M 人份的炖肉。当野人 们想吃的时候，如果锅中不空，他们就自助着从大锅中吃肉。如果大锅空了，他们就叫 醒厨师，等待厨师再做一锅肉。 野人线程未同步的代码如下： while (true){ getServingFromPot()； eat() } 厨师线程未同步的代码如下： while (true) { putServingsInPot(M) } 同步的要求是： 当大锅空的时候，野人不能够调用 getServingFromPot() 仅当大锅为空的时候，大厨才能够调用 putServingsInPot() 问题：请写出使用 PV 满足同步要求的完整程序。分析交互关系：野人之间互斥，肉份数不够时，就不能吃厨师仅在锅空的时候被唤醒共享资源：锅内的肉份数、锅的情况（因为锅的情况会作为信息量唤醒厨师）int servings =0;//使用int的原因是一次要增加M个，用信息量显然不合适，不如采用全局变量+信息量保护的模式 semaphore mutex=1;//作为互斥量保护servingssemaphore empty=0;//锅空的信息 semaphore full=0;//锅满的信息 voidcook(){while(true){p(empty);//锅若不空则阻塞 putServingInPot(M);v(full);}}voideat(){while(true){p(mutex);if(servings==0){v(empty);p(full);//同步了！！cook实现以后，eat进程得到消息，就可以修改serving状态了 servings+=M;} serving--;getServingFromPot();v(mutex);}}这道题可圈可点的地方在于实现了两个进程的固定顺序：cook的servein实现后，才能继续进行eat的所有操作。

• 读者写者问题的写者优先算法 : 1）共享读; 2）互斥写、读写互斥; 3）写者优先于读者 （一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）这道题是课上的拓展，但是有个要求：写者优先。也即当存在写者时，阻塞所有的读进程，等待写进程执行完毕时，才能继续进行读分析交互关系：读者-读者：可以多个同时进行读者-写者：读写互斥，同时保证写者优先写者-写者：写写int readcount=0;//读进程数目 int writecount=0;//写进程数目 semaphore rcntmutex=1;//对read count的互斥semaphore wcntmutex=1;//对write count的互斥semaphore queue=1;//展示是否有writer semaphore fmutex=1;//对data访问的互斥 voidwrite(){p(wcntmutex);if(writecount==0){p(queue);} writecount++;v(wcntmutex);p(fmutex); 进入临界区 v(fmutex);p(wcntmutex); writecount--;if(writecount==0)v(queue);v(wcntmutex);}voidread(){p(queue);p(rcntmutex);if(readcount==0)p(fmutex); readcount++;v(rmutex);v(queue); 进入data临界区 p(rcntmutex); readcount--;if(rcntmutex==0)v(fmutex);v(rcntmutex);}总结：如何实现优先级：让某个进程进行计数，当进程最开始为0时进行P操作申请互斥资源，直到该类进程数为0时才释放资源

4. 补充

• AND型信号量机制
• 一般信息量机制