死結

關於尚未發行的電子遊戲，請見「死鎖 (遊戲)」。

「死結」重新導向至此。關於有關繩結上的死結，請見「單結」。

死結（英語：deadlock），又譯為死鎖，電腦科學名詞。當兩個以上的運算單元，雙方都在等待對方停止執行，以取得系統資源，但是沒有一方提前退出時，就稱為死結^[1]。在多工作業系統中，作業系統為了協調不同線程，能否取得系統資源時，為了讓系統正常運作，必須要解決這個問題。另一種相似的情況稱為「活結」。

兩個行程以相反的順序競爭兩個資源。

1. 經過一個行程。
2. 後面的行程需要等待。
3. 當第一個行程鎖定第一個資源而第二個行程鎖定第二個資源時，就會發生死鎖。
4. 可以透過取消並重新啟動第一個行程來解決死鎖

P1、P2兩個process都需要資源才能繼續執行。P1擁有資源R2、還需要額外資源R1才能執行；P2擁有資源R1、還需要額外資源R2才能執行，兩邊都在互相等待而沒有任何一個可執行。

四個行程（藍線）競爭一種資源（灰色圓圈），遵循先右後左的策略。當所有行程同時鎖定資源（黑線）時，就會發生死鎖。可以透過打破對稱性來解決死鎖。

簡介

例如，一個行程p1佔用了顯示器，同時又必須使用印表機，而印表機被行程p2佔用，p2又必須使用顯示器，這樣就形成了死結。 因為p1必須等待p2釋出印表機才能夠完成工作並釋出螢幕，同時p2也必須等待p1釋出顯示器才能完成工作並釋出印表機，形成循環等待的死結。

起因

如果系統中只有一個行程，當然不會產生死結。如果每個行程僅需求一種系統資源，也不會產生死結。不過這只是理想狀態，在現實中是可遇不可求的。

死結的四個條件是：

• 禁止搶佔（no preemption）：系統資源不能被強制從一個行程中退出。

• 持有和等待（hold and wait）：一個行程可以在等待時持有系統資源。

• 互斥（mutual exclusion）：資源只能同時分配給一個行程，無法多個行程共用。

• 循環等待（circular waiting）：一系列行程互相持有其他行程所需要的資源。

死結只有在四個條件同時滿足時發生，預防死結必須至少破壞其中一項。

預防

(A) 兩個行程競爭一種資源，遵循先到先得的策略。 (B) 當兩個行程同時鎖定資源時，就會發生死鎖。 (C) 可以透過破壞鎖的對稱性來解決死鎖。 (D) 可以透過改變鎖的機構對稱性來防止死鎖。

系統也可以嘗試迴避死結。因為在理論上，死結總是可能產生的，所以作業系統嘗試監視所有行程，使其沒有死結。

消除

最簡單的消除死結的辦法是重新啟動系統。更好的辦法是終止一個行程的執行。

同樣也可以把一個或多個行程轉返到先前的某個狀態。如果一個行程被多次轉返，遲遲不能佔用必需的系統資源，可能會導致資源匱乏。

活結

活結（livelock），與死結相似，死結是行程都在等待對方先釋放資源；活結則是行程彼此釋放資源又同時佔用對方釋放的資源。當此情況持續發生時，儘管資源的狀態不斷改變，但每個行程都無法取得所需資源，使得事情沒有任何進展。

範例

假設兩人正好面對面碰上對方：

• 死結：兩人互不相讓，都在等對方先讓開。
• 活結：兩人互相禮讓，卻恰巧站到同一側，再次讓開，又站到同一側，同樣的情況不斷重複下去導致雙方都無法通過。

參見

• 競爭危害

參考文獻

1. Coulouris, George. Distributed Systems Concepts and Design. Pearson. 2012: 716. ISBN 978-0-273-76059-7.