35產(chǎn)生死鎖的原因和必要條件(編輯修改稿)
2024-11-05 10:31 本頁面
【文章內容簡介】 存在一個安全序列 P2， P1， P3 32 安全狀態(tài)的例子 例：假定系統(tǒng)有三個進程 P P P3，共有 12臺磁帶機。進程 P1總共要求 10臺磁帶機， P2和 P3分別要求 4臺和九臺。設在 T0時刻，進程 P P2和 P3已經(jīng)獲得 5臺、 2臺和2臺，還有 3臺空閑沒有分配 。 進程 最大需求 已分配 可用 P1 10 5 3 P2 P3 4 2 2 9 T0時刻系統(tǒng)時安全的。這時存在一個安全序列 P2， P1， P3 33 ? 雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當系統(tǒng)進入不安全狀態(tài)后，便有可能進入死鎖狀態(tài)；反之只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進入死鎖狀態(tài)。 因此，避免死鎖的實質是如何使系統(tǒng)不進入不安全狀態(tài)。 ? 系統(tǒng)的狀態(tài)可能通過下述來描述： 進程剩余申請數(shù)＝最大申請數(shù)－占有數(shù) 。 可分配資源數(shù)＝總數(shù)－占有數(shù)之和 。 34 ? 銀行家算法 – 銀行家擁有一筆周轉資金 – 客戶要求分期貸款 ， 如果客戶能夠得到各期貸款 ， 就一定能夠歸還貸款 ， 否則就一定不能歸還貸款 – 銀行家應謹慎的貸款 ， 防止出現(xiàn)壞帳 ? 用銀行家算法避免死鎖 – 操作系統(tǒng) （ 銀行家 ） – 操作系統(tǒng)管理的資源 (周轉資金 ) – 進程 （ 要求貸款的客戶 ） 35 銀行家算法 ? 銀行家算法是最有代表性的避免死鎖算法，是 Dijkstra提出的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。為實現(xiàn)銀行家算法，系統(tǒng)中必須設置若干數(shù)據(jù)結構。 36 ? 一 、 銀行家算法中的數(shù)據(jù)結構 ? 1 可利用資源向量 Available ? 是一個含有 m個元素 ， 其中的每一個元素代表一類可利用的資源數(shù)目 ， 其初值是系統(tǒng)中所配 置 的 該 類 全 部 可 用 資 源 數(shù) 目 。 如果Available[j]=k， 表示系統(tǒng)中現(xiàn)有 Rj類資源 k個 。 ? 2 最大需求矩陣 Max ? 是一個含有 n?m的矩陣 ， 它定義了系統(tǒng)中 n個進程中的每一個進程對 m類資源的最大需求 。如果 Max(i,j)=k， 表示進程 i需要 Rj類資源的最大數(shù)目為 k。 Available= 3 5 4 2 8 3 8 6 1 37 ? 3 分配矩陣 Allocation 是一個含有 n?m的矩陣 ， 它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù) 。 如果 Allocation(i,j)=k， 表示進程 i當前已分得 Rj類資源 k個 。 ? 4 需求矩陣 Need 是一個含有 n?m的矩陣 ， 用以表示每一個進程尚需的各類資源數(shù) 。 如果 Need(i,j)=k， 表示進程 i還需要 Rj類資源 k個 ， 方能完成其任務 。 Need(i,j)= Max(i,j)Allocation(i,j) 38 ? 二 、 銀行家算法 設 Requesti是進程 Pi的請求向量 ， 如果進程 Pi需要 K個Rj類資源 ， 當 Pi發(fā)出資源請求后 ， 系統(tǒng)按下述步驟進行檢查： 1 如果 Requesti≤ Needi,則轉向步驟 2；否則認為出錯 。（ 因為它所需要的資源數(shù)已超過它所宣布的最大值 。 2如果 Requesti≤ Available,則轉向步驟 3；否則 ， 表示系統(tǒng)中尚無足夠的資源 ， Pi必須等待 3 系統(tǒng)試探把要求的資源分配給進程 Pi， 并修改下面數(shù)據(jù)結構中的數(shù)值： Available:=AvailableRequesti。 Allocation:=Allocation+Requesti。 Needi:= Needi Requesti。 4 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，正式將資源分配給進程 Pi，以完成本次分配；否則，將試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程 Pi等待。 39 三 、 安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下： 1 設置兩個向量 ① 工作向量 源 的 數(shù) 目 ， 它 含 有 m 個 元 素 ， 執(zhí) 行 安 全 算 法 開 始 時 ，Work:=Available。 ② ， 使之運行完成 。開始時先做 Finish[i]:=false；當有足夠的資源分配給進程時 ，令 Finish[i]:=true. 2 從 進 程 集 合 中 找 到 一 個 能 滿 足 下 述 條 件 的 進 程 ： ①Finish[i]=false。 ② Needi≤Work . 如找到 ， 執(zhí)行步驟 3；否則執(zhí)行步驟 4。 3 當進程 Pi獲得資源后 ， 可順利執(zhí)行 ， 直至完成 ， 并釋放出分配給它的資源 ， 故執(zhí)行： Work:=Work+Allocation。 Finish[i]:=true。 Goto step2。 4 如果所有進程的 Finish[i]=true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 40 要記住的一些變量的名稱 1 Available（ 可利用資源向量 ） 某類可利用的資源數(shù)目 ， 其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目 。 2 Max最大需求矩陣 某個進程對某類資源的最大需求數(shù) 3 Allocation分配矩陣 某類資源當前非配給某進程的資源數(shù) 。 4 Need需求矩陣 某個進程還需要的各類資源數(shù) 。 Need= MaxAllocation 系統(tǒng)把進程請求的資源分配給它以后要修改的變量 Available:=AvailableRequest。 Allocation:=Allocation+Request。 Need:= Need Request。 41 銀行家算法之例 ? 假
教學課件相關推薦
鄂ICP備17016276號-1