死鎖
 |
死鎖（英語：deadlock），又譯為死鎖，計算機科學名詞。當兩個以上的運算單元，雙方都在等待對方停止執行，以取得系統資源，但是沒有一方提前退出時，就稱為死結。在多工作業系統中，作業系統為了協調不同行程，能否取得系統資源時，為了讓系統正常運作，必須要解決這個問題。另一種相似的情況稱為「活鎖」。
簡介
例如，一個進程 p1占用了顯示器，同時又必須使用打印機，而打印機被進程p2占用，p2又必須使用顯示器，這樣就形成了死鎖。 因為p1必須等待p2釋出打印機才能夠完成工作並釋出螢幕，同時p2也必須等待p1釋出顯示器才能完成工作並釋出打印機，形成循環等待的死結。
起因
如果系統中只有一個進程，當然不會產生死鎖。如果每個進程僅需求一種系統資源，也不會產生死鎖。不過這只是理想狀態，在現實中是可遇不可求的。
死鎖的四個條件是：
- 禁止搶占（no preemption）：系統資源不能被強制從一個進程中退出。
- 持有和等待（hold and wait）：一個進程可以在等待時持有系統資源。
- 互斥（mutual exclusion）：資源只能同時分配給一個行程，無法多個行程共用。
- 循環等待（circular waiting）：一系列進程互相持有其他進程所需要的資源。
死鎖只有在四個條件同時滿足時發生，預防死鎖必須至少破壞其中一項。
預防
系統也可以嘗試迴避死鎖。因為在理論上，死鎖總是可能產生的，所以操作系統嘗試監視所有進程，使其沒有死鎖。
消除
最簡單的消除死鎖的辦法是重啟系統。更好的辦法是終止一個進程的運行。
同樣也可以把一個或多個進程回滾到先前的某個狀態。如果一個進程被多次回滾，遲遲不能占用必需的系統資源，可能會導致資源匱乏。
活結
活結（livelock），與死結相似，死結是行程都在等待對方先釋放資源；活結則是行程彼此釋放資源又同時占用對方釋放的資源。當此情況持續發生時，儘管資源的狀態不斷改變，但每個行程都無法取得所需資源，使得事情沒有任何進展。
範例
假設兩人正好面對面碰上對方：
- 死結：兩人互不相讓，都在等對方先讓開。
- 活結：兩人互相禮讓，卻恰巧站到同一側，再次讓開，又站到同一側，同樣的情況不斷重複下去導致雙方都無法通過。