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

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

調(diào)度算法

實時調(diào)度

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

預防死鎖的方法

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

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

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

進程在運行過程中，請求和釋放資源的順序不當，導致了進程死鎖。

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

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

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

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

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

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

調(diào)度算法

實時調(diào)度

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

預防死鎖的方法

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

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

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

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

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

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

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

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

(2)如果Requesti[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。Page392023/6/9(3)系統(tǒng)試探著把資源分配給進程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)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。Page402023/6/93.安全性算法(1)設置兩個向量：

①工作向量Work:它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work:=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish[i]:=false;當有足夠資源分配給進程時，再令Finish[i]:=true。Page412023/6/9(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;

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

假定系統(tǒng)中有五個進程｛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/6/9(1)T0時刻的安全性：圖3-16T0時刻的安全序列truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在T0時刻處于安全狀態(tài)。Page442023/6/9

(2)P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查：

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

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

(3)P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查：

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

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

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

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

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

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

調(diào)度算法

實時調(diào)度

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

預防死鎖的方法

死鎖的檢測與解除Page542023/6/9死鎖的檢測與解除死鎖的檢測死鎖的解除Page552023/6/9死鎖的檢測

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

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

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

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