死鎖
英文名
deadlocks（死鎖）
簡介
由於資源佔用是互斥的，當某個進程提出申請資源後，使得有關進程在無外力協助下，永遠分配不到必需的資源而無法繼續運行，這就產生了一種特殊現象死鎖。 死鎖一種情形，此時執行程序中兩個或多個線程發生永久堵塞（等待），每個線程都在等待被其他線程佔用並堵塞了的資源。例如，如果線程A鎖住了記錄1並等待記錄2，而線程B鎖住了記錄2並等待記錄1，這樣兩個線程就發生了死鎖現象。
相關背景
最好的死鎖例子可能是Kansas立法機構於20世紀早期通過的一個法規，其中說到「當兩列車在十字路口逼近時，它們要完全停下來，且在一列列車開走之前另一列列車不能啟動。」死鎖－－在多道程序設計環境下，多個進程可能競爭一定數量的資源。一個進程申請資源，如果資源不可用，那麼進程進入等待狀態。如果所申請的資源被其他等待進程佔有，那麼該等待進程有可能無法改變狀態。
死鎖的特點
a、互斥至少有一個資源必須處於非共享模式；即一次只有一個進程使用。如果另一個進程申請該資源，那麼申請進程必須延遲直到該資源釋放為止。b、佔有並等待一個進程必須佔有至少一個資源，並等待另一資源，而該資源為其他進程佔有。c、非搶佔資源不能被搶佔；即，只在進程完成其任務之後，才會釋放其資源。 死鎖d、循環等待有一組進程{P0，P1，...，Pn}，P0等待的資源為P1所佔有，P1等待的資源為P2所佔有，Pn-1等待的資源為Pn所佔有，Pn等待的資源為P0所佔有。四個條件必須同時滿足才會出現死鎖，循環等待條件意味着佔有並等待條件，這樣四個條件並不完全獨立。
死鎖預防
出先死鎖有四個必要條件。只要確保至少一個必要條件不成立，就能預防死鎖的發生。 死鎖1、確保佔有並等待條件不會在系統內出現。必須保證：當一個進程申請一個資源時，它不能佔有其他資源。一種可以使用的協議是每個進程在執行前申請並獲得所有資源。另外一種協議允許進程在沒有資源時才可申請資源。2、確保「非搶佔」。為了確保這一條件不成立，可使用如下協議。如果一個進程佔有資源並申請另一個不能立即分配的資源，那麼其現已分配的資源都被搶佔。3、確保「循環等待」確保此條件不成立的方法是對所有資源類型進行完全排序，且要求每個進程按遞增順序來申請資源。
死鎖避免
銀行家算法：1),進程一開始向系統提出最大需求量.2),進程每次提出新的需求(分期貸款)都統計是否超出它事先提出的最大需求量.3),若正常,則判斷該進程所需剩餘剩餘量(包括本次申請)是否超出系統所掌握的剩餘資源量,若不超出,則分配,否則等待.
死鎖檢測
如果一個系統既不採用死鎖預防算法也不採用死鎖避免算法，那麼可能會出現死鎖。在這種環境下，系統應提供：1、一個用來檢查系統狀態從而確定是否出現了死鎖的算法；2、一個用來從死鎖狀態中恢復的算法。方法：a、每種資源類型只有單個實例b、每種資源類型有多個單個實例的算法c、應用檢測算法
死鎖恢復
1、進程終止a、終止所有死鎖進程b、一次只終止一個進程直到取消死鎖循環為止具體操作需注意：1)選擇中斷順序2)進程的優先級3)多少個進程需要計算，需要多長時間4)進程使用的資源5)進程完成還需要多少資源6)多少個進程需要被中斷7)進程是交互的還是批處理2、資源搶佔需要解決的問題：選擇一個犧牲品、回滾、飢餓
資源分配圖
死鎖問題可用稱為系統資源分配圖的有向圖進行更為精確地描述。這種圖有一個節點的集合V和一個邊的集合E組成。節點的集合V分成兩種類型的節點＝{P0，P1，...，Pn}和R＝{R0，R1，...，Rn}。 死鎖如果圖沒有環，那麼系統就沒有進程死鎖。如果圖有環，那麼可能存在死鎖。
