操作系統(tǒng)課件第三章2

第三章處理機(jī)調(diào)度與死鎖操作系統(tǒng)Page12023/2/3第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

調(diào)度算法實時調(diào)度

多處理機(jī)系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件

預(yù)防死鎖的方法死鎖的檢測與解除Page22023/2/3產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page32023/2/3死鎖的基本概念死鎖例子一個由于申請不同類型資源而產(chǎn)生死鎖的例子設(shè)系統(tǒng)有一臺打印機(jī)(R1)一臺掃描儀(R2)，兩進(jìn)程共享這兩臺設(shè)備。用信號量S1表示R1是否可用，用信號量S2表示R2是否可用，S1、S2初值為1。Page42023/2/3死鎖的基本概念這兩個進(jìn)程在并發(fā)執(zhí)行過程中，可能會發(fā)生死鎖。大家可以思考一下，如何修改，進(jìn)程才不會發(fā)生死鎖？Page52023/2/3死鎖的基本概念死鎖的概念指多個進(jìn)程因競爭共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。即：一組進(jìn)程中，每個進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。Page62023/2/3死鎖的基本概念關(guān)于死鎖的一些結(jié)論參與死鎖的進(jìn)程最少是兩個

參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。Page72023/2/3死鎖的基本概念永久性資源和臨時性資源永久性資源：可以被多個進(jìn)程多次使用（可再用資源）可搶占資源：CPU不可搶占資源：打印機(jī)臨時性資源：只可使用一次的資源；即由一個進(jìn)程產(chǎn)生，被另一進(jìn)程使用后就再也無用的資源，也稱為消耗性資源如信號量,中斷信號，同步信號等（可消耗性資源）“申請--分配--使用--釋放”模式Page82023/2/3產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page92023/2/33.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因競爭資源。當(dāng)系統(tǒng)中供多個進(jìn)程所共享的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖。

(2)進(jìn)程間推進(jìn)順序非法。

進(jìn)程在運行過程中，請求和釋放資源的順序不當(dāng)，導(dǎo)致了進(jìn)程死鎖。

所謂死鎖（Deadlock），是指多個進(jìn)程因競爭資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。Page102023/2/3產(chǎn)生死鎖的原因競爭資源引起進(jìn)程死鎖可剝奪和非剝奪性資源可剝奪性資源是指進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪，如處理機(jī)、內(nèi)存等非剝奪性資源是指當(dāng)系統(tǒng)把這類資源分配給某個進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放，如磁帶機(jī)、打印機(jī)等競爭非剝奪性資源系統(tǒng)中的非剝奪性資源由于數(shù)量有限而不能滿足進(jìn)程運行的需要，進(jìn)程在運行過程中因爭奪這些資源而限入僵局競爭臨時性資源Page112023/2/3產(chǎn)生死鎖的原因I/O設(shè)備共享時的死鎖情況

若系統(tǒng)中只有一臺打印機(jī)R1和一臺讀卡機(jī)R2，可供進(jìn)程P1和P2共享。若形成環(huán)路，這樣會產(chǎn)生死鎖。R1R2P1P2分配分配請求請求Page122023/2/3產(chǎn)生死鎖的原因

進(jìn)程之間通信時的死鎖S2P1S3P3S1P2產(chǎn)生P2產(chǎn)生P3產(chǎn)生要求接收要求接收要求接收Page132023/2/3產(chǎn)生死鎖的原因進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D不安全區(qū)Page142023/2/3產(chǎn)生死鎖的原因若并發(fā)進(jìn)程P1和P2按曲線④所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。此時P1保持了資源R1,P2保持了資源R2,系統(tǒng)處于不安全狀態(tài)。因為，這時兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)P1運行到P1:Request(R2)時，將因R2已被P2占用而阻塞；當(dāng)P2運行到P2:Request(R1)時，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖Page152023/2/3產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page162023/2/3產(chǎn)生死鎖的必要條件互斥條件

進(jìn)程對所分配到的資源進(jìn)行排它性的使用請求和保持條件

進(jìn)程已經(jīng)至少保持了一個資源，但又提出了新的資源請求，而該資源又已被其他進(jìn)程占有不剝奪條件進(jìn)程已獲得的資源在未使用完之前不能被剝奪環(huán)路等待條件在發(fā)生死鎖時，必然存在一個進(jìn)程--資源循環(huán)等待的環(huán)形鏈Page172023/2/3產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page182023/2/3處理死鎖的基本方法預(yù)防死鎖避免死鎖檢測死鎖解除死鎖Page192023/2/33.5.3處理死鎖的基本方法

目前用于處理死鎖的方法可歸結(jié)為以下四種：1、預(yù)防死鎖通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來防止發(fā)生死鎖。2、避免死鎖不須采用各種限制措施去破壞產(chǎn)生死鎖的必要條件，防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖，只需在事先加以較弱的限制條件。3、檢測死鎖不須檢查系統(tǒng)是否已進(jìn)入不安全區(qū)，允許系統(tǒng)在運行過程中發(fā)生死鎖。4、解除死鎖常用的實施方法是撤消或掛起一些進(jìn)程，以便回收一些資源，再將這些資源分配給已處于阻塞狀態(tài)的進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運行。Page202023/2/3處理死鎖的基本方法方法資源分配策略各種可能模式主要優(yōu)點主要缺點預(yù)防Prevention保守的；寧可資源閑置（從機(jī)制上使死鎖條件不成立，即摒棄三個必要條件）一次請求所有資源<條件2>適用于作突發(fā)式處理的進(jìn)程；不必剝奪效率低；進(jìn)程初始化時間延長剝奪次數(shù)過多；多次對資源重新起動不便靈活申請新資源資源剝奪<條件3>適用于狀態(tài)可以保存和恢復(fù)的資源資源按序申請<條件4>避免Avoidance是“預(yù)防”和“檢測”的折衷（在運行時判斷是否可能死鎖）尋找可能的安全的運行順序不必進(jìn)行剝奪使用條件：必須知道將來的資源需求；進(jìn)程可能會長時間阻塞檢測Detection寬松的；只要允許，就分配資源定期檢查死鎖是否已經(jīng)發(fā)生不延長進(jìn)程初始化時間；允許對死鎖進(jìn)行現(xiàn)場處理通過剝奪解除死鎖，造成損失可以在編譯時（而不必在運行時）就進(jìn)行檢查Page212023/2/3第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

調(diào)度算法實時調(diào)度

多處理機(jī)系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件

預(yù)防死鎖的方法死鎖的檢測與解除Page222023/2/3預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖Page232023/2/3產(chǎn)生死鎖的必要條件互斥條件

進(jìn)程對所分配到的資源進(jìn)行排它性的使用請求和保持條件

進(jìn)程已經(jīng)至少保持了一個資源，但又提出了新的資源請求，而該資源又已被其他進(jìn)程占有不剝奪條件進(jìn)程已獲得的資源在未使用完之前不能被剝奪環(huán)路等待條件在發(fā)生死鎖時，必然存在一個進(jìn)程--資源循環(huán)等待的環(huán)形鏈Page242023/2/3預(yù)防死鎖摒棄“請求和保持”條件所有進(jìn)程在開始運行之前必須一次性的申請整個運行過程所需的全部資源簡單、易于實現(xiàn)、安全資源浪費嚴(yán)重進(jìn)程延遲運行Page252023/2/3預(yù)防死鎖摒棄“不剝奪”條件進(jìn)程逐個地申請所需資源當(dāng)一個已經(jīng)保持了某些資源的進(jìn)程申請新資源而不能得到滿足時，必須放棄所有已保持的資源實現(xiàn)復(fù)雜、代價高昂延長了進(jìn)程的周轉(zhuǎn)時間，還增加了系統(tǒng)開銷，降低了系統(tǒng)的吞吐量Page262023/2/3預(yù)防死鎖摒棄“環(huán)路等待”條件系統(tǒng)將所有資源按類型分配序號并排隊所有進(jìn)程申請資源必須按序號遞增的順序資源利用率和系統(tǒng)吞吐量較高但在資源管理和資源申請方面仍有問題Page272023/2/3預(yù)防死鎖存在問題：資源的需求順序不等于序號，仍存在資源浪費。Page282023/2/3預(yù)防死鎖摒棄“環(huán)路等待”條件其資源利用率和系統(tǒng)吞吐量，都有較明顯的改善，但也存在下述嚴(yán)重問題：（1）資源所分配的序號，必須相對穩(wěn)定，這就限制了新設(shè)備類型的增加。（2）進(jìn)程使用各資源的順序，與系統(tǒng)規(guī)定的順序不同，造成對資源的浪費。（3）按規(guī)定次序申請資源的方法，必然會限制了用戶簡單、自主地編程。Page292023/2/3處理死鎖的基本方法方法資源分配策略各種可能模式主要優(yōu)點主要缺點預(yù)防Prevention保守的；寧可資源閑置（從機(jī)制上使死鎖條件不成立，即摒棄三個必要條件）一次請求所有資源<條件2>適用于作突發(fā)式處理的進(jìn)程；不必剝奪效率低；進(jìn)程初始化時間延長剝奪次數(shù)過多；多次對資源重新起動不便靈活申請新資源資源剝奪<條件3>適用于狀態(tài)可以保存和恢復(fù)的資源資源按序申請<條件4>避免Avoidance是“預(yù)防”和“檢測”的折衷（在運行時判斷是否可能死鎖）尋找可能的安全的運行順序不必進(jìn)行剝奪使用條件：必須知道將來的資源需求；進(jìn)程可能會長時間阻塞檢測Detection寬松的；只要允許，就分配資源定期檢查死鎖是否已經(jīng)發(fā)生不延長進(jìn)程初始化時間；允許對死鎖進(jìn)行現(xiàn)場處理通過剝奪解除死鎖，造成損失可以在編譯時（而不必在運行時）就進(jìn)行檢查Page302023/2/3預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖Page312023/2/3產(chǎn)生死鎖的原因進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④DPage322023/2/3系統(tǒng)安全狀態(tài)安全狀態(tài)在避免死鎖的方法中，允許進(jìn)程動態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計算此次資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，令進(jìn)程等待所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個進(jìn)程Pi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)Page332023/2/32.安全狀態(tài)之例我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進(jìn)程P1、P2和P3，共有12臺磁帶機(jī)。進(jìn)程P1總共要求10臺磁帶機(jī)，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機(jī)，尚有3臺空閑未分配，如下表所示：29P324P23510P1可用已分配最大需求進(jìn)程415100109312存在安全序列：P2-P1-P3，系統(tǒng)處于安全狀態(tài)。Page342023/2/33.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機(jī)，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。32404不安全狀態(tài)Page352023/2/3預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖Page362023/2/33.6.3利用銀行家算法避免死鎖1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。

Page372023/2/3(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。

(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。

(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。Need[i,j]=Max[i,j]–Allocation[i,j]Page382023/2/3

2.銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti[j]=K，表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(1)如果Requesti[j]≤Need[i,j]，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。

(2)如果Requesti[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。Page392023/2/3(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等待。Page402023/2/33.安全性算法(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。Page412023/2/3(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;

gotostep2;(4)如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。Page422023/2/34.銀行家算法之例

假定系統(tǒng)中有五個進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。圖3-15T0時刻的資源分配表2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeed[i,j]=Max[i,j]–Allocation[i,j]Page432023/2/3(1)T0時刻的安全性：圖3-16T0時刻的安全序列truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在T0時刻處于安全狀態(tài)。Page442023/2/3(2)P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查：

①Request1(1,0,2)≤Need1(1,2,2)

②Request1(1,0,2)≤Available1(3,3,2)Page452023/2/3③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號所示。Request1(1，0，2)2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Page462023/2/3④再利用安全性算法檢查此時系統(tǒng)是否安全。truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork+AllocationAllocationNeedWork圖3-17P1申請資源時的安全性檢查存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足P1資源分配請求。Page472023/2/3(3)P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：

①Request4(3,3,0)≤Need4(4,3,1);

②Request4(3,3,0)≤Available(2,3,0)，讓P4等待。/Page482023/2/3(4)P0請求資源：P0發(fā)出請求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：

①Request0(0,2,0)≤Need0(7,4,3);

②Request0(0,2,0)≤Available(2,3,0);Page492023/2/3③系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖3-18所示。Request0(0，2，0)723210030圖3-18為P0分配資源后的有關(guān)資源數(shù)據(jù)不安全狀態(tài)Page502023/2/3(5)P0請求資源：P0發(fā)出請求向量改為Request0(0,1,0)，系統(tǒng)按銀行家算法進(jìn)行檢查：

①Request0(0,1,0)≤Need0(7,4,3);

②Request0(0,1,0)≤Available(2,3,0);Page512023/2/3③系統(tǒng)先假定可為P0分配資源，并修改Available,Allocation0和Need0向量，由此形成的資源變化情況如圖所示。Request0(0,1,0)0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Page522023/2/3④再利用安全性算法檢查此時系統(tǒng)是否安全。truetruetruetruetrueFinish75532C55332B20212C02010B03110C03312B55320C53322B10367P27047P45302P17077P07205P3AAAAWork+AllocationAllocationNeedWork圖3-17P1申請資源時的安全性檢查存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足P0資源分配請求。Page532023/2/3第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

調(diào)度算法實時調(diào)度

多處理機(jī)系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件

預(yù)防死鎖的方法

死鎖的檢測與解除Page542023/2/3死鎖的檢測與解除死鎖的檢測死鎖的解除Page552023/2/3死鎖的檢測

允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生一旦死鎖發(fā)生則采取專門的措施，解除死鎖并以最小的代價恢復(fù)操作系統(tǒng)運行Page562023/2/3死鎖的檢測檢測時機(jī)當(dāng)進(jìn)程等待時檢測死鎖其缺點是系統(tǒng)的開銷大定時檢測系統(tǒng)資源利用率下降時檢測死鎖Page572023/2/33.7死鎖的檢測與解除3.7.1死鎖的檢測

當(dāng)系統(tǒng)為進(jìn)程分配資源時，若未采取任何限制性措施，則系統(tǒng)必須提供檢測和解除死鎖的手段，為此，系統(tǒng)必須：（1）保存有關(guān)資源的請求和分配信息；（2）提供一種算法，以利用這些信息來檢測系統(tǒng)是否進(jìn)入死鎖狀態(tài)。Page582023/2/3死鎖的檢測資源分配圖(ResourceAllocationGraph)

用有向圖描述進(jìn)程的死鎖優(yōu)點：準(zhǔn)確、形象系統(tǒng)由若干類資源構(gòu)成，一類資源稱為一個資源類；每個資源類中包含若干個同種資源，稱為資源實例Page592023/2/33.7死鎖的檢測與解除

系統(tǒng)死鎖可利用資源分配圖來描述。該圖是由一組結(jié)點N和一組邊E所組成的一個對偶G=（N，E），具有下述形成的定義和限制：（1）N被分為兩個互斥的子集，一組進(jìn)程結(jié)點P=（p1，p2，…，pn），一組資源結(jié)點R={r1，r2，…，rn}，N=P∪R。在圖3-19所示的例子中：1.資源分配圖(ResourceAllocationGraph)Page602023/2/33.7死鎖的檢測與解除3.7.1死鎖的檢測1.資源分配圖(ResourceAllocationGraph)圖3-19每類資源有多個時的情況P={p1，p2}，R={r1，r2}，N={r1，r2}∪{p1，p2}P1P2r1r2Page612023/2/3死鎖的檢測資源分配圖表示法:資源類:用方框表示（資源的不同類型）資源實例:用方框中的圓點表示（存在于每個資源中）進(jìn)程:用圓圈中加進(jìn)程名表示分配邊：資源實例進(jìn)程的一條有向邊申請邊：進(jìn)程資源類的一條有向邊P1P2r1r2獲得申請Page622023/2/3死鎖的檢測死鎖定理如果資源分配圖中沒有環(huán)路，則系統(tǒng)中沒有死鎖，如果圖中存在環(huán)路則系統(tǒng)中可能存在死鎖。如果每個資源類中只包含一個資源實例，則環(huán)路是死鎖存在的充分必要條件。Page632023/2/3死鎖的檢測死鎖定理有環(huán)有死鎖Page642023/2/3死鎖的檢測死鎖定理有環(huán)無死鎖Page652023/2/3死鎖的檢測死鎖定理——資源分配圖化簡找出一個既不阻塞又非獨立的進(jìn)程結(jié)點pi，在順利的情況下pi可獲得資源而繼續(xù)運行，再釋放所有資源。消去pi所有的請求邊和分配邊，將其變?yōu)楣铝⒔Y(jié)點再把相應(yīng)的資源分配給一個等待該資源的進(jìn)程，即將某進(jìn)程的申請邊變?yōu)榉峙溥呍谶M(jìn)行一系列化簡后若能消去圖中所有的邊，使所有進(jìn)程結(jié)點成為孤立結(jié)點，則稱該圖是可完全簡化的；否則是不可完全簡化的已經(jīng)證明：所有的化簡順序都得到相同的不可簡化圖。同樣可以證明，S為死鎖的充分條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理Page662023/2/3死鎖的檢測死鎖定理資源分配圖的簡化Page672023/2/3死鎖的檢測死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available它表示了m類資源中每一類資源的可用數(shù)目把不占用資源的進(jìn)程(向量Allocation:=0)記入L表中，即Li∪L從進(jìn)程集合中找到一個Requ