这里写目录标题

• 信号量机制
• 用信号量解决同步互斥问题
• • 实现互斥同步前驱问题
  • 生产者消费者问题
  • 多生产者消费者问题
  • 吸烟者问题
  • 读者 - 写者问题
  • 哲学家问题

信号量机制

背景：无论是软件方法与硬件方法都不能实现放权等待，需要有新的机制实现

信号量：跟变量差不多，可以直接用一个int就实现，也可以使用记录型信号量。通常用一个信号量表示系统中某个资源的数量。
一对原语wait，signal。传入信号量，决定这时候临界资源是否可进入，不进入就怎么怎么样。巴拉巴拉。因为原语，整个操作一气呵成，可以实现互斥。
wait signal通常称为P V操作

//记录型信号量
typedef struct {int value;				//资源数struct process * L; 	//等待队列
} semaphore;void wait(semaphore s){s.value --;if (S.value < 0){block(s.l);			//如果资源不够，调用阻塞原语，将其加入阻塞队列}
}void signal (semaphore s){s.value ++;if (S.value <= 0){wakeup(s.L);		//释放资源之后，发现有别的进程需要使用调用wakeup原语}}

用信号量解决同步互斥问题

实现互斥同步前驱问题

• 怎么实现互斥？
  将初始值设为1，表示当前临界资源只有一个，那么就可以实现互斥

semaphore mutex = 1;
p1(){...P(mutex);				//先P操作表示自己想用，如果临界资源不够就会将自己这个进程阻塞critical section;V(mutex);				//V操作表示自己已经用完这个资源，如果有别的资源就会唤醒其他进程
}
p2(){...P(mutex);critical section;V(mutex);
}

• 怎么实现同步
  将mutex初始值为0，前V后P

semaphore s = 0;
p1(){代码xx;xxx;xx;V(s);xx;
}
p2(){xxP(s);			//如果p2先运行到这里，执行P操作，此时信号量为0，就会将自己阻塞xxx;			//那么就可以实现只有p1运行完V操作p2才能运行P操作之后代码xxx;
}

生产者消费者问题

问题背景：有一个缓冲区，一个进程要写另外一个进程要读。
要点：

1. 缓冲区是临界资源，需要互斥访问
2. 缓冲区要有东西读进程才可以读
3. 缓冲区没满写进程才可以写。

semaphore mutex = 1, full = 0, empty = 5;
//mutex表示互斥信号量，full表示当前缓冲区有0块数据，empty表示刚开始有5个大小空间
consumer(){while(1){P(full);		//表示自己需要消耗一个数据P(mutex);		//我需要访问缓冲区拿走;V(mutex);		//我要释放缓冲区访问权限V(empty);		//我拿走了一个数据，就有一个空间被释放出来}
}producer(){while(1){P(empty);		//我要占用一个空位写入数据P(mutex);写数据;V(mutex);V(full);		//}
}

• full、empty信号量的p操作不能与mutex的p操作互换。因为有可能数据不存在，但是此时占用了缓冲区而且不释放缓冲区，这会导致其他进程无法访问缓冲区也就无法放入数据。一个进程占用了缓冲区等待其他进程放入数据，一个进程等待缓冲区再放入数据。产生思索。
• 正确逻辑应该是我先瞅一眼有没有我想要的东西，发现有立马说这个东西我要定了，然后在进行排队使用释放。

多生产者消费者问题

问题：爸爸给女儿苹果吃，妈妈给儿子橘子吃，但妈妈爸爸用的是一个盘子。
要点：用上一个问题类似分析就可以得到

1. 四个人都需要对盘子进行访问，盘子是一个临界资源，需要一个互斥信号量
2. 爸爸需要看有没有空缺的盘子，需要占用一个空缺盘子再放橘子
3. 妈妈一样
4. 女儿要看有没有盘子有没有橘子，有的话拿来吃掉，然后把盘子放回去
5. 儿子一样

semaphore mutex = 1, empty = 5, orange = 0, apple = 0;
//mutex盘子互斥量，empty表示当前有5个盘子是空的，orange表示盘子当前有0个橘子，apple类似
father(){P(empty);P(mutex);放橘子;V(orange);
}
//妈妈类似，把orange改apple
daughter(){P(orange);P(mutex);吃橘子;V(empty)；
}

吸烟者问题

问题：一个提供者，为三个吸烟者提供原材料，三个吸烟者需要用不同的东西抽烟。
要点：如何控制提供者为三个吸烟者提供原材料呢？

1. 采用取模运算可以解决为三个吸烟者提供不同原材料
2. 先提供原材料再吸烟

semaphore s1 = s2 = s3 = 0;
int turn = 0;
provider(){switch (turn):case 0:提供第一个原材料;V(s1);break;case 1:提供第二种原材料V(s2);break;case 2:提供第三种原材料;V(s3);break;turn = (turn + 1) % 3;
}smoker1(){p(s1);抽烟;
}
//其他类似

读者 - 写者问题

问题：允许多个读者可以同时对文件进行读操作。只允许一个写者文件对文件进行写。写文件时候不允许其他进程进行读或者写。写执行写之前保证其余读者和写者全部退出。
要点：

1. 写与写之间要互斥
2. 写与读之间要互斥
3. 读与读之间不互斥

第一个方法：对读者进行计数，如果有计数，说明有进程在读，其他读者可以直接进行读文件，写文件直接阻塞就行。

semaphore rw = 1;
int count = 0;
semaphore mutex = 1;writer(){P(rw);				//写文件表示我想写写文件;V(rw);
}reader(){P(mutex);			//控制读文件互斥访问count变量if (count == 0)		//如果当前是第一个读进程，跟写文件表示我想读P(rw);count ++;V(mutex);读文件;P(mutex);count --;if (count == 0);V(rw);V(mutex);
}

• 这个解决方法核心思想是让读进程打包，通过count变量让所有读进程好像是一起的，只要之前有读进程后面读进程就可以进入文件进行读，绕过对写文件表示我想写。
• 这个方法问题在于降低了写文件的优先级，可能导致写文件饥饿

另外一个方法，在上一个方法之上再添加一个控制信号量，可以实现读写公平。分析可以发现确实可以读写公平，为什么不知道。

semaphore rw = 1;
int count = 0;
semaphore mutex = 1;
semaphore w = 1;		//添加的信号量writer(){P(w);P(rw);				//写文件表示我想写写文件;V(rw);P(w);
}reader(){P(w);P(mutex);			//控制读文件互斥访问count变量if (count == 0)		//如果当前是第一个读进程，跟写文件表示我想读P(rw);count ++;V(mutex);V(w);读文件;P(mutex);count --;if (count == 0);V(rw);V(mutex);
}

哲学家问题

问题：有n个哲学家，但是只有n-1双筷子。哲学家坐在圆桌旁边，左右手各放一个筷子。只有拿起左右两边的筷子才能吃饭。
此问题涉及死锁，可以先看死锁在看这个问题。

解决办法

1. 所有奇数拿左边筷子，偶数拿右边筷子
2. 直接每个哲学家互斥地拿筷子