PV操作详解（附详细例题解析和总结） |
您所在的位置：网站首页 › 至少和最多的应用题怎么做 › PV操作详解（附详细例题解析和总结） |
PV操作详解（附详细例题解析和总结）
|
PV操作详解
写在前面：本文主要讲解PV操作与信息量结合，实现进程的同步与互斥 文章目录 PV操作详解1. PV操作定义2. 信号量的应用3. 经典问题分析3.1 课上例题3.2 课下习题分析 4. 补充 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); } }读者－写者问题 问题描述：对共享资源的读写操作，任一时刻“写者 ”最多只允许一个，而“读者”则允许多个。即： “读－写”互斥，“写－写”互斥，“读－读”允许。
分析交互关系： 读者-读者:共享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(readcount==0) v(fmutex); v(rmutex); } }（补充：这种模式下，当系统负载很高时，写者基本无机会，因为读者源源不断地进来，把锁牢牢掌握在自己手中，后续会提到写者优先的写法） 哲学家进餐问题 问题描述： （由Dijkstra首先提出并解决）5个哲学家围绕一 张圆桌而坐，桌子上放着5支筷子，每两个哲学家 之间放一支；哲学家的动作包括思考和进餐，进餐 时需要同时拿起他左边和右边的两支筷子，思考时 则同时将两支筷子放回原处。如何保证哲学家们的 动作有序进行？如：不出现相邻者同时要求进餐； 不出现有人永远拿不到筷子； 交互性分析：筷子与人绑定，并且互斥 Var chopstick : array[0..4] of semaphore; P(chopstick[i]); P(chopstick[(i+1)mod 5]); eating V(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;//作为互斥量保护servings semaphore 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); } }这道题可圈可点的地方在于实现了两个进程的固定顺序：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); }总结：如何实现优先级：让某个进程进行计数，当进程最开始为0时进行P操作申请互斥资源，直到该类进程数为0时才释放资源 4. 补充 AND型信号量机制一般信息量机制 |
【本文地址】
今日新闻 |
推荐新闻 |