## 死锁 由于任务可以被阻塞，因此一个任务有可能卡在等待另一个任务上，而后者又在等待别的任务，这样一直下去，知道这个链条上的任务又在等待第一个任务释放锁。这得到了一个任务之间相互等待的连续循环， 没有哪个线程能继续， 这称之为死锁[^6] 如果你运行一个程序，而它马上就死锁了， 你可以立即跟踪下去。真正的问题在于，程序看起来工作良好， 但是具有潜在的死锁危险。这时， 死锁可能发生，而事先却没有任何征兆， 所以 `bug` 会潜伏在你的程序例，直到客户发现它出乎意料的发生（以一种几乎肯定是很难重现的方式发生）。因此在编写并发程序的时候，进行仔细的程序设计以防止死锁是关键部分。 埃德斯·迪克斯特拉（`Essger Dijkstra`）发明的“哲学家进餐"问题是经典的死锁例证。基本描述指定了五位哲学家（此处显示的示例允许任何数目）。这些哲学家将花部分时间思考，花部分时间就餐。他们在思考的时候并不需要任何共享资源；但是他们使用的餐具数量有限。在最初的问题描述中，餐具是叉子，需要两个叉子才能从桌子中间的碗里取出意大利面。常见的版本是使用筷子， 显然，每个哲学家都需要两根筷子才能吃饭。 引入了一个困难：作为哲学家，他们的钱很少，所以他们只能买五根筷子（更一般地讲，筷子的数量与哲学家相同）。他们围在桌子周围，每人之间放一根筷子。 当一个哲学家要就餐时，该哲学家必须同时持有左边和右边的筷子。如果任一侧的哲学家都在使用所需的筷子，则我们的哲学家必须等待，直到可得到必须的筷子。 **StickHolder** 类通过将单根筷子保持在大小为1的**BlockingQueue**中来管理它。**BlockingQueue**是一个设计用于在并发程序中安全使用的集合，如果你调用take()并且队列为空，则它将阻塞（等待）。将新元素放入队列后，将释放该块并返回该值： ```java // concurrent/StickHolder.java import java.util.concurrent.*; public class StickHolder { private static class Chopstick { } private Chopstick stick = new Chopstick(); private BlockingQueue<Chopstick> holder = new ArrayBlockingQueue<>(1); public StickHolder() { putDown(); } public void pickUp() { try { holder.take(); // Blocks if unavailable } catch (InterruptedException e) { throw new RuntimeException(e); } } public void putDown() { try { holder.put(stick); } catch (InterruptedException e) { throw new RuntimeException(e); } } } ``` 为简单起见，`Chopstick`(`static`) 实际上不是由 `StickHolder` 生产的，而是在其类中保持私有的。 如果您调用了`pickUp()`，而 `stick` 不可用，那么`pickUp()`将阻塞该 `stick`，直到另一个哲学家调用`putDown()` 将 `stick` 返回。 注意，该类中的所有线程安全都是通过 `BlockingQueue` 实现的。 每个哲学家都是一项任务，他们试图把筷子分别 `pickUp()` 在左手和右手上，这样筷子才能吃东西，然后通过 `putDown()` 放下 `stick`。 ```java // concurrent/Philosopher.java public class Philosopher implements Runnable { private final int seat; private final StickHolder left, right; public Philosopher(int seat, StickHolder left, StickHolder right) { this.seat = seat; this.left = left; this.right = right; } @Override public String toString() { return "P" + seat; } @Override public void run() { while (true) { // System.out.println("Thinking"); // [1] right.pickUp(); left.pickUp(); System.out.println(this + " eating"); right.putDown(); left.putDown(); } } } ``` 没有两个哲学家可以同时成功调用take()同一只筷子。另外，如果一个哲学家已经拿过筷子，那么下一个试图拿起同一根筷子的哲学家将阻塞，等待其被释放。 结果是一个看似无辜的程序陷入了死锁。我在这里使用数组而不是集合，只是因为这种语法更简洁： ```java // concurrent/DiningPhilosophers.java // Hidden deadlock // {ExcludeFromGradle} Gradle has trouble import java.util.*; import java.util.concurrent.*; import onjava.Nap; public class DiningPhilosophers { private StickHolder[] sticks; private Philosopher[] philosophers; public DiningPhilosophers(int n) { sticks = new StickHolder[n]; Arrays.setAll(sticks, i -> new StickHolder()); philosophers = new Philosopher[n]; Arrays.setAll(philosophers, i -> new Philosopher(i, sticks[i], sticks[(i + 1) % n])); // [1] // Fix by reversing stick order for this one: // philosophers[1] = // [2] // new Philosopher(0, sticks[0], sticks[1]); Arrays.stream(philosophers) .forEach(CompletableFuture::runAsync); // [3] } public static void main(String[] args) { // Returns right away: new DiningPhilosophers(5); // [4] // Keeps main() from exiting: new Nap(3, "Shutdown"); } } ``` - 当你停止查看输出时，该程序将死锁。但是，根据你的计算机配置，你可能不会看到死锁。看来这取决于计算机上的内核数[^7]。两个核心不会产生死锁，但两核以上却很容易产生死锁。 - 此行为使该示例更好地说明了死锁，因为你可能正在具有2核的计算机上编写程序（如果确实是导致问题的原因），并且确信该程序可以正常工作，只能启动它将其安装在另一台计算机上时出现死锁。请注意，不能因为你没或不容易看到死锁，这并不意味着此程序不会在2核机器上发生死锁。 该程序仍然有死锁倾向，只是很少发生——可以说是最糟糕的情况，因为问题不容易出现。 - 在 `DiningPhilosophers` 的构造方法中，每个哲学家都获得一个左右筷子的引用。除最后一个哲学家外，都是通过把哲学家放在下一双空闲筷子之间来初始化： - 最后一位哲学家得到了第0根筷子作为他的右筷子，所以圆桌就完成。 - 那是因为最后一位哲学家正坐在第一个哲学家的旁边，而且他们俩都共用零筷子。[1]显示了以n为模数选择的右筷子，将最后一个哲学家绕到第一个哲学家的旁边。 - 现在，所有哲学家都可以尝试吃饭，每个哲学家都在旁边等待哲学家放下筷子。 - 为了让每个哲学家在[3]上运行，调用 `runAsync()`，这意味着DiningPhilosophers的构造函数立即返回到[4]。 - 如果没有任何东西阻止 `main()` 完成，程序就会退出，不会做太多事情。 - `Nap` 对象阻止 `main()` 退出，然后在三秒后强制退出(假设/可能是)死锁程序。 - 在给定的配置中，哲学家几乎不花时间思考。因此，他们在吃东西的时候都争着用筷子，而且往往很快就会陷入僵局。你可以改变这个: 1. 通过增加[4]的值来添加更多哲学家。 2. 在Philosopher.java中取消注释行[1]。 任一种方法都会减少死锁的可能性，这表明编写并发程序并认为它是安全的危险，因为它似乎“在我的机器上运行正常”。你可以轻松地说服自己该程序没有死锁，即使它不是。这个示例相当有趣，因为它演示了看起来可以正确运行，但实际上会可能发生死锁的程序。 要修正死锁问题，你必须明白，当以下四个条件同时满足时，就会发生死锁： 1) 互斥条件。任务使用的资源中至少有一个不能共享的。 这里，一根筷子一次就只能被一个哲学家使用。 2) 至少有一个任务它必须持有一个资源且正在等待获取一个被当前别的任务持有的资源。也就是说，要发生死锁，哲学家必须拿着一根筷子并且等待另一根。 3) 资源不能被任务抢占， 任务必须把资源释放当作普通事件。哲学家很有礼貌，他们不会从其它哲学家那里抢筷子。 4) 必须有循环等待， 这时，一个任务等待其它任务所持有的资源， 后者又在等待另一个任务所持有的资源， 这样一直下去，知道有一个任务在等待第一个任务所持有的资源， 使得大家都被锁住。 在 `DiningPhilosophers.java` 中， 因为每个哲学家都试图先得到右边的 筷子, 然后得到左边的 筷子, 所以发生了循环等待。 因为必须满足所有条件才能导致死锁，所以要阻止死锁的话，只需要破坏其中一个即可。在此程序中，防止死锁的一种简单方法是打破第四个条件。之所以会发生这种情况，是因为每个哲学家都尝试按照特定的顺序拾起自己的筷子：先右后左。因此，每个哲学家都有可能在等待左手的同时握住右手的筷子，从而导致循环等待状态。但是，如果其中一位哲学家尝试首先拿起左筷子，则该哲学家决不会阻止紧邻右方的哲学家拿起筷子，从而排除了循环等待。 在**DiningPhilosophers.java**中，取消注释[1]和其后的一行。这将原来的哲学家[1]替换为筷子颠倒的哲学家。通过确保第二位哲学家拾起并在右手之前放下左筷子，我们消除了死锁的可能性。 这只是解决问题的一种方法。你也可以通过防止其他情况之一来解决它。 没有语言支持可以帮助防止死锁；你有责任通过精心设计来避免这种情况。对于试图调试死锁程序的人来说，这些都不是安慰。当然，避免并发问题的最简单，最好的方法是永远不要共享资源-不幸的是，这并不总是可能的。