作業系統設計/併發/死鎖
在計算機科學中，死鎖指的是兩個或多個程序都等待另一個程序釋放資源的特定狀態，或者兩個以上程序在迴圈鏈中等待資源（參見必要條件）。死鎖是多處理中常見的問題，在多處理中，許多程序共享一種特定型別的互斥資源，稱為軟體或軟鎖。 用於分時和/或即時市場的計算機通常配備硬體鎖（或硬鎖），它保證獨佔訪問程序，強制序列化。 死鎖特別麻煩，因為沒有通用的解決方案可以避免（軟）死鎖。
這個情況可以用兩個人畫圖來理解，他們之間只有一支鉛筆和一把尺子。 如果一個人拿了鉛筆，另一個人拿了尺子，當拿鉛筆的人需要尺子，而拿尺子的人需要鉛筆才能放棄尺子時，就會發生死鎖。 兩個請求都無法滿足，因此發生了死鎖。
電信對死鎖的描述更強一些：當所有程序都沒有滿足條件可以轉移到另一個狀態（如程序的有限狀態機中所述）並且所有通訊通道都為空時，就會發生死鎖。 第二個條件通常在其他系統中被忽略，但在電信環境及其系統中很重要。
發生死鎖有四個必要條件，被稱為Coffman 條件，源自 E. G. Coffman 在 1971 年的一篇文章中對它們的首次描述。
- 互斥條件：一個資源一次只能被一個程序使用
- 持有並等待條件：已經持有資源的程序可以請求新的資源
- 不可搶佔條件：只有持有資源的程序才能釋放它
- 迴圈等待條件：兩個或多個程序形成一個迴圈鏈，其中每個程序都等待鏈中下一個程序持有的資源
只有在所有 4 個條件都滿足的情況下才會發生死鎖。
迴圈等待預防包括允許程序等待資源，但要確保等待不會形成迴圈。 一種方法可能是為每個資源分配優先順序，並強制程序按優先順序遞增的順序請求資源。 也就是說，如果一個程序持有某些資源，而這些資源中優先順序最高的為m，那麼這個程序就不能請求優先順序小於m的任何資源。 這將強制資源分配遵循特定且非迴圈的排序，因此不會發生迴圈等待。 另一種方法是允許每個程序只持有單個資源； 如果程序請求另一個資源，它必須先釋放它當前持有的資源（或持有並等待）。
在資料庫產品中可能發生死鎖的一個例子如下。 使用資料庫的客戶端應用程式可能需要對錶進行獨佔訪問，為了獲得獨佔訪問，它們會請求鎖。 如果一個客戶端應用程式持有對一個表的鎖，並嘗試獲取另一個已經被第二個客戶端應用程式持有的表的鎖，這可能會導致死鎖，如果第二個應用程式隨後嘗試獲取第一個應用程式持有的鎖。（但是這種特定型別的死鎖很容易防止，例如，使用全部或無資源分配演算法。）
另一個例子可能是文字格式化程式，它接收發送給它的文字進行處理，然後返回結果，但只有在收到“足夠”的文字可以處理後才會返回結果（例如 1KB）。 一個文字編輯器程式被編寫為向格式化程式傳送一些文字，然後等待結果。 在這種情況下，在最後一個文字塊上可能會發生死鎖。 由於格式化程式可能沒有足夠的文字可供處理，它會掛起自己，同時等待額外的文字，而這些文字永遠不會到達，因為文字編輯器已經發送了它所有的文字。 同時，文字編輯器本身也掛起，等待來自格式化程式的最後一個輸出。 這種型別的死鎖有時被稱為死鎖（只在兩個應用程式參與時使用）或飢餓。 然而，這種情況也容易防止，方法是讓文字編輯器用它最後一個（部分）文字塊傳送一個強制訊息（例如 EOF），這將強制格式化程式在格式化後返回最後一個（部分）塊，而不是等待額外的文字。
儘管如此，由於沒有通用的死鎖預防解決方案，因此必須預測每種型別的死鎖並專門防止。 但是，可以在作業系統中實現通用演算法，這樣如果一個或多個應用程式被阻塞，它通常會在（並且在此期間，不允許其他資源，可能需要放棄它已經擁有的資源，回滾到獲取之前狀態）之後終止。
如果在分配資源之前提前獲得有關程序的某些資訊，則可以避免死鎖。 對於每個資源請求，系統都會檢視授予該請求是否意味著系統將進入不安全狀態，這意味著可能導致死鎖的狀態。 然後，系統只授予導致安全狀態的請求。 為了讓系統能夠弄清楚下一個狀態是安全還是不安全，它必須提前知道任何時候所有存在的、可用的和請求的資源的數量和型別。 一個用於死鎖避免的已知演算法是銀行家演算法，它需要提前知道資源使用限制。 然而，對於許多系統來說，在提前知道每個程序會請求什麼是不可能的。 這意味著死鎖避免通常是不可能的。
還有兩種其他演算法，Wait/Die 和 Wound/Wait，它們都使用對稱性破壞技術。 在這兩種演算法中，都存在一個較舊的程序 (O) 和一個較年輕的程序 (Y)。 程序年齡可以透過程序建立時間時的 timestamps 來確定。 timestamps 越小，程序越舊，而 timestamps 越大，程序越年輕。
| Wait/Die | Wound/Wait | |
|---|---|---|
| O 需要 Y 持有的資源 | O 等待 | Y 死亡 |
| Y 需要 O 持有的資源 | Y 死亡 | Y 等待 |
需要注意的是，程序可能處於不安全狀態，但不會導致死鎖。 安全/不安全狀態的概念只指系統是否可能進入死鎖狀態。 例如，如果一個程序請求 A，這將導致不安全狀態，但釋放 B 將防止迴圈等待，那麼該狀態是不安全的，但系統沒有處於死鎖狀態。
可以透過確保以下四個條件中的至少一個發生來防止死鎖
- 消除互斥條件意味著任何程序都不能獨佔訪問資源。 對於無法卷繞的資源，這證明是不可能的，即使對於卷繞的資源，死鎖仍然可能發生。 避免互斥的演算法稱為非阻塞同步演算法。
- 可以透過要求程序在啟動之前（或在執行特定操作集之前）請求它們將需要的全部資源來消除“持有並等待”條件； 這種預先的知識通常難以滿足，而且無論如何都是對資源的低效使用。 另一種方法是要求程序在請求所需全部資源之前釋放所有資源。 這也經常不切實際。（此類演算法，例如序列化令牌，被稱為全有或全無演算法。）
- “不可搶佔”（鎖定）條件也可能難以或無法避免，因為程序必須能夠在一定時間內擁有資源，否則處理結果可能不一致或發生抖動。 然而，無法強制搶佔可能會干擾優先順序演算法。（注意：對“鎖定”資源的搶佔通常意味著回滾，應該避免，因為它在開銷方面非常昂貴。）允許搶佔的演算法包括無鎖和無等待演算法以及樂觀併發控制。
- 迴圈等待條件：避免迴圈等待的演算法包括“在臨界區停用中斷”，以及“使用層次結構來確定資源的部分排序”（在沒有明顯層次結構的情況下，甚至資源的記憶體地址也被用來確定排序）以及 Dijkstra 的解決方案。
通常既不能使用死鎖避免也不能使用死鎖預防。 相反，透過使用跟蹤資源分配和程序狀態並回滾和重啟一個或多個程序以消除死鎖的演算法，使用死鎖檢測和程序重啟。 檢測已經發生的死鎖很容易，因為每個程序鎖定的和/或當前請求的資源都是資源排程器或作業系統已知的。
在死鎖發生之前檢測死鎖的可能性要困難得多，實際上，通常是不可判定的，因為停機問題可以重新表述為死鎖場景。但是，在特定的環境中，使用特定的資源鎖定方式，死鎖檢測可能是可判定的。在一般情況下，無法區分僅僅在等待極不可能發生的事件集發生的演算法和由於死鎖而永遠無法完成的演算法。
當分散式事務或併發控制被使用時，分散式死鎖可能發生在分散式系統中。分散式死鎖可以透過構建全域性等待圖（從死鎖檢測器的本地等待圖）或透過像邊追逐這樣的分散式演算法來檢測。
幽靈死鎖是指在分散式系統中檢測到的死鎖。