1.算法準備
∙ \bullet ∙
銀行家算法
(資源配置設定拒絕政策)目的是選擇合适的資源配置設定順序進而避免死鎖的發生。
∙ \bullet ∙ 該方法允許程序動态的申請資源,使得系統一直保持
安全狀态
。那麼什麼是安全狀态呢?
我們考慮一個系統它有固定的程序數目與資源數目,比如說有n個程序和m個不同類型的資源,現在已知如下矩陣(題目中會給出):
R e s o u r c e = ( R 1 , R 2 , . . . R m ) 系 統 中 每 種 資 源 的 總 量 {\color{Violet}Resource = (R_{1},R_{2},...R_{m})} \ 系統中每種資源的總量 Resource=(R1,R2,...Rm) 系統中每種資源的總量
A v a i l a b l e = ( V 1 , V 2 , . . . V m ) 沒 有 分 配 的 每 種 資 源 總 量 {\color{Violet}Available = (V_{1},V_{2},...V_{m})} \ 沒有配置設定的每種資源總量 Available=(V1,V2,...Vm) 沒有配置設定的每種資源總量
M a x = [ C 11 C 12 ⋯ C 1 m C 21 C 22 ⋯ C 2 m ⋮ ⋮ ⋮ C n 1 C n 2 ⋯ C n m ] 每 個 進 程 對 每 種 資 源 的 最 大 需 求 {\color{Violet}Max = \begin{bmatrix} C_{11} & C_{12} & \cdots & C_{1m}\\ C_{21} & C_{22} & \cdots & C_{2m}\\ \vdots & \vdots & & \vdots \\ C_{n1} & C_{n2} & \cdots & C_{nm} \end{bmatrix}} \ 每個程序對每種資源的最大需求 Max=⎣⎢⎢⎢⎡C11C21⋮Cn1C12C22⋮Cn2⋯⋯⋯C1mC2m⋮Cnm⎦⎥⎥⎥⎤ 每個程序對每種資源的最大需求
A l l o c a t i o n = [ A 11 A 12 ⋯ A 1 m A 21 A 22 ⋯ A 2 m ⋮ ⋮ ⋮ A n 1 A n 2 ⋯ A n m ] 資 源 當 前 分 配 情 況 {\color{Violet}Allocation= \begin{bmatrix} A_{11} & A_{12} & \cdots & A_{1m}\\ A_{21} & A_{22} & \cdots & A_{2m}\\ \vdots & \vdots & & \vdots \\ A_{n1} & A_{n2} & \cdots & A_{nm} \end{bmatrix}} \ 資源目前配置設定情況 Allocation=⎣⎢⎢⎢⎡A11A21⋮An1A12A22⋮An2⋯⋯⋯A1mA2m⋮Anm⎦⎥⎥⎥⎤ 資源目前配置設定情況
∙ \bullet ∙ 安全狀态就是至少存在一個安全序列 < P 1 , P 2 , . . . , P m > {\color{Red}<P_{1},P_{2},...,P_{m}>} <P1,P2,...,Pm>,按照這個順序為程序配置設定資源可以使每個程序都順利完成,保證系統不進入死鎖狀态。
2.算法執行個體
∙ \bullet ∙ 假設現在系統中有 R 1 、 R 2 、 R 3 {\color{Red}R_{1}、R_{2}、R_{3}} R1、R2、R3三種資源,它們資源總數為(9,3,6),目前已經配置設定給了4個程序,并且配置設定狀态如下,那麼這4個程序是否處于安全狀态呢?
目前給出的資訊如下(我們需要計算
Need
矩陣來表示剩下每個程序所需的資源個數,計算方法為Max矩陣減去Allocation矩陣):
此時我們未配置設定的資源總數為(0,1,1),對比Need矩陣進行觀察後發現唯一可以滿足 P 2 P_{2} P2程序的需求,是以先配置設定給該程序使其完成任務,完成任務以後就會釋放 P 2 P_{2} P2程序占有的所有資源,是以現在Available矩陣的值為(6,1,2)+(0,1,1)=(6,2,3),安全序列中放入 P 2 P_{2} P2。
繼續看下去,此時未配置設定的資源數可以滿足程序 P 1 和 P 4 P_{1}和P_{4} P1和P4需求,此時就有兩種可能的情況我們随機選擇其中一種就好(由此也可以看出安全序列的
結果可能不唯一
),這裡我們選擇 P 1 P_{1} P1,結果如下:
接下來同理我們可以配置設定給 P 4 P_{4} P4,使其完成任務,結果如下:
最後可以配置設定給P_{3},是以得到的一種安全序列為: < P 2 , P 1 , P 4 , P 3 > {\color{Red}<P_{2},P_{1},P_{4},P_{3}>} <P2,P1,P4,P3>