第六章

死鎖若對資源不加限制的分配可能導致進程間由于競爭資源而相互制約以至無法繼續(xù)運行的局面，這就是死鎖。一、死鎖的基本概念1、死鎖產生的原因系統(tǒng)中兩個或兩個以上的進程無限期的等待永遠不可能發(fā)生的事件，則稱這些進程處于死鎖狀態(tài)中。

進程執(zhí)行的速度

例6-1對臨時資源使用不加限制

例6-2例6-3生活中的例子：獨木橋其他：waitsignal操作順序不對2、死鎖的必要條件1）互斥條件2）保持和請求條件3）不剝奪條件4）環(huán)路條件

3、死鎖的對策1）鴕鳥策略忽略死鎖的發(fā)生,unix和linux中會如此處理2）預防策略

破壞四個必要條件中的一個，但會影響資源利用率和系統(tǒng)吞吐量3）避免策略

與預防策略不同，預防策略要求破壞一個必要條件，而避免策略不必嚴格限制必要條件的存在，因為必要條件存在也不一定發(fā)生死鎖。因此死鎖避免使在事先加以較弱的限制條件，目的是提高系統(tǒng)資源利用率。4）死鎖的檢查和解除通過系統(tǒng)設置檢查機構、及時檢查死鎖的發(fā)生，并確定死鎖進程和卷入死鎖的資源，并采取適當措施，將死鎖進程從死鎖中解除。

二、死鎖預防1、破壞互斥條件允許多個進程同時訪問資源2、破壞不剝奪條件

在允許進程動態(tài)申請資源的前提下：一個進程在申請新資源的要求不能立刻得到滿足時，便處于等待狀態(tài)。而一個處于等待狀態(tài)的進程的全部資源可以被剝奪。

4、

破壞“循環(huán)等待”條件針對環(huán)路條件的，資源的動態(tài)分配有序資源使用法

：將系統(tǒng)中的所有資源順序編號，一般原則是，較為緊缺、稀少的的資源編號較大。進程申請資源時，必須嚴格按照資源編號的順序進行，否則系統(tǒng)不予分配。即一進程只有得到編號小的資源，才能申請編號較大的資源，釋放資源是，應該按編號遞減的次序進行。三、死鎖避免

系統(tǒng)對進程發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進行動態(tài)檢查，并根據(jù)檢查結果決定是否分配資源，如果分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配，這是一種保證系統(tǒng)不進入死鎖狀態(tài)的動態(tài)策略。1、安全和不安全狀態(tài)

安全狀態(tài)：在某一時刻，系統(tǒng)能按照某種次序，如<P1,P2……Pn>來為并發(fā)進程分配所需要的資源，直到最大需求，使每個進程都順利完成，則程此時的系統(tǒng)狀態(tài)為安全狀態(tài)。此序列為安全序列。

不安全狀態(tài)：某一時刻，不存在這樣的一個安全序列，則稱為不安全狀態(tài)。

2、利用銀行家算法避免死鎖一個銀行家把他的固定資金貸給若干顧客。只要不出現(xiàn)一個顧客借走所有資金后還還不夠，銀行家的資金應是安全的。銀行家需一個算法保證借出去的資金在有限時間內可收回。為保證資金的安全，銀行家規(guī)定：1）

當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時可以接納該顧客。2）

顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量。3）

當銀行家現(xiàn)有的資金不能滿足顧客尚須得貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間能得到貸款。4）

當顧客得到所需的全部資金后，能在有限的時間里歸還所有的資金。推廣到操作系統(tǒng)，操作系統(tǒng)按照銀行家的規(guī)定為進程分配資源，進程首先提出對資源的最大需求量，當進程在執(zhí)行過程中每次申請資源時，系統(tǒng)測試該進程已占用的資源與本次申請的資源之和是不是超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過，則系統(tǒng)再測試系統(tǒng)現(xiàn)存的資源是否能滿足該進程尚需要的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。

（一）數(shù)據(jù)結構可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目

。最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。

需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數(shù)

。注意：Need［i,j］=Max［i,j］-Allocation［i,j］

(3)系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結構中的數(shù)值：Available［j］:=Available［j］-Requesti［j］Allocation［i,j］:=Allocation［i,j］+Requesti［j］;

Need［i,j］:=Need［i,j］-Requesti［j］;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。

若安全，才正式將資源分配給進程Pi，以完成本次分配；

否則，

將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。（三）安全性問題（1）設置兩個向量：①

工作向量Work:它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］∶=false;當有足夠資源分配給進程時，

再令Finish［i］∶=true。

(2)從進程集合中找到一個能滿足下述條件的進程：

①Finish［i］=false;②Need［i,j］≤Work［j］；

若找到，

執(zhí)行步驟(3)，

否則，執(zhí)行步驟(4)。(3)當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行Work［j］∶=Work［i］+Allocation［i,j］Finish［i］∶=true;gotostep（2）;(4)如果所有進程的Finish［i］=true都滿足，

則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

(1)分析此狀態(tài)是否為安全狀態(tài)(2)P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查是否安全(3)P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查是否安全

銀行家算法在理論上是出色的，能保證系統(tǒng)一直工作在安全狀態(tài)下。此外，作為資源分配的一種算法，銀行家算法允許互斥條件、請求和保持條件以及不剝奪條件成立，相比死鎖預防，其限制條件放松，資源利用率得到改善，但仍有不足：1）算法要求分配的資源數(shù)量不定不變2）算法要求用戶數(shù)目也不定不便。3）算法保證所有用戶的資源要求能在有限時間內得到相應，但實時用戶要求有更好的相應速度。4）算法要求用戶在提交作業(yè)時說明對各類資源請求的最大數(shù)量，這對于用戶而言不方便也很困難。

四、死鎖的檢測系統(tǒng)如果沒有防范機制，則系統(tǒng)在運行過程中可能存在死鎖。為此，在操作系統(tǒng)中通常設立一個檢測進程，它平時處于睡眠狀態(tài)，周期性的或發(fā)現(xiàn)系統(tǒng)性能下降時被喚醒以檢查系統(tǒng)中有無死鎖進程。采用這種技術時，系統(tǒng)需要監(jiān)視資源的申請和釋放，其中廣為應用的是以描述系統(tǒng)內資源使用與申請狀況的有向圖，叫做資源分配圖。

2、死鎖定理1）找一個非孤立點進程結點且只有分配邊，去掉分配邊，將其變?yōu)楣铝⒔Y點2）再把相應的資源分配給一個等待該資源的進程，即將某進程的申請邊變?yōu)榉峙溥?/p>

某狀態(tài)為死鎖的充分條件是：當且僅當該狀態(tài)的資源分配圖是完全化簡得，經過化簡后非孤立的進程是死鎖進程。

死鎖的環(huán)路條件與資源分配圖中有環(huán)路時等價的，系統(tǒng)中出現(xiàn)死鎖，資源分配圖必然有環(huán)路，但有環(huán)路不一定死鎖。六、

死鎖的綜合處理資源順序分類法：1、內部資源（系統(tǒng)所用資源，如p