銀行家算法問題

1、,.銀行家算法問題1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)（ 1）可利用資源向量 Available： Availabel j k式中： j0jm1一個(gè)含有 m 個(gè)（類）元素的數(shù)組， 每個(gè)元素代表一類可利用的資源數(shù)目。上式表示系統(tǒng)中現(xiàn)有的第 j 類資源可用數(shù)目為 k 個(gè)。（ 2）最大需求矩陣 Max ： Maxi , j k式中： i0 in1j0jm1n 個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m 類資源的最大需求量，上式表示進(jìn)程i 需求第 j類資源的最大數(shù)目為 k 。（ 3）分配矩陣 Allocation： Allocation i, j k式中： i0in1j0jm1n 個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì) m 類資源的分配量， 上

2、式表示進(jìn)程 i 已分配到第 j 類資源的數(shù)目為 k 。（ 4）需求矩陣 Need： Need i, j k式中：i0in1j0jm1n 個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的需求量， 上式表示進(jìn)程 i 對(duì)第 j 類資源的需求量為 k 個(gè)。（ 5）三個(gè)矩陣間的關(guān)系Need i, j Max i, j Allocation i , j ;.,.2、銀行家算法設(shè) Re questi 是進(jìn)程 Pi 的請(qǐng)求向量，如果Re questi jk ，當(dāng) Pi 發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查。（ 1）如果 Re quest j Needi , j ，便轉(zhuǎn)向步驟（），否則認(rèn)為出錯(cuò)，因?yàn)樗鵬2需要的資源數(shù)已超過

3、它所宣布的最大值。（ 2）如果 Re questi j Available j 便轉(zhuǎn)向步驟（），否則表示尚無足夠資源，3Pi 須等待。（ 3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面的數(shù)據(jù)結(jié)構(gòu)中的值：Availabel jAvailabel jRe questi j A l l o c a t i ,o n i jA l l o c, at ioRne ii j q u e s t jNeedi, j Needi , j Re questi j （ 4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，則分配給進(jìn)程 Pi 資源，完成本次分配；若不安全，試探分配作廢，恢復(fù)原來

4、的資源分配狀態(tài)，讓進(jìn)程Pi 等待。3、安全性算法（ 1）設(shè)置兩個(gè)向量：工作向量 Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有 m 個(gè)元素，在執(zhí)行安全算法開始時(shí)， Work Available 。Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish i :false ；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish i:true 。（ 2）從進(jìn)程集合中找一個(gè)能滿足下述條件的進(jìn)程：F i n i s h :if a l s eNeed i , j Work j ，若找到，執(zhí)行步驟（3），否則，執(zhí)行步驟（ 4）。（ 3）當(dāng)進(jìn)程 Pi 獲得資源后，

5、可順利執(zhí)行直至完成，并釋放出分配給它的資源，;.,.執(zhí)行如下操作：Work j :Work j Allocation i , j ;Finishi true;Go to step2（ 4）如果所有進(jìn)程的 Finish i : true 都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)。例：五個(gè)進(jìn)程P , P,P , P , P和三類資源A, B,C ， T0 時(shí)刻資源分配情況01234數(shù)據(jù)MaxAllocationNeedAvailable進(jìn)程 ABCABCABCABCP7530107433320P1322200122P9023026002P3222211011P4330024314（

6、1） T0 時(shí)刻安全性，存在一個(gè)安全序列P1 , P3 , P4 , P2 , P0數(shù)據(jù)WorkNeedAllocationWork+AllocationFinish進(jìn)程ABCABCABCABCP1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057true;.,.（ 2） P1 請(qǐng)求資源： Request1 (1,0,2) ,系統(tǒng)各按銀行家算法進(jìn)行檢查：1） Re quest11,0, 2Need11,2, 22） Re quest11,0, 2Available 13,

7、3, 23）系統(tǒng)假定可為1 分配資源，并修改Available ; Allocation 1和 Need1 向量P4）再利用安全性算法檢查此時(shí)系統(tǒng)是否安全：找到一個(gè)安全序列P , P , P , P , P，因此，系統(tǒng)安全?？梢粤⒓磳1 所申請(qǐng)的資源分給它。13402數(shù)據(jù)WorkNeedAllocationWork+AllocationFinish進(jìn)程ABCABCABCABCP230020302532true1P3532011211743trueP743431002745true4P0745743010755trueP7556003021057true2（ 3） P4 請(qǐng)求資源：在 P1提出

8、請(qǐng)求，獲得資源，但尚未釋放資源時(shí)， P4 發(fā)出請(qǐng)求向量 Re quest4 (3,3,0) ，系統(tǒng)按銀行家算法進(jìn)行檢查，1） Re quest43,3,0Need44,3,12） Re quest43,3,0Available 2,3,0 。故，讓 P4 等待。（ 4） P 請(qǐng)求資源：在1 提出請(qǐng)求，獲得資源，但尚未釋放資源時(shí)，P0 發(fā)出請(qǐng)0P;.,.求向量 Re quest0 (0, 2,0) ，系統(tǒng)按銀行家算法進(jìn)行檢查，1） Re quest00, 2,0Need0 7, 4,32） Re quest00, 2,0Available 12,3,03）系統(tǒng)暫時(shí)先假定可為P0 分配資源，并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，如下圖數(shù)據(jù)AllocationNeedA