这个问题似乎一般翻译成哲学家就餐问题
我觉得太文邹邹的了，还是把它叫成智者吃饭问题比较好，但是似乎长者吃包子更好呢

这个问题演示了死锁的现象

死锁的情况不难想象，当所有的长者都恰好拿起了左边的筷子，这时每个长者都想去拿右边的筷子，没有一个长者能继续运行下去，于是就卡住了
所有的长者都恰好拿起了右边的筷子也是一种情况

从好的方向去看，至少长者的时间凝固了，你不再需要给他续一秒了

这个问题的其中一种常见的解决方法，大致上是：我们要求一个长者总是先拿右边的筷子，再拿左边的筷子，其它长者则相反

但是我一直不太明白这个解决方法的出发点在哪里，现在我想明白了(也许对有些人来说这是显而易见的，但是每个人总会碰到很多让他不觉得显而易见的问题)

在我给出对这个解决方法的动机的理解之前，我们不妨先直接地证明这个方法的正确性

我们首先给长者按逆时针顺序编号，其中0，1，2，3的长者都是先拿左边的筷子，4号长者会先拿右边的筷子
同样我们把筷子也编号，每个长者左边的筷子和他的编号一样，这样0号和4号长者中间的筷子就是0号筷子，此时第i个长者都想拿起i和i+1的筷子，而第i个筷子能被i-1和i的长者拿起

哲学家就餐

我们注意到0号长者和4号长者因为撇性不同，都要先拿起0号筷子，因此他们总是有一个人是两手空空的（或者两人都是），换句话说：

任何一个时刻，手里拿着筷子的长者数至多为4，因此我们可以这么证明这个方案的正确性：

  • 如果5个筷子都被拿起，由于手持筷子的长者数至多为4，根据鸽笼原理，至少有一个长者拿到了2个筷子，他可以吃包子并放下筷子
  • 如果有筷子未被拿起，那么：
    • 如果0，1，2，3这四个筷子中有未被拿起的，那么它们可以被对应编号的长者拿起
    • 如果0，1，2，3这四个筷子都已经被拿起，只有4未被拿起，那么：
      • 如果3这个筷子是被3号长者拿起，那么他可以拿起4号筷子并吃包子
      • 如果3这个筷子是被2号长者拿起，那么他已经手持2个筷子，可以吃包子了

挺不错的证明吧？不仅思路清晰，而且我们也能看出这个解决方案能解决问题的原因就在于0号和4号长者因为竞争0号筷子，使得他们至少一人为空手，避免了前面提到的那两种死锁情况

如果想得更仔细一些，可以发现其实重要的一点是：上面描述的这两种死锁情况，是原问题（不限制长者拿左右筷子的顺序）中唯二的会出现死锁的情况，原因：

  • 如果有筷子还没被拿起，那么这个筷子两边的长者都可以拿起它
  • 如果所有的筷子都被拿起，那么：
    • 如果有一个长者拿起了两个筷子，那么他可以吃包子，然后放下筷子
    • 如果每个长者都拿起了一个筷子，我们可以断定这就是上面描述的两种情况之一，原因是：
      • 相邻的两个长者肯定拿起了同侧的筷子（否则他们中间的筷子就还没被拿起），因此所有的长者都拿起了同侧的筷子

在证明了死锁情况的唯一性之后，再证明我们的方案的正确性就只需要一句话了，因为0号和4号长者竞争0号筷子，导致至少有一个长者没有拿起筷子，因为不可能进入人手一筷的状态，因此就不会死锁

并且这个问题的另一个解决方案也更容易理解了：如果我们用一个最大值为4的信号量（Semaphore）来限制拿起筷子的长者数，也可以保证不会进入唯一的那种5人都拿起筷子的死锁情况

一开始我以为问题到这里就差不多了，但是昨天我意识到这两种方法都可以用一个共同的方式去解释它们能成功的原因：它们都打破了一个图中存在的有向的环 方法1是将一条边的方向改变，使得有向环失效 方法2则是增加了一个限制：同时最多能存在的边数为4，而这个环的顶点数为5，因此也不能成环

为了说明问题，我需要先把原问题简化：我们要求长者总是先拿左边的筷子，再拿右边的筷子。加上这个约束不会改变问题的最重要的部分：这种情况下，长者们仍然会出现没人左手拿着筷子的死锁情况

接着我们要定义一个有向图的顶点和边 1，每个筷子（锁）都是一个顶点 2，每个长者（线程）在运行时，如果会出现先拿起筷子A，再拿起筷子B的情况，那么我们就新增一条A->B的边

这样这个图就是一个5个顶点的有向环，而这个有向环的存在就代表了一个死锁：每个线程获取这个环上的一个顶点的时候，都想要沿着边去获取下一个锁，但是下一个锁都被另一个线程持有