2.3_10_哲学家进餐问题

各位同学大家好，在这个小节中我们会介绍进程同步互斥的最后一个经典问题，哲学家进餐问题。

‍

在 1 个圆桌上做了 5 位哲学家，在桌子的中间放了一盆海底捞火锅，这 5 位哲学家各自只需要做两件事情，要么是在思考，要么是在吃饭进餐。

那么当这些哲学家在思考的时候并不会影响其他人，但是在进餐的时候，每一位哲学家需要有两只筷子才可以正常的吃饭，但是这个饭店比较奇怪，5 位哲学家只有 5 只筷子，每个哲学家的左边和右边分别会摆放一只筷子，就像这个样子。那么这些哲学家在吃饭之前需要依次拿起自己左边和右边的两只筷子才可以正常的吃饭，如果其中的一只筷子正在被其他的哲学家使用，那么哲学家吃饭这件事就应该被阻塞，它需要等待。

别的哲学家把自己需要的筷子放下之后，才可以拿起筷子继续吃饭，并且每个哲学家只能拿自己左手边和右手边的这两只筷子，而不能拿其他的这些筷子。所以我们按照之前学习过的那些分析方法来依次分析一下

这个题目当中很显然总共有 5 个哲学家进程，那么每个哲学家和自己相邻的另外的哲学家之间都存在一对互斥关系，他们需要互斥的访问他们之间的这一只筷子，如果这只筷子正在被这个人使用，那么另一个人就暂时不能使用这只筷子，其他的也类似。

这个题目和咱们之前介绍过的那些互斥问题不太一样的是，每一位哲学家他需要拿起两个筷子，也就是两个临界资源，他才可以正常的开始执行吃饭这件事。

而咱们在之前介绍的那些互斥问题当中，每一个进程一般来说都只需要持有一个临界资源就可以顺利的执行了，所以这是哲学家问题和之前的那些互斥问题不同的地方。

由于每一位哲学家都需要同时持有两个临界资源，它才可以顺利的执行吃饭这件事情。所以如果说我们对这些临界资源的分配不当的话，那么这些哲学家进程有可能会发生死锁的现象，所以这也是哲学家问题最主要要解决的问题。怎么避免死锁

那么为了实现对这些临界资源的互斥访问，我们设置了一个互斥信号量数组叫 chopstick，总共有 5 个元素分别对应这 5 支筷子。为了描述方便我们为 5 只筷子一次编上号分别是 0 ~ 4 号，并且也为各个哲学家也依次编上号也是 0 ~ 4 号，总共 5 个哲学家，编号为 i 的哲学家，它的左边的这只筷子的编号刚好也是 i，和它的编号是相同的，而编号为 i 的哲学家，右边的这支筷子的编号可以用 i 加一，然后对 5 取余来表示。

​

那么各个哲学家想要做的事情无非就是两件，要么就是肚子饿的时候吃饭，要么就是在思考，而在吃饭之前他需要先拿起他左右两边的筷子，所以如果按比较直接的想法的话，我们会想到让每个哲学家在吃饭之前依次拿起自己左边和右边的两只筷子，所以在吃饭操作之前，需要对左边这个筷子对应的互斥信号量执行一个 p 操作，还要对右边这只筷子对应的互斥信号量也执行一个 p 操作，也就是申请占用这两个资源。然后吃饭，结束了之后再依次对这两个资源进行释放。

​

但是这么做的问题在于，假如说此时是 5 个哲学家都并发的执行吃饭这件事情，第一个哲学家他在执行了这一句，也就是拿起了他左边的筷子之后，又切换回第二个哲学家也拿起了左边的筷子。接下来又切换回第三个哲学家，也拿起左边的筷子，就像这个样子。

​

但是当每一个哲学家在尝试拿自己的右边这只筷子的时候，会发现自己右边的筷子是已经被别人占用了，所以当执行 p 操作的时候，所有的哲学家进程都会被阻塞，他们会循环的等待自己右边的那个人，放下自己想要的那一只筷子。所以这就出现了之前咱们提到过的死锁的现象，每一个哲学家进程都阻塞的互相等待对方来释放资源，但是对于自己手里的资源来说，他们又不会主动的把资源给放回去，所以这就导致了所有的哲学家进程没有办法往下推进，谁都不能吃饭的现象，所以这种解决方案其实是不合理的。

那么我们要怎么避免刚才所说的这种死锁现象的发生呢？我们可以对哲学家进程施加一些限制的条件，比如说最多只允许 4 个哲学家同时进餐，比如说此时我们只允许 0123 这 4 个哲学家同时进餐，那么即使这些哲学家并发的执行，即使每一个哲学家先都已经拿起了自己身边的一只筷子，但是最后肯定还会有一只筷子是剩余的，这只筷子只要分配给予它相邻的哲学家，那么这个哲学家就可以拥有两只筷子，并且顺利的吃饭，等他吃完饭之后把这两个筷子放下了，那么其他的这些哲学家就依次又可以被激活。所以如果我们用这种方案的话，就可以保证至少会有一个哲学家是可以拿到左右 2 只筷子的，因为筷子总共有 5 只，而我们最多只允许 4 个哲学家同时进餐，所以这种方案是可行的。

第二种方案，我们可以做一个这样的先知，对于奇数号的哲学家来说，他必须先拿自己左边的这只筷子，而对于偶数号的哲学家来说，他必须先拿右边的这双筷子这只筷子。所以如果做了这样的限制，那么 0 和 1 这两个哲学家他们首先会争抢着使用他们之间的这只 0 号筷子，2,3 这两个哲学家又会争抢着使用他们之间的 3 号筷子，而 4 号哲学家需要优先拿 0 号筷子，所以如果我们加上这样的规则的话，我们就可以保证两个相邻的基偶号哲学家，如果他们同时都想吃饭的话，那么他们首先会优先的争抢他们之间的这只筷子，肯定只会有一个哲学家可以得到筷子资源，另一个哲学家如果抢失败，那么他就会在手里没有筷子的情况下就发生阻塞的现象，而不会像刚才一样手里拿了一只筷子同时又发生了阻塞，这样的话我们就可以避免一个进程在占有了一个资源之后，还要等待另一个资源这样的现象，从而我们就能避免死锁现象的发生。

​

这两个方式的代具体的代码实现其实都不复杂，大家可以思考，并且尝试在稿纸上自己写一遍，给 1 个小小的提示。第一个方案要实现最多允许 4 个哲学家同时进餐的话，那么我们可以设置 1 个初始值为 4 的同步信号量，这个信号量怎么使用，大家自己动手尝试一下。而第二个方案的话就更简单了，我们可以在每一个哲学家拿筷子之前先判断一下他们的序号到底是奇数号还是偶数号，然后再根据自己的序号来做下面的一些处理，具体的大家也自己动手尝试一下。

那么除了这两种方式之外，我们还可以用这样的方式来解决思索问题。我们可以规定仅当一个哲学家左右，两只筷子都可以使用的时候，才允许他抓起筷子。

可以设置一个互斥信号量 mutex，然后在哲学家拿筷子之前和拿完筷子之后，分别对互斥信号量执行 p 和 v 两个操作。我们具体来分析一下，如果用这样的代码的话会发生什么情况。

​

假设现在是 0 号哲学家在尝试拿筷子，那么首先他对 mutex 执行 p 操作显然不会被阻塞，于是他可以开始拿第一支筷子，对第一个筷子对应的互斥性和两执行 p 操作，当 p 操作结束之后，他就拥有了这只筷子。此时如果说发生了进程切换，切换回了二号哲学家进程，那么当二号哲学家对 mutex 执行 p 操作的时候，由于 0 号哲学家还没有对 mutex 执行 v 操作，所以二号哲学家在执行 p 操作的时候暂时会被阻塞，一直到 0 号哲学家在切换回 0 号哲学家，并且他顺利的拿到了右边这只筷子，在对这个 mutex 执行 v 操作之后，二号哲学家又可以被激活，然后他就可以顺利的开始执行下面的这两个 p 操作，也就是分别拿起自己左边和右边的两只筷子。

所以通过刚才的分析，我们发现一个哲学家左右两边的筷子都可以用的时候，它是可以一气呵成的一次拿左右两只筷子的。 ‍ 再来看第二种情况，假设刚开始是 0 号哲学家在运行，他打算吃饭，那么他会顺利的通过第一个 p 操作，然后拿起第一只筷子，再拿起第二只筷子，再对 mutex 进行 v 操作，于是他可以顺利的开始吃饭。但是如果在这个时候，一号哲学家他也想吃饭，那么他在 p 操作并不会把它阻塞，他可以顺利的通过。但是当一号哲学家尝试拿左边的这只筷子的时候，它就会发生阻塞，它会卡在这个地方。 而此时如果说在发生调度，二号哲学家开始运行，那么二号哲学家他也想吃饭，于是他会尝试着对 mutex 执行 p 操作，由于之前一号哲学家已经对 mutex 执行了一个 p 操作，并且暂时还没有释放，所以二号哲学家在之后执行 mutex 的 p 操作的时候，他会被阻塞在这个地方。所以如果从这种情况下来看，即使二号哲学家此时左右两边的筷子其实都可以用，但是这个哲学家依然拿不起他两边的筷子，他依然有可能会被阻塞。

​

再来看第三种情况，如果说刚开始是 0 号哲学家拿了左边的筷子和右边的筷子，然后 0 号哲学家开始吃饭，之后 4 号哲学家他也尝试拿左边的筷子，由于左边的筷子暂时没人用，所以他可以拿起来。但是当他在尝试拿右边的这只筷子的时候，由于这只筷子此此时已经被别的哲学家拿走了，所以 4 号哲学家也会发生阻塞。所以如果在这种情况下，4 号哲学家拿了一只筷子的同时在等待别的筷子。

​

因此通过刚才的这两种情况的分析，我们发现虽然咱们的书上说的是只有两边的筷子都可以用时，才允许哲学家拿起筷子，但其实即使一个哲学家两边的筷子，其中某一边不能用的情况下，哲学家依然有可能拿起其中的一只筷子。所以这种说法其实是不太严谨的，比较准确的说法应该是我们用互斥信号量，保证了每个哲学家拿筷子这件事都是互斥的进行的。 ‍ 如果一个哲学家正在拿筷子，不管是拿左边还是拿右边，那么另一个哲学家就不允许同时来做拿筷子这样的操作。如果一个哲学家因为拿筷子的过程中被阻塞了，那么其他的哲学家在尝试拿筷子的时候，他连 p 操作都过不了，就会被阻塞在外面这一层，所以所有的哲学家拿筷子这个操作都是可以互斥的执行的。

那么由于这种特性，我们就可以保证，即使一个哲学家在拿筷子拿到一半的时候被阻塞，也不会有别的哲学家再继续拿筷子。既然哲学家被阻塞了，那么就意味着肯定有另外的哲学家现在手里已经持有了他所需要的筷子。

只有哲学家吃完饭把筷子还到原位之后，哲学家就可以拿起他所需要的另一只筷子，然后顺利的吃饭，然后之后再把他手里的两个筷子再释放，所有的哲学家就可以依次的被激活，这样的话就可以避免循环等待发生死锁的那种现象。因此这种解决方案是可行的，它并不会发生死锁。

​

小结

那么我们在学习哲学家进餐问题的时候，我最关键的地方就是要理解他解决进程死锁的这种思想。再次强调，哲学家进餐问题与咱们之前提到的那些简单的互斥关系不同的是，每一个进程可能都需要同时持有两个或者两个以上的临界资源，才可以顺利的执行吃饭这件事。

所以由于这个特性就会有死锁的隐患，所以如果我们在考试的时候，如果遇到各个进程都需要同时持有两个或者两个以上的临界资源的时候，我们就需要考虑一下是不是可以用哲学家问题的这种思想来避免死锁的发生。我们可以参考三刚才咱们提出的那三种解决思路，来避免死锁的发生。而具体死锁什么时候会发生，死锁的发生又需要一些什么样的条件，在之后的小节当中还会有更详细的说明。

​ ‍