死鎖

死鎖：

定義：

在多道程式環境下，多個程序可能競争一定數量的資源。某個程序申請資源，如果這時資源不可用，那麼該程序進入等待程序。如果所申請的資源被其他等待程序占有，那麼該等待程序有可能再也無法改變其狀态。這種情況稱為死鎖。

條件（同時滿足）：

1，互斥（資源）：資源隻能一個程序使用，其他程序申請隻能等待

2，占有并等待（程序）：一個程序必須占有一個資源并等待另一個資源，而等待的那個資源正在被使用

3，非搶占（資源）：資源不能被搶占，資源隻能在程序完成任務後自動釋放

4，循環等待（程序）：a等待的資源被b占有，b等待的資源被c占有，，，n等待的資源被a占有

處理方法：

一，使用協定以預防或避免死鎖，確定系統不會進出入死鎖狀态：

死鎖預防：確定死鎖成立的至少一個條件不成立，通過限制如何申請資源的方法來預防死鎖

1，互斥：不可解決，有的資源本身就是非共享資源。非共享資源必須要有互斥條件，共享資源不要求互斥通路

2，占有并等待：

1）每個程序執行前申請所有所需資源

2）程序沒有占資源時才能申請

3，非搶占：等待申請的資源時，隐式釋放已搶占資源，若配置設定到了所申請資源，則恢複隐式釋放的資源

4，循環等待：對所有資源類型排序，每個程序隻按資源類型遞增順序申請資源。

缺點：低裝置使用率和吞吐率

死鎖避免：獲得以後如何申請資源的附加資訊，有了每個程序的申請與釋放順序，可決定程序是否因申請而等待。每次申請要求系統考慮現有可用資源，現已配置設定給每個程序的資源和每個程序将來申請與釋放的資源，以決定目前申請是否滿足或必須等待，進而避免死鎖發生的可能性

死鎖避免動态地檢測資源配置設定狀态以確定循環等待條件不可能成立。資源配置設定狀态是由可用資源和已配置設定資源，及程序最大需求決定的

常用的方法：安全狀态，資源配置設定圖算法，銀行家算法

二，檢測恢複：

檢測：死鎖檢測算法：

等待圖：從資源配置設定圖中删除所有資源類型節點，合并适當邊，就可以得到等待圖

當且僅當等待圖中有一個環，系統中存在死鎖。為了檢測死鎖，系統需要維護等待圖，并周期性地調用在圖中進行搜尋的算法

每次請求配置設定不能立即允許時就調用死鎖檢測算法，每次調用都會引起相當大的開銷，另一個不太昂貴的方法就是以一個不太高的頻率調用算法。

恢複：

1）通知操作員死鎖已經發生，人工處理死鎖

2）讓系統從死鎖狀态中自動恢複過來

終止死鎖的方法：

1）終止一個或者多個程序以打破循環等待

2）從一個或者多個死鎖程序那裡搶占一個或者多個資源（1，選擇一個犧牲品程序；2，復原；3，饑餓）

三，直接忽視

系統允許死鎖發生

本文轉自   Taxing祥   51CTO部落格，原文連結:http://blog.51cto.com/12118369/1961421