概念：多個(gè)并發(fā)進(jìn)程因爭(zhēng)奪系統(tǒng)資源而產(chǎn)生相互等待的現(xiàn)象。

原理：當(dāng)一組進(jìn)程中的每個(gè)進(jìn)程都在等待某個(gè)事件發(fā)生，而只有這組進(jìn)程中的其他進(jìn)程才能觸發(fā)該事件，這就稱這組進(jìn)程發(fā)生了死鎖。

本質(zhì)原因：

        1）、系統(tǒng)資源有限。

        2）、進(jìn)程推進(jìn)順序不合理。

1、互斥：某種資源一次只允許一個(gè)進(jìn)程訪問(wèn)，即該資源一旦分配給某個(gè)進(jìn)程，其他進(jìn)程就不能再訪問(wèn)，直到該進(jìn)程訪問(wèn)結(jié)束。

2、占有且等待：一個(gè)進(jìn)程本身占有資源（一種或多種），同時(shí)還有資源未得到滿足，正在等待其他進(jìn)程釋放該資源。

3、不可搶占：別人已經(jīng)占有了某項(xiàng)資源，你不能因?yàn)樽约阂残枰撡Y源，就去把別人的資源搶過(guò)來(lái)。

4、循環(huán)等待：存在一個(gè)進(jìn)程鏈，使得每個(gè)進(jìn)程都占有下一個(gè)進(jìn)程所需的至少一種資源。

當(dāng)以上四個(gè)條件均滿足，必然會(huì)造成死鎖，發(fā)生死鎖的進(jìn)程無(wú)法進(jìn)行下去，它們所持有的資源也無(wú)法釋放。這樣會(huì)導(dǎo)致CPU的吞吐量下降。所以死鎖情況是會(huì)浪費(fèi)系統(tǒng)資源和影響計(jì)算機(jī)的使用性能的。那么，解決死鎖問(wèn)題就是相當(dāng)有必要的了。

1、死鎖預(yù)防——確保系統(tǒng)永遠(yuǎn)不會(huì)進(jìn)入死鎖狀態(tài)

 產(chǎn)生死鎖需要四個(gè)條件。那么，只要這四個(gè)條件中至少有一個(gè)條件得不到滿足，就不可能發(fā)生死鎖了。由于互斥條件是非共享資源所必須的，不僅不能改變，還應(yīng)加以保證，所以，主要是破壞產(chǎn)生死鎖的其他三個(gè)條件。

a、破壞“占有且等待”條件

    方法1：所有的進(jìn)程在開始運(yùn)行之前，必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過(guò)程中所需要的全部資源。

     優(yōu)點(diǎn)：簡(jiǎn)單易實(shí)施且安全。

    缺點(diǎn)：因?yàn)槟稠?xiàng)資源不滿足，進(jìn)程無(wú)法啟動(dòng)，而其他已經(jīng)滿足了的資源也不會(huì)得到利用，嚴(yán)重降低了資源的利用率，造成資源浪費(fèi)。

     使進(jìn)程經(jīng)常發(fā)生饑餓現(xiàn)象。

    方法2：該方法是對(duì)第一種方法的改進(jìn)，允許進(jìn)程只獲得運(yùn)行初期需要的資源，便開始運(yùn)行，在運(yùn)行過(guò)程中逐步釋放掉分配到的已經(jīng)使用完畢的資源，然后再去請(qǐng)求新的資源。這樣的話，資源的利用率會(huì)得到提高，也會(huì)減少進(jìn)程的饑餓問(wèn)題。

b、破壞“不可搶占”條件

     當(dāng)一個(gè)已經(jīng)持有了一些資源的進(jìn)程在提出新的資源請(qǐng)求沒(méi)有得到滿足時(shí)，它必須釋放已經(jīng)保持的所有資源，待以后需要使用的時(shí)候再重新申請(qǐng)。這就意味著進(jìn)程已占有的資源會(huì)被短暫地釋放或者說(shuō)是被搶占了。

     該種方法實(shí)現(xiàn)起來(lái)比較復(fù)雜，且代價(jià)也比較大。釋放已經(jīng)保持的資源很有可能會(huì)導(dǎo)致進(jìn)程之前的工作實(shí)效等，反復(fù)的申請(qǐng)和釋放資源會(huì)導(dǎo)致進(jìn)程的執(zhí)行被無(wú)限的推遲，這不僅會(huì)延長(zhǎng)進(jìn)程的周轉(zhuǎn)周期，還會(huì)影響系統(tǒng)的吞吐量。

c、破壞“循環(huán)等待”條件

    可以通過(guò)定義資源類型的線性順序來(lái)預(yù)防，可將每個(gè)資源編號(hào)，當(dāng)一個(gè)進(jìn)程占有編號(hào)為i的資源時(shí)，那么它下一次申請(qǐng)資源只能申請(qǐng)編號(hào)大于i的資源。如圖所示：

這樣雖然避免了循環(huán)等待，但是這種方法是比較低效的，資源的執(zhí)行速度回變慢，并且可能在沒(méi)有必要的情況下拒絕資源的訪問(wèn)，比如說(shuō)，進(jìn)程c想要申請(qǐng)資源1，如果資源1并沒(méi)有被其他進(jìn)程占有，此時(shí)將它分配個(gè)進(jìn)程c是沒(méi)有問(wèn)題的，但是為了避免產(chǎn)生循環(huán)等待，該申請(qǐng)會(huì)被拒絕，這樣就降低了資源的利用率。

2、避免死鎖——在使用前進(jìn)行判斷，只允許不會(huì)產(chǎn)生死鎖的進(jìn)程申請(qǐng)資源

的死鎖避免是利用額外的檢驗(yàn)信息，在分配資源時(shí)判斷是否會(huì)出現(xiàn)死鎖，只在不會(huì)出現(xiàn)死鎖的情況下才分配資源。

兩種避免辦法：

    1、如果一個(gè)進(jìn)程的請(qǐng)求會(huì)導(dǎo)致死鎖，則不啟動(dòng)該進(jìn)程

    2、如果一個(gè)進(jìn)程的增加資源請(qǐng)求會(huì)導(dǎo)致死鎖，則拒絕該申請(qǐng)。

避免死鎖的具體實(shí)現(xiàn)通常利用銀行家算法。

銀行家算法

銀行家算法的相關(guān)數(shù)據(jù)結(jié)構(gòu)

可利用資源向量Available：用于表示系統(tǒng)里邊各種資源剩余的數(shù)目。由于系統(tǒng)里邊擁有的資源通常都是有很多種（假設(shè)有m種），所以，我們用一個(gè)有m個(gè)元素的數(shù)組來(lái)表示各種資源。數(shù)組元素的初始值為系統(tǒng)里邊所配置的該類全部可用資源的數(shù)目，其數(shù)值隨著該類資源的分配與回收動(dòng)態(tài)地改變。

最大需求矩陣Max：用于表示各個(gè)進(jìn)程對(duì)各種資源的額最大需求量。進(jìn)程可能會(huì)有很多個(gè)（假設(shè)為n個(gè)），那么，我們就可以用一個(gè)nxm的矩陣來(lái)表示各個(gè)進(jìn)程多各種資源的最大需求量

分配矩陣Allocation：顧名思義，就是用于表示已經(jīng)分配給各個(gè)進(jìn)程的各種資源的數(shù)目。也是一個(gè)nxm的矩陣。

需求矩陣Need：用于表示進(jìn)程仍然需要的資源數(shù)目，用一個(gè)nxm的矩陣表示。系統(tǒng)可能沒(méi)法一下就滿足了某個(gè)進(jìn)程的最大需求（通常進(jìn)程對(duì)資源的最大需求也是只它在整個(gè)運(yùn)行周期中需要的資源數(shù)目，并不是每一個(gè)時(shí)刻都需要這么多），于是，為了進(jìn)程的執(zhí)行能夠向前推進(jìn)，通常，系統(tǒng)會(huì)先分配個(gè)進(jìn)程一部分資源保證進(jìn)程能夠執(zhí)行起來(lái)。那么，進(jìn)程的最大需求減去已經(jīng)分配給進(jìn)程的數(shù)目，就得到了進(jìn)程仍然需要的資源數(shù)目了。

銀行家算法通過(guò)對(duì)進(jìn)程需求、占有和系統(tǒng)擁有資源的實(shí)時(shí)統(tǒng)計(jì)，確保系統(tǒng)在分配給進(jìn)程資源不會(huì)造成死鎖才會(huì)給與分配。

死鎖避免的優(yōu)點(diǎn)：不需要死鎖預(yù)防中的搶占和重新運(yùn)行進(jìn)程，并且比死鎖預(yù)防的限制要少。

死鎖避免的限制：

    必須事先聲明每個(gè)進(jìn)程請(qǐng)求的最大資源量

   考慮的進(jìn)程必須無(wú)關(guān)的，也就是說(shuō)，它們執(zhí)行的順序必須沒(méi)有任何同步要求的限制

    分配的資源數(shù)目必須是固定的。

    在占有資源時(shí)，進(jìn)程不能退出

3、死鎖檢測(cè)與解除-----在檢測(cè)到運(yùn)行系統(tǒng)進(jìn)入死鎖，進(jìn)行恢復(fù)。

允許系統(tǒng)進(jìn)入到死鎖狀態(tài)

下圖截自《操作系統(tǒng)——精髓與設(shè)計(jì)原理》

如果利用死鎖檢測(cè)算法檢測(cè)出系統(tǒng)已經(jīng)出現(xiàn)了死鎖，那么，此時(shí)就需要對(duì)系統(tǒng)采取相應(yīng)的措施。常用的解除死鎖的方法：

1、搶占資源：從一個(gè)或多個(gè)進(jìn)程中搶占足夠數(shù)量的資源分配給死鎖進(jìn)程，以解除死鎖狀態(tài)。

2、終止（或撤銷）進(jìn)程：終止或撤銷系統(tǒng)中的一個(gè)或多個(gè)死鎖進(jìn)程，直至打破死鎖狀態(tài)。

a、終止所有的死鎖進(jìn)程。這種方式簡(jiǎn)單粗暴，但是代價(jià)很大，很有可能會(huì)導(dǎo)致一些已經(jīng)運(yùn)行了很久的進(jìn)程前功盡棄。

b、逐個(gè)終止進(jìn)程，直至死鎖狀態(tài)解除。該方法的代價(jià)也很大，因?yàn)槊拷K止一個(gè)進(jìn)程就需要使用死鎖檢測(cè)來(lái)檢測(cè)系統(tǒng)當(dāng)前是否處于死鎖狀態(tài)。另外，每次終止進(jìn)程的時(shí)候終止那個(gè)進(jìn)程呢？每次都應(yīng)該采用最優(yōu)策略來(lái)選擇一個(gè)“代價(jià)最小”的進(jìn)程來(lái)解除死鎖狀態(tài)。一般根據(jù)如下幾個(gè)方面來(lái)決定終止哪個(gè)進(jìn)程：

    進(jìn)程的優(yōu)先級(jí)

    進(jìn)程已運(yùn)行時(shí)間以及運(yùn)行完成還需要的時(shí)間

    進(jìn)程已占用系統(tǒng)資源

    進(jìn)程運(yùn)行完成還需要的資源

    終止進(jìn)程數(shù)目

    進(jìn)程是交互還是批處理

盛圖科技

高端IT培訓(xùn)第一品牌