產生死鎖的原因

當進程需要以獨占的方式訪問資源時，可能會發生死鎖（Deadlock）。死鎖是指兩個或以上進程因競爭臨界資源而造成的一種僵局，即一個進程等待一個已經被占用且永不釋放的資源。若無外力作用，這些進程都無法向前推進。

產生死鎖的根本原因是操作系統能夠提供的資源個數比要求該資源的進程數要少。

產生死鎖的基本原因可以分為兩類：資源競爭和進程推進順序不合理。

在資源競爭場景下，系統所擁有的資源是有限的，不能滿足每個進程的需要。

例子：

A有紙，B有筆

A：你不給我筆，我就寫不了作業

B：你不給我紙，我就寫不了作業

彼此僵持不下……

多個程序同時運行時，進程推進順序不合理。

例子：

A要前進2步，到桌子前，再后退2步。

但如果執行順序不合理：A先后退，就永遠到不了桌子前，觸發不了后續動作，就會死鎖。

產生死鎖的必要條件

產生死鎖的四個必要條件：

互斥條件 涉及的資源是非共享的，即一次只能有一個進程使用。如果有另一個進程申請該資源，那么申請進程必須等待，直到該資源被釋放。

不剝奪條件（非搶占） 進程所獲得的資源在未使用完畢之前，不能被其他進程強行奪走，即只能由獲得該資源的進程自行釋放。

占有并等待（部分分配） 進程每次申請它所需要的一部分資源。在等待一新資源的同時，進程繼續占用已分配到的資源。

環路條件（循環等待） 存在一種進程收尾相接的循環鏈，鏈中每個進程都在等待下一個進程所持有的資源，造成這組進程處于永遠等待狀態。

注意：這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件必然成立。反之，上述條件只要有一個不滿足，就不會發生死鎖。所以要避免發生死鎖，只需要破壞其必要條件。 死鎖的處理策略

對于死鎖一般有三種處理策略：預防死鎖、避免死鎖、死鎖的檢測及解除

預防死鎖

通過設置一些限制條件，破壞死鎖的四個必要條件中的一個或幾個，讓死鎖無法發生。 例如，將資源分層，得到上一層資源后才能夠申請下一層資源，這樣就破壞了環路等待條件。用戶申請資源時，要求一次性申請所需要的全部資源，這就破壞了占有并等待條件。當一個已經占有某些不可剝奪資源的進程，請求新的資源而得不到滿足時，它必須釋放已經占有的所有資源，待以后需要時再重新申請，這就破壞了不剝奪條件。 這些預防死鎖的方法破壞了系統的并行性和并發性，通常會降低系統的效率。

避免死鎖

該方法同樣屬于事先預防，但它并不事先采取各種限制措施去破壞產生死鎖的四個必要條件，而是在動態分配資源的過程中，用一些算法來防止系統進入不安全狀態，避免死鎖的發生。

具體策略如下：

1. 如果進程請求的資源會導致死鎖，系統就拒絕啟動該進程；

2. 如果對一個資源的分配會導致下一步的死鎖，系統就拒絕本次分配；

顯然要避免死鎖，系統必須事先知道所擁有的資源數量及其屬性。

一個著名的避免死鎖的算法是銀行家算法。

銀行家算法是DijkstraE W于1968年提出的。之所以稱為銀行家算法，是因為該算法可用于銀行系統。

所謂銀行家算法，是指分配資源之前先確定資源分配是否會造成系統死鎖。如果會死鎖，則不分配，只有確認不會死鎖后才進行分配。

銀行家算法，需要按如下原則判斷是否分配資源：

新進程進入系統時，它必須說明對各類資源的最大需求量，這一數量不能超過系統的資源總數。只有滿足這一條件系統才接納該進程。

當進程申請一組資源時，該算法需要檢查進程對各類資源的最大需求量，如果系統現存的各類資源的數量可以滿足此時的資源最大需求量時，就分配資源；否則進程必須等待，直到其他進程釋放足夠的資源為止。

進程需要在一定時間內無條件地歸還它所申請的全部資源。

死鎖的檢測及解除

死鎖預防和避免都是對資源分配進行適當限制，屬于事前措施，并不利于系統資源的充分共享。而死鎖檢測不會試圖阻止死鎖，即在死鎖發生前不會做任何操作，只是通過設置的檢測機制，檢測當前是否發生死鎖。若發生死鎖，則采取一些措施來解除死鎖。

判斷死鎖的法則主要基于第四條死鎖的必要條件：

資源分配路徑中沒有環路，則系統不會出現死鎖

資源分配路徑中存在環路，則系統可能出現死鎖

如果環路中的每個資料類中都只有一個資源，則系統存在死鎖

如果環路中的每個資源類的資源個數不止一個，則環路的存在是產生死鎖的必要條件但不是充分條件

解除死鎖的方法包括資源剝奪法、進程撤銷法、進程回退法、系統重啟法等：

資源剝奪法

剝奪陷入死鎖的進程所占用的資源，但并不撤銷此進程，再將這些資源分配給需要的進程，直至死鎖解除。

進程撤銷法

一次性撤銷陷入死鎖的所有進程，回收所有占用的資源，等死鎖解除后，再重新運行進程。

逐個撤銷陷入死鎖的進程，依次回收其資源并重新分配，直至死鎖解除。可以優先撤銷優先級低、預計剩余執行時間最長、CPU消耗時間少的進程。

進程回退法

讓所有的進程回退到系統保存的檢查點，這種方法要求系統建立并保存檢查點、建立回退機制。

系統重啟法 結束所有進程并重啟系統。這種方法很簡單，但損失很大，先前的工作可能都浪費了。

責任編輯：YYX