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 死鎖的檢測(cè)和恢復(fù)死鎖的檢測(cè)和恢復(fù)v3.6 3.6 處理死鎖的綜合方式處理死鎖的綜合方式v3.7 3.7 本章小結(jié)本章小結(jié)3.1 資源3.1.1 3.1.1 資源使用模式資源使用模式 申請(qǐng)申請(qǐng) 使用使用 釋放釋放3.1.2 可剝奪資源與不可剝奪資源按占有方式劃分：按占有方式劃分： 可剝奪資源可剝奪資源 當(dāng)該資源被某進(jìn)程擁有后，其它進(jìn)程仍可當(dāng)該資源被某進(jìn)程擁有后，其它進(jìn)程仍可以把它剝奪過(guò)去為己所用，并且不會(huì)

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

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

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

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

6、。 頂點(diǎn)集合可分為兩部分：頂點(diǎn)集合可分為兩部分： P P=p p1 1, , p p2 2, , , , p pn n 由系統(tǒng)中所有活動(dòng)進(jìn)程組成由系統(tǒng)中所有活動(dòng)進(jìn)程組成 R R=r r1 1, , r r2 2, , , , r rm m 由系統(tǒng)中全部資源類(lèi)型組成由系統(tǒng)中全部資源類(lèi)型組成v有向邊有向邊p pi i r rj j稱(chēng)為稱(chēng)為申請(qǐng)邊申請(qǐng)邊 有向邊有向邊r rj j p pi i 稱(chēng)為稱(chēng)為賦給邊賦給邊v在資源分配圖中，通常用圓圈表示每個(gè)進(jìn)程，用方在資源分配圖中，通常用圓圈表示每個(gè)進(jìn)程，用方框表示每種資源類(lèi)型?？虮硎久糠N資源類(lèi)型。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）進(jìn)程狀態(tài)）進(jìn)程狀態(tài) 該圖不含環(huán)路，沒(méi)有死鎖該圖不含環(huán)路，沒(méi)有死鎖 資源分配圖示例資源分配圖示例3.2.3 資源分配圖3 3環(huán)路與死鎖環(huán)路與死鎖 如果每類(lèi)資源的實(shí)體都只有一個(gè)，如果每類(lèi)

8、資源的實(shí)體都只有一個(gè)，那么圖中出現(xiàn)環(huán)路就說(shuō)明死鎖了。那么圖中出現(xiàn)環(huán)路就說(shuō)明死鎖了。3.2.3 資源分配圖 環(huán)路與死鎖 如果每類(lèi)資源的實(shí)體不止一個(gè)，那么資源分配圖如果每類(lèi)資源的實(shí)體不止一個(gè)，那么資源分配圖中出現(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)不會(huì)進(jìn)入死鎖狀態(tài)。統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)。允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)并克服它。并克

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

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

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

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

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

14、T03229473T14229472T24429470T3402974v若不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全若不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(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)致死鎖的危機(jī)。在死鎖狀態(tài)，而是表示存在導(dǎo)致死鎖的危機(jī)。 如果一個(gè)進(jìn)程申請(qǐng)的資源當(dāng)前是可用的，但如果一個(gè)進(jìn)程申請(qǐng)的資源當(dāng)前是可用的，但為了避免死鎖，該進(jìn)程也可能必須等待。此時(shí)為了避免死鎖，該進(jìn)程也可能必須等待。此時(shí)資源利用率會(huì)下降。資

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

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

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

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

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

20、 k個(gè)個(gè)r rj j類(lèi)資源。當(dāng)進(jìn)程類(lèi)資源。當(dāng)進(jìn)程p pi i申請(qǐng)資源時(shí)申請(qǐng)資源時(shí)，就執(zhí)行下列動(dòng)作：，就執(zhí)行下列動(dòng)作： 若若RequestRequesti iNeedNeedi i，表示出錯(cuò)，表示出錯(cuò)， 如果如果RequestRequesti iAvailableAvailable，則，則p pi i等待。等待。 假設(shè)系統(tǒng)把申請(qǐng)的資源分給進(jìn)程假設(shè)系統(tǒng)把申請(qǐng)的資源分給進(jìn)程p pi i，則應(yīng)對(duì)有關(guān)數(shù)據(jù)，則應(yīng)對(duì)有關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改：結(jié)構(gòu)進(jìn)行修改： 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í)行安全性算法，查看此時(shí)系統(tǒng)狀態(tài)是否安全。系統(tǒng)執(zhí)行安全性算法，查看此時(shí)系統(tǒng)狀態(tài)是否安全。如果是安全的，就實(shí)際分配資源，滿(mǎn)足進(jìn)程如果是安全的，就實(shí)際分配資源，滿(mǎn)足進(jìn)程p pi i 的此次的此次申請(qǐng)；否則，若新?tīng)顟B(tài)是不安全的，則申請(qǐng)；否則，若新?tīng)顟B(tài)是不安全的，則p pi i等待，對(duì)所申等待，對(duì)所申請(qǐng)資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成之前請(qǐng)資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成之

22、前的情況。的情況。2 2安全性算法安全性算法 令令WorkWork和和FinishFinish分別表示長(zhǎng)度為分別表示長(zhǎng)度為m m和和n n的向量，最初，的向量，最初，置置Work= AvailableWork= Available，F(xiàn)inishFinishi i=false=false，i i=1, 2, =1, 2, n n 搜尋滿(mǎn)足下列條件的搜尋滿(mǎn)足下列條件的i i值：值： FinishFinishi i=false=false，且，且NeedNeedi iWorkWork。 若沒(méi)有找到，則轉(zhuǎn)向。若沒(méi)有找到，則轉(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對(duì)所有對(duì)所有i i都成立（任一進(jìn)程都可能是都成立（任一進(jìn)程都可能是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個(gè)進(jìn)程個(gè)進(jìn)程A, B, C, DA, B, C, D和三類(lèi)資源和三類(lèi)資源R R1 1, , R R2 2和和R R3 3，各自的數(shù)量分別為，各自的數(shù)量分別為9, 39, 3

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

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

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

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

28、加了系統(tǒng)開(kāi)銷(xiāo) 進(jìn)程進(jìn)程 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類(lèi)資源類(lèi)資源(R1、R2、R3)，每一種資源的可用量，每一種資源的可用量為（為（10，5，7）：）：（1）當(dāng)前系統(tǒng)是否安全）當(dāng)前系統(tǒng)是否安全 （2）進(jìn)程）進(jìn)程P1發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量Request1（2，0，4），系統(tǒng)能否將資），系統(tǒng)能否將資源分配給它？源分配給它？（3）如果進(jìn)程）如果進(jìn)程P3發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量Request3（4，0

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

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

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

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

33、它應(yīng)滿(mǎn)足條件：，它應(yīng)滿(mǎn)足條件： 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、，則進(jìn)程，則進(jìn)程p pi i處于死鎖環(huán)中。處于死鎖環(huán)中。 對(duì)多體資源類(lèi)的死鎖檢測(cè)對(duì)多體資源類(lèi)的死鎖檢測(cè)v設(shè)系統(tǒng)中有設(shè)系統(tǒng)中有5 5個(gè)進(jìn)程個(gè)進(jìn)程p p1 1, , p p2 2, , p p3 3, , p p4 4和和p p5 5，有，有3 3類(lèi)資源類(lèi)資源R R1 1, , R R2 2和和R R3 3 ，每類(lèi)資源的個(gè)數(shù)分別為，每類(lèi)資源的個(gè)數(shù)分別為7, 2, 67, 2, 6。 AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202p3303000p4211100p5002002資源情況資源情況進(jìn)程進(jìn)程假定，進(jìn)程假定，進(jìn)程

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