操作系統(tǒng)第五章死鎖與饑餓-在線瀏覽
2025-07-16 23:52本頁(yè)面
【正文】 預(yù)先計(jì)算資源分配的安全性 。 其中最具有代表性的避免死鎖算法是 銀行家算法 。進(jìn)程 P1總共要求 10臺(tái)磁帶機(jī)， P2和 P3分別要求 4臺(tái)和 9臺(tái)。 例如 ， 在 T0時(shí)刻以后 ， P3又請(qǐng)求 1臺(tái)磁帶機(jī) ， 若此時(shí)系統(tǒng)把剩余 3臺(tái)中的 1臺(tái)分配給 P3， 則系統(tǒng)便進(jìn)入不安全狀態(tài) 。 安全狀態(tài)與不安全狀態(tài) 不安全狀態(tài) :不存在一個(gè)安全序列。 如果系統(tǒng)有能力 ， 則實(shí)施預(yù)分配 。 ③ 判斷分配后系統(tǒng)是否安全 ， 若安全 ， 則真正實(shí)施分配 。 資源分配的安全性 是指要保證至少有一個(gè)進(jìn)程能夠運(yùn)行到結(jié)束，并且通過回收該進(jìn)程所占用的資源再分配能依次使其他進(jìn)程運(yùn)行結(jié)束，然后繼續(xù)回收資源、繼續(xù)分配等，直到全部進(jìn)程運(yùn)行結(jié)束。 銀行家算法 (Cont.) 數(shù)據(jù)結(jié)構(gòu)： ① Available: array[1..m]of integer。 ② Claim: array[1..n,1..m]of integer。 ③ Allocation: array[1..n,1..m]of integer。 銀行家算法 (Cont.) ④ Need: array[1..n,1..m]of integer。 //當(dāng)前請(qǐng)求 ? Request[i,j]=k表示進(jìn)程 Pi申請(qǐng) Rj類資源中 k個(gè)資源實(shí)例。 ⑦ Finish: array[1..n]of boolean 假設(shè)某一時(shí)刻 ， 進(jìn)程 Pi提出了資源請(qǐng)求 Request[j] ，銀行家算法的操作過程可用以下各步表示： (1) 如果 Request［ j］ ≤Need［ i,j］ ， 便 轉(zhuǎn)向步驟 2；否則認(rèn)為出錯(cuò) ， 因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值 。 算法 51：銀行家算法 資源分配算法 (3)系統(tǒng)對(duì)進(jìn)程 Pi實(shí)施資源的 預(yù)分配 Available［ j］ =Available［ j］ Requesti［ j］ 。 Need［ i,j］ =Need［ i,j］ Requesti［ j］ 。 調(diào)用安全性算法 ， 根據(jù)返回值判斷此次分配的真正實(shí)施是否安全 。 算法 51：銀行家算法 資源分配算法 資源分配 Pi請(qǐng)求資源 Request[I]?Need[I] 請(qǐng)求超量，錯(cuò)返 Request[I]?Available 不滿足，等待 Available:=AvailableRequest[I] Allocation[I]:=Allocation[I]+Request[I] Need[I]:=Need[I]Request[I] 安全 確認(rèn)， pi繼續(xù) Available:=Available+Request[I] Allocation[I]:=Allocation[I]Request[I] Need[I]:=Need[I]+Request[I] pi等待 F T F T T F (1) 設(shè)置兩個(gè)向量： ① 工作向量 Work 用于記錄當(dāng)前可用的每類資源的數(shù)目在執(zhí)行安全算法開始時(shí) ， Work∶ =Available。 比如 ，F(xiàn)inish [i]=true， 表示進(jìn)程 Pi可運(yùn)行完成； Finish [i]=false，表示進(jìn)程 Pi不能運(yùn)行完成 開始時(shí)先做 Finish［ i］ =false。 算法 52：銀行家算法 ? 安全性檢查算法 算法 52：銀行家算法 ? 安全性檢查算法 安全性算法按以下各步操作尋找進(jìn)程的安全序列 1. Work = Available； Finish = false； 2. 尋找滿足如下條件的 i: (1) Finish[i]==false； (2) Need[i]≤Work[i]； 如果不存在 , 則轉(zhuǎn)步驟 4； 3. Work = Work + Allocation[i]； Finish[i] = true； 轉(zhuǎn)步驟 2 4. 如果對(duì)于所有 i, Finish[i] = true, 則系統(tǒng)處于安全狀態(tài) , 否則處于不安全狀態(tài) . 安全性檢測(cè)算法 F Work:=Available。 有滿足條件的 j: Finish[j]=false Need[j]?Work Finish[j]=true。 銀行家算法例子 Max Allocation Need Available Work Finish A B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 2 3 0 3 2 2 3 0 2 0 2 0 9 0 2 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3 1 P0: p1: p2: p3: p4: 假定分配： 安全進(jìn)程序列： p1,p3,p4,p0,p2 ① p4請(qǐng)求： Request[4]=(3,3,0), 能否滿足？ ② p0請(qǐng)求： Request[0]=(0,2,0), 能否滿足？ (3) p4請(qǐng)求資源 ： p4發(fā)出請(qǐng)求向量 Request(3， 3， 0)， 系統(tǒng)按銀行家算法進(jìn)行檢查： ① Request(3, 3, 0)≤Need(4, 3, 1)。 (4) p0請(qǐng)求資源 ： p0發(fā)出請(qǐng)求向量 Requst(0， 2， 0)， 系統(tǒng)按銀行家算法進(jìn)行檢查： ① Request(0, 2, 0)≤Need(7, 4, 3)。 ③ 系統(tǒng)暫時(shí)先假定可為 p0分配資源，并修改有關(guān)數(shù)據(jù) ??銀行家算法的保守性 例子： R={A,B}, 申請(qǐng) a, b。 p2:b b b a a b Max Allocation Need Available Work Finish A B A B A B A B A B p1： 1 1 0 0 1 1 1 1 p2： 1 1 0 0 1 1 Request[1]=(1,0), 安全，分配。若 P P P3已申請(qǐng)到 4臺(tái)、 2臺(tái)和 2臺(tái)。 例 2：假定系統(tǒng)中有 4個(gè)進(jìn)程 P P P P4和 3類資源 R R R3（資源數(shù)量分別為 6），在 t0時(shí)刻的資源分配情況如下表所示： 資源情況 claim allocation need available 進(jìn)程 R1R2R3 R1R2R3 R1R2R3 R1R2R3 P1 3 2 2 1 0 0 2 2 2 1 1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1