# PV操作及经典同步问题 > 首先要确保你自己知道什么是信号量机制，什么是整型信号量下观看以下内容 ## 一、使用信号量实现同步 设S为实现进程P1,P2同步的一个公共信号量，初始值为0。进程P2中语句y要使用进程P1中的语句x的结果所以当x执行完成之后才能执行语句y。实现进程同步的伪代码如下: ```c++ semaphore S = 0 p1() { x; V(S);//S=S+1 表示P1已经完成 相当于唤醒P2 ... ... } p2() { ... ... P(s);//若S>0时，让S=S-1,不是就阻塞，执行下面的语句，相当于等待 y; ... ... } ``` ## 二、 利用信号量实现互斥 设S为实现进程P1,P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值为1(就是可用资源数为1)。实现进程互斥的伪代码如下: ```c++ semaphore S = 1; P1(){ ... P(S); //准备访问，加锁，若 S>0 S = S - 1 进程P1的临界区; V(S); //访问结束，解锁，S = S + 1 } P2(){ ... P(S);//准备访问，加锁，若 S>0 S = S - 1 进程P2的临界区; V(S);//访问结束，解锁，S = S + 1 ... } ``` 这里相当于一把锁，而要是只有一把，你锁住了别人就不能进入，只有当你出来的时候把钥匙给别人，别人才能进入。 ## 三、利用信号量机制实现前驱关系  如图，其中S1,S2,S3,... ...,S6为简单的程序段(只有一条语句)。为了程序段正确的执行，我们应设置若干初始值为"0"的信号量。有多少个关系就设置多少个信号量,设S1->S2,S1->S3，S2->S4,S2->S5,S3->S6,S4->S6,S5->S6分别为a1,a2,b1,b2,c,d,e,伪代码如下: ```c++ semaphone a1=a2=b1=b2=c=d=e=0; S1() { ...; V(a1);V(a2);// a1+=1, a2+=1;相当于解锁 让下一个程序运行 } S2(){ P(a1); // 若a1>0 ,a1-=1,检查S1是否完成 ...; V(b1);V(b2); //S2运行完成，提醒下面的程序 } S3(){ P(a2); // 检查S1运行完成 ...; V(c); // S3运行完成，提醒 } S4(){ P(b1); //检查S2是否完成 ...; V(d);//S4运行完成 } .....以下省略 ``` ## 四、经典同步问题 ### 1. 生产者-消费者问题 **问题描述** > 一组生产者进程和一组消费者进程共享一个初始为空，大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，他只允许一个生产者放入消息，一个消费者从中取出消息 我们来分析一下关系 生产者和消费者对缓冲区互斥访问是一个**互斥关系**，同时生产者和消费者是一个**协作关系**，只有在生产者生产之后，消费者才能消费，他们也是**同步的关系**。 这里只有生产者和消费者**两个进程**，正好两个进程存在着**互斥关系**和**同步关系**，我们就只需要解决互斥和同步的PV操作的位置 信号量的设置，信号量**mutex**作为互斥信号量，用来互斥的访问缓冲区，**初始值为1**；信号量**full**用来记录当前缓冲区中消息的个数**初始值为0**，信号量**empty**用于记录当前缓冲区空的数量，**初始值为n** **伪代码如下** ```c++ semaphore mutex = 1; semaphore empty = n; semaphore full = 0; producer(){ while(1) { produce an item in nextp; P(empty);// 要用到空的缓冲区,empty-=1.要用到什么就P一下 P(mutex);// 互斥加锁 add nextp to buffer; // 行为，加入缓冲区 V(mutex);//互斥解锁 V(full);// 增加缓存区消息个数的记录值,提供什么就V一下,full+=1 } } comsumer(){ while(1) { P(full); //若full不为0，消费掉一个消息 P(mutex);//互斥加锁 remove an item from buffer; (行为) V(mutex); //互斥解锁 V(empty);//空的缓冲区单元加一 comsume the item; // 消费数据 } } ``` ### 2. 读者-写者问题 **问题描述** > 有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据不会产生副作用，但某个写进程和其他进程同时访问共享数据时则会导致数据不一致的错误，因此要求①允许多个读者可以同时对文件执行读操作②只允许一个写者往文件里写信息③任一写者完成写操作之前不允许其他读者或写者工作④写者执行写操作之前，应让已有的读者和写者全部退出 **问题分析** 读者和写者是**互斥关系**，写者和写者也是**互斥关系**，而读者和读者之间**不存在**互斥关系 一个两个进程读者和写者，写者是比较简单，他和任何进程互斥，用**PV操作进程互斥**就行。读者的问题比较复杂，他必须和写者互斥，同时和其他读者同步，这里简单的PV操作就不能解决了，我们再这里用一个**计数器**，用它来判断当前是否有读者读文件，当有读者时，写者无法写文件，此时读者就会一直占用文件，当没有读者时，写者才可以写文件，这里不同的读者对于计数器的访问也是**互斥的** 设置信号量count，记录读者的数量，初始值为0；设置mutex为互斥信号量，初始值为1;设置互斥信号量rw，用于读者和写者的互斥访问，初始值为1 **伪代码如下:** ```c++ int count = 0; //用于记录当前的读者数量 semaphore mutex = 1; semaphore rw = 1; writer(){ while(1){ P(rw); //互斥访问共享文件 writing; //写入数据信息 v(rw); //释放共享文件 } } reader(){ while(1){ P(mutex); //互斥访问count变量 if(count==0) P(rw); //阻止写进程写 count++; //读者计数器+1 V(mutex);//释放互斥变量cout reading; //读取数据 P(mutex); //互斥访问cout变量 count--; if(count == 0) //当最后一个进程完成了读操作 V(rw); //允许写进程写 V(mutex); //释放互斥变量count } } ``` 这个算法是读优先的，如果读用户一直占用文件，写进程就无法写入，会出现“饥饿现象”,我们可以让写进程优先。我们只要加一对PV操作就行。 ### 3. 哲学家进餐问题 **问题描述** > 一张圆桌边上坐着五名哲学家，每两名哲学家之间的桌上摆着一根筷子，两根筷子之间试试一碗米饭。如图所示。哲学家们倾注精力去思考和进餐。哲学家在思考时并不影响他人。只有当哲学家在思考时，并不影响他人。只有当哲学家饥饿时才会试图拿起左右两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。  **问题分析** 5名哲学家和左右邻居对其中间的筷子是互斥关系 显然，这里有五个进程。关键是如何让一名哲学家拿到左右两根筷子而不构成死锁或饥饿现象。解决办法有两个 ： - 让他们同时拿两根筷子 - 对每名哲学家的动作制定规则，避免饥饿或死锁现象 定义互斥信号量数组mutexs[5] = {1,1,1,1,1},用于对5根筷子的互斥访问。哲学家编号按顺序为0~4，哲学家i左边的筷子为i，右边的筷子为(i+1)%5 **初步实现代码如下** ```c++ semaphonre mutexs[5] = {1,1,1,1,1} Pi(){ do{ P(mutexs[i]); //取左边的筷子 P(mutexs[(i+1)%5]); //取右边的筷子 eat; //进餐 V(mutexs[i]);//放回左边的筷子 V(mutexs[(i+1)%5]); //放回右边的筷子 thinking; // 思考 }while(1); } ``` 改算法会出现当所有的哲学家都拿起左边的筷子就会出现循环等待的死锁现象。 为了防止死锁，我们要对哲学家进餐加一些限制，比如至多允许四个哲学家同时进餐；仅当一名哲学家左右两边的筷子均可用时才允许他抓起筷子；对哲学家的顺序进行编号要求奇数号先拿起左边的筷子，然后拿右边的筷子，偶数号相反。 我们使用第一个规则来看一下，设置一个新的信号量记录进餐人数persons,初始值为4 ```c++ semaphonre mutexs[5] = {1,1,1,1,1} semaphonre persons = 4; Pi(){ do{ P(persons); // 占用一个进餐的位置 P(mutexs[i]); //取左边的筷子 P(mutexs[(i+1)%5]); //取右边的筷子 eat; //进餐 V(mutexs[i]);//放回左边的筷子 V(mutexs[(i+1)%5]); //放回右边的筷子 V(persons); //返还进餐的位置 thinking; // 思考 }while(1); } ``` ### 5. 吸烟者问题 **问题描述** > 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉他，但要卷起一根烟，抽烟者需要三种材料： > > - 烟草 > - 纸 > - 胶水 > > 三个抽烟者种，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者无限制的供应这三种材料，供应者每次放两种材料放在桌子上，拥有剩下那种材料的抽烟者卷一根烟并把它抽掉，并给供应者一个信号告诉他已完成，此时供应者会将另外两种材料放到桌子上，如从重复 **问题分析** 供应者和三个抽烟者为同步关系。由于供应者无法满足两个或两个以上的抽烟者，所以三个抽烟者对于抽烟这个动作是互斥的。 显然这里有四个进程，供应者作为生产者向三个抽烟者提供材料。 信号量offer1,offer2,offer3分别表示烟草和纸,烟草和胶水，胶水和纸的组合资源。信号量finish表示互斥的抽烟完成 **代码如下** ```c++ int random; //存储随机数 semaphore offer1 = 0; semaphore offer2 = 0; semaphore offer3 = 0; semaphore finish = 0; process P1(){ while(1){ random = random(); // 任意一个整数随机数 random %= 3; if(random==0) V(offer1); //提供烟草和纸 else if(random == 1) V(offer2); // 提供烟草和胶水 else if(random == 2) V(offer3); //提供胶水和纸 put two items to desktop; P(finish); //等待抽烟完成 } } process P2() { while(1) { P(offer3); 拿纸和胶水，卷成烟，抽掉; V(finish); //通知抽掉了 } } process P3(){ while(1) { P(offer2); 拿烟草和胶水，卷成烟，抽掉; V(finish); } } process P4() { while(1) { P(offer1); 拿烟草和纸，卷成烟，抽掉; V(finish); } } ``` 最后修改：2020 年 08 月 16 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
