OS第3章死鎖(MR)

1、操作系統(tǒng)操作系統(tǒng)第3章 死鎖本章教學(xué)內(nèi)容v3.1 3.1 資源資源v3.2 3.2 死鎖概念死鎖概念v3.3 3.3 死鎖的預(yù)防死鎖的預(yù)防v3.4 3.4 死鎖的避免死鎖的避免v3.5 3.5 死鎖的檢測和恢復(fù)死鎖的檢測和恢復(fù)v3.6 3.6 處理死鎖的綜合方式處理死鎖的綜合方式v3.7 3.7 本章小結(jié)本章小結(jié)3.1 資源3.1.1 3.1.1 資源使用模式資源使用模式 申請申請 使用使用 釋放釋放3.1.2 可剝奪資源與不可剝奪資源按占有方式劃分：按占有方式劃分： 可剝奪資源可剝奪資源 當(dāng)該資源被某進程擁有后，其它進程仍可當(dāng)該資源被某進程擁有后，其它進程仍可以把它剝奪過去為己所用，并且不會

2、產(chǎn)生任以把它剝奪過去為己所用，并且不會產(chǎn)生任何不良影響。例如，內(nèi)存就是可剝奪資源。何不良影響。例如，內(nèi)存就是可剝奪資源。 不可剝奪資源不可剝奪資源 該資源一旦被某進程占有，則其它進程不該資源一旦被某進程占有，則其它進程不能強行搶占，必須由擁有者自動釋放，否則能強行搶占，必須由擁有者自動釋放，否則會引起相關(guān)計算的失效。如光盤刻錄機。會引起相關(guān)計算的失效。如光盤刻錄機。 死鎖和不可剝奪資源有關(guān)死鎖和不可剝奪資源有關(guān) 3.2 死鎖概念v什么是死鎖什么是死鎖v死鎖的條件死鎖的條件v資源分配圖資源分配圖v處理死鎖的方法處理死鎖的方法3.2 死鎖概念 3.2.1 3.2.1 什么是死鎖什么是死鎖 1 1死

3、鎖示例死鎖示例汽車過窄橋時的沖突汽車過窄橋時的沖突在計算機系統(tǒng)中，涉及軟件、硬件資源的進在計算機系統(tǒng)中，涉及軟件、硬件資源的進程都可能發(fā)生死鎖程都可能發(fā)生死鎖 DijkstraDijkstra在在19651965年提出了死鎖。年提出了死鎖。死鎖的概念v 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因: :多個并發(fā)進程因多個并發(fā)進程因競爭資源而造成的一種僵局，若無競爭資源而造成的一種僵局，若無外力的作用，這些進程將都不能再外力的作用，這些進程將都不能再繼續(xù)執(zhí)行。繼續(xù)執(zhí)行。 v死鎖：死鎖：是指在一個進程集合中的每個進程是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能都在等待僅由該集合中的另一個進程

4、才能引發(fā)的事件而無限期地僵持下去的局面。引發(fā)的事件而無限期地僵持下去的局面。v計算機系統(tǒng)產(chǎn)生死鎖的根本原因就是計算機系統(tǒng)產(chǎn)生死鎖的根本原因就是資源資源有限有限且且操作不當(dāng)操作不當(dāng)v死鎖的危害死鎖的危害 系統(tǒng)癱瘓系統(tǒng)癱瘓 資源浪費資源浪費 死鎖的概念 什么是死鎖v有兩個進程有兩個進程A A和和B B，競爭兩個資源，競爭兩個資源R R和和S S，這兩個資源，這兩個資源都是不可剝奪資源。都是不可剝奪資源。 進程進程A A 進程進程B B 申請并占用申請并占用R R 申請并占用申請并占用S S 申請并占用申請并占用S S 申請并占用申請并占用R R 釋放釋放R R 釋放釋放S S 釋放釋放S S 釋放

5、釋放R R 什么是死鎖進程推進順序?qū)σl(fā)死鎖的影響進程推進順序?qū)σl(fā)死鎖的影響死鎖的概念v 產(chǎn)生死鎖有四個必要條件：產(chǎn)生死鎖有四個必要條件：（1 1）互斥條件。）互斥條件。 （2 2）不剝奪條件。）不剝奪條件。（3 3）部分分配（請求和保持條件）部分分配（請求和保持條件）（4 4）環(huán)路等待條件。）環(huán)路等待條件。 只要有一個必要條件不滿足，則死鎖就只要有一個必要條件不滿足，則死鎖就可以排除?？梢耘懦?.2.3 資源分配圖1 1資源分配圖的構(gòu)成資源分配圖的構(gòu)成v由由結(jié)對結(jié)對組成：組成： G G = (= (V V, , E E) ) V V是是頂點頂點的集合，的集合，E E是是邊邊的集合。的集合

6、。 頂點集合可分為兩部分：頂點集合可分為兩部分： P P=p p1 1, , p p2 2, , , , p pn n 由系統(tǒng)中所有活動進程組成由系統(tǒng)中所有活動進程組成 R R=r r1 1, , r r2 2, , , , r rm m 由系統(tǒng)中全部資源類型組成由系統(tǒng)中全部資源類型組成v有向邊有向邊p pi i r rj j稱為稱為申請邊申請邊 有向邊有向邊r rj j p pi i 稱為稱為賦給邊賦給邊v在資源分配圖中，通常用圓圈表示每個進程，用方在資源分配圖中，通常用圓圈表示每個進程，用方框表示每種資源類型?？虮硎久糠N資源類型。2 2資源分配圖示例資源分配圖示例（1 1）集合）集合P P

7、, , R R和和E E如下：如下： P P=p p1, 1, p p2, 2, p p33 R R=r r1, 1, r r2, 2, r r3, 3, r r44 E E=p p11r r1, 1, p p22r r3, 3, r r11p p2, 2, r r22p p2, 2, r r22p p1, 1, r r33p p33（2 2）資源數(shù)量）資源數(shù)量 分別為分別為1 1，2 2，1 1，3 3（3 3）進程狀態(tài)）進程狀態(tài) 該圖不含環(huán)路，沒有死鎖該圖不含環(huán)路，沒有死鎖 資源分配圖示例資源分配圖示例3.2.3 資源分配圖3 3環(huán)路與死鎖環(huán)路與死鎖 如果每類資源的實體都只有一個，如果每類

8、資源的實體都只有一個，那么圖中出現(xiàn)環(huán)路就說明死鎖了。那么圖中出現(xiàn)環(huán)路就說明死鎖了。3.2.3 資源分配圖 環(huán)路與死鎖 如果每類資源的實體不止一個，那么資源分配圖如果每類資源的實體不止一個，那么資源分配圖中出現(xiàn)環(huán)路并不表明一定出現(xiàn)死鎖。中出現(xiàn)環(huán)路并不表明一定出現(xiàn)死鎖。 資源分配圖中存在環(huán)路是死鎖產(chǎn)生的必要條件，資源分配圖中存在環(huán)路是死鎖產(chǎn)生的必要條件，但不是充分條件。但不是充分條件。3.2.4 處理死鎖的方法利用某些協(xié)議預(yù)防或避免死鎖，保證系利用某些協(xié)議預(yù)防或避免死鎖，保證系統(tǒng)不會進入死鎖狀態(tài)。統(tǒng)不會進入死鎖狀態(tài)。允許系統(tǒng)進入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)允許系統(tǒng)進入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)并克服它。并克

9、服它。完全忽略這個問題，好像系統(tǒng)中從來也完全忽略這個問題，好像系統(tǒng)中從來也不會出現(xiàn)死鎖。不會出現(xiàn)死鎖。3.3 死鎖的預(yù)防3.3.1 3.3.1 破壞互斥條件破壞互斥條件3.3.2 3.3.2 破壞占有且等待條件破壞占有且等待條件 預(yù)分資源策略：預(yù)分資源策略：靜態(tài)分配靜態(tài)分配 “空手空手”申請資源策略：申請資源策略：不占有資源時才可不占有資源時才可以申請資源以申請資源 存在以下存在以下4 4個主要缺點個主要缺點 不可預(yù)測不可預(yù)測 利用率低利用率低 降低并發(fā)性降低并發(fā)性 “饑餓饑餓” ” 現(xiàn)象現(xiàn)象3.3.3 破壞非搶占條件v隱式搶占方式（申請資源失敗釋放隱式搶占方式（申請資源失敗釋放所有資源）所有

10、資源） v搶占等待者資源搶占等待者資源3.3.4 破壞循環(huán)等待條件資源有序分配策略資源有序分配策略 資源編號資源編號 設(shè)設(shè)R R=r r1 1, , r r2 2, , , , r rm m ，表示一組資源，表示一組資源 定義一對一的函數(shù)定義一對一的函數(shù)F F：R RN N，N N是一組自然數(shù)是一組自然數(shù) 如：如：F F（磁帶機）（磁帶機）= 1= 1，F(xiàn) F（磁盤機）（磁盤機）= 5= 5，F(xiàn) F（打（打印機）印機）= 12= 12 依序分配依序分配 約定：所有進程對資源的申請嚴格按照序號約定：所有進程對資源的申請嚴格按照序號遞增的次序進行。遞增的次序進行。 破壞循環(huán)等待條件先棄大，再取小先

11、棄大，再取小 一個進程申請資源一個進程申請資源r rj j，它應(yīng)釋放所有滿足，它應(yīng)釋放所有滿足F F( (r ri i)F F( (r rj j) ) 關(guān)系的資源關(guān)系的資源r ri i 這兩種辦法都是可行的，都可排除環(huán)路等待條件這兩種辦法都是可行的，都可排除環(huán)路等待條件 優(yōu)點：優(yōu)點：資源利用率和系統(tǒng)吞吐量都有很大提高資源利用率和系統(tǒng)吞吐量都有很大提高缺點：缺點：v資源請求受限，合理編號困難，增加系統(tǒng)開銷。資源請求受限，合理編號困難，增加系統(tǒng)開銷。v暫不使用的資源也需提前申請，增加資源占用時暫不使用的資源也需提前申請，增加資源占用時間。間。3.4 3.4 死鎖的避免死鎖的避免排除死鎖的排除死鎖的

12、動態(tài)策略。動態(tài)策略。關(guān)鍵是確定資源分配的安關(guān)鍵是確定資源分配的安全性全性 3.4.1 3.4.1 安全狀態(tài)安全狀態(tài)v在當(dāng)前分配狀態(tài)下，進程的安全序列在當(dāng)前分配狀態(tài)下，進程的安全序列 P P1 1, , P P2 2, , , P Pn n 是：是：若對于每一個進程若對于每一個進程P Pi i（11i in n），它需要的附加資源可被系統(tǒng)中），它需要的附加資源可被系統(tǒng)中當(dāng)前可用資源與所有進程當(dāng)前可用資源與所有進程P Pj j（j ji i）當(dāng)前當(dāng)前占有資源之和所滿足，則占有資源之和所滿足，則 P P1 1, , P P2 2, , , P Pn n 為一個安全序列。為一個安全序列。 這時系統(tǒng)處于

13、安全狀態(tài)。這時系統(tǒng)處于安全狀態(tài)。存在安全序列時一定不會有死鎖發(fā)生存在安全序列時一定不會有死鎖發(fā)生 死鎖是不安全狀態(tài)中的特例死鎖是不安全狀態(tài)中的特例 安全狀態(tài)安全狀態(tài)時時 刻刻已占有臺數(shù)已占有臺數(shù)最大需求臺數(shù)最大需求臺數(shù)當(dāng)前可用臺當(dāng)前可用臺數(shù)數(shù)進程進程P1進程進程P2進程進程P3進程進程P1進程進程P2進程進程P3T03229473T13429471T2302975T3307970T430097T59001T600010 不安全狀態(tài)示意不安全狀態(tài)示意時刻時刻已占有臺數(shù)已占有臺數(shù)最大需求臺數(shù)最大需求臺數(shù)當(dāng)前當(dāng)前可用可用臺數(shù)臺數(shù)進程進程P1進程進程P2進程進程P3進程進程P1進程進程P2進程進程P3

14、T03229473T14229472T24429470T3402974v若不按照安全序列分配資源，則系統(tǒng)可能會由安全若不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)轉(zhuǎn)換為不安全狀態(tài)狀態(tài)轉(zhuǎn)換為不安全狀態(tài) 死鎖的避免死鎖的避免死鎖狀態(tài)是不安全狀態(tài)。死鎖狀態(tài)是不安全狀態(tài)。如果系統(tǒng)處于不安全狀態(tài)，并不意味著它就如果系統(tǒng)處于不安全狀態(tài)，并不意味著它就在死鎖狀態(tài)，而是表示存在導(dǎo)致死鎖的危機。在死鎖狀態(tài)，而是表示存在導(dǎo)致死鎖的危機。 如果一個進程申請的資源當(dāng)前是可用的，但如果一個進程申請的資源當(dāng)前是可用的，但為了避免死鎖，該進程也可能必須等待。此時為了避免死鎖，該進程也可能必須等待。此時資源利用率會下降。資

15、源利用率會下降。練習(xí)練習(xí): :假定系統(tǒng)中有三個進程假定系統(tǒng)中有三個進程P P1 1、P P2 2和和P P3 3，共有，共有1212臺磁帶機。進程臺磁帶機。進程P P1 1總共要求總共要求1010臺磁帶機，臺磁帶機，P P2 2和和P P3 3分別要求分別要求9 9臺和臺和4 4臺。假設(shè)在臺。假設(shè)在T T0 0時刻，進程時刻，進程P P1 1、P P2 2和和P P3 3已分別獲得已分別獲得5 5臺、臺、2 2臺和臺和2 2臺磁帶機，尚有臺磁帶機，尚有3 3臺空閑未分配臺空閑未分配。求安全序列。求安全序列。 進進 程程 最大需求最大需求 已分配已分配 可用可用 P P1 1P P2 2P P3

16、 310109 94 45 52 22 2死鎖的排除方法死鎖的排除方法3.4.2 資源分配圖算法資源分配圖算法v資源類資源類 單體資源類單體資源類 多體資源類多體資源類v單體資源類的資源分配圖單體資源類的資源分配圖 除申請邊和賦給邊之外，還要有一種稱為除申請邊和賦給邊之外，還要有一種稱為“要求邊要求邊”的新的新邊。要求邊邊。要求邊 p pi i r rj j表示進程表示進程p pi i能夠申請能夠申請資源資源r rj j，有時用虛線表示。，有時用虛線表示。資源分配圖示例資源分配圖示例3.4.3 銀行家算法銀行家算法v“銀行家算法銀行家算法”（BankerBankers Algorithms A

17、lgorithm）針對多體資源類針對多體資源類 v設(shè)計思想：設(shè)計思想： 當(dāng)用戶申請一組資源時，系統(tǒng)必須做出判斷：當(dāng)用戶申請一組資源時，系統(tǒng)必須做出判斷：如果把這些資源分出去，系統(tǒng)是否還處于安全如果把這些資源分出去，系統(tǒng)是否還處于安全狀態(tài)。若是，就可以分出這些資源；否則，該狀態(tài)。若是，就可以分出這些資源；否則，該申請暫不予滿足。申請暫不予滿足。銀行家算法數(shù)據(jù)結(jié)構(gòu)銀行家算法數(shù)據(jù)結(jié)構(gòu)令令n n表示系統(tǒng)中進程的數(shù)目，表示系統(tǒng)中進程的數(shù)目，m m表示資源分類數(shù)。表示資源分類數(shù)。 AvailableAvailable是一個長度為是一個長度為m m的向量，它表示每類資源可的向量，它表示每類資源可用的數(shù)量。用

18、的數(shù)量。AvailableAvailablej j=k k，表示，表示r rj j類資源可用的數(shù)類資源可用的數(shù)量是量是k k。 MaxMax是一個是一個n nm m矩陣，它表示每個進程對資源的最大矩陣，它表示每個進程對資源的最大需求。需求。MaxMaxi i, , j j=k k，表示進程，表示進程p pi i至多可申請至多可申請k k個個r rj j類資類資源單位。源單位。 AllocationAllocation是一個是一個n nm m矩陣，它表示當(dāng)前分給每個進矩陣，它表示當(dāng)前分給每個進程的資源數(shù)目。程的資源數(shù)目。Allocation Allocation i i, , j j=k k，表

19、示進程，表示進程p pi i當(dāng)當(dāng)前分到前分到k k個個r rj j類資源。類資源。 NeedNeed是一個是一個n nm m矩陣，它表示每個進程還缺少多少資矩陣，它表示每個進程還缺少多少資源。源。Need Need i i, , j j=k k，表示進程，表示進程pipi尚需尚需k k個個r rj j類資源才類資源才能完成其任務(wù)。能完成其任務(wù)。3.4.3 銀行家算法銀行家算法1 1資源分配算法資源分配算法v令令RequestRequesti i表示進程表示進程pipi的申請向量。的申請向量。RequestRequesti i j j= = k k，表示進程表示進程p pi i需要申請需要申請k

20、 k個個r rj j類資源。當(dāng)進程類資源。當(dāng)進程p pi i申請資源時申請資源時，就執(zhí)行下列動作：，就執(zhí)行下列動作： 若若RequestRequesti iNeedNeedi i，表示出錯，表示出錯， 如果如果RequestRequesti iAvailableAvailable，則，則p pi i等待。等待。 假設(shè)系統(tǒng)把申請的資源分給進程假設(shè)系統(tǒng)把申請的資源分給進程p pi i，則應(yīng)對有關(guān)數(shù)據(jù)，則應(yīng)對有關(guān)數(shù)據(jù)結(jié)構(gòu)進行修改：結(jié)構(gòu)進行修改： AvailableAvailable：= Available Request= Available Requesti i Allocation Alloca

21、tioni i：= Allocation= Allocationi i + Request+ Requesti i Need Needi i：= Need= Needi i Request Requesti i 系統(tǒng)執(zhí)行安全性算法，查看此時系統(tǒng)狀態(tài)是否安全。系統(tǒng)執(zhí)行安全性算法，查看此時系統(tǒng)狀態(tài)是否安全。如果是安全的，就實際分配資源，滿足進程如果是安全的，就實際分配資源，滿足進程p pi i 的此次的此次申請；否則，若新狀態(tài)是不安全的，則申請；否則，若新狀態(tài)是不安全的，則p pi i等待，對所申等待，對所申請資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成之前請資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成之

22、前的情況。的情況。2 2安全性算法安全性算法 令令WorkWork和和FinishFinish分別表示長度為分別表示長度為m m和和n n的向量，最初，的向量，最初，置置Work= AvailableWork= Available，F(xiàn)inishFinishi i=false=false，i i=1, 2, =1, 2, n n 搜尋滿足下列條件的搜尋滿足下列條件的i i值：值： FinishFinishi i=false=false，且，且NeedNeedi iWorkWork。 若沒有找到，則轉(zhuǎn)向。若沒有找到，則轉(zhuǎn)向。 修改數(shù)據(jù)值：修改數(shù)據(jù)值： WorkWork：=Work+ Allocat

23、ion=Work+ Allocationi i（pipi釋放所占的全部釋放所占的全部資源）資源） FinishFinishi i=true=true 轉(zhuǎn)向。轉(zhuǎn)向。 若若FinishFinishi i=true=true對所有對所有i i都成立（任一進程都可能是都成立（任一進程都可能是p pi i），則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀），則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。態(tài)。v假定系統(tǒng)中有假定系統(tǒng)中有4 4個進程個進程A, B, C, DA, B, C, D和三類資源和三類資源R R1 1, , R R2 2和和R R3 3，各自的數(shù)量分別為，各自的數(shù)量分別為9, 39, 3

24、和和6 6個單位。個單位。進程進程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420 資源資源情況情況3算法應(yīng)用示例 資源資源 情情況況WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723trueC723103211934trueD934420002936true進程3算法應(yīng)用示例v 假定系統(tǒng)中有假定系統(tǒng)中有4 4個進程個進程A

25、, B, C, DA, B, C, D和三類資源和三類資源R R1 1, , R R2 2和和R R3 3，各自，各自的數(shù)量分別為的數(shù)量分別為9, 39, 3和和6 6個單位。個單位。v （1 1）T T0 0時刻是安全的，存在一個安全序列時刻是安全的，存在一個安全序列B, A, C, DB, A, C, D v假定系統(tǒng)中有假定系統(tǒng)中有4 4個進程個進程A, B, C, DA, B, C, D和三類資源和三類資源R R1 1, , R R2 2和和R R3 3，各自的數(shù)量分別為，各自的數(shù)量分別為9, 39, 3和和6 6個單位。個單位。v進程進程A A請求資源，進程請求資源，進程A A發(fā)出請求

26、發(fā)出請求Request(1, 0, 1)Request(1, 0, 1) 進程進程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420資源資源情況情況 資源情資源情況況進進 程程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系統(tǒng)進入不安全的狀態(tài)系統(tǒng)進入不安全的狀態(tài) 不能為進程不能為進程A A分配所申請的資源分配所申請的

27、資源 3算法應(yīng)用示例v 假定系統(tǒng)中有假定系統(tǒng)中有4 4個進程個進程A, B, C, DA, B, C, D和三類資源和三類資源R R1 1, , R R2 2和和R R3 3，各自，各自的數(shù)量分別為的數(shù)量分別為9, 39, 3和和6 6個單位。個單位。v 進程進程A A請求資源，進程請求資源，進程A A發(fā)出請求發(fā)出請求Request(1, 0, 1)Request(1, 0, 1) 銀行家算法銀行家算法v優(yōu)點優(yōu)點： 限制條件少限制條件少 資源利用程度提高資源利用程度提高 v缺點：缺點： 難以保證進程數(shù)固定不變難以保證進程數(shù)固定不變 未考慮實時進程快速響應(yīng)未考慮實時進程快速響應(yīng) 增加了系統(tǒng)開銷增

28、加了系統(tǒng)開銷 進程進程 AllocationMaxNeedAvailableP1 0，1，0 7，5，3 P2 2，0，0 3，2，2 P3 3，0，2 9，0，2 P4 2，1，12，2，2 P5 0，0，24，3，3 v假設(shè)某系統(tǒng)中有假設(shè)某系統(tǒng)中有3類資源類資源(R1、R2、R3)，每一種資源的可用量，每一種資源的可用量為（為（10，5，7）：）：（1）當(dāng)前系統(tǒng)是否安全）當(dāng)前系統(tǒng)是否安全 （2）進程）進程P1發(fā)出請求向量發(fā)出請求向量Request1（2，0，4），系統(tǒng)能否將資），系統(tǒng)能否將資源分配給它？源分配給它？（3）如果進程）如果進程P3發(fā)出請求向量發(fā)出請求向量Request3（4，0

29、，0），系統(tǒng)能否），系統(tǒng)能否將資源分配給它？將資源分配給它？（4）如果此刻進程）如果此刻進程P2發(fā)出請求向量發(fā)出請求向量Request2（1，0，2），系統(tǒng)），系統(tǒng)能否將資源分配給它？能否將資源分配給它？（5）在（在（4）的基礎(chǔ)上）的基礎(chǔ)上如果又有進程如果又有進程P5發(fā)出請求向量發(fā)出請求向量Request5（2，2，0），系統(tǒng)能否將資源分配給它？），系統(tǒng)能否將資源分配給它？3.5 死鎖的檢測和恢復(fù)死鎖的檢測和恢復(fù)v 死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機構(gòu)，當(dāng)死鎖發(fā)生時，該機構(gòu)能夠檢測機構(gòu)，當(dāng)死鎖發(fā)生時，該機構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，且能通過外到死鎖發(fā)生的位

30、置和原因，且能通過外力破壞死鎖發(fā)生的必要條件，從而使并力破壞死鎖發(fā)生的必要條件，從而使并發(fā)進程從死鎖狀態(tài)中解脫出來。發(fā)進程從死鎖狀態(tài)中解脫出來。3.5.1 3.5.1 對單體資源類的死鎖檢測對單體資源類的死鎖檢測等待圖等待圖資源分配圖的變形資源分配圖的變形 從資源分配圖中去掉表示資源類的節(jié)點，且把相應(yīng)從資源分配圖中去掉表示資源類的節(jié)點，且把相應(yīng)邊折疊在一起得到的邊折疊在一起得到的資源分配圖和對應(yīng)的等待圖資源分配圖和對應(yīng)的等待圖3.5.2 3.5.2 對多體資源類的死鎖檢測對多體資源類的死鎖檢測v采用若干隨時間變化的數(shù)據(jù)結(jié)構(gòu)，與銀行家算采用若干隨時間變化的數(shù)據(jù)結(jié)構(gòu)，與銀行家算法相似法相似 Ava

31、ilableAvailable是一個長度為是一個長度為m m的向量的向量 AllocationAllocation是一個是一個n nm m的矩陣的矩陣 RequestRequest是一個是一個n nm m的矩陣，的矩陣，RequestRequesti i, , j j=k k，表示進程，表示進程p pi i正申請正申請k k個個r rj j類資源類資源 仍把矩陣仍把矩陣AllocationAllocation和和RequestRequest的行作為向量的行作為向量對待，并分別表示為對待，并分別表示為AllocationAllocationi i和和RequestRequesti i 對多體資源

32、類的死鎖檢測對多體資源類的死鎖檢測檢測算法：檢測算法： 簡單地調(diào)查尚待完成的各個進程所有可能的分配序列簡單地調(diào)查尚待完成的各個進程所有可能的分配序列 令令WorkWork和和FinishFinish分別表示長度為分別表示長度為m m和和n n的向量，初始化的向量，初始化 Work=AvailableWork=Available；對于；對于i i=1, 2, =1, 2, n n 如果如果AllocationAllocationi i00，則，則FinishFinishi i=false=false；否則；否則FinishFinishi i=true=true。 尋找一個下標尋找一個下標i i，

33、它應(yīng)滿足條件：，它應(yīng)滿足條件： FinishFinishi i=false=false且且RequestRequesti iWorkWork 若找不到這樣的若找不到這樣的i i，則轉(zhuǎn)到。，則轉(zhuǎn)到。 修改數(shù)據(jù)值：修改數(shù)據(jù)值： Work=Work+AllocationWork=Work+Allocationi i Finish Finishi i=true=true 轉(zhuǎn)向。轉(zhuǎn)向。 若存在某些若存在某些i i（11i in n），），F(xiàn)inishFinishi i=false=false，則系統(tǒng)處于死，則系統(tǒng)處于死鎖狀態(tài)。此外，若鎖狀態(tài)。此外，若FinishFinishi i=false=false

34、，則進程，則進程p pi i處于死鎖環(huán)中。處于死鎖環(huán)中。 對多體資源類的死鎖檢測對多體資源類的死鎖檢測v設(shè)系統(tǒng)中有設(shè)系統(tǒng)中有5 5個進程個進程p p1 1, , p p2 2, , p p3 3, , p p4 4和和p p5 5，有，有3 3類資源類資源R R1 1, , R R2 2和和R R3 3 ，每類資源的個數(shù)分別為，每類資源的個數(shù)分別為7, 2, 67, 2, 6。 AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202p3303000p4211100p5002002資源情況資源情況進程進程假定，進程假定，進程

35、p p3 3現(xiàn)在申請一個單位的現(xiàn)在申請一個單位的R R3 3資源資源AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202000p3303001p4211100p5002002 由于對所有由于對所有i i=1, 2,=1, 2, 5, 5，AllocationAllocationi i00，所以，所以FinishFinishi i=false=false。 資源情況資源情況進程進程3.5.3 3.5.3 從死鎖中恢復(fù)從死鎖中恢復(fù)v通過搶占資源實現(xiàn)恢復(fù)通過搶占資源實現(xiàn)恢復(fù)v通過回退執(zhí)行實現(xiàn)恢復(fù)通過回退執(zhí)行實現(xiàn)恢復(fù) 發(fā)生死鎖的某個進程或某些進程回退到它發(fā)生死鎖的某個進程或某些進程回退到它取得另外某個資源之前的一個檢查點取得另外某個資源之前的一個檢查點 系統(tǒng)中應(yīng)保存一系列檢查點的文件系統(tǒng)中應(yīng)保存一系列檢查點的文件 要確定這個進程后退多遠要確定這個進程后退多遠 “全體全體”回退方式回退方式v通過殺掉進程實現(xiàn)恢復(fù)通過殺掉進程實現(xiàn)恢復(fù) 終止所有的死鎖進程。終止所有的死鎖進程。 一次終止一個進程，直至消除死鎖環(huán)路。一次終止一個進程，直至消除死鎖環(huán)路。3.5.4 3.5.4 “饑餓饑餓”狀態(tài)狀態(tài)v在某些策略下，系統(tǒng)會出