#操作系统
系统中有一组生产者进程和一组消费者进程（可能是多个），生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）生产者、消费者共享一个初始为空、大小为n的缓冲区。
★要求：
- 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
- 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
- 缓冲区是临界资源，各进程必须互斥地访问。
PV操作题目分析步骤：
- 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
- 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
- 设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）
在这样的环境下，设置信号量如下：
semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0; // 同步信号量，表示产品的数量，也即非空缓冲区的数量信号量同步机制：
// 占有信号量资源 --- wait
P(semaphore s) {
while(s == 0); // 忙等
s--;
}
// 释放信号量资源 --- signal
V(semaphore s) {
s++;
}生产者：
// 生产者
producer ()
{
while(true) {
produce(); // 生产一个产品;
P(empty); // 占有一个空闲缓冲区资源(空闲缓冲区 -1)
P(mutex); // 加锁
buffer_in_put(); // 把产品放入缓冲区;
V(mutex); // 解锁
V(full); // 释放非缓冲区资源(非空闲缓冲区 +1)
}
}消费者：
consumer ()
{
while(true) {
P(full); // 占据一个非缓冲区资源（非空闲缓冲区 -1）
P(mutex); // 加锁
buffer_out_put(); //从缓冲区取出一个产品;
V(mutex); // 解锁
V(empty); // 释放一个空闲缓冲区资源(空闲缓冲区 +1)
consume(); // 使用产品;
}
}站在空间的角度，空间被占用和不被占用是两种对立的状态，一个缓冲区，空闲资源和非空闲资源也是描述这个缓冲区两个对立的属性，虽然两者相关联，但是，对于生产者而言，每生产一个，就是实际上在占有一个空闲空间，释放一个非空空间（有点难理解，释放非空空间就是满空间资源数被归还+1），对于消费者恰恰相反。无法理解非空空间，不妨站在阴阳黑白的角度，思考下空间的对立的实体。实体（embody）和空间（space）相互对立，每个空间的资源减少对应实体资源的增加，而生产者非缓冲区资源的释放，就意味着实体（embody）资源的释放。
生产者消费者问题是一个互斥、同步的综合问题。 对于初学者来说最难的是发现题目中隐含的两对同步关系。 有时候是消费者需要等待生产者生产（空缓冲区无法消费），有时候是生产者要等待消费者消费（满缓冲区无法生产），因此，这是不是一个简单的前后依赖关系，而是两个不同的“一前一后问题”，因此也需要设置两个同步信号量。
是否可以改变同一个进程的P、V操作顺序，例如将：
P(empty); // 占有一个空闲缓冲区资源和
P(mutex); // 加锁对调，变成：
// 生产者
producer ()
{
while(true) {
produce(); // 生产一个产品;
P(mutex); // 先加锁 ----- P1
P(empty); // 再占有一个空闲缓冲区资源 ----- P2
buffer_in_put(); // 把产品放入缓冲区;
V(mutex); // 解锁
V(full); // 释放非空闲缓冲区资源（非缓冲区 +1）
}
}
// 消费者
consumer ()
{
while(true) {
P(mutex); // 加锁 ----- P3
P(full); // 占据一个非缓冲区资源（非缓冲区+1） ----- P4
buffer_out_put(); //从缓冲区取出一个产品;
V(mutex); // 解锁
V(empty); // 释放一个空闲缓冲区资源
consume(); // 使用产品;
}
}是否会有其他问题？
若此时缓冲区内已经放满产品，则 empty = 0，full = n。
- 生产者进程执行 P1，使mutex变为0，
- 再执行 P2，由于已没有空闲缓冲区，因此生产者被阻塞。
- 由于生产者阻塞，循环结束，因此切换回消费者进程。消费者进程执行P3，
- 由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。
- 这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。
- 同样的，若缓冲区中没有产品，即full=0，empty=n。
- 按P3、P4、P1的顺序执行就会发生死锁。
因此，实现互斥的P操作一定要在实现同步的P操作之后。但是，V操作不会导致进程阻塞，因此两个V操作顺序可以交换。
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。 用P - V操作实现上述过程。
“多生产者-多消费者”问题中的“多”，并非是指多个，而是指的是多类。
- 互斥关系：（mutex = 1）对缓冲区（盘子）的访问要互斥地进行。
- 同步关系：（一前一后）：
- 父亲将苹果放入盘子后，女儿才能取苹果
- 母亲将橘子放入盘子后，儿子才能取橘子
- 只有盘子为空时，父亲或母亲才能放入水果
“盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果。
semaphore mutex = 1; // 实现互斥访问盘子（缓冲区）
semaphore apple = 0; // 盘子中有几个苹果
semaphore orange = 0; // 盘子中有几个橘子
semaphore plate = 1; // 盘子中还可以放多少个水果父亲进程：
dad() {
while(1) {
准备一个苹果;
P(plate); // 占有盘子资源
P(mutex);
把苹果放入盘子;
V(mutex);
V(apple); // 释放苹果资源，苹果资源 +1
}
}母亲进程：
mom() {
while(1) {
准备一个橘子;
P(plate); // 占有盘子资源
P(mutex);
把橘子放入盘子;
V(mutex);
V(orange); // 释放橙子资源，橙子资源 +1
}
}女儿进程：
daughter() {
while(1) {
P(apple); // 占有苹果资源（消费）
P(mutex);
从盘中取出苹果;
V(mutex);
V(plate); // 释放盘子资源
吃掉苹果;
}
}儿子进程：
son() {
while(1){
P(orange); // 占有橙子资源（消费）
P(mutex);
从盘中取出橘子;
V(mutex);
V(plate); // 释放盘子资源
吃掉橘子;
}
}当缓冲区大小为1的时候，并不需要互斥信号量。详细的过程如下：如果刚开始是父亲进程先上处理机运行，则步骤顺序如下：
- 父亲
P(plate)，可以访问盘子 - 母亲
P(plate)，发生阻塞等待（因为plate被占用，一直陷于循环中，无法再影响临界资源被影响） - 父亲放入苹果
V(apple)，女儿进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源（盘子） - 女儿
P(apple)，访问盘子，V(plate)，等待盘子的母亲进程被唤醒 - 母亲进程访问盘子（其他进程暂时都无法进入临界区）
当缓冲区大小不为1的时候，如果不采用mutex互斥信号量，会发生这样的情况。
- 父亲
P(plate)，可以访问盘子 - 母亲
P(plate)，可以访问盘子 - 父亲在往盘子里放苹果，同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。
因此，如果缓冲区大小大于1，就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区。
假设一个系统有三个抽烟者进程和一个供应者进程。 每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。
本质上这题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”。
- 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
- 整理思路。根据各进程的操作流程确定P、V操作的大致顺序
- 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）。
桌子可以抽象为容量为1的缓冲区，要互斥访问。
semaphore offer1 = 0; // 桌上组合一的数量
semaphore offer2 = 0; // 桌上组合二的数量
semaphore offer3 = 0; // 桌上组合三的数量
semaphore finish = 0; // 抽烟是否完成
int i = 0; // 用于实现“三个抽烟者轮流抽烟”三位吸烟者
smoker1 () {
while(1) {
P(offer1); // 占有组合一资源 (消费)
// 从桌上拿走组合一；卷烟；抽掉；
take_offer1();
roll();
smoke();
V(finish); // 释放资源，抽烟完成
}
}smoker2 () {
while(1) {
P(offer2); // 占有组合二资源 (消费)
// 从桌上拿走组合二；卷烟；抽掉；
take_offer2();
roll();
smoke();
V(finish); // 释放资源，抽烟完成
}
}smoker3 () {
while(1) {
P(offer3); // 占有组合三资源 (消费)
// 从桌上拿走组合三；卷烟；抽掉；
take_offer3();
roll();
smoke();
V(finish); // 释放资源，抽烟完成
}
}对于提供者而言：
provider () {
while(1) {
if(i == 0) {
// 将组合一放桌上;
provide_offer1();
V(offer1);
} else if(i == 1){
// 将组合二放桌上;
provide_offer2();
V(offer2);
} else if(i == 2){
// 将组合三放桌上;
provide_offer3();
V(offer3);
}
i = (i + 1) % 3;
P(finish);
}
}值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三，注意体会我们是如何用一个整型变量 i 实现这个“轮流”过程的。
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
因此要求：
- 允许多个读者可以同时对文件执行读操作；
- 只允许一个写者往文件中写信息；
- 任一写者在完成写操作之前不允许其他读者或写者工作；
- 写者执行写操作前，应让已有的读者和写者全部退出。
- 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系；
- 整理思路。根据各进程的操作流程确定P、V操作的大致顺序；
- 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1， 同步信号量的初始值要看对应资源的初始值是多少）。
semaphore rw = 1; // 用于实现对共享文件的互斥访问
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1;// 用于保证对count变量的互斥访问
semaphore w = 1; //用于实现“写优先”读者：
writer() {
while(1) {
P(w);
P(rw); // 写之前“加锁”
// 写文件
Write();
V(rw); // 写完了“解锁”
V(w);
}
}写者：
reader() {
while(1) {
P(w);
P(mutex); // 各读进程互斥访问count
if (count == 0) // 由第一个读进程负责
{
P(rw); // 读之前“加锁”
}
count++; // 访问文件的读进程数+1
V(mutex);
V(w);
// 读文件
Read();
P(mutex); // 各读进程互斥访问count
count--; // 访问文件的读进程数-1
if (count == 0) // 由最后一个读进程负责
{
V(rw); // 读完了“解锁”
}
V(mutex);
}
}count这个变量的值，保证仅有第一个读进程需要对文件加锁，最后一个读进程对文件解锁。因此，可以保证多个读进程同时对文件进行读取。(这样，所有的读进程都没有了，才可以进行写操作)- 为什么需要
mutex这个变量，因为对count的访问，也是需要并发执行，防止覆盖改写的问题。 - 只要有读进程还在读，那么写进程就必须阻塞等待，会不会产生“饿死”的现象？
- 使用
w这个信号量，用于实现“写优先”； - 写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。
- 使用
哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌上有五碗意大利面，每位哲学家之间各有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和五根筷子而不是意大利面和餐叉来描述，因为吃米饭必须用两根筷子。
这个问题不考虑意大利面有多少，也不考虑哲学家的胃有多大。假设两者都是无限大。
- 关系分析。 系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
- 整理思路。 这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
- 信号量设置。
定义互斥信号量数组
chopstick[5]={1, 1, 1, 1, 1}，用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i + 1) % 5。
按照正常场景，每个哲学家吃饭的时候先后拿起左右两支的筷子的时候。
semaphore chopstick[5] = {1, 1, 1, 1, 1};
Pi() { // i号哲学家的进程
while(1) {
P(chopstick[i]); // 拿左
P(chopstick[(i + 1) % 5]); // 拿右
// 吃饭
eat();
V(chopstick[i]); // 放左
V(chopstick[(i + 1) % 5]); // 放右
// 思考
think();
}
}每个哲学家吃饭前依次拿起左、右两支筷子，如果5个哲学家并发地拿起了自己左手边的筷子，那么每位哲学家循环等待右边的人放下筷子（阻塞）。这样就发生了 “死锁”。
方法：
- 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
- 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
- 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。
实现过程在原有的基础上，需要进行修改：
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex; // 互斥地取筷子
Pi() { // i号哲学家的进程
while(1) {
P(mutex);
P(chopstick[i]); // 拿左
P(chopstick[(i + 1) % 5]); // 拿右
V(mutex);
// 吃饭
eat();
V(chopstick[i]); // 放左
V(chopstick[(i + 1) % 5]); // 放右
// 思考
think();
}
}mutex这个变量，保证了各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。