《計算機操作系統(tǒng) 》課件-3.7進程死鎖

死鎖的基本概念預(yù)防死鎖避免死鎖死鎖的檢測與解除3.7進程死鎖3.7.1死鎖的基本概念3.7進程死鎖1.死鎖的概念：例1：兩輛車過單車道的僵局例2.

競爭外部設(shè)備。設(shè)系統(tǒng)中有打印機、掃描儀各一臺，進程A、B的申請如下：掃描儀進程A進程B占用占用請求請求阻塞阻塞死鎖打印機3.7.1死鎖的基本概念3.7進程死鎖1.死鎖的概念：死鎖的定義：一組進程中，每個進程都無限等待被該組進程中另一進程所占有的且永遠無法釋放的資源，這種現(xiàn)象稱為進程死鎖，這一組進程就稱為死鎖進程。關(guān)于死鎖的一些結(jié)論：

參與死鎖的進程最少是兩個參與死鎖的進程至少有兩個已經(jīng)占有資源參與死鎖的所有進程都在等待資源參與死鎖的進程是當(dāng)前系統(tǒng)中所有進程的子集注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。3.7.1死鎖的基本概念3.7進程死鎖1.死鎖的概念：競爭資源：2.產(chǎn)生死鎖的原因3.7.1死鎖的基本概念3.7進程死鎖系統(tǒng)資源可重用資源消耗性資源不可剝奪資源可剝奪資源處理器，主存等打印機，磁帶機，隊列，文件等中斷，信號，消息等死鎖掃描儀進程A進程B占用占用請求請求阻塞阻塞死鎖打印機2.產(chǎn)生死鎖的原因3.7.1死鎖的基本概念3.7進程死鎖競爭資源競爭不可剝奪資源產(chǎn)生死鎖：執(zhí)行順序1：P1:…Release(S1);Request(S3);…P2:…Release(S2);Request(S1);…P3:…Release(S3);Request(S2);…執(zhí)行順序2：P1:…Request(S3);Release(S1);…P2:…Request(S1);Release(S2);…P3:…Request(S2);Release(S3);…進程P2進程P3進程P1臨時性資源S3臨時性資源S1臨時性資源S2請求產(chǎn)生產(chǎn)生請求產(chǎn)生請求不會“死鎖”“死鎖”2.產(chǎn)生死鎖的原因3.7.1死鎖的基本概念競爭資源競爭消耗性資源產(chǎn)生死鎖：合理的推進順序：如按曲線①、②和③不會產(chǎn)生“死鎖”進程推進順序不當(dāng)①③②DP2Req(S1)P2Req(S2)P1Req(S2)P1Req(S1)P1Rel(S2)P1Rel(S1)P2Rel(S2)P2Rel(S1)DP2P12.產(chǎn)生死鎖的原因3.7.1死鎖的基本概念①③②DP2Req(S1)P2Req(S2)P1Req(S2)P1Req(S1)P1Rel(S2)P1Rel(S1)P2Rel(S2)P2Rel(S1)D不合理的推進順序：如曲線④，產(chǎn)生“死鎖”。

④死鎖點區(qū)域D稱為“死鎖區(qū)”P2P1進程推進順序不當(dāng)2.產(chǎn)生死鎖的原因3.產(chǎn)生死鎖的必要條件互斥條件：請求和保持條件：不剝奪條件：環(huán)路等待條件：資源分配圖

這四個必要條件中只要有一個條件不滿足，都不會形成“死鎖”，又稱為Coffman條件。P1P2R1R2資源請求邊資源分配邊3.7.1死鎖的基本概念3.7進程死鎖4.處理死鎖的基本方法3.7.1死鎖的基本概念3.7進程死鎖

預(yù)防死鎖

避免死鎖

檢測與解除死鎖破壞產(chǎn)生死鎖的4個必要條件之一避免系統(tǒng)進入不安全狀態(tài)允許系統(tǒng)發(fā)生死鎖破壞占有且等待條件靜態(tài)分配資源：在作業(yè)調(diào)度時為選中的作業(yè)分配它所需要的所有資源，當(dāng)資源一旦分配給該作業(yè)后，在其整個運行期間這些資源為它獨占。

缺點：1）資源利用率低；

2）進程的運行可能被推遲，甚至產(chǎn)生“饑餓”現(xiàn)象；要求進程在沒有資源時才可申請資源：

允許動態(tài)申請資源3.7.2預(yù)防死鎖3.7進程死鎖2.破壞不可剝奪條件進程申請資源r時，有則分配；若沒有則需釋放其所占有的全部資源后進入阻塞狀態(tài)。進程申請資源r時，有則分配；若沒有則進一步判斷是否能從其他進程那里進行剝奪；若不能剝奪則進入阻塞狀態(tài)。

3.7.2預(yù)防死鎖3.7進程死鎖3.破壞循環(huán)等待條件：

采用按序分配資源策略：例如：1磁帶機，2掃描儀，3打印機，4繪圖儀，…，P1：申請2申請4…P2：申請2申請4…P3……P10優(yōu)點：較之前面兩種方法提高了資源利用率和系統(tǒng)吞吐量。缺點：(1)降低了添加新設(shè)備的靈活性；

(2)作業(yè)使用資源的順序與系統(tǒng)規(guī)定的申請順序不同時，會降低資

源的利用率3.7.2預(yù)防死鎖將所有的系統(tǒng)資源按類型進行線性排隊，并賦予不同的序號；所有進程對資源的請求應(yīng)嚴(yán)格按資源序號遞增順序提出。安全狀態(tài)定義

設(shè)系統(tǒng)中有n個進程，若存在一個進程序列<P1，P2，…，Pn>。使得進程Pi（i=1,2，…，n）以后還需要的資源可以通過系統(tǒng)現(xiàn)有空閑資源加上所有Pj（j<i）已占有的資源來滿足，則稱此時系統(tǒng)處于安全狀態(tài)，進程序列<P1，P2，…，Pn>稱為安全序列，因為各進程至少可以按照安全序列中的順序依次執(zhí)行完成。

如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

1.安全狀態(tài)3.7.3避免死鎖3.7進程死鎖安全狀態(tài)之例：

假設(shè)某系統(tǒng)共有15臺磁帶機和三個進程P0、P1、P2，各進程對磁帶機的最大需求數(shù)量、T0時刻已經(jīng)分配到的磁帶機數(shù)量、還需要的磁帶機數(shù)量以及系統(tǒng)剩余的可用磁帶機數(shù)量如下表所示：P1P0P21.安全狀態(tài)3.7.3避免死鎖3.7進程死鎖進程最大需求已分配數(shù)量還需要的數(shù)量剩余可用數(shù)量P012664P1523P21037

由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全順序分配資源，則系統(tǒng)可能由安全狀態(tài)進入不安全狀態(tài)。進程最大需求量已分配可用

P01264

P152

P2103

已分配還需要可用

66323

46

1.安全狀態(tài)3.7.3避免死鎖3.7進程死鎖在T0時刻P2又申請了一臺磁帶機，若將剩余4臺中的一臺分配給P2

則系統(tǒng)會進入不安全狀態(tài)。為什么？2.銀行家算法基本思想：

DijkstraE.W于1968年提出銀行家算法：

它的模型基于一個小城鎮(zhèn)的銀行家，該算法可描述如下：假定一個銀行家擁有資金，數(shù)量為∑，被N個客戶共享。銀行家對客戶提出下列約束條件：每個客戶必須預(yù)先說明自己所要求的最大資金量；每個客戶每次提出部分資金量申請；如果銀行滿足了某客戶對資金的最大需求量，那么，客戶在資金運作后，應(yīng)在有限時間內(nèi)全部歸還銀行。3.7.3避免死鎖3.7進程死鎖銀行家算法中的數(shù)據(jù)結(jié)構(gòu)①可利用資源向量Available[m]。其中的每一個元素代表一類可利用的資源數(shù)目Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。②最大需求矩陣Max[1..n,1..m]

該矩陣定義了系統(tǒng)中n個進程對m類資源的最大需求。Max[i,j]=K，則表示進程i需要Rj類資源的最大數(shù)目為K。2.銀行家算法3.7.3避免死鎖3.7進程死鎖③分配矩陣Allocation[1..n,1..m]

該矩陣表示系統(tǒng)中每個進程當(dāng)前已分配到的每類資源數(shù)量。

Allocation[i,j]=K，表示進程i當(dāng)前已分得Rj類資源的數(shù)目為K。④需求矩陣Need[1..n,1..m]

該矩陣表示每個進程尚需的各類資源數(shù)。Need[i,j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務(wù)。Need[i,j]=Max[i,j]-Allocation[i,j]⑤請求向量Requesti[m];

某進程提出的資源請求向量。

銀行家算法中的數(shù)據(jù)結(jié)構(gòu)2、銀行家算法3.7.3避免死鎖當(dāng)進程Pi提出資源申請Requesti[m]時，系統(tǒng)執(zhí)行下列步驟：⑴若Request[i]≤Need[i],轉(zhuǎn)⑵；否則錯誤返回；⑵若Request[i]≤Available，轉(zhuǎn)⑶；否則，表示尚無足夠資源，Pi須等待；⑶系統(tǒng)嘗試把資源分配給進程Pi，并修改以下數(shù)據(jù)結(jié)構(gòu)：

Available:=Allocation[i]:=Need[i]:=⑷執(zhí)行安全性算法：檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，則將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。Available-Request[i];Allocation[i]+Request[i];Need[i]-Request[i];

銀行家算法描述2、銀行家算法3.7.3避免死鎖①設(shè)置兩個臨時向量：工作向量Work:

表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work=Available;

Finish[n]:

它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］=false;當(dāng)有足夠資源分配給進程時，再令Finish［i］=true。安全性算法描述2、銀行家算法3.7.3避免死鎖②從進程集合中找到一個能滿足下述條件的進程：

1）Finish［i］=false;2）Need［i,j］≤Work［j］；

若找到，執(zhí)行步驟③，否則，執(zhí)行步驟④；③當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work［j］=

Finish［i］=

gotostep②;④如果所有進程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)Work［j］+Allocation［i,j］;true;安全性算法描述2、銀行家算法3.7.3避免死鎖例1：假定系統(tǒng)中有4個進程P0、P1、P2、P3，3類資源R1、R2、R3，數(shù)量分別為9、3、6，在T0時刻的資源分配情況如圖所示。

銀行家算法舉例2、銀行家算法3.7.3避免死鎖R1R2R3AvailableNeedAllocationMax

進程資源1001121100232261331442222202103420

112P0P1P2P3R1R2R3R1R2R3R1R2R3

WorkNeedAllocationWork+Allocation進程資源102222103420112623723934511100211002

623723934936P1P0P2P3truetruetruetrueFinish由于T0時刻存在安全序列{P1，P0，P2，P3},故此時系統(tǒng)是安全的。(1)判斷T0時刻的安全性R1R2R3R1R2R3R1R2R3R1R2R3（2）P1請求資源：Request1（1，0，1）時：①Request1（1，0，1）≦Need1（1，0，2）②Request1（1，0，1）≦Available（1，1，2）③試分配資源后，修改數(shù)據(jù)結(jié)構(gòu)。④對試分配后狀態(tài)進行安全性檢查：銀行家算法舉例R1R2R3AvailableNeedAllocationMax

進程資源1001121100232261331442222202103420

112P0P1P2P3R1R2R3R1R2R3R1R2R3612001011

WorkNeedAllocationWork+Allocation進程資源001222103420011623723934612100211002

623723934936P1P0P2P3truetruetruetrueFinish由于此時存在安全序列{P1，P0，P2，P3},故系統(tǒng)是安全的，可為P1分配上述資源。R1R2R3AvailableNeedAllocationMax

進程資源00612211002322613314422222001103420

011P0P1P2P3R1R2R3R1R2R3R1R2R3R1R2R3R1R2R3R1R2R3R1R2R3（3）P0請求資源：Request0（1，0，1）：①Request0（1，0，1）≦Need0（2，2，2）成立；②Request0（1，0，1）≦Available（0，1，1）不成立，故讓P0等待。

銀行家算法舉例R1R2R3AvailableNeedAllocationMax

進程資源00612211002322613314422222001103420

011P0P1P2P3R1R2R3R1R2R3R1R2R3（4）P2請求資源：Request2（0，0，1）時：①Request2（0，0，1）≦Need2（1，0，3）成立；②Request2（0，0，1）≦Available（0，1，1）成立；③試分配資源后，修改數(shù)據(jù)結(jié)構(gòu)。④對試分配后的狀態(tài)進行安全性檢查：由于Available（2,1,0）已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，所以不能為P0分配資源，而應(yīng)恢復(fù)原來的狀態(tài)，讓P0等待。

R1R2R3AvailableNeedAllocationMax

進程資源00612211002322613314422222001103420

011P0P1P2P3R1R2R3R1R2R3R1R2R32,1,21,0,20,1,0教材P153：第33題

課堂小組討論：解答：（1）系統(tǒng)安全，因為存在安全序列（P1,P3,P0,P2,P4），判斷過程略。

（2）系統(tǒng)要想避免死鎖，就必須保證每次分配后都能得到安全序列，否則就拒絕分配。根據(jù)這一原則，對于進程的請求應(yīng)考慮分配以后是否安全，若不安全，則不能進行此次分配。題目中有3個請求，按照順序依次考慮，先考慮能否滿足P1，分配后系統(tǒng)仍處于安全狀態(tài)，因此存在安全序列（P1,P3,P2,P0,P4）。滿足P1的請求之后，剩余資源為（2,2,0），對于P4的請求，由于系統(tǒng)沒有那么多剩余資源，因此無法滿足，系統(tǒng)拒絕P4的請求。最后考慮P0的請求，如果滿足P0，分配后剩余資源為（2,1,0），可以找到安全序列（P1,P3,P0,P2,P4），因此可以滿足P0的請求。（1）T0時刻系統(tǒng)資源分配情況如下表所示：

課堂小組討論：（3）銀行家算法的局限性：1）系統(tǒng)中進程數(shù)量及資源數(shù)量眾多，而且每當(dāng)進程申請資源時都要運行該算法，因此算法本身的運行開銷大；2）銀行家算法是按照最嚴(yán)苛的條件判斷安全性的，過于保守，會降低資源利用率及延遲進程推進速度；3）銀行家算法在尋找安全序列時完全沒有考慮進程之間的同步關(guān)系：相互協(xié)作進程間的前驅(qū)后繼關(guān)系，這在實際系統(tǒng)中是很不現(xiàn)實的。（1）T0時刻系統(tǒng)資源分配情況如下表所示：1.資源分配圖(ResourceAllocationGraph)

每類資源有多個時的情況3.7進程死鎖3.7.4死鎖的檢測與解除P1P3P2●●R1●●R2●●●R3簡化資源分配圖：

如果資源分配圖能完全簡化，則系統(tǒng)中沒有死鎖；否則系統(tǒng)存在死鎖。2.死鎖定理

（1）在資源分配圖中，找出一個既非獨立又不阻塞的進程節(jié)點Pi，如果找到轉(zhuǎn)（2）；否則轉(zhuǎn)（3）；（2）去掉Pi的所有邊，使其成為一個獨立節(jié)點，并轉(zhuǎn)（1）；（3）判斷是否所有節(jié)點都成為獨立節(jié)點？如果是，稱為資源分配圖能完全簡化，系統(tǒng)無死鎖；否則系統(tǒng)存在死鎖。3.7.4死鎖的檢測與解除P1P3P2●●R1●●R2●●●R3P4有死鎖無死鎖例：2.死鎖定理

有死鎖無死鎖例：2.死鎖定理

數(shù)據(jù)結(jié)構(gòu)：可利用資源向量Available[m];

資源分配矩陣Allocation[n,m];

資源請求矩陣Request[n,m]；工作向量Work=Available

finish[n]向量：

若Allocation[i]=0,則finish[i]=True；

否則finish[i]=False

3.死鎖檢測算法：Coffman算法3.7進程死鎖3.7.4死鎖的檢測與解除算法描述：work=available;Finish[i]=False或True;(i=0,1,2,…n-1)①尋找同時滿足下述條件的進程：

Finish[i]=False;Requesti≤Work

若找到，則轉(zhuǎn)②；否則轉(zhuǎn)③；②執(zhí)行：Work=Work+Allocationi，F(xiàn)inish[i]=True；

再轉(zhuǎn)回第①步③判斷：若對所有i=(0,1,2,…n-1),Finish[i]=True，則無死鎖；否則，若Finish[i]=False，則進程Pi死鎖

3.死鎖檢測算法：Coffman算法3.7進程死鎖3.7.4死鎖的檢測與解除綜合考慮幾個因素：4.死鎖檢測時機

3.7進程死鎖3.7.4死鎖的檢測與解除

死鎖出現(xiàn)的頻繁