银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
银行家算法中的数据结构
为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
上述三个矩阵间存在下述关系:Need[i,j] = Max[i,j] – Allocation[i, j]
银行家算法详述：
设 Request；是进程Pi的请求向量，如果 Requesti[j] = K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检査:
如果 Requesti[j] ≤ Need[i,j]便转向步骤2 否则认为出错，因为它所需要的资源数已超过它所事先声明需要的最大值。如果 Requesti[j] ≤ Available[j]，便转向步骤3；否则，表示尚无足够资源，Pi须等待。系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值Available[j] = Available[j] – Requesti[j];Allocation[i,j] = Allocation[i,j] + Requesti[j];Need[i,j] = Need[i,j] – Requesti[j];系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待安全性算法
系统所执行的安全性算法可描述如下:
设置两个向量:从进程集合中找到一个能满足下述条件的进程① Finish[i] = false;② Need[i,j] ≤ Work[j];若找到，执行步骤3，否则，执行步骤4。当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:Work[j] = Work[j] + Allocation[i,j];Finish[i] = true;go to step 2;如果所有进程的 Finish[i] =true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。代码
C++的银行家算法的具体实现代码（By Titan）
代码语言：javascript
复制
#include
#define MAX 100
using namespace std;
int totalResource,totalProcess;
int Max[MAX][MAX]; // 最大需求矩阵max
int Allocation[MAX][MAX]; // 分配矩阵
int Need[MAX][MAX]; // 最多还需要资源矩阵
int Available[MAX]; // 可用资源向量
void inputMaxMartix() {
cout << "请输入Max矩阵的数据：" << endl;
for(int i=0; i<totalProcess; i++) {
for(int j=0; j> Max[i][j];
}
}
}
void inputAllocationMartix() {
cout << "请输入Allocation矩阵的数据：" << endl;
for(int i=0; i<totalProcess; i++) {
for(int j=0; j> Allocation[i][j];
}
}
}
void inputAvailable() {
cout << "请输入Available资源向量" << endl;
for(int i=0; i> Available[i];
}
}
// 通过Max矩阵和Allocation矩阵的数据来计算Need矩阵
void calculateNeed() {
for(int i=0; i<totalProcess; i++) {
for(int j=0; j<totalResource; j++) {
Need[i][j]=Max[i][j]-Allocation[i][j];
}
}
}
// 输出当前数据
void print() {
cout << "当前资源分配情况：" << endl;
cout << "进程ID" << "tt" << "Max" << "tt" << "Allocation" << "tt" << "Need" << endl;
for(int i=0; i<totalProcess; i++) {
cout << i << "ttt";
for(int j=0; j<totalResource; j++) {
cout << Max[i][j] << " ";
}
cout << "ttt";
for(int j=0; j<totalResource; j++) {
cout << Allocation[i][j] << " ";
}
cout << "ttt";
for(int j=0; j<totalResource; j++) {
cout << Need[i][j] << " ";
}
cout << endl;
}
cout << "各类资源可用数量：" << endl;
for(int i=0; i<totalResource; i++) {
cout << Available[i] << " ";
}
cout << endl;
}
//安全性检查函数
bool check() {
int safeSeq[totalProcess];
int work[totalResource];
int count = 0; // 安全序列Cursor;
bool finish[totalProcess];
for(int i=0; i<totalProcess; i++) {
safeSeq[i] = 0;
finish[i] = false;
}
for(int i=0; i<totalResource; i++) {
work[i] = Available[i];
}
int unfinished = totalProcess;
bool flag;
do {
for(int i=0; i<totalProcess; i++) {
if(finish[i] == false) {
flag = true;
for(int j=0; j work[j]) {
flag = false;
break;
}
}
if(flag) {
finish[i] = true;
safeSeq[count++] = i;
for(int j=0; j0);
flag = true;
// 判断是否所有进程都完成
for(int i=0; i<totalProcess; i++) {
if(finish[i]==false) {
flag=false;
break;
}
}
// 判断是否安全
if(flag==false) {
cout << "系统处于不安全状态！" << endl;
} else {
cout << "系统当前为安全状态，安全序列为：" << endl;
for(int i=0; i<totalProcess; i++) {
cout << safeSeq[i] << " ";
}
cout << endl;
}
return flag;
}
void handleRequest() {
int requestPid;
int request[totalResource];
int snapShotOfAvailable[totalResource];
int snapShotOfAllocation[totalResource];
int snapShotOfNeed[totalResource];
cout << "请输入请求资源的ID：" <> requestPid;
cout << "请输入请求向量Request：" << endl;
for(int i=0; i> request[i];
}
for(int i=0; i Need[requestPid][i]) {
cout << "请求资源数大于需要数量，分配失败" < Available[i]) {
cout << "可用资源不足，分配失败" << endl;
return;
}
}
// 尝试分配
for(int i=0; i<totalResource; i++) {
//保存快照
snapShotOfAvailable[i] = Available[i];
snapShotOfAllocation[i] = Allocation[requestPid][i];
snapShotOfNeed[i] = Need[requestPid][i];
// 进行尝试分配
Available[i] -= request[i];
Allocation[requestPid][i] += request[i];
Need[requestPid][i] -= request[i];
}
// 打印当前资源情况
print();
if(check() == false) { // 不安全，返回分配
// 恢复快照
for(int i=0; i<totalResource; i++) {
// 进行尝试分配
Available[i] = snapShotOfAvailable[i];
Allocation[requestPid][i] = snapShotOfAllocation[i];
Need[requestPid][i] -= snapShotOfNeed[i];
}
}
}
int main() {
cout << "请输入进程数量：" <> totalProcess;
cout << "请输入资源种类数量：" <> totalResource;
inputMaxMartix();
inputAllocationMartix();
inputAvailable();
calculateNeed();
print();
check();
while(true){
char signal;
handleRequest();
cout << "输入Y继续，输入N退出" <> signal;
if(signal == 'N'){
return 0;
}
}
}