经典同步问题最易理解的解题思路（PV操作/操作系统/408）

信号量是操作系统用来解决并发中的互斥和同步问题的一种方法，具体的原理在此不做赘述。本文将从题目出发一步步的对同步问题（生产者消费者问题，读者写者问题，哲学家进餐问题）进行理解，并将以王道上的一道例题来验证解题思路。此处仅战术pv操作的逻辑，逻辑与程序一致，可以自行对其进行转换。

一、生产者消费者问题

问题描述: 一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待;只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。
（1）首先对各个进程所需要完成的动作进行确认

（2）找到临界资源

此处的临界资源为放入产品的区域，这里用mutex作为其指代。

（3）找出可能导致死锁的原因

此处找原因主要靠经验，可以对每种原因进行记录。在生产者消费者问题中最最常见的便是生产者想放入而没有空间，消费者想消费获得不了资源导致；消费者想消费没有资源，生产者想生产获得不了空间导致的死锁。解决方案为增加full和empty的信号量保证生产者只有空着才能放入，消费者只有有资源才能消费。

二、读者写者问题

问题描述: 有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前，应让已有的读者和写者全部退出。

（1）理解题目，确认各个程序动作

（2）找到临界资源

这里临界资源是读者要读写者要写的东西，定义为rw。

但是注意到这样写并不能保证多个读者进行读，因此需要增加count计数使得读者只有第一个来才需要获取临界资源，最后一个走才释放：

（3）找出可能导致死锁的原因

但是我们可以注意到，读者是可以多个同时运行的，所以此处count依然是临界资源，当多个读者同时认为自己是第一个时会导致多个读者对rw进行p操作。因此要对临界资源增加pv操作：

（4）写者优先的优化

增加信号量w，保证当读者要写的时候不再有读者能读：

 三、哲学家进餐问题

问题描述:一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭，如图2.12所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

 （1）首先确认动作找到临界资源筷子

（2）找到可能导致死锁的问题进行优化

最简单的优化是，当一个人拿筷子时其他人都不能拿。当然还有很多优化方案，比如只能限制i-1个人同时拿，比如奇数哲学家拿左边筷子，偶数哲学家拿右边筷子。

四、 例题

 问题描述：某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中、水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入缸取水仅为1桶水，且不可同时进行。试给出有关从缸取水、入水的算法描述。

（1）确认动作

（2）找到临界资源

这里是桶，井，缸

（3）找到可能导致死锁的原因

这里是生产者消费者问题一样的原因，解决方案也相同：

 五、其他

其他题目可能会有更复杂的运用，比如取号，比如用pv操作决定顺序，这些只要熟悉题目并不复杂。