死鎖（Deadlock）是指多個進程因競爭資源而造成的一種互相等待對方手里的資源的僵局，其使得各個進程都被阻塞，即若無外力干涉，這些進程都無法向前推進。出現死鎖時，系統必然同時滿足互斥條件、請求和保持條件、不可搶占條件和循環等待這四個條件。一旦死鎖發生，整個系統將停滯或做空操作，操作員難以察覺，從而造成資源浪費。
1965年，荷蘭計算機科學家狄克斯特拉（Edsger Wybe Dijkstra）在研究銀行家算法的過程中，首次提出了死鎖問題，以探索銀行家如何安全地將有限資金借給多個客戶。這一問題隨后引起了廣泛關注，并被眾多科學家進一步研究。1971年，考夫曼（E. G. Coffman）等人在分析了大量死鎖現象后總結了產生死鎖的4個必要條件，并給出了有關多個資源實例的死鎖檢測算法。1973年，霍華德（Howard）提出了死鎖綜合處理的策略，即把系統中的資源分為幾大類，整體上采用資源順序分配法，再根據每類資源的特點選擇最適合的方法。20世紀80年代以后，各種死鎖檢測、死鎖解除、死鎖避免等算法得到了廣泛的應用和研究，涌現了大量的相關研究成果。
并行進程的執行改善了系統資源的利用率，提高了系統的處理能力，但同時也可能產生由于進程資源競爭或推進順序不當，使系統進入死鎖狀態的問題。隨著云計算和分布式系統的發展，死鎖問題日益普遍，有效處理和預防死鎖是確保系統效率和可靠性的核心挑戰。
發展歷程
1965年，荷蘭計算機科學家E.W.Dijkstra在研究銀行家算法時提出了死鎖問題，并提出了單個資源類型的死鎖避免的銀行家算法。銀行家算法（Banker's Algorithm）是Dijkstra為T.H.E操作系統設計的一種避免發生死鎖的算法，該算法通過預測未來可能的資源請求，即在死鎖形成之前進行評估，從而有效避免產生死鎖。Banker's Algorithm需要檢查申請者對各類資源的最大需求量，如果系統現存的各類資源可以滿足它對各類資源的最大需求量，就滿足當前的申請。
1971年，美國科學家Coffman等人在"System Deadlocks"中總結了產生死鎖的4個必要條件：互斥條件、請求和保持條件、不可搶占條件、循環等待條件。Coffman在該文章中還給出了有關多個資源實例的死鎖檢測算法，該算法使用了一些隨時間變化的數據結構，且其檢測算法為需要完成的所有進程探究各種可能的分配序列。
1972年，加拿大科學家霍爾特（R. C. Holt）在其論文 “Some Deadlock Properties of 計算機 Systems"中第一次將死鎖問題用分配圖模型來形式化，并討論了饑餓問題。饑餓和死鎖一樣，是一種由于資源競爭所導致的進程無法向前推進的現象，但餓死現象的進程不僅可能處于等待態，也可能處于運行態或就緒態，且進程等待的是會被釋放但不會分配給自己的資源。
20世紀80年代以后，隨著計算機系統規模的擴大和復雜度的增加，死鎖問題逐漸成為實際系統中需要解決的重要問題。各種死鎖檢測、死鎖解除、死鎖避免等算法得到了廣泛的應用和研究，涌現了大量的相關研究成果。例如，1987年，美國科學家巴赫（M. J. Bach）討論了傳統unix內核如何處理死鎖。1998年，加利福尼亞大學卡勒（D. E. Culler）等教授討論了網絡中死鎖問題的解決方案，其綜合考慮資源管理、協議設計、算法優化等多個方面來避免死鎖的發生，以確保網絡的穩定性和可靠性。2003年，費爾利·迪金森大學教授萊文（G. N. Levine）進一步給出了有關死鎖處理方面的研究，其對死鎖的不同狀態進行了更精確的分類和定義。
進入21世紀以后，隨著云計算、大數據、物聯網等新技術和新應用場景的興起，死鎖問題在分布式系統、并行計算、嵌入式系統等領域變得更加復雜和重要。隨著進程的數量增多，程序的多線程化，持久文件和數據庫服務器更受重視，死鎖問題越來越普遍。新的死鎖檢測算法、預防機制和故障容許度機制在不斷涌現，以應對不斷變化的系統環境和需求。
死鎖的產生原因
系統資源的競爭
在系統中，某些非搶占式資源（例如磁帶機和打印機）的數量有限，無法同時滿足多個進程的需求。這種情況下，進程在運行過程中可能會因為爭奪這些有限資源而陷入死鎖。死鎖通常發生在對非搶占式資源的競爭中，而搶占式資源（如CPU和主存）的競爭則不會導致死鎖。
進程推進順序非法
請求和釋放資源的順序不當，也同樣會導致死鎖。例如，進程分別保持了資源，而 申請資源、申請資源時，兩者都會因為所需資源被占用而阻塞，于是導致死鎖。
產生死鎖的必要條件
產生死鎖必須同時滿足包括互斥條件、請求和保持條件、不可搶占條件和循環等待條件在內的4個條件，只要其中任一條件不成立，死鎖就不會發生。
死鎖的預防
預防死鎖是通過設置某些限制條件，去破壞產生死鎖的四個必要條件中的一個或幾個以避免產生死鎖。在產生死鎖的四個必要條件中，由于互斥條件是非共享設備所必須的，不僅不能改變，還應加以保證，因此死鎖的預防主要是通過破壞請求和保持條件、不可搶占條件以及循環等待條件來實現。
破壞“請求和保持”條件
系統通過保證當一個進程在請求資源時，該進程不能持有不可搶占資源來破壞“請求和保持”條件。該保證可通過以下兩種協議實現。
第一種協議
協議規定進程在開始前一次性申請所有必需資源。如果系統不能滿足全部資源需求，則不分配任何資源，直至所有資源可用。這避免了“請求”和“保持”死鎖條件，簡單、易行且安全，但可能導致資源浪費和進程饑餓。
第二種協議
改進版協議允許進程獲取初期資源后開始運行，隨后根據需要逐步釋放已用資源并請求新資源。例如，一個處理任務的進程先復制數據，完成后釋放資源再請求下一步所需資源。這種方式使進程更快完成任務，提升資源效率，減少了饑餓風險。
破壞“不可搶占”條件
協議規定，當持有特定不可被搶占資源的進程發出新資源請求而未獲滿足時，必須釋放其當前保有的所有資源。后續再根據需要重新申請資源，以此方法破壞“不可搶占”條件。該方法實現起來比較復雜，且可能會造成進程前一階段工作的失效。同時，還可能使進程的執行因為反復地申請和釋放資源致而被無限地推遲，從而延長了進程的周轉時間，增加了系統開銷，降低了系統吞吐量。
破壞“循環等待”條件
通過對所有資源類型進行排序并賦予唯一序號，可以破壞“循環等待”條件。設定一個資源序列，每種資源賦予一個序號。例如，盒式錄音磁帶驅動器、HDD和打印機分別賦予不同的序號，函數按如下形式來定義:
協議規定進程按照資源的序號遞增順序請求資源。進程初始可以請求任意資源Ri，后續僅在條件下，才能請求資源。若需多個相同資源，需一次性請求。例如，進程若需打印機和磁帶機，需先請求序號較低的磁帶機。該策略避免資源分配圖中形成環路，破壞“循環等待”條件。
死鎖的避免
通過在資源的動態分配過程中，用某種方法防止系統進入不安全狀態，從而避免發生死鎖。
系統安全狀態
在死鎖避免方法中，把系統的狀態分為安全狀態和不安全狀態。當系統處于安全狀態時，可避免發生死鎖。反之，系統可能進入死鎖狀態。在該方法中，允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次資源分配的安全性。若此次分配不會導致系統進入不安全狀態，才可將資源分配給進程，否則，令進程等待。
系統安全狀態是指系統能按某種進程推進順序為每個進程分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成，其中被稱為安全序列。如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。
例如，系統中有三個進程，以及12臺磁帶機。各進程對磁帶機的總需求和在時刻已獲得資源如下表所示，
此時存在一個安全序列，使得系統按此進程序列分配資源，可保證每個進程都順利完成。例如先為進程分配給兩臺磁帶機，使之繼續運行，其完成便可釋放出4臺磁帶機，于是剩余可用磁帶機增值5臺；再將5臺磁帶機全部分配給進程，待運行完成后，釋放磁帶機，是剩余可用磁帶機增值10臺；之后進程可獲得足夠的資源以運行，從而使三個進程都能順利完成。因此，在時刻系統是安全的。
銀行家算法
該算法要求每一個新進程在進入系統時，必須申明其在運行過程中可能需要的每種資源類型的最大單元數目，其數目不應超過系統所擁有的資源總量。而當進程請求一組資源時，系統需先確定是否有足夠的資源分配給該進程，并進一步計算若將這些資源分配給該進程，是否會使系統處于不安全狀態。若系統有足夠的資源分配，并不會導致系統進入不安全狀態，則將資源分配給該進程，否則讓進程等待。
為實現銀行家算法，系統中需設置四個數據結構，分別用來描述系統中可利用的資源、所有進程對資源的最大需求、系統中的資源分配，以及所有進程還需要多少資源。
三個矩陣Max、Allocation、Need之間存在關系：
死鎖檢測和解除
當系統中不采取死鎖預防措施和死鎖避免算法時，系統很可能會發生死鎖。此時，系統應提供死鎖檢測算法用于檢測系統狀態，以確定系統中是否發生了死鎖；以及死鎖解除算法用于認定系統中已發生了死鎖時，將系統從死鎖狀態中解脫出來。
死鎖的檢測
死鎖檢測要求系統中必須保存有關資源的請求和分配信息，以及提供一種算法利用這些信息來檢測系統是否已進入死鎖狀態。
資源分配圖
資源分配圖是由一組結點和一組邊所組成的一個對聯 ，可以更精確地描述死鎖,定義和限制如下：
例，在下面的資源分配圖中，用圓形表示進程，用矩形表示資源類型。由于可能有多個實例，矩形內的點的數量表示資源類型的實例數量。
根據資源分配圖的定義，證明了如果分配圖沒有環，那么系統就沒有進程死鎖。
死鎖定理
簡化資源分配圖可檢測系統狀態S是否為死鎖狀態。以下面所示的資源分配圖為例，簡化方法如下：
為死鎖的條件是當且僅當狀態的資源分配圖是不可完全簡化的，該條件為死鎖定理。
死鎖的解除
一旦檢測出死鎖，就應立即采取相應的措施來解除死鎖。死鎖解除的主要方法有資源剝奪法和撤銷進程法。
死鎖的處理策略
處理死鎖的策略有預防死鎖、避免死鎖、死鎖的檢測，各有優缺點如下：
死鎖綜合策略
上述策略中，無論哪種方法都無法適用于各類資源。1973年，Howard對此提出了死鎖綜合處理的策略。其具體步驟為：首先根據資源特性把資源分成幾大類；為了預防資源類之間由于循環等待產生死鎖，整體上采用資源線性排序策略；最后對每類資源根據其特點擇最適合的方法。
死鎖與饑餓
在一個動態系統中，進程會不斷地請求資源和釋放資源，并發執行向前推進。進程申請資源后，申請的資源正在被其他進程使用，則需要等待，當等待時間給進程的推進和響應帶來明顯的影響時，就稱發生進程的饑餓。當饑餓到一定程度的進程所賦予的任務即使完成也不再具有實際意義時，稱該進程被餓死。
死鎖和饑餓的共同點是都是由于資源競爭所導致的進程無法向前推進的現象，但從進程狀態考慮，參與死鎖的進程都處于等待態，而發生餓死現象的進程不僅可能處于等待態，也可能處于運行態或就緒態；另外死鎖進程等待的是永遠不會被釋放的資源，而餓死進程等待的是會被釋放但不會分配給自己的資源。
死鎖處理實例
Windows
在 Windows 操作系統中，針對死鎖問題，有以下具體策略：
Linux
在 Linux 操作系統中，針對死鎖問題，有以下具體策略：
相關概念
可搶占資源與不可搶占資源
計算機系統中的資源按照占用方式，可分為可搶占資源與不可搶占資源。
可重用資源和可消耗資源
計算機系統中的資源按照資源的利用方式，可分為可重用資源和可消耗資源。
①每一個可重用資源中的單元只能分配給一個進程使用，不允許多個進程共享。
②進程在使用資源時需要遵循的使用順序為：申請資源，若進程申請資源失敗，則該進程被阻塞或循環等待；使用資源，即該進程對資源進行操作；釋放資源，該進程使用完資源后自己主動釋放資源。
③系統中每一類可重用資源中的單元數目是相對固定的，進程在運行期間既不能創建也不能刪除它。
①每一類可消耗資源的單元數目在進程運行期間是可以不斷變化的。
②進程在運行過程中可以不斷地創建可消耗資源的單元，將它們放入該資源類的緩沖區中以增加該資源類的單元數目。
③進程在運行過程中可請求若干個可消耗資源，用于進程自己的消耗，不再將它們返回給該資源類中。
未來發展方向
分布式系統中的死鎖檢測
分布式數據庫系統在提供強大計算和存儲能力的同時，由于在各種事務處理過程中大多采用封閉技術，以及大量用戶頻繁訪問分布式數據庫，容易發生同資源異操作的問題，從而導致分布式數據庫死鎖。 若計算機系統無法及時檢測到死鎖，死鎖持續時間不斷延長，最終會導致系統癱瘓。 目前，已有多種針對分布式系統的死鎖檢測算法被提出。如閆盛楠教授于2020年提出的提出一種基于關聯規則挖掘的檢測方法，但是該方法受到空間爆炸影響不能及時更新分布式數據庫死鎖集合，導致死鎖檢測精準度較低。基于靜態分析的死鎖檢測方法的提出有效提高死鎖檢測的精準度，但其在理論和工程上的難點方面還有很多有待研究和改進的地方，如完善分布式數據庫敏感數據分析流程，以提高檢測效率。
新型動態死鎖分析方法
常見的死鎖檢測方法有模型檢測、符號執行、靜態分析和動態分析四種。其中，動態分析通過分析程序運行軌跡及研究鎖授權順序中存在的特定模式，從而進行死鎖檢測，其具有分析效率高、可自動化進行的優點，但同時由于對鎖的授權／釋放操作及其執行場景難以準確刻畫，可能導致誤報現象。因此，如何減少誤報，提高準確率，對于死鎖檢測具有重要意義。
Linux操作系統用戶態死鎖檢測方法
Linux系統提供了基于Lockdep的內核死鎖檢測方法，可以有效檢測內核死鎖問題。目前Lockdep已經移植到用戶態，即liblockdep，但是仍然缺乏對信號量和自旋鎖的死鎖檢測。為此，東南大學陳教授提出了一種Linux用戶態死鎖檢測方法，其基于統一的實現機制，有效解決了Linux操作系統在運行時由于用戶態互斥鎖、信號量、讀寫鎖、自旋鎖等資源爭用而導致的多線程死鎖檢測問題，具有很好的通用性。
參考資料 >
Edsger Wybe Dijkstra.ACM.2024-04-25