## 死鎖 由于任務可以被阻塞，因此一個任務有可能卡在等待另一個任務上，而后者又在等待別的任務，這樣一直下去，知道這個鏈條上的任務又在等待第一個任務釋放鎖。這得到了一個任務之間相互等待的連續循環， 沒有哪個線程能繼續， 這稱之為死鎖[^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]替換為筷子顛倒的哲學家。通過確保第二位哲學家拾起并在右手之前放下左筷子，我們消除了死鎖的可能性。 這只是解決問題的一種方法。你也可以通過防止其他情況之一來解決它。 沒有語言支持可以幫助防止死鎖；你有責任通過精心設計來避免這種情況。對于試圖調試死鎖程序的人來說，這些都不是安慰。當然，避免并發問題的最簡單，最好的方法是永遠不要共享資源-不幸的是，這并不總是可能的。