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

P1、P2兩個process都需要資源才能繼續執行。P1擁有資源R2、還需要額外資源R1才能執行;P2擁有資源R1、還需要額外資源R2才能執行,兩邊都在互相等待而沒有任何一個可執行。
四個行程(藍線)競爭一種資源(灰色圓圈),遵循先右後左的策略。當所有行程同時鎖定資源(黑線)時,就會發生死鎖。可以透過打破對稱性來解決死鎖。
兩個行程以相反的順序競爭兩個資源。
  1. 經過一個行程。
  2. 後面的行程需要等待。
  3. 當第一個行程鎖定第一個資源而第二個行程鎖定第二個資源時,就會發生死鎖。
  4. 可以透過取消並重新啟動第一個行程來解決死鎖

簡介

編輯

例如,一個進程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.