產生死鎖的原因

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

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

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

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

例子：

A有紙，B有筆

A：你不給我筆，我就寫不了作業(yè)

B：你不給我紙，我就寫不了作業(yè)

彼此僵持不下……

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

例子：

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

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

產生死鎖的必要條件

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

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

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

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

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

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

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

預防死鎖

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

避免死鎖

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

具體策略如下：

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

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

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

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

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

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

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

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

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

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

死鎖的檢測及解除

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

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

資源分配路徑中沒有環(huán)路，則系統(tǒng)不會出現(xiàn)死鎖

資源分配路徑中存在環(huán)路，則系統(tǒng)可能出現(xiàn)死鎖

如果環(huán)路中的每個資料類中都只有一個資源，則系統(tǒng)存在死鎖

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

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

資源剝奪法

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

進程撤銷法

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

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

進程回退法

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

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

責任編輯：YYX