操作系統(tǒng)原理第六章死鎖課件

第六章

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

進(jìn)程執(zhí)行的速度

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

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

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

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

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

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

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

4、

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(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)。

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

否則，

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

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

再令Finish［i］∶=true。

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

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

若找到，

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

否則，執(zhí)行步驟(4)。(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行Work［j］∶=Work［i］+Allocation［i,j］Finish［i］∶=true;gotostep（2）;(4)如果所有進(jìn)程的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)按銀行家算法進(jìn)行檢查是否安全(3)P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查是否安全

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

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

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

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

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

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