關于死鎖的一系列問題

概念：多個并發進程因争奪系統資源而産生相(xiàng)互等待的現(xiàn)象。

原理：當一組進程中的每個進程都在等待某個事件發生，而隻有這組進程中的其他進程才能觸發該事件，這就稱這組進程發生了死鎖。

本質原因：

        1）、系統資源有限。

        2）、進程推進順序不合理。

1、互斥：某種資源一次隻允許一個進程訪問，即該資源一旦分配給某個進程，其他進程就不能再訪問，直到該進程訪問結束。

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

3、不可搶占：别人已經占有了某項資源，你不能因爲自己也需要該資源，就去(qù)把别人的資源搶過來。

4、循環等待：存在一個進程鏈，使得每個進程都占有下一個進程所需的至少一種資源。

當以上四個條件均滿足，必然會造成死鎖，發生死鎖的進程無法進行下去(qù)，它們所持有的資源也無法釋放(fàng)。這樣會導緻CPU的吞吐量下降。所以死鎖情況是(shì)會浪費(fèi)系統資源和影響計算機的使用性能的。那麽，解決死鎖問題就是(shì)相(xiàng)當有必要的了。

1、死鎖預防——确保系統永遠不會進入死鎖狀态

 産生死鎖需要四個條件。那麽，隻要這四個條件中至少有一個條件得不到滿足，就不可能發生死鎖了。由于互斥條件是(shì)非共享資源所必須的，不僅不能改變，還應加以保證，所以，主要是(shì)破壞産生死鎖的其他三個條件。

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

    方法1：所有的進程在開始運行之前，必須一次性地申請其在整個運行過程中所需要的全部資源。

     優點：簡單易實施且安全。

    缺點：因爲某項資源不滿足，進程無法啓動，而其他已經滿足了的資源也不會得到利用，嚴重降低了資源的利用率，造成資源浪費(fèi)。

     使進程經常發生饑餓現(xiàn)象。

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

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

     當一個已經持有了一些資源的進程在提出新的資源請求沒有得到滿足時，它必須釋放(fàng)已經保持的所有資源，待以後需要使用的時候再重新申請。這就意味着進程已占有的資源會被短暫地釋放(fàng)或者說是(shì)被搶占了。

     該種方法實現(xiàn)起來比較複雜(zá)，且代價也比較大。釋放(fàng)已經保持的資源很有可能會導緻進程之前的工作實效等，反複的申請和釋放(fàng)資源會導緻進程的執行被無限的推遲，這不僅會延長進程的周轉周期，還會影響系統的吞吐量。

c、破壞“循環等待”條件

    可以通過定義資源類型的線(xiàn)性順序來預防，可将每個資源編号，當一個進程占有編号爲i的資源時，那麽它下一次申請資源隻能申請編号大于i的資源。如圖所示：

這樣雖然避免了循環等待，但(dàn)是(shì)這種方法是(shì)比較低效的，資源的執行速度回變慢(màn)，并且可能在沒有必要的情況下拒絕資源的訪問，比如說，進程c想要申請資源1，如果資源1并沒有被其他進程占有，此時将它分配個進程c是(shì)沒有問題的，但(dàn)是(shì)爲了避免産生循環等待，該申請會被拒絕，這樣就降低了資源的利用率。

2、避免死鎖——在使用前進行判斷，隻允許不會産生死鎖的進程申請資源

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

兩種避免辦法：

    1、如果一個進程的請求會導緻死鎖，則不啓動該進程

    2、如果一個進程的增加資源請求會導緻死鎖，則拒絕該申請。

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

銀行家算法

銀行家算法的相(xiàng)關數據結構

可利用資源向量Available：用于表示系統裏邊各種資源剩餘的數目。由于系統裏邊擁有的資源通常都是(shì)有很多種（假設有m種），所以，我們用一個有m個元素的數組來表示各種資源。數組元素的初始值爲系統裏邊所配置的該類全部可用資源的數目，其數值随着該類資源的分配與回收動态地改變。

最大需求矩陣Max：用于表示各個進程對各種資源的額最大需求量。進程可能會有很多個（假設爲n個），那麽，我們就可以用一個nxm的矩陣來表示各個進程多各種資源的最大需求量

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

需求矩陣Need：用于表示進程仍然需要的資源數目，用一個nxm的矩陣表示。系統可能沒法一下就滿足了某個進程的最大需求（通常進程對資源的最大需求也是(shì)隻它在整個運行周期中需要的資源數目，并不是(shì)每一個時刻都需要這麽多），于是(shì)，爲了進程的執行能夠向前推進，通常，系統會先分配個進程一部分資源保證進程能夠執行起來。那麽，進程的最大需求減去(qù)已經分配給進程的數目，就得到了進程仍然需要的資源數目了。

銀行家算法通過對進程需求、占有和系統擁有資源的實時統計，确保系統在分配給進程資源不會造成死鎖才會給與分配。

死鎖避免的優點：不需要死鎖預防中的搶占和重新運行進程，并且比死鎖預防的限制要少。

死鎖避免的限制：

    必須事先聲明每個進程請求的最大資源量

   考慮的進程必須無關的，也就是(shì)說，它們執行的順序必須沒有任何同步要求的限制

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

    在占有資源時，進程不能退出

3、死鎖檢測與解除-----在檢測到運行系統進入死鎖，進行恢複。

允許系統進入到死鎖狀态

下圖截自《操作系統——精髓與設計原理》

如果利用死鎖檢測算法檢測出系統已經出現(xiàn)了死鎖，那麽，此時就需要對系統采取相(xiàng)應的措施。常用的解除死鎖的方法：

1、搶占資源：從一個或多個進程中搶占足夠數量的資源分配給死鎖進程，以解除死鎖狀态。

2、終止（或撤銷）進程：終止或撤銷系統中的一個或多個死鎖進程，直至打破死鎖狀态。

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

b、逐個終止進程，直至死鎖狀态解除。該方法的代價也很大，因爲每終止一個進程就需要使用死鎖檢測來檢測系統當前是(shì)否處于死鎖狀态。另外，每次終止進程的時候終止那個進程呢？每次都應該采用最優策略來選擇一個“代價最小”的進程來解除死鎖狀态。一般根據如下幾個方面來決定終止哪個進程：

    進程的優先級

    進程已運行時間以及運行完成還需要的時間

    進程已占用系統資源

    進程運行完成還需要的資源

    終止進程數目

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

盛圖科技

高端IT培訓第一品牌