进程同步互斥之吸烟者问题，读者写者问题，哲学家进餐问题

1.吸烟者问题

1.问题描述

假设一个系统有三个抽烟者进程和一个供应者进程。
每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。
三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。
供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟)

2.互斥关系

桌子可以抽象为容量为1的缓冲区,要互斥访问。
组合一:纸+胶水
组合二:烟草+胶水
组合三:烟草+纸

3.同步关系

（从事件的角度来分析）:
桌上有组合一$\to$第一个抽烟者取走东西
桌上有组合二$\to$第二个抽烟者取走东西
桌上有组合三$\to$ 第三个抽烟者取走东西
发出完成信号$\to$供应者将下一个组合放到桌上

4.代码实现（轮流让各个吸烟者吸烟）

定义同步信号量和缓冲区：

提供者函数：

吸烟者函数：

在这个问题中，不需要设置专门的互斥信号量。
原因是缓冲区大小为1，同一时刻，四个同步信号量中至多有一个的值为1。

若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的“事件”发生之后的位置。

2.读者写者问题

1.问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
因此要求:
①允许多个读者可以同时对文件执行读操作;
②只允许一个写者往文件中写信息;
③任一写者在完成写操作之前不允许其他读者或写者工作;
④写者执行写操作前，应让已有的读者和写者全部退出。

2.互斥关系

两类进程：写进程、读进程。
互斥关系：写进程―写进程、写进程―读进程。
读进程与读进程不存在互斥问题。

3.代码实现

定义信号量

读者函数：

写者函数：

结论:
在这种算法中，连续进入的多个读者可以同时读文件;
写者和其他进程不能同时访问文件;
写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。
有的书上把这种算法称为“读写公平法”。

1. 读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。
2. 其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。
3. 我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。
4. 另外，对count变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自如果需要实现“一气呵成”，自然应该想到用互斥信号量。

3.哲学家进餐问题

1.问题描述

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

2. 互斥关系

1. 系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2. 这个问题中只有互斥关系，但与之前遇到的问题不同的事，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
3. 信号量设置：定义互斥信号量数组$chopstick[5]=1,1,1,1,1$用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。

3.防止死锁的发生的三种思路

1. 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有中一个可以拿起第一只筷子，另一个会直接阻塞。这避免了占有一支后再等待另一只的情况。
3. 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。更准确的说法应该是:各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞,也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

哲学家进餐问题的关键在于解决进程死锁。

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。