2.3.4 经典同步问题
1.生产者-消费者问题
问题描述：
一组生产者进程和一组消费者进程共享一个初始为空，大小为n的缓冲区
1.只有缓冲区没满的时候，生产者才能将消息放入缓冲区，否则必须等待
2.只有缓冲区不空的时候才能从中取出消息，否则必须等待
3.由于缓冲区是临界资源，它只允许一个生产者放入消息，或者从一个消费者中取出消息
问题分析:
1）关系分析：“1.”生产者（削苹果的人）与消费者（吃苹果的人）是同步关系，当缓冲区（桌子）的资源（苹果）满的时候，只有消费者消费了一个资源（吃了一瓣苹果），生产者才能将产品放在缓冲区中：
所以，当缓冲区满的时候，消费者移走缓冲区资源和生产者将资源放入缓冲区是同步关系（一前一后）
“2.”同上，缓冲区空的时候，生产者将资源放到缓冲区和消费者将资源移出缓冲区是同步关系（一前一后）
“3.”缓冲区是临界资源，往缓冲区内放入/取走产品需要互斥（一般在一个进程中完成）
2）整理思路：生产者每次要生产一个产品（v)，消耗一个缓冲区（p）
消费者每次要消耗一个产品（p），释放一个缓冲区（v）
3）信号量设置：mutex为互斥信号量设为1，full用来记录满的缓冲区的个数设为0，empty用于记录空的缓冲区的个数，记作n。
代码描述：
semaphore mutex=1;
semaphore full=0;
semaphore empty=n;
producer(){
while(1){
produce a series of data; //生产产品
P(empty); //获取一个空闲的缓冲区（第一次写错了）
P(mutex); //与producer进程下的V(mutex)是一对，不能与P(empty)交换位置
add data to buffer; //将生产的产品放入缓冲区
V(mutex);
V(full);
}
}
consumer(){
while(1){
P(full); //获取一个满的缓冲区（第一次写错了）
P(mutex);
remove an item from buffer; //移走缓冲区中的产品
V(mutex);
V(empty); //空闲缓冲区＋1
consume the item; //消费产品
}
}
而两个进程各自的V(mutex）和V（full），V(mutex）和V（empty）操作可以交换
2.多生产者和多消费者问题
问题描述：
桌上有一只盘子，每次只能向其中放入一个水果。
爸爸向盘子中只放苹果，妈妈向盘子中只放橘子，儿子只吃橘子，女儿只吃苹果。
只有盘子为空时，爸爸妈妈才可以向盘子中放入 一个水果。
仅当盘子中有自己需要的水果时，儿子或者女儿才可以从盘子中取出水果。用PV操作实现以上过程
关系分析：
互斥关系：对缓冲区（盘子）的访问要互斥的进行
同步关系：
- 父亲放入苹果和女儿取出苹果为同步关系
- 母亲放入橘子和女儿取出橘子是同步关系
- 盘子为空事件->放入水果事件
（容易忽略的为第3条）
伪代码：
semaphore mutex=1; //互斥信号量
semaphore apple=0; //苹果的同步信号量
semaphore orange=0; //橘子的同步信号量
semaphore plate=0; //盘子的水果有多少的同步信号量
dad(){
while(1){
拿出一个苹果
P(mutex);
放在桌子上
V(mutex);
V(apple);
V(plate);
}
}
mom(){
while(1){
拿出一个橘子
P(mutex);
放在桌子上
V(mutex);
V(orange);
V(plate);
}
}
daughter(){
while(1){
P(plate);
P(apple);
P(mutex);
桌子上拿走一个苹果
V(mutex);
吃掉
}
}
son(){
while(1){
P(plate);
P(orange);
P(mutex);
桌子上拿走一个橘子
V(mutex);
吃掉
}
}
上述的问题中，如果不设置mutex信号量，也可以互斥的访问盘子，但是如果缓冲区为2，则必须设置互斥的访问缓冲区
总结一下，不管缓冲区为多少，尽可能设置mutex记录型信号量
3.吸烟者问题
问题描述：
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）
问题分析：
这个题目本质上也是生产者消费者问题（单个生产者可以生产多个消费品的过程）：
假设：
组合1：卷纸+胶水
组合2：烟草+胶水
组合3：卷纸+烟草
同步关系（事件的相互关系）：
供应者提供组合1->吸烟者1拿走组合1
供应者提供组合2->吸烟者2拿走组合2
供应者提供组合3->吸烟者3拿走组合3
发出完成信号->供应者将下一个组合放到桌上（易忽略）
互斥关系：
对桌子上资源的访问只能互斥的进行
伪代码：
semaphore combination1=0;
semaphore combination2=0;
semaphore combination3=0;
semaphore left=0; //桌子上剩余组合数
semaphore mutex=1;
int i=0;
producer(){
while(1){
if(i==0){
P(mutex);
把组合1放到桌子上
V(mutex);
V(combination1);
}else if(i==1){
P(mutex);
把组合2放到桌子上
V(mutex);
V(combination2);
}else if(i==2){
P(mutex);
把组合3放到桌子上
V(mutex);
V(combination3);
}
i=(i+1)%3;
V(left);
}
}
smoker1(){
while(1){
if(i==0){
P(left);
P(combination1);
P(mutex);
拿走组合1
V(mutex);
}
}
}
smoker2(){
while(1){
if(i==1){
P(left);
P(combination2);
P(mutex);
拿走组合2
v(mutex);
}
}
}
smoker3(){
while(1){
if(i==2){
P(left);
P(combination3);
P(mutex);
拿走组合3
v(mutex);
}
}
}
4.读者写者问题
问题描述：
有读者(reader)和写者(writer)两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
因此要求：
① 允许多个读进程可以同时对文件执行读操作；
② 只允许一个写进程往文件中写信息；
③ 任一写进程在完成写操作之前不允许其它读进程或写进程工作；
④ 写进程执行写操作前，应让已有的读进程和写进程全部退出。
关系分析：
读进程和读进程可以同时进行（最关键的点）
读进程和写进程是互斥的关系
写进程和写进程也是互斥的关系
起始思路：
semaphore rw=0; //表示当前是否有进程在访问共享文件
int count=0; //记录当前有几个读进程在访问文件
writer(){
while(1){
P(rw);
写文件
V(rw);
}
}
reader(){
while(1){
if(count==0){
P(rw);
}
count++;
读文件
count--;
if(count==0){
V(rw);
}
}
}
这时发现一个问题，就是reader中如果第一个两个读进程并发执行，则可能第一个进程执行P(rw)，在count还没有加一的时候，切换到第二个读进程，此时count=0从而，第二个进程访问时出现阻塞的情况
对于这种问题，我们发现他是因为检查和count的赋值不能同时进行
所以想到了一种改进方法：
semaphore mutex=1; //用于保证对count变量的互斥访问
semaphore rw=0; //表示当前是否有进程在访问共享文件
int count=0; //记录当前有几个读进程在访问文件
writer(){
while(1){
P(rw);
写文件
V(rw);
}
}
reader(){
while(1){
P(mutex); //改进的地方
if(count==0){
P(rw);
}
count++;
V(mutex); //改进的地方
读文件
P(mutex); //改进的地方
count--;
if(count==0){
V(rw);
}
V(mutex); //改进的地方
}
}
而上述程序又出现一个问题，即只要count!=0，写进程就一直无法开始写，
容易出现饥饿的现象，解决的办法就是再加一个“写优先 ”：
semaphore w=1; //用于实现“写优先”
semaphore mutex=1; //用于保证对count变量的互斥访问
semaphore rw=0; //表示当前是否有进程在访问共享文件
int count=0; //记录当前有几个读进程在访问文件
writer(){
while(1){
P(w); //修改
P(rw);
写文件
V(rw);
V(w); //修改
}
}
reader(){
while(1){
P(w); //修改
P(mutex);
if(count==0){
P(rw);
}
count++;
V(mutex);
V(w); //修改
读文件
P(mutex); //改进的地方
count--;
if(count==0){
V(rw);
}
V(mutex); //改进的地方
}
}
上面这种方法称为读写公平法，即如果出现
读者1->写者1->读者2
这种情况时，不会再像倒数第二种算法一样读者2优先于写者1执行的情况了
总结：
读者写者问题的思路
1）核心思想就是设置了一个计数器count，用count的值来判断当前进入的值是第一个还是最后一个读进程，从而进行不同的PV操作
2）count变量的检查和赋值不能一气呵成，所以想到了使用互斥信号量
3）认真体会如何解决写进程饥饿的问题的
5.哲学家问题
有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，在圆桌上有5个碗和5只筷子，他们的生活方式是交替地进行思考和进餐。平时，每个哲学家进行思考，饥饿时便试图拿起其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。
起始思路：
semaphore chopstick[5]={1,1,1,1,1};
Pi{ //i号哲学家的进程
while(1){
P(chopstick[i]); //拿左边的筷子
P(chopstick[(i+1)%5]); //拿右边的筷子
吃饭
V(chopstick[i]); //放左边的筷子
V(chopstick[(i+1)%5]); //放右边的筷子
思考
}
}
这种解决办法有弊端，就是当每个哲学家都拿起自己左边的筷子时，每个哲学家都只有一只筷子，无法就餐，每个哲学家都在等待身边的哲学家放下自己手里的筷子，所以出现了死锁的现象
为了防止死锁：
方案一：对哲学家进程施加一定的限制 条件，比如最多允许四个哲学家同时进餐
伪代码：
semaphore chopstick[5]={1,1,1,1,1};
int count=0;
Pi{ //i号哲学家的进程
while(1){
if(count<5){
P(chopstick[i]); //拿左边的筷子
P(chopstick[(i+1)%5]); //拿右边的筷子
吃饭
V(chopstick[i]); //放左边的筷子
V(chopstick[(i+1)%5]); //放右边的筷子
count++;
}
思考
}
}
方案二:要求奇数号哲学家先拿左边的筷子，再拿右边的筷子，与偶数号哲学家正好相反
伪代码：
semaphore chopstick[5]={1,1,1,1,1};
Pi{ //i号哲学家的进程
while(1){
if(i%2!=0){
P(chopstick[i]); //拿左边的筷子
P(chopstick[(i+1)%5]); //拿右边的筷子
吃饭
V(chopstick[i]); //放左边的筷子
V(chopstick[(i+1)%5]); //放右边的筷子
思考
}
if(i%2==0){
P(chopstick[(i+1)%5]); //拿右边的筷子
P(chopstick[i]); //拿左边的筷子
吃饭
V(chopstick[(i+1)%5]); //放右边的筷子
V(chopstick[i]); //放左边的筷子
思考
}
}
}
方案3（代码最简单，思维最复杂）：仅当一个哲学家左右两只筷子都可以使用时，才允许他抓起筷子
方法：互斥的拿筷子，设置一个互斥信号量
源代码：
semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1;
Pi{ //i号哲学家的进程
while(1){
P(mutex);
P(chopstick[i]); //拿左边的筷子
P(chopstick[(i+1)%5]); //拿右边的筷子
V(mutex);
吃饭
V(chopstick[i]); //放左边的筷子
V(chopstick[(i+1)%5]); //放右边的筷子
思考
}
}
2.3.5 管程
1.为什么要引入管程
由于信号量机制存在编写复杂，易出错的情况，
2.管程的定义和基本特征
管程的组成：
1）管程的名称
2）管程内部的数据结构说明
3）对数据结构初始化的语句
4）对数据结构进行操作的一组函数
管程的特殊之处（个人理解）：
1）管程把许多操作都封装起来，对外只提供一个大的函数，就像输入，输出一样
2）每次仅允许一个进程进入管程，从而实现进程互斥