二、进程管理（四）经典同步互斥问题

目录

4.1生产者-消费者问题

4.1.1单类生产者-单类消费者问题

4.1.2多类生产者-多类消费者问题

4.1.3吸烟者问题

4.2读者-写者问题

4.3哲学家进餐问题

---

分析进程同步和互斥问题的三步：

1. 关系分析：分析问题中的同步（前驱关系）、互斥关系。 
2. 写出进程：根据问题写出各个进程的P/V操作顺序和必要操作顺序。
3. 信号值设置：确定各个PV操作的信号量名称和值。

4.1生产者-消费者问题

生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。该问题描述了两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。 

4.1.1单类生产者-单类消费者问题

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满的时候生产者才能把消息放入缓冲区，只有当缓冲区不为空时消费者才能从中取出消息。缓冲区是临界资源，不能同时访问。

 问题分析：

关系分析：同步问题：缓冲区有空位→生产者生产。缓冲区有信息→消费者消费。互斥资源：生产者不能同时生产，消费者不能同时消费，生产者和消费者不能同时访问。

写出进程:由于单类生产者和单类消费者使用的是同样的进程，我们有两个进程：

 信号值设置：信号量mutex作为互斥信号量，初始为1；用full表示缓冲区满了的资源的数量，初始为0；用empty表示缓冲区空位资源的数量，初始为n。

• 可以看到我们让临界区尽可能短，而将生成一个产品和使用产品放在临界区外。
• 实现互斥的P操作一定要在实现同步的P操作后面，否则会发生死锁。这点跟前面软件实现互斥的方法之双标志先检查法在进入区先判断标志后设置标志会发生死锁一致。
• 两个V操作可以互换。

4.1.2多类生产者-多类消费者问题

问题描述 

 问题分析

关系分析：同步问题：爷爷生成→女儿消费；奶奶生成→儿子消费。盘子空（孩子们取）→爷爷或奶奶写。互斥资源：只有一个盘子，所以人都不能同时访问。

写出进程：很明显这是4个不同的进程。

信号量设置：互斥信号量设为mutex初始为1，爷爷生成的是apple，奶奶生成的是orange初始都为0。

• 可以看到 “盘子空→爷爷或奶奶生产” 这个事件的同步关系其实是涉及到4个进程，但只需一种PV操作。
• 可以看到当临界区容量为1时不需要额外设置互斥信号量。

4.1.3吸烟者问题

 问题描述

 可以看到其实是“一个生产者多类消费者问题”。

 问题分析：

关系分析：同步问题：生成者生产①号→消费者①；生成者生产②号→消费者②；生成者生产③号→消费者③；任一消费者取走信息→生产者生产。互斥资源：所以人都不能同时访问临界区。

写出进程：可以看到是四个不同的进程。互斥关系由于只有一个临界区没有给出。

信号量设置：

• 可以看到设置信号量的思路不同，PV操作的顺序不同。

4.2读者-写者问题

问题描述：

 问题分析

关系分析：同步问题：文件不空→读者读。文件有空位→写者写。互斥资源：写者不能同时写，写者写时读者不能读，读者可以同时读。

写出进程和信号量设置：可以看出来有两种进程，写者进程和读者进程，同步性用两个PV操作可以解决，互斥性用一个PV操作可以让所有人都不能同时访问临界区，但问题是读者可以读，所以可以设置一个count计数只让第一个读者使用PV操作进行互斥。 同时由前面解决互斥问题的几种方法让我们需要警觉这个计数操作必须是原子性的。

上述解决问题方法如果读者源源不断则会使写进程无法进行，是一种读优先算法。

下面介绍一种“读写公平法”

拓展：此外还有一种写优先算法，4个信号量，两个int count。

4.3哲学家进餐问题

问题描述 

 

问题分析：

关系分析：同步问题：一个哲学家拿起左右手筷子→吃饭。互斥资源：一个筷子没法同时被两个哲学家拿起来

写出进程和信号量设置：可以看到圆桌上每个哲学家都是访问两个临界区，所以有五个进程和五个临界区。如果我们采用一个PV操作来限制其中某一个临界区不能同时被访问。用两个临界区的PV操作来实现同步。如以下操作，会发生死锁现象。

进而我们要对哲学家进程施加一些限制条件。下面给出三种实现方案。

最多允许4名哲学家同时进餐，这样可以保证至少有一个哲学家是可以拿到左右两个筷子的。（破坏循环等待条件，不会出现循环等待链）

 

 要求奇数号哲学家先拿起左边的筷子，然后拿右边的。偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇号和偶号哲学家想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞，避免了占有一支后再等待另一只的情况。（破坏循环等待条件，这种策略避免了循环等待链的出现）

仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子。 （典型的破坏请求并保持条件）

第三条是书上的描述，但跟代码并不符合。

更准确的说法应该是：各哲学家拿筷子这件事必须互斥地执行。这就保证了即使一个哲学家在拿到筷子拿一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。然后等目前正在吃饭的哲学家放下阻塞刚才那个哲学家的筷子后，被阻塞的哲学家就可以获得等待的筷子了。 

如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。