產(chǎn)生死鎖的原因

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

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

產(chǎn)生死鎖的基本原因可以分為兩類：資源競(jìng)爭(zhēng)和進(jìn)程推進(jìn)順序不合理。

在資源競(jìng)爭(zhēng)場(chǎng)景下，系統(tǒng)所擁有的資源是有限的，不能滿足每個(gè)進(jìn)程的需要。

例子：

A有紙，B有筆

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

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

彼此僵持不下……

多個(gè)程序同時(shí)運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合理。

例子：

A要前進(jìn)2步，到桌子前，再后退2步。

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

產(chǎn)生死鎖的必要條件

產(chǎn)生死鎖的四個(gè)必要條件：

互斥條件 涉及的資源是非共享的，即一次只能有一個(gè)進(jìn)程使用。如果有另一個(gè)進(jìn)程申請(qǐng)?jiān)撡Y源，那么申請(qǐng)進(jìn)程必須等待，直到該資源被釋放。

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

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

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

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

對(duì)于死鎖一般有三種處理策略：預(yù)防死鎖、避免死鎖、死鎖的檢測(cè)及解除

預(yù)防死鎖

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

避免死鎖

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

具體策略如下：

1. 如果進(jìn)程請(qǐng)求的資源會(huì)導(dǎo)致死鎖，系統(tǒng)就拒絕啟動(dòng)該進(jìn)程；

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

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

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

銀行家算法是DijkstraE W于1968年提出的。之所以稱為銀行家算法，是因?yàn)樵撍惴捎糜阢y行系統(tǒng)。

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

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

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

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

進(jìn)程需要在一定時(shí)間內(nèi)無條件地歸還它所申請(qǐng)的全部資源。

死鎖的檢測(cè)及解除

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

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

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

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

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

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

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

資源剝奪法

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

進(jìn)程撤銷法

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

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

進(jìn)程回退法

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

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

責(zé)任編輯：YYX