一.写在前面
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
你没看错，就是那个Dijkstra
还记得数据结构中的最短路径Dijkstra算法吗？没错就是你想的那样
操作系统进程同步问题中的信号量和PV原语也是Dijkstra提出的，顺便还提出并解决了”哲学家问题”
并且是第一个Algol 60编译器的设计者和实现者。
头发还是比较多的。
二.问题描述
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
简单的说就是：系统资源有限，要使用银行家算法来进行资源分配要求：既要满足当前正在运行的若干进程运行又要避免因为资源分配问题导致的死锁问题。
说明一些下用到的数据结构
1）可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。
4）需求矩阵Need
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
看一道2018年408题目：
假设系统中有4个同类资源，进程P1和P2需要的资源数分别为4，3和1，P1，P2和P3已申请到的资源数分别为2，1和0，则执行安全检测算法的结果是（）
A:不存在安全序列，系统处于不安全态
B:存在多个安全序列，系统处于安全状态
C:存在唯一安全序列P3，P1，P2，系统处于安全状态
D:存在唯一安全序列P3，P2，P1，系统处于安全状态
这道题还是比较简单的，还是那句老话，学习要由浅入深，循序渐进嘛。
首先阅读题目画出下面这张表格
问号部分是我们要计算的
对于Available来说还是比较好算出的直接用系统资源总数（本道题就一种资源）减去当前已经分配出去的资源数即可即4-（2+1+0）= 1
对于Need列来说计算也是灰常简单的直接用每个进程对应的Max列减去Allocation列即可
P1进程Need = 4-2=2
P2进程Need = 3-1=2
P3进程Need = 1-0=1
现在手动模拟银行家算法进行安全检查：
由于当前可用资源为1，所以扫描Need列时发现只有P3进程需求满足小于等于可用条件，所以只能尝试将资源分配给P3进程；当资源分配给P3进程后P3进程运行完成，此时可用资源数为1+0 = 1,还是1，而P2和P1都需要至少2个资源所以不存在安全序列使得所有进程都能完成。
所以这道题正确答案是：A
二.编码实现
银行家算法.cpp
// Dijkstra 于1965年提出能够避免死锁的调度方法，称为银行家算法
// @Author: Michael Jiang sencom1997@outlook.com
// 2019年9月22日 20点26分
#include <iostream>
// 资源种类数
const size_t RESOURCE_KIND_NUMS =3;
// 进程数
const size_t PROCESS_NUMS = 5;
//进程完成标志数组
bool finshed[PROCESS_NUMS] = {false};
// a,b矩阵相减结果存放在c中
void matrixSub( int (*a)[RESOURCE_KIND_NUMS],\
int (*b)[RESOURCE_KIND_NUMS],\
int (*c)[RESOURCE_KIND_NUMS])
{
for (size_t i = 0; i < PROCESS_NUMS; i++)
{
for (size_t j = 0; j < RESOURCE_KIND_NUMS; j++)
{
c[i][j] = a[i][j] - b[i][j];
}
}
}
// 打印矩阵
void printMatrix(int (*a)[RESOURCE_KIND_NUMS]){
for (size_t i = 0; i < PROCESS_NUMS; i++)
{
for (size_t j = 0; j < RESOURCE_KIND_NUMS; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
// 在分配矩阵中求出某个资源的已分配数
int getAllocationCount(int (*allocation)[RESOURCE_KIND_NUMS],int index){
int count = 0;
for (size_t i = 0; i < PROCESS_NUMS; i++)
{
count += allocation[i][index];
}
return count;
}
// 求出各资源的当前可用量
void getAvailable(int (*available),\
int (*resource),\
int (*allocation)[RESOURCE_KIND_NUMS])
{
for (size_t i = 0; i < RESOURCE_KIND_NUMS; i++)
{
available[i] = resource[i] - getAllocationCount(allocation,i);
}
}
bool safeSub(int *a, int *b)
{
for (size_t i = 0; i < RESOURCE_KIND_NUMS; i++)
{
if (a[i] < b[i] )
{
return false;
}
}
return true;
}
void safeAdd(int (*allocation)[RESOURCE_KIND_NUMS],int (*available),int index)
{
for (size_t i = 0; i < RESOURCE_KIND_NUMS; i++)
{
available[i] += allocation[index][i];
}
}
void isSafe(int (*available),\
int (*need)[RESOURCE_KIND_NUMS],\
int (*max)[RESOURCE_KIND_NUMS],\
int (*allocation)[RESOURCE_KIND_NUMS])
{
for (size_t i = 0; i < PROCESS_NUMS; i++)
{
if (safeSub(available,need[i]) && !finshed[i])
{
//如果够分配的话，就将该进程原先分配的全部收回
safeAdd(allocation,available,i);
//将线程完成标志置true
finshed[i] = true;
printf("Process-%d ==> ",i);
isSafe(available,need,max,allocation);
}
}
}
int main(int argc, char const *argv[])
{
// 资源数目
int resource[RESOURCE_KIND_NUMS] = {
3,7,11
};
// 可利用资源向量
int available[RESOURCE_KIND_NUMS];
// 最大需求矩阵
int max[PROCESS_NUMS][RESOURCE_KIND_NUMS] = {
{0,0,4},
{1,7,5},
{2,3,5},
{0,6,4},
{0,6,5}
};
// 分配矩阵
int allocation[PROCESS_NUMS][RESOURCE_KIND_NUMS] = {
{0,0,3},
{1,0,0},
{1,3,5},
{0,0,2},
{0,0,1}
};
// 需求矩阵
int need[PROCESS_NUMS][RESOURCE_KIND_NUMS];
//求出need矩阵
matrixSub(max,allocation,need);
//求出当前可用资源数
getAvailable(available,resource,allocation);
printf("allocation(分配矩阵):\n");
printMatrix(allocation);
printf("\n");
printf("max(最大需求矩阵):\n");
printMatrix(max);
printf("\n");
printf("need(需求矩阵):\n");
printMatrix(need);
printf("\n");
printf("\n");
printf("available(可利用资源向量):\n");
for (size_t i = 0; i < RESOURCE_KIND_NUMS; i++)
{
printf("available[%d] = %d\n",i,available[i]);
}
printf("\n");
// 进行安全检查
printf("安全序列:\n");
isSafe(available,need,max,allocation);
printf("\n");
printf("\n");
printf("各进程完成情况:\n");
bool safe = true;
for (size_t i = 0; i < PROCESS_NUMS; i++)
{
printf("Process-%d : %s\n",i,finshed[i]?"finshed":"locked");
if(!finshed[i]){
safe = false;
}
}
printf("\n");
printf("是否安全:\n");
printf("isSafe=%s\n",safe?"true":"false");
return 0;
}代码模拟的是5个进程P0~P4和三种资源0，1，2在给定的状态下看到系统是否处于安全状态。
运行结果如下：
C:\Users\Michael Jiang\Desktop\408数据结构>g++ 银行家算法.cpp && a.exe
allocation(分配矩阵):
0 0 3
1 0 0
1 3 5
0 0 2
0 0 1
max(最大需求矩阵):
0 0 4
1 7 5
2 3 5
0 6 4
0 6 5
need(需求矩阵):
0 0 1
0 7 5
1 0 0
0 6 2
0 6 4
available(可利用资源向量):
available[0] = 1
available[1] = 4
available[2] = 0
安全序列:
Process-2 ==> Process-0 ==> Process-1 ==> Process-3 ==> Process-4 ==>
各进程完成情况:
Process-0 : finshed
Process-1 : finshed
Process-2 : finshed
Process-3 : finshed
Process-4 : finshed
是否安全:
isSafe=true下面对main()方法做一些简单的修改：
// 资源数目
int resource[RESOURCE_KIND_NUMS] = {
3,7,11
};将上面的代码改为
// 资源数目
int resource[RESOURCE_KIND_NUMS] = {
3,4,12
};再次执行：
C:\Users\Michael Jiang\Desktop\408数据结构>g++ 银行家算法.cpp && a.exe
allocation(分配矩阵):
0 0 3
1 0 0
1 3 5
0 0 2
0 0 1
max(最大需求矩阵):
0 0 4
1 7 5
2 3 5
0 6 4
0 6 5
need(需求矩阵):
0 0 1
0 7 5
1 0 0
0 6 2
0 6 4
available(可利用资源向量):
available[0] = 1
available[1] = 1
available[2] = 1
安全序列:
Process-0 ==> Process-2 ==>
各进程完成情况:
Process-0 : finshed
Process-1 : locked
Process-2 : finshed
Process-3 : locked
Process-4 : locked
是否安全:
isSafe=false这就不安全了，不相信？要不你手算一下？