1、第3章 死 鎖 本章內(nèi)容提要3.1 資源3.1.1 資源使用模式 申請 使用 釋放3.1.2 可剝奪資源與不可剝奪資源按占有方式劃分：按占有方式劃分： 可剝奪資源可剝奪資源 當(dāng)該資源被某進(jìn)程擁有后，其它進(jìn)程仍可以把它剝奪過去為己所用，并且不會產(chǎn)生任何不良影響。例如，內(nèi)存就是可剝奪資源。 不可剝奪資源不可剝奪資源 該資源一旦被某進(jìn)程占有，則其它進(jìn)程不能強(qiáng)行搶占，必須由擁有者自動釋放，否則會引起相關(guān)計(jì)算的失效。如光盤刻錄機(jī)。 死鎖和不可剝奪資源有關(guān) 按其它方式劃分按其它方式劃分3.2 死鎖概念 3.2.1 什么是死鎖 1死鎖示例汽車過窄橋時(shí)的沖突在計(jì)算機(jī)系統(tǒng)中，涉及軟件、硬件資源的進(jìn)程都可能發(fā)生死

2、鎖 2死鎖定義n死鎖 是指在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待僅由該集合中的另一個(gè)進(jìn)程才能引發(fā)的事件而無限期地僵持下去的局面。n計(jì)算機(jī)系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng)n死鎖的危害 系統(tǒng)癱瘓 資源浪費(fèi) 什么是死鎖 有兩個(gè)進(jìn)程A和B，競爭兩個(gè)資源R和S，這兩個(gè)資源都是不可剝奪資源。 進(jìn)程A 進(jìn)程B 申請并占用R 申請并占用S 申請并占用S 申請并占用R 釋放R 釋放S 釋放S 釋放R 什么是死鎖進(jìn)程推進(jìn)順序?qū)σl(fā)死鎖的影響3.2.2 死鎖的條件產(chǎn)生死鎖的4個(gè)必要條件 1互斥條件 2占有且等待條件 3不可搶占條件 4循環(huán)等待條件只要有一個(gè)必要條件不滿足，則死鎖就可以排除。3.2.3 資源分

3、配圖1資源分配圖的構(gòu)成n由結(jié)對組成： G = (V, E) V是頂點(diǎn)的集合，E是邊的集合。 頂點(diǎn)集合可分為兩部分： P=p1, p2, , pn 由系統(tǒng)中所有活動進(jìn)程組成 R=r1, r2, , rm 由系統(tǒng)中全部資源類型組成n有向邊pi rj稱為申請邊 有向邊rj pi 稱為賦給邊n在資源分配圖中，通常用圓圈表示每個(gè)進(jìn)程，用方框表示每種資源類型。2資源分配圖示例（1）集合P, R和E如下： P=p1, p2, p3 R=r1, r2, r3, r4 E=p1r1, p2r3, r1p2, r2p2, r2p1, r3p3（2）資源數(shù)量 分別為1，2，1，3（3）進(jìn)程狀態(tài) 該圖不含環(huán)路，沒有死

4、鎖 資源分配圖示例3 3環(huán)路與死鎖環(huán)路與死鎖 如果每類資源的實(shí)體都只有一個(gè)，那么圖中出現(xiàn)環(huán)路就說明死鎖了。 環(huán)路與死鎖 如果每類資源的實(shí)體不止一個(gè)，那么資源分配圖中出現(xiàn)環(huán)路并不表明一定出現(xiàn)死鎖。 資源分配圖中存在環(huán)路是死鎖產(chǎn)生的必要條件，但不是充分條件。3.2.4 處理死鎖的方法利用某些協(xié)議預(yù)防或避免死鎖，保證系統(tǒng)不會進(jìn)入死鎖狀態(tài)。允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)并克服它。完全忽略這個(gè)問題，好像系統(tǒng)中從來也不會出現(xiàn)死鎖。3.3 死鎖的預(yù)防3.3.1 3.3.1 破壞互斥條件破壞互斥條件3.3.2 3.3.2 破壞占有且等待條件破壞占有且等待條件 預(yù)分資源策略靜態(tài)分配 “空手”申請資源策略不占

5、有資源時(shí)才可以申請資源 存在以下4個(gè)主要缺點(diǎn) 不可預(yù)測 利用率低 降低并發(fā)性 “饑餓” 現(xiàn)象3.3.3 破壞非搶占條件n隱式搶占方式 n搶占等待者資源3.3.4 破壞循環(huán)等待條件資源有序分配策略 資源編號 設(shè)R=r1, r2, , rm，表示一組資源 定義一對一的函數(shù)F：RN，N是一組自然數(shù)。 如：F（磁帶機(jī)）= 1，F(xiàn)（磁盤機(jī)）= 5，F(xiàn)（打印機(jī)）= 12 依序分配 約定：所有進(jìn)程對資源的申請嚴(yán)格按照序號遞增的次序進(jìn)行。 破壞循環(huán)等待條件先棄大，再取小 一個(gè)進(jìn)程申請資源rj，它應(yīng)釋放所有滿足F(ri)F(rj) 關(guān)系的資源ri 這兩種辦法都是可行的，都可排除環(huán)路等待條件 優(yōu)點(diǎn)：資源利用率和系

6、統(tǒng)吞吐量都有很大提高缺點(diǎn)：資源請求受限，合理編號困難，增加系統(tǒng)開銷。暫不使用的資源也需提前申請，增加資源占用時(shí)間。 3.4 死鎖的避免排除死鎖的動態(tài)策略。關(guān)鍵是確定資源分配的安全性 3.4.1 安全狀態(tài)n在當(dāng)前分配狀態(tài)下，進(jìn)程的安全序列P1, P2, Pn是： 若對于每一個(gè)進(jìn)程Pi（1in），它需要的附加資源可被系統(tǒng)中當(dāng)前可用資源與所有進(jìn)程Pj（ ji）當(dāng)前占有資源之和所滿足，則P1, P2, Pn為一個(gè)安全序列。 這時(shí)系統(tǒng)處于安全狀態(tài)。存在安全序列時(shí)一定不會有死鎖發(fā)生 死鎖是不安全狀態(tài)中的特例 安全狀態(tài)時(shí) 刻已占有臺數(shù)最大需求臺數(shù)當(dāng)前可用臺數(shù)進(jìn)程P1進(jìn)程P2進(jìn)程P3進(jìn)程P1進(jìn)程P2進(jìn)程P3T

7、03229473T13429471T2302975T3307970T430097T59001T600010 不安全狀態(tài)示意時(shí)刻已占有臺數(shù)最大需求臺數(shù)當(dāng)前可用臺數(shù)進(jìn)程P1進(jìn)程P2進(jìn)程P3進(jìn)程P1進(jìn)程P2進(jìn)程P3T03229473T14229472T24429470T3402974n若不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)轉(zhuǎn)換為不安全狀態(tài) 死鎖的避免 死鎖狀態(tài)是不安全狀態(tài)。 如果系統(tǒng)處于不安全狀態(tài)，并不意味著它就在死鎖狀態(tài)，而是表示存在導(dǎo)致死鎖的危機(jī)。 如果一個(gè)進(jìn)程申請的資源當(dāng)前是可用的，但為了避免死鎖，該進(jìn)程也可能必須等待。此時(shí)資源利用率會下降。3.4.2 資源分配圖算法n資源類 單體資

8、源類 多體資源類n單體資源類的資源分配圖 除申請邊和賦給邊之外，還要有一種稱為“要求邊”的新邊。要求邊 pi rj表示進(jìn)程pi能夠申請資源rj，有時(shí)用虛線表示。資源分配圖示例3.4.3 銀行家算法n“銀行家算法”（Bankers Algorithm）針對多體資源類 n設(shè)計(jì)思想： 當(dāng)用戶申請一組資源時(shí)，系統(tǒng)必須做出判斷：如果把這些資源分出去，系統(tǒng)是否還處于安全狀態(tài)。若是，就可以分出這些資源；否則，該申請暫不予滿足。銀行家算法銀行家算法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)令n表示系統(tǒng)中進(jìn)程的數(shù)目，m表示資源分類數(shù)。 Available是一個(gè)長度為m的向量，它表示每類資源可用的數(shù)量。Available j=k，表示rj

9、類資源可用的數(shù)量是k。 Max是一個(gè)nm矩陣，它表示每個(gè)進(jìn)程對資源的最大需求。Maxi, j=k，表示進(jìn)程pi至多可申請k個(gè)rj類資源單位。 Allocation是一個(gè)nm矩陣，它表示當(dāng)前分給每個(gè)進(jìn)程的資源數(shù)目。Allocation i, j=k，表示進(jìn)程pi當(dāng)前分到k個(gè)rj類資源。 Need是一個(gè)nm矩陣，它表示每個(gè)進(jìn)程還缺少多少資源。Need i, j=k，表示進(jìn)程pi尚需k個(gè)rj類資源才能完成其任務(wù)。 記號：令X和Y表示長度為n的向量 可以把矩陣Allocation和Need中的每一行當(dāng)做一個(gè)向量，并分別寫成Allocationi和Needi。Allocationi表示當(dāng)前分給進(jìn)程pi的

10、資源。1資源分配算法n令Requesti表示進(jìn)程pi的申請向量。Requestij= k，表示進(jìn)程pi需要申請k個(gè)rj類資源。當(dāng)進(jìn)程pi申請資源時(shí)，就執(zhí)行下列動作： 若RequestiNeedi，表示出錯(cuò)， 如果RequestiAvailable，則pi等待。 假設(shè)系統(tǒng)把申請的資源分給進(jìn)程pi，則應(yīng)對有關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改： Available：= Available Requesti Allocationi：= Allocationi + Requesti Needi：= Needi Requesti 系統(tǒng)執(zhí)行安全性算法，查看此時(shí)系統(tǒng)狀態(tài)是否安全。如果是安全的，就實(shí)際分配資源，滿足進(jìn)程pi 的

11、此次申請；否則，若新狀態(tài)是不安全的，則pi等待，對所申請資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成之前的情況。2 2安全性算法安全性算法 令Work和Finish分別表示長度為m和n的向量，最初，置Work：= Available，F(xiàn)inishi：=false，i=1, 2, n。 搜尋滿足下列條件的i值： Finishi=false，且NeediWork。 若沒有找到，則轉(zhuǎn)向。 修改數(shù)據(jù)值： Work：=Work+ Allocationi（pi釋放所占的全部資源） Finishi=true 轉(zhuǎn)向。 若Finishi=true對所有i都成立（任一進(jìn)程都可能是pi），則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)

12、處于不安全狀態(tài)。3算法應(yīng)用示例假定系統(tǒng)中有4個(gè)進(jìn)程A, B, C, D和三類資源R1, R2和R3，各自的數(shù)量分別為9, 3和6個(gè)單位。進(jìn)程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420 資源情況（1）T0時(shí)刻是安全的 存在一個(gè)安全序列B, A, C, D 資源 情況WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723tru

13、eC723103211934trueD934420002936true進(jìn)程（2）進(jìn)程A請求資源 進(jìn)程A發(fā)出請求Request（1, 0, 1） 資源情況進(jìn) 程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系統(tǒng)進(jìn)入不安全的狀態(tài) 不能為進(jìn)程A分配所申請的資源 銀行家算法n優(yōu)點(diǎn)： 限制條件少 資源利用程度提高 n缺點(diǎn)： 難以保證進(jìn)程數(shù)固定不變 未考慮實(shí)時(shí)進(jìn)程快速響應(yīng) 增加了系統(tǒng)開銷 3.5 死鎖的檢測和恢復(fù) 死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生

14、時(shí)，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，且能通過外力破壞死鎖發(fā)生的必要條件，從而使并發(fā)進(jìn)程從死鎖狀態(tài)中解脫出來。3.5.1 3.5.1 對單體資源類的死鎖檢測對單體資源類的死鎖檢測等待圖等待圖資源分配圖的變形資源分配圖的變形 從資源分配圖中去掉表示資源類的節(jié)點(diǎn)，且把相應(yīng)邊折疊在一起得到的資源分配圖和對應(yīng)的等待圖3.5.2 對多體資源類的死鎖檢測采用若干隨時(shí)間變化的數(shù)據(jù)結(jié)構(gòu)，與銀行家算法相似 Available是一個(gè)長度為m的向量 Allocation是一個(gè)nm的矩陣 Request是一個(gè)nm的矩陣，Requesti, j=k，表示進(jìn)程pi正申請k個(gè)rj類資源 仍把矩陣Allocation和R

15、equest的行作為向量對待，并分別表示為Allocationi和Requesti 對多體資源類的死鎖檢測檢測算法 簡單地調(diào)查尚待完成的各個(gè)進(jìn)程所有可能的分配序列 令Work和Finish分別表示長度為m和n的向量，初始化 Work：=Available；對于i=1, 2, n 如果Allocationi0，則Finishi：=false；否則Finishi：=true。 尋找一個(gè)下標(biāo)i，它應(yīng)滿足條件： Finishi=false且RequestiWork 若找不到這樣的i，則轉(zhuǎn)到。 修改數(shù)據(jù)值： Work：=Work+Allocationi Finishi=true 轉(zhuǎn)向。 若存在某些i（1

16、in），F(xiàn)inishi=false，則系統(tǒng)處于死鎖狀態(tài)。此外，若Finishi=false，則進(jìn)程pi處于死鎖環(huán)中。 對多體資源類的死鎖檢測n設(shè)系統(tǒng)中有5個(gè)進(jìn)程p1, p2, p3, p4和p5，有3類資源R1, R2和R3 ，每類資源的個(gè)數(shù)分別為7, 2, 6。 AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202p3303000p4211100p5002002資源情況進(jìn)程假定，進(jìn)程p3現(xiàn)在申請一個(gè)單位的R3資源AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p101000000

17、0p2200202000p3303001p4211100p5002002 由于對所有i=1, 2, 5，Allocationi0，所以Finishi=false。 資源情況進(jìn)程3.5.3 從死鎖中恢復(fù)1通過搶占資源實(shí)現(xiàn)恢復(fù) 臨時(shí)性地把資源從當(dāng)前占有它的進(jìn)程那里拿過來，分給另外某些進(jìn)程，直至死鎖環(huán)路被打破。2通過回退執(zhí)行實(shí)現(xiàn)恢復(fù)n由系統(tǒng)管理員做出安排，定期對系統(tǒng)中各個(gè)進(jìn)程進(jìn)行檢查，并將檢查點(diǎn)的有關(guān)信息（如進(jìn)程狀態(tài)、資源狀態(tài)等）寫入文件。n當(dāng)檢測到死鎖時(shí)，就讓某個(gè)占有必要資源的進(jìn)程回退到它取得另外某個(gè)資源之前的一個(gè)檢查點(diǎn)?；赝诉^程所釋放的資源分配給一個(gè)死鎖進(jìn)程，然后重新啟動運(yùn)行。n系統(tǒng)中應(yīng)保存一系

18、列檢查點(diǎn)的文件。n要確定這個(gè)進(jìn)程后退多遠(yuǎn)。n還有一種“全體”回退方式3 3通過殺掉進(jìn)程實(shí)現(xiàn)恢復(fù)通過殺掉進(jìn)程實(shí)現(xiàn)恢復(fù)n終止所有的死鎖進(jìn)程。n一次終止一個(gè)進(jìn)程，直至消除死鎖環(huán)路。3.5.4 3.5.4 “饑餓饑餓”狀態(tài)狀態(tài)n在某些策略下，系統(tǒng)會出現(xiàn)這樣一種情況：在可以預(yù)計(jì)的時(shí)間內(nèi)，某個(gè)或某些進(jìn)程永遠(yuǎn)得不到完成工作的機(jī)會，因?yàn)樗鼈兯璧馁Y源總是被別的進(jìn)程占有或搶占。這種狀況稱做“饑餓”或者“餓死”（Starvation）。n饑餓不同于死鎖3.6 處理死鎖的綜合方式n把以前介紹的基本方法組合起來，使得系統(tǒng)中各級資源都以最優(yōu)的方式加以利用。n對待死鎖問題除以上三種最基本的方法外，還有第四種方法，即采取“鴕鳥政策” 完全忽略死鎖問題。 操作系統(tǒng)處理死鎖的三種方法比較資源分配策略死鎖預(yù)防死鎖避免死鎖檢測和恢復(fù)很保守；對資源不做調(diào)配使用介于預(yù)防和檢測方法之間，安全狀態(tài)下才