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}void produce(){ while(true){ p(space);//关于mutex和space的p顺序，可以颠倒，最后会导致运行速度不一样， //联系java多线程可以理解 p(mutex); 进入临界区 v(mutex); v(product); }}void consumer(){ while(true){ p(product); p(mutex); 进入临界区 v(mutex); v(space); }}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
-
读者－写者问题
问题描述：对共享资源的读写操作，任一时刻“写者 ”最多只允许一个，而“读者”则允许多个。即： “读－写”互斥，“写－写”互斥，“读－读”允许。
分析交互关系：
读者-读者:共享Data, 互斥访问readcount
读者-写者:互斥访问Data
写者-写者:互斥访问Data
所以必须建立读写锁和写写锁(这个读写锁特殊在第一个读的时候得设置互斥，之后进入的读进程不必如此，最后一个读进程负责释放互斥)
int readcount=0;//读进程数目 semaphore rmutex=1;//对read count的互斥semaphore fmutex=1;//对data访问的互斥 void write(){ while(true){ p(fmutex); 进入临界区 v(fmutex); }}void read(){ 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); }}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
（补充：这种模式下，当系统负载很高时，写者基本无机会，因为读者源源不断地进来，把锁牢牢掌握在自己手中，后续会提到写者优先的写法）
-
哲学家进餐问题
问题描述： （由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- 1
- 2
- 3
- 4
- 5
- 6
- 7
这道题还有其他的解答：
至多只允许四个哲学家同时（尝试）进餐,以保证 至少有一个哲学家能够进餐,最终总会释放出他所 使用过的两支筷子,从而可使更多的哲学家进餐。 设置信号量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- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
注意书写格式：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; //锅满的信息 void cook(){ while(true){ p(empty);//锅若不空则阻塞 putServingInPot(M); v(full); }}void eat(){ while(true){ p(mutex); if(servings==0){ v(empty); p(full);//同步了！！cook实现以后，eat进程得到消息，就可以修改serving状态了 servings+=M; } serving--; getServingFromPot(); v(mutex); }}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
这道题可圈可点的地方在于实现了两个进程的固定顺序：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访问的互斥 void write(){ p(wcntmutex); if(writecount==0){ p(queue); } writecount++; v(wcntmutex); p(fmutex); 进入临界区 v(fmutex); p(wcntmutex); writecount--; if(writecount==0) v(queue); v(wcntmutex);}void read(){ 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);}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
总结：如何实现优先级：让某个进程进行计数，当进程最开始为0时进行P操作申请互斥资源，直到该类进程数为0时才释放资源
4. 补充
- AND型信号量机制
- 一般信息量机制