死鎖概念和產生原因

死鎖是指多個程序迴圈等待彼此佔有的資源而無限期的僵持等待下去的局面。原因是：

系統提供的資源太少了，遠不能滿足併發程序對資源的需求程序推進順序不合適，互相佔有彼此需要的資源，同時請求對方佔有的資源，往往是程式設計不合理死鎖產生的必要條件

需要同時具有以下四個條件：

互斥條件：即某個資源在一段時間內只能由一個程序佔有，不能同時被兩個或兩個以上的程序佔有不可搶佔條件：程序所獲得的資源在未使用完畢之前，資源申請者不能強行的從資源佔有者手中奪取資源，而只能由該資源的佔有者程序自行釋放佔有且等待條件：程序至少已經佔有了一個資源，但又申請了一個新的被其他程序所佔有的資源，此時處於等待狀態迴圈等待條件：若干個程序形成環形鏈，每個都佔用對方申請的下一個資源死鎖的處理策略

為使系統不發生死鎖，必須設法破壞產生死鎖的四個必要條件之一，或者允許死鎖產生，但當死鎖發生時能檢測出思索，並有能力實現恢復。一般有死鎖的預防、死鎖避免、死鎖的檢測與恢復三種方法。(1) 死鎖預防：破壞導致死鎖必要條件中的任意一個就可以預防死鎖。例如，要求使用者申請資源時一次性申請所需要的全部資源，這就破壞了保持和等待條件；將資源分層，得到上一層資源後，才能夠申請下一層資源，它破壞了環路等待條件。預防通常會降低系統的效率。

(2) 死鎖避免：避免是指程序在每次申請資源時判斷這些操作是否安全，例如，使用銀行家演算法。死鎖避免演算法的執行會增加系統的開銷。

(3) 死鎖檢測：死鎖預防和避免都是事前措施，而死鎖的檢測則是判斷系統是否處於死鎖狀態，如果是，則執行死鎖解除策略。

(4) 死鎖解除：這是與死鎖檢測結合使用的，它使用的方式就是剝奪。即將某程序所擁有的資源強行收回，分配給其他的程序。

死鎖預防：打破互斥條件：允許程序同時訪問資源（有些資源就是不可以同時訪問的，無實用價值）打破不可搶佔條件：比如給程序設定優先順序，高優先順序的可以搶佔資源(實現困難，降低系統性能)打破佔有且等待條件：實行資源預分配策略，即程序在執行前一次性的向系統申請它所需要的全部資源(不可預測資源的使用，利用率低，降低併發性)破壞迴圈等待條件：採用這種策略，即把資源事先分類編號，按號分配，使程序在申請，佔用資源時不會形成環路。所有程序對資源的請求必須嚴格按資源序號遞增的順序提出（限制和編號實現困難，增加系統開銷，有些資源暫時不用也需要先申請，增加了程序對資源的佔用時間）死鎖避免

允許程序動態的申請資源，但系統在進行資源分配前，應先計算此次資源分配的安全性。若此次分配不會導致系統進入不安全狀態，則將資源你分配給程序，否則，讓程序等待。所謂安全狀態，是指系統能按某種程序推進順序，為每個程序分配其所需的資源，直至滿足每個程序對資源的最大需求，是每個程序都可以順序的完成。此時成P1P2P3...為安全序列，如果系統無法找到一個安全序列，則稱系統處於不安全狀態。並非所有的不安全狀態都是死鎖狀態，但當系統進入不安全狀態後，便可能進入死鎖狀態；反之，只要系統處於安全狀態，系統便可以避免進入死鎖狀態。銀行家演算法是最著名的死鎖避免演算法。

死鎖的檢測

資源分配圖&&死鎖定理

死鎖解除

1）資源剝奪法。掛起某些思索程序，並搶佔它的資源，將這些資源分配給其他的死鎖程序。但應防止被掛起的程序長時間得不到資源時，而處於資源匱乏的狀態。2）程序撤銷法。強制撤銷一個或一部分程序並剝奪這些程序的資源。撤銷的原則可以按程序的優先順序和撤銷程序代價的高低進行。3）程序回退法。讓一個或多個程序回退到足以迴避死鎖的地步，程序回退時資源釋放資源而不是被剝奪。要求系統保持程序的歷史資訊，設定還原點。

分哪種死鎖，一般在請求資源的時候會遇到鎖，在獲取鎖失敗後之後程序會再次嘗試獲得鎖，直到真正獲取到鎖。這個不斷嘗試的過程可能會變成請求的不斷提交，因為死鎖是無論如何無法獲得鎖的，所以會導致程序反覆嘗試，提交的請求過多，就會佔用CPU很高的資源。