进程同步互斥相关问题
生产者-消费者问题
- 问题描述
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）
生产者、消费者共享一个初始为空、大小为 n 的缓冲区
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待（缓冲区没满→生产者生产）
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待（缓冲区没空→消费者消费）
缓冲区是临界资源，各进程必须互斥地访问
PV 操作题目分析步骤
- 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系
- 整理思路。根据各进程的操作流程确定 P 、 V 操作的大致顺序
- 设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为 1 ，同步信号量的初始值要看对应资源的初始值是多少）
根据问题描述，可以得出以下关系：
有产品（缓冲区未空） V → full → P 消费者消费
生产者生产 P ← empty ← V 缓冲区没满
semaphore mutex = 1; // 互斥信号量,实现对缓冲区的互斥访问
semaphore empty = n; // 同步信号量,表示空闲缓冲区的数量
semaphore full = 0; // 同步信号量，表示产品的数量，也即非空缓冲区的数量producer() {
while(1) {
生产一个产品;
P(empty); // 消耗一个空闲缓冲区
P(mutex); // 实现互斥是在同一进程中进行一对PV操作
把产品放入缓冲区;
V(mutex);
V(full); // 增加一个产品，实现两进程的同步关系，是在其中一个进程中执行 P 操作，在另一个进程中执行 V 操作
}
}consumer() {
while(1) {
P(full); // 消耗一个产品（非空缓冲区）
P(mutex);
从缓冲区取出一个产品;
V(mutex);
V(empty); // 增加一个空闲缓冲区
使用产品;
}
}注意
实现互斥的 P 操作一定要在实现同步的 P 操作之后，因为：
两者 P 操作调换变成如下情况时，会导致死锁：
producer() {
while(1) {
生产一个产品;
P(empty);
P(mutex);
P(mutex); // ①
P(empty); // ②
把产品放入缓冲区;
V(mutex);
V(full);
}
}consumer() {
while(1) {
P(full);
P(mutex);
P(mutex); // ③
P(full); // ④
从缓冲区取出一个产品;
V(mutex);
V(empty);
使用产品;
}
}若此时缓冲区内已经放满产品，则 empty = 0 ，full = n
则生产者进程执行 ① 使 mutex 变为 0 ，再执行 ② ，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。
消费者进程执行 ③ ，由于 mutex 为 0 ，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。
这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”同样的，若缓冲区中没有产品，即 full = 0 ， empty = n 。
按 ③④① 的顺序执行就会发生死锁。
V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换
- 总结
生产者消费者问题是一个互斥、同步的综合问题
对于初学者来说最难的是发现题目中隐含的两对同步关系
有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费
这是两个不同的“一前一后问题”，因此也需要设置两个同步信号量
实现“一前一后”需要“前 V 后 P ”
易错点：实现互斥和实现同步的两个 P 操作的先后顺序（死锁问题）
多生产者-多消费者问题
- 问题描述
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用 PV 操作实现上述过程。
可以看成以下对应关系：
盘子：大小为 1 ，初始大小为空的缓冲区
爸爸：生产者进程 1
妈妈：生产者进程 2
女儿：消费者进程 1
儿子：消费者进程 2
问题分析
关系分析
- 互斥关系
对缓冲区（盘子）的访问要互斥地进行
- 同步关系
- 父亲将苹果放入盘子后，女儿才能取苹果
- 母亲将橘子放入盘子后，儿子才能取橘子
- 只有盘子为空时，父亲或母亲才能放入水果（“盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果）
整理思路
多生产者-多消费者问题各进程关系 - 设置信号量
同步信号量：
apple 初始为 0
orange 初始为 0
plate 初始为 n ，表示盘子还能存放多少水果
互斥信号量：
- mutex 初始为 1
代码实现
semaphore mutex = 1; // 实现互斥访问盘子（缓冲区）
semaphore apple = 0; // 盘子中有几个苹果
semaphore orange = 0; // 盘子中有几个橘子
semaphore plate = 1; // 盘子中还可以放多少个水果producer1() {
while(1) {
生产一个苹果;
P(plate);
P(mutex);
把苹果放入盘子;
V(mutex);
V(apple);
}
}producer2() {
while(1) {
生产一个橘子;
P(plate);
P(mutex);
把橘子放入盘子;
V(mutex);
V(orange);
}
}consumer1() {
while(1) {
P(apple);
P(mutex);
从盘子中取出一个苹果;
V(mutex);
V(plate);
使用苹果;
}
}consumer2() {
while(1) {
P(orange);
P(mutex);
从盘子中取出一个橘子;
V(mutex);
V(plate);
使用橘子;
}
}可不可以不用互斥信号量（ mutex ）？
- 分析：
刚开始， CP1 、 CP2 进程即使上处理机运行也会被阻塞。如果刚开始是 PP1 进程先上处理机运行，则：PP1 执行 P(plate) ，可以访问盘子 → PP2 执行 P(plate) ，阻塞等待盘子 → PP1 放入苹果后执行 V(apple) ， CP1 进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源（盘子） → CP1 执行 P(apple) ，访问盘子， V(plate) ，等待盘子的 PP2 进程被唤醒 → PP2 进程访问盘子（其他进程暂时都无法进入临界区） → ……
- 结论：
即使不设置专门的互斥变量 mutex ，也不会出现多个进程同时访问盘子的现象
原因在于：本题中的缓冲区大小为 1 ，在任何时刻， apple 、 orange 、 plate 三个同步信号量中最多只有一个是 1 。因此在任何时刻最多只有一个进程的 P 操作不会被阻塞，并顺利地进入临界区
但是如果缓冲区大小大于 1 ，就会出现多个进程同时访问盘子的现象，可能会导致数据覆盖丢失的问题
- 总结
在生产者-消费者问题中，如果缓冲区大小为 1 ，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析
“多生产者-多消费者问题”的关键在于理清复杂的同步关系。在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系
比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：
如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了？
正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”：
盘子变空事件 → 放入水果事件
“盘子变空事件”既可由儿子引发，也可由女儿引发；“放水果事件既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了
读者-写者问题
- 问题描述
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：
① 允许多个读者可以同时对文件执行读操作
② 只允许一个写者往文件中写信息
③ 任一写者在完成写操作之前不允许其他读者或写者工作（如果他同时读写可能导致数据不一致）
④ 写者执行写操作前，应让已有的读者和写者全部退出
为什么允许同时存在多个对同一文件的读操作？
与消费者进程不同，读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可同时访问共享数据
问题分析
关系分析
- 两类进程
- 写进程
- 读进程
- 互斥关系
- 写进程——写进程
- 写进程——读进程
- 读进程与读进程不存在互斥问题
设置信号量
- 互斥信号量， rw 初始为 1
- 互斥信号量， mutex 初始为 1
代码实现
semaphore rw = 1; // 用于实现对共享文件的互斥访问
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1; // 用于保证对 count 变量的互斥访问writer() {
while (1) {
P(rw); // 写进程之前加锁
写文件...
V(rw); // 写进程之后解锁
}
}reader() {
while (1) {
P(mutex); // 各读进程互斥访问 count
if (count == 0) { // 由第一个读进程负责
P(rw); // 读之前“加锁”
}
count++; // 访问文件的读进程数 +1
V(mutex);
读文件...
P(mutex); // 各读进程互斥访问 count
count--; // 访问文件的读进程数 -1
if (count == 0) { // 由最后一个读进程负责
V(rw); // 读完了“解锁”
}
V(mutex);
}
}未设置 mutex 的情况
若两个读进程并发执行，则 count = 0 时两个进程也许都能满足 if 条件，都会执行 P(rw) ，从而使第二个读进程阻塞的情况。
如何解决：出现上述问题的原因在于对 count 变量的检查和赋值无法一气呵成，因此需要设置一个互斥信号量（ mutex ）来保证各读进程对 count 的访问是互斥的
潜在的问题
只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，这种算法中，读进程是优先的
为了解决这个问题需要设置一个写优先信号量（ wrt ），初始值为 1
此时的代码实现为：
semaphore wrt = 1; // 用于实现写优先
semaphore rw = 1; // 用于实现对共享文件的互斥访问
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1; // 用于保证对 count 变量的互斥访问writer() {
while (1) {
P(wrt); // 写进程之前加锁
P(rw); // 写进程之前加锁
写文件...
V(rw); // 写进程之后解锁
V(wrt); // 写进程之后解锁
}
}reader() {
while (1) {
P(wrt); // 读进程之前加锁
P(mutex); // 各读进程互斥访问 count
if (count == 0) { // 由第一个读进程负责
P(rw); // 读之前“加锁”
}
count++; // 访问文件的读进程数 +1
V(mutex);
V(wrt); // 读进程之后解锁
读文件...
P(mutex); // 各读进程互斥访问 count
count--; // 访问文件的读进程数 -1
if (count == 0) { // 由最后一个读进程负责
V(rw); // 读完了“解锁”
}
V(mutex);
}
}思考以下情况：
读进程 1 和读进程 2 同时访问
写进程 1 和写进程 2 同时访问
写进程 1 先访问，读进程 1 再访问
读进程 1 先访问，写进程 1 再访问，最后读进程 2 访问
写进程 1 先访问，读进程 1 再访问，最后写进程 2 访问
（对于互斥信号量的唤醒顺序取决于被阻塞时所处在的对应信号量的阻塞队列中的顺序，先阻塞的先被唤醒，详见记录型信号量）
- 总结
在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；
写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先，来先服务原则
有的书上把这种算法称为“读写公平法”
读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路
其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是 第一个/最后一个 读进程，从而做出不同的处理
另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量
最后，还要认真体会我们是如何解决“写进程饥饿”问题的
绝大多数的考研 PV 操作大题都可以用之前介绍的几种生产者-消费者问题的思想来解决，如果遇到更复杂的问题，可以想想能否用读者写者问题的这几个思想来解决
哲学家进食问题
- 问题描述
一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下子继续思考。
问题分析
- 关系分析
系统中有 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]); // 拿右
吃饭...
V(chopstick[i]); // 放左
V(chopstick[( i + 1 ) % 5]); // 放右
思考...
}
}这种情况下有可能发生：如果 5 个哲学家并发地拿起了自己左手边的筷子，每位哲学家都在循环等待右边的人放下筷子（阻塞），最终发生“死锁”
为了避免这种情况发生，可以采取两种办法：
可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子，具体实现
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]); // 放右
思考...
}
}更准确的说法应该是：各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试全筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了
- 总结
哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患
如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路
更新日志
90dd5-于5a46d-于9a5fd-于