【正文】 序進行。 破壞循環(huán)等待條件 ② 先棄大，再取小 一個進程申請資源 rj，它應(yīng)釋放所有滿足 F(ri)≥ F(rj) 關(guān)系的資源 ri ▲ 這兩種辦法都是可行的，都可排除環(huán)路等待條件 ▲ 優(yōu)點 ： 資源利用率和系統(tǒng)吞吐量都有很大提高 ▼ 缺點： ①資源請求受限，合理編號困難，增加系統(tǒng)開銷。 ②暫不使用的資源也需提前申請，增加資源占用時間。 死鎖的避免 ● 排除死鎖的 動態(tài)策略。 關(guān)鍵是確定資源分配的安全性 安全狀態(tài) ? 在當前分配狀態(tài)下，進程的安全序列 {P1, P2,… , Pn}是： 若對于每一個進程 Pi（ 1≤ i≤ n），它需要的附加資源可被系統(tǒng)中當前可用資源與所有進程 Pj（ j＜ i） 當前占有資源之和所滿足，則 {P1, P2,… , Pn}為一個安全序列。 這時系統(tǒng)處于安全狀態(tài)。 ● 存在安全序列時一定不會有死鎖發(fā)生 死鎖是不安全狀態(tài)中的特例 安全狀態(tài) ? 安全狀態(tài)示意 設(shè)系統(tǒng)中共有 10臺磁帶機，有三個進程 p1, p2和 p3，分別擁有 3臺、 2臺和 2臺磁帶機，而它們各自的最大需求分別是 9臺、 4臺和 7臺磁帶機。此時，系統(tǒng)已分配了 7臺磁帶機，還有 3臺空閑。下表給出三個進程在不同時刻占有資源及向前推進的情況。 時 刻 已占有臺數(shù) 最大需求臺數(shù) 當前可用臺數(shù) 進程 P1 進程 P2 進程 P3 進程 P1 進程 P2 進程 P3 T0 3 2 2 9 4 7 3 T1 3 4 2 9 4 7 1 T2 3 0 2 9 — 7 5 T3 3 0 7 9 — 7 0 T4 3 0 0 9 — — 7 T5 9 0 0 — — — 1 T6 0 0 0 — — — 10 不安全狀態(tài)示意 時刻 已占有臺數(shù) 最大需求臺數(shù) 當前可用臺數(shù) 進程 P1 進程P2 進程P3 進程P1 進程P2 進程P3 T0′ 3 2 2 9 4 7 3 T1′ 4 2 2 9 4 7 2 T2′ 4 4 2 9 4 7 0 T3′ 4 0 2 9 — 7 4 ? 若不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)轉(zhuǎn)換為不安全狀態(tài) 死鎖的避免 ① 死鎖狀態(tài)是不安全狀態(tài)。 ② 如果系統(tǒng)處于不安全狀態(tài)，并不意味著它就在死鎖狀態(tài)，而是表示存在導致死鎖的危機。 ③ 如果一個進程申請的資源當前是可用的，但為了避免死鎖，該進程也可能必須等待。此時資源利用率會下降。 資源分配圖算法 ? 資源類 單體資源類 多體資源類 ? 單體資源類的資源分配圖 除申請邊和賦給邊之外，還要有一種稱為 “ 要求邊 ” 的新邊。要求邊 pi rj表示進程 pi能夠申請 資源 rj，有時用虛線表示。 資源分配圖示例 處于不安全狀態(tài)的資源分配圖 銀行家算法 ? ―銀行家算法 ” （ Banker’s Algorithm） ——針對 多體資源類 ? 設(shè)計思想： 當用戶申請一組資源時，系統(tǒng)必須做出判斷：如果把這些資源分出去，系統(tǒng)是否還處于安全狀態(tài)。若是，就可以分出這些資源；否則，該申請暫不予滿足。 銀行家算法 數(shù)據(jù)結(jié)構(gòu) 令 n表示系統(tǒng)中進程的數(shù)目， m表示資源分類數(shù)。 ① Available是一個長度為 m的向量，它表示每類資源可用的數(shù)量。 Available[ j]=k，表示 rj類資源可用的數(shù)量是 k。 ② Max是一個 n m矩陣，它表示每個進程對資源的最大需求。Max[i, j]=k，表示進程 pi至多可申請 k個 rj類資源單位。 ③ Allocation是一個 n m矩陣，它表示當前分給每個進程的資源數(shù)目。 Allocation [i, j]=k，表示進程 pi當前分到 k個rj類資源。 ④ Need是一個 n m矩陣，它表示每個進程還缺少多少資源。Need [i, j]=k，表示進程 pi尚需 k個 rj類資源才能完成其任務(wù)。 ▲ 記號：令 X和 Y表示長度為 n的向量 可以把矩陣 Allocation和 Need中的每一行當做一個向量，并分別寫成 Allocationi和 Needi。 Allocationi表示當前分給進程 pi的資源。 1．資源分配算法 ? 令 Requesti表示進程 pi的申請向量。 Requesti[j]= k，表示進程 pi需要申請 k個 rj類資源。當進程 pi申請資源時，就執(zhí)行下列動作： ① 若 Requesti＞ Needi，表示出錯， ② 如果 Requesti＞ Available，則 pi等待。 ③ 假設(shè)系統(tǒng)把申請的資源分給進程 pi，則應(yīng)對有關(guān)數(shù)據(jù)結(jié)構(gòu)進行修改： Available： = Available – Requesti Allocationi： = Allocationi + Requesti Needi： = Needi – Requesti ④ 系統(tǒng)執(zhí)行安全性算法，查看此時系統(tǒng)狀態(tài)是否安全。如果是安全的，就實際分配資源，滿足進程 pi 的此次申請；否則，若新狀態(tài)是不安全的，則 pi等待，對所申請資源暫不予分配，并且把資源分配狀態(tài)恢復成③之前的情況。 2．安全性算法 ① 令 Work和 Finish分別表示長度為 m和 n的向量，最初，置Work： = Available， Finish[i]： =false， i=1, 2,… , n。 ② 搜尋滿足下列條件的 i值： Finish[i]=false，且 Needi≤Work 。 若沒有找到，則轉(zhuǎn)向④。 ③ 修改數(shù)據(jù)值： Work： =Work+ Allocationi（ pi釋放所占的全部資源） Finish[i]=true 轉(zhuǎn)向②。 ④ 若 Finish[i]=true對所有 i都成立（任一進程都可能是pi），則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 3．算法應(yīng)用示例 假定系統(tǒng)中有 4個進程 {A, B, C, D}和三類資源 R1, R2和 R3，各自的數(shù)量分別為 9, 3和 6個單位。 進程 Allocation Max Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 A 1 0 0 3 2 2 2 2 2 1 1 2 B 5 1 1 6 1 3 1 0 2 C 2 1 1 3 1 4 1 0 3 D 0 0 2 4 2 2 4 2 0 T0時刻資源分配表（ 安全 ） 資源情況 （ 1） T0時刻是安全的 存在一個安全序列 {B, A, C, D} 資源 情況 Work Need Allocation Work+Allocation Finish R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 B 1 1 2 1 0 2 5 1 1 6 2 3 true A 6 2 3 2 2 2 1 0 0 7 2 3 true C 7 2 3 1 0 3 2 1 1 9 3 4 true D 9 3 4 4 2 0 0 0 2 9 3 6 true 進程 T0時刻的安全序列 （ 2）進程 A請求資源 進程 A發(fā)出請求 Request（ 1, 0, 1） 資源情況 進 程 Max Allocation Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 A 3 2 2 2 0 1 1 2 1 0 1 1 B 6 1 3 5 1 1 1 0 2 C 3 1 4 2 1 1 1 0 3 0 1 1 D 4 2 2 0 0 2 4 2 0 系統(tǒng)進入不安全的狀態(tài) 不能為進程 A分配所申請的資源 為進程 A分配資源后的有關(guān)數(shù)據(jù) 銀行家算法 ? 優(yōu)點 ： 限制條件少 資源利用程度提高 ? 缺點 ： ①難以保證進程數(shù)固定不變 ②未考慮實時進程快速響應(yīng) ③增加了系統(tǒng)開銷 死鎖的檢測和恢復 死鎖檢測與恢復是指系統(tǒng)設(shè)有專門的機構(gòu)，當死鎖發(fā)生時，該機構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，且能通過外力破壞死鎖發(fā)生的必要條件，從而使并發(fā)進程從死鎖狀態(tài)中解脫出來。 對單體資源類的死鎖檢測 ■ 等待圖 ——資源分配圖的變形 從資源分配圖中去掉表示資源類的節(jié)點，且把相應(yīng)邊折疊在一起得到的 資源分配圖和對應(yīng)的等待圖 對多體資源類的死鎖檢測 ■ 采用若干隨時間變化的數(shù)據(jù)結(jié)構(gòu)，與銀行家算法相似 ① Available是一個長度為 m的向量 ② Allocation是一個 n m的矩陣 ③ Request是一個 n m的矩陣， Request[i, j]=k，表示進程 pi正申請 k個 rj類資源 仍把矩陣 Allocation和 Request的行作為向量對待，并分別表示為 Allocationi和 Requesti 對多體資源類的死鎖檢測 ■ 檢測算法 簡單地調(diào)查尚待完成的各個進程所有可能的分配序列 ① 令 Work和 Finish分別表示長度為 m和 n的向量，初始化 Work： =Available；對于 i=1, 2,… , n 如果 Allocationi≠0 ，則 Finish[i]： =false；否則 Finish[i]：=true。 ② 尋找一個下標 i，它應(yīng)滿足條件： Finish[i]=false且 Requesti≤Work 若找不到這樣的 i，則轉(zhuǎn)到④。 ③ 修改數(shù)據(jù)值： Work： =Work+Allocationi Finish[i]=true 轉(zhuǎn)向②。 ④ 若存在某些 i（ 1≤ i≤ n）， Finish[i]=false，則系統(tǒng)處于死鎖狀態(tài)。此外，若 Finish[i]=false，則進程 pi處于死鎖環(huán)中。 對多體資源類的死鎖檢測 ? 設(shè)系統(tǒng)中有 5個進程 p1, p2, p3, p4和 p5，有 3類資源 R1, R2和 R3 ，每類資源的個數(shù)分別為 7, 2, 6。 Allocation Request Available R1 R2 R3 R1 R2 R3 R1 R2 R3 p1 0 1 0 0 0 0 0 0 0 p2 2 0 0 2 0 2 p3 3 0 3 0 0 0 p4 2 1 1 1 0 0 p5 0 0 2 0 0 2 死鎖檢測示例資源分配情況 ▲ 可以找到序列 {p1, p3, p4, p2, p5}，對于所有的 i都有 Finish[i]=true，系統(tǒng)在 T0時刻沒有死鎖。 資源情況 進程 假定，進程 p3現(xiàn)在申請一個單位的 R3資源 Allocation Request Available R1 R2 R3 R1 R2 R3 R1 R2 R3 p1 0 1 0 0 0 0 0 0 0 p2 2 0 0 2 0 2 0 0 0 p3 3 0 3 0 0 1 p4 2 1 1 1 0 0 p5 0 0 2 0 0 2 ▲ 由于對所有 i=1, 2,… , 5， Allocationi≠0 ，所以 Finish[i]=false。 p3申請一個單位的 R3資源后的資源分配數(shù)據(jù) 資源情況 進程 從死鎖中恢復 1．通過搶占資源實現(xiàn)恢復 臨時性地把資源從當前占有它的進程那里拿過來，分給另外某些進程，直至死鎖環(huán)路被打破。 2．通過回退執(zhí)行實現(xiàn)恢復 ? 由系統(tǒng)管理員做出安排，定期對系統(tǒng)中各個進程進行檢查，并將檢查點的有關(guān)信息（如進程狀態(tài)、資源狀態(tài)等）寫入文件。 ? 當檢測到死鎖時，就讓某個占有必要資源的進程回退到它取得另外某個資源之前的一個檢查點。回退過程所釋放的資源分配給一個死鎖進程，然后重新啟動運行。 ? 系統(tǒng)中應(yīng)保存一系列檢查點的文件。 ? 要確定這個進程后退多遠。 ? 還有一種 “ 全體 ” 回退方式 3．通過殺掉進程實現(xiàn)恢復 ? 終止所有的死鎖進程。 ? 一次終止一個進程，直至消除死鎖環(huán)路。 “饑餓 ” 狀態(tài) ? 在某些策略下，系統(tǒng)會出現(xiàn)這樣一種情況：在可以預計的時間內(nèi)，某個或某些進程永遠得不到完成工作的機會，因為它們所需的資源總是被別的進程占有或搶占。這種狀況稱做 “ 饑餓 ” 或者“ 餓死 ” （ Starvation）。 ? 饑餓不同于死鎖 處理死鎖的綜合方式 ? 把以前介紹的基本方法組合起來，使得系統(tǒng)中各級資源都以最優(yōu)的方式加以利用。 ? 對待死鎖問題除以上三種最基本的方法