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