前言：銀行家演算法就真的是銀行家演算法，可以用銀行貸款的實體來類比銀行家演算法，
一、銀行貸款問題
假設有一家銀行有一筆m億的資金，n個客戶需要貸款，他們都和銀行簽訂了貸款協議，每個客戶所需要貸款的資金不同，且都不超過m億，但是他們加起來的總貸款和遠遠超過了m億，那銀行怎樣貸款給客戶才能使之運轉正常呢？
二、銀行家演算法
1、銀行家演算法基本思想
在資源分配前，判斷系統是否處于安全的狀態，若處于安全的狀態，就把資源分配給申請的行程，如果處于不安全的狀態則令申請資源分配的行程阻塞，不回應其資源申請，
安全狀態：就是系統按照，為每個相交往的行程分配所需的資源，使每個行程都能在有限的時間內結束，
2、銀行家演算法的資料結構
可利用資源向量Available：這是含有m個元素的陣列，表示當前系統還有多少可以利用的資源可供分配，最大需求矩陣Max：這是一個n*m的矩陣，定義了n個行程中的每一個行程對m類資源的最大需求，分配矩陣Allocation：這是一個n*m的矩陣，表示系統中每一類資源已分配給每一個行程的資源數，需求矩陣Need：這是一個n*m的矩陣，表示每一個行程尚需的各類資源數，資源申請向量Requesti[j]：表示行程pi申請k個j類資源，
3、銀行家演算法
- 如果
Request + Allocation <= Max成立，接著執行步驟2,；否則說明行程的j類資源申請超過了其最大需求量，報錯中斷回傳， - 如果
Request <= Available成立，接著執行步驟3；否則說明系統中現有的j類資源不能滿足行程pi的資源申請，結束演算法回傳， - 系統試探著把資源分配給行程，并修改下面資料結構中的值：
Available = Available - RequestAllocation = Allocation + RequestNeed = Need - Request
- 呼叫系統安全性演算法，檢查此次資源分配后系統是否處于安全狀態，若安全，滿足行程pi的資源申請；否則，將本次試探分配作廢，恢復原來資源分配的狀態，不回應行程pi的資源申請，讓pi等待，
4、安全性演算法
（1）設定兩個向量
作業向量Work：表示系統可提供給行程繼續運行所需的各類資源數目，在演算法開始時，Work = Available，Finish：表示是否有足夠的資源分配給行程，使之運行完成，有就true，沒有就false，
（2）在行程集合中找到滿足以下條件的行程：
- Finish[i] = false;
- Need[i,j] <=Work[j];
如果找到了，接著執行步驟（3）
（3）當行程pi獲得資源后，可以順利執行，完畢后釋放所分配的資源，
- Work = Work + Allocation
- Finish = true
（4）如果所有行程的finish都為true，表示系統處于安全狀態，
三、總結
- 了解系統當前可分配的資源數目，行程已經分配的資源數目，行程還需分配的資源數目，行程一共需要的資源數目，
- 向系統提交申請資源的請求，系統先試著分配給所有的行程（找到一個安全序列）如果申請滿足系統的約定，則分配；否則不分配，
- 呼叫系統安全分配演算法，看是否安全（找到了安全序列），就真的分配給行程，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271519.html
標籤：其他
下一篇：執行緒池