1 创作的小心思

该作旨在完成老师布置的实验任务，也借此机会系统的将银行家算法再学一遍。也可以蹭一波大家的热度，嘻嘻🤭，欢迎来访🎉🎉🎉

2 追根溯源

银行家算法（Banker’s Algorithm） 是一个避免死锁（Deadlock） 的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。(来源：百度百科)

3 算法设计

3.1 银行家算法

3.1.1 所需维护的数据结构

1、可利用资源向量 A v a i l a b l e Available Available。这是一个含有 m m m个元素的一维数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。若
A v a i l a b l e [ j ] = K Available[j] = K Available[j]=K,则表示系统中现有 R j R_j Rj​ 类资源 K K K 个。

2、最大需求矩阵 M a x Max Max。这是一个 n × m n×m n×m 的矩阵，它定义了系统中 n n n 个进程中的每个进程对 m m m 类资源的最大需求。若 M a x [ i ] [ j ] = K Max[i][j] = K Max[i][j]=K ,则表示进程 i i i 需要 R j R_j Rj​ 类资源的最大数目为 K K K 。

3、分配矩阵 A l l o c a t i o n Allocation Allocation。这是一个 n × m n×m n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。若 A l l o c a t i o n [ i ] [ j ] = K Allocation[i][j] = K Allocation[i][j]=K ,则表示进程 i i i 当前已分得 R j R_j Rj​ 类资源的数目为 K K K 。

4、需求矩阵 N e e d Need Need。这是一个 n × m n×m n×m 的矩阵，用以表示每一个进程尚需的各类资源数。若 N e e d [ i ] [ j ] = K Need[i][j] = K Need[i][j]=K ,则表示进程 i i i 还需要 R j R_j Rj​ 类资源 K K K个方能完成其任务。

3.1.2 算法执行步骤

设 R e q u e s t [ i ] Request[i] Request[i] 是进程 P i P_i Pi​ 的请求向量， 如果 R e q u e s t [ i ] [ j ] = K Request[i][j]=K Request[i][j]=K, 表示进程 P i P_i Pi​ 需要 K K K 个 R j R_j Rj​类型的资源。
当 P i P_i Pi​ 发出资源请求后，系统按下述步骤进行检查：
(1)、如果 R e q u e s t [ i ] [ j ] ≤ N e e d [ i ] [ j ] Request[i][j]≤Need[i][j] Request[i][j]≤Need[i][j],便转向步骤(2); 否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。
(2)、如果 R e q u e s t [ i ] [ j ] ≤ A v a i l a b l e [ j ] Request[i][j]≤Available[j] Request[i][j]≤Available[j] ,便转向步骤(3); 否则，表示尚无足够资源， P i P_i Pi​ 须等待。
(3)、系统试探着把资源分配给进程 P i P_i Pi​ ，并修改下面数据结构中的值：
A v a i l a b l e [ j ] = A v a i l a b l e [ j ] − R e q u e s t [ i ] [ j ] A l l o c a t i o n [ i ] [ j ] = A l l o c a t i o n [ i ] [ j ] + R e q u e s t [ i ] [ j ] N e e d [ i ] [ j ] = N e e d [ i ] [ j ] − R e q u e s t [ i ] [ j ] Available[j]=Available[j]-Request[i][j] \\ Allocation[i][j]=Allocation[i][j]+Request[i][j] \\ Need[i][j]=Need[i][j]-Request[i][j] Available[j]=Available[j]−Request[i][j]Allocation[i][j]=Allocation[i][j]+Request[i][j]Need[i][j]=Need[i][j]−Request[i][j]
(4)、系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 P i P_i Pi​ ，以完成本次分配；否则，将本次试探分配作废，恢复原来资源分配状态，让进程 P i P_i Pi​ 等待。

3.1.3 流程图

3.2 安全性算法

3.2.1 所需维护的数据结构

1、工作向量 W o r k Work Work, 这是一个含有 m m m 个元素的一维数组，它表示系统可提供给进程继续运行所需的各类资源的数目，在执行安全算法开始时， W o r k = A v a i l a b l e Work=Available Work=Available。（其实和 A v a i l a b l e Available Available 所维护的内容一样）
2、进程状态向量 F i n i s h Finish Finish，这是一个含有 n n n 个元素的一维数组,它表示每一个进程是否运行完成，用布尔值来表示进程的状态， F i n i s h [ i ] = T r u e Finish[i]=True Finish[i]=True 表示进程 P i P_i Pi​ 已经运行完成，否则运行未完成。

3.2.2 算法执行步骤

(1) 从进程集合中找到一个能满足下述条件的进程：
① F i n i s h [ i ] = F a l s e Finish[i]=False Finish[i]=False;
② N e e d [ i ] [ j ] ≤ W o r k [ j ] Need[i][j]≤Work[j] Need[i][j]≤Work[j];（注意：此处需要所有 m m m 类资源都满足该条件）
若找到，执行步骤(2)，否则，执行步骤(3)。
(2) 当进程 P i P_i Pi​获得资源后，可顺利执行，直至完成，并释放出分配给它的资源：
W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i ] [ j ] ; F i n i s h [ j ] = T r u e ; g o   t o   s t e p   1 ; Work[j]=Work[j]+Allocation[i][j]; \\ Finish[j]=True; \\ go\ to\ step\ 1; Work[j]=Work[j]+Allocation[i][j];Finish[j]=True;go to step 1;
(4) 如果所有进程的Finish[i]=True都满足，则表示处于安全状态；否则，系统处于不安全状态。

3.2.3 流程图

4 算法示例

4.1 示例题目

4.2 例题求解

5 C++代码实现

5.1 C++源代码（全）

1.0版本，后续有时间了可能会再回来加强一波。请求资源方面，目前只能一次性分配一个，不能同时得到请求，需要改进，其他的基本功能算是实现了。执行过程的状态，比交好实现，加个输出就OK，比较简单，代码中就没实现。

#include<cstdio>
#include<queue>
#include<vector>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 1010;
int n, m;
int Max[N][M], Allocation[N][M], Need[N][M];
int Available[M], Finish[N];
int Work[M], Request[M];
int Sum[M];//系统中m类资源的总量
void Init()
{
	cout << "请输入合法的矩阵" << endl;
	cout << "初始化Max矩阵" << endl;
	cout << "请输入一个" << n << "行" << m << "列的矩阵:" << endl;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			cin >> Max[i][j];

	cout << "初始化Allocation矩阵" << endl;
	cout << "请输入一个" << n << "行" << m << "列的矩阵:" << endl;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			cin >> Allocation[i][j];

	cout << "初始化Available向量" << endl;
	cout << "请输入一行" << m << "个元素表示当前可用资源的数量:" << endl;
	for (int i = 1;i <= m;i++) cin >> Available[i];

	/*初始化Need矩阵*/
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			Need[i][j] = Max[i][j] - Allocation[i][j];
		}
	}
	/*初始化Sum矩阵*/
	for (int j = 1;j <= m;j++)
	{
		for (int i = 1;i <= n;i++)
		{
			Sum[j] += Allocation[i][j];
		}
		Sum[j] += Available[j];
	}
	cout << "初始化成功>^V^<" << endl;
}
/*判断初始化矩阵的合法性*/
bool Judge()
{
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			if (Allocation[i][j] > Max[i][j]) return false;
		}
	}
	return true;
}
/*判断当前work向量是否大于Need[i]向量*/
bool Judge(int k)
{
	for (int j = 1;j <= m;j++)
	{
		if (Need[k][j] > Work[j]) return false;
	}
	return true;
}
/*安全性检查的时候虚拟处理*/
void VirtureDeal(int k)
{
	for (int j = 1;j <= m;j++)
	{
		Work[j] += Allocation[k][j];
	}
	Finish[k] = true;
}
/*安全性检查*/
bool SecurityCheck(queue<int>& q)
{
	memcpy(Work, Available, sizeof Available);
	memset(Finish, false, sizeof Finish);
	for(int k = 1;k <= n;k++) //n次迭代
	{
		bool flag = false;
		for (int i = 1;i <= n;i++)
		{
			if (!Finish[i] && Judge(i))
			{
				flag = true;
				q.push(i);
				VirtureDeal(i);
				break;
			}
		}
		if (!flag) return false;
	}
	return true;
}
/*试探性分配资源*/
void Alloc(int k)
{
	for (int j = 1;j <= m;j++)
	{
		Allocation[k][j] += Request[j];
		Need[k][j] -= Request[j];
		Available[j] -= Request[j];
	}
}
/*恢复原状*/
void Recover(int k)
{
	for (int j = 1;j <= m;j++)
	{
		Allocation[k][j] -= Request[j];
		Need[k][j] += Request[j];
		Available[j] += Request[j];
	}
}
/*请求资源*/
void Query()
{
	int ID;
	cout << "请输入进程ID(1 -- " << n << "):" << endl; cin >> ID;
	cout << "请输入请求向量(输入" << m << "个有效整数):" << endl;
	for (int j = 1;j <= m;j++) cin >> Request[j];
	for (int j = 1;j <= m;j++)
	{
		if (Request[j] > Need[ID][j])
		{
			cout << "出错，请求的资源大于需求资源" << endl;
			return;
		}
		else if (Request[j] > Available[j])
		{
			cout << "进程无法得到资源，继续处于等待状态！" << endl;
			return;
		}
	}
	Alloc(ID);//试探性分配
	queue<int> q;
	if (SecurityCheck(q))
	{
		cout << "分配资源成功！" << endl;
		cout << "其中的一个安全序列是：";
		bool mark = false;
		while (q.size())
		{
			if (mark) cout << "->";
			cout << q.front();q.pop();
			mark = true;
		}
		cout << endl;
	}
	else {
		cout << "无法执行分配任务！" << endl;
		Recover(ID);//无法执行分配，恢复原状
	}
}
int main()
{
	cout << "请输入进程个数: "; cin >> n;
	cout << "请输入资源的种类数: "; cin >> m;
	Init();
	system("pause");
	while (1)
	{
		system("cls");
		cout << "1、请求资源" << endl;
		cout << "2、检查当前状态的安全性" << endl;
		cout << "0、退出主程序" << endl;
		while (1)
		{
			int op; cin >> op;
			if (op < 0 || op > 2) {
				cout << "操做错误，请重新输入！！！" << endl;
				system("pause");
			}
			else {
				if (op == 0) exit(0);
				else if (op == 1) {
					Query();
					system("pause");
				}
				else if (op == 2)
				{
					queue<int> q;
					if (SecurityCheck(q))
					{
						cout << "当前状态安全" << endl;
						cout << "其中的一个安全序列是：";
						bool mark = false;
						while (q.size())
						{
							if (mark) cout << "->";
							cout << q.front();q.pop();
							mark = true;
						}
						cout << endl;
					}
					else {
						cout << "当前状态不安全，极有可能进入死锁状态" << endl;
					}
					system("pause");
				}
			}
			break;
		}
	}
	return 0;
}
/*
Max
3 2 2
6 1 3
3 1 4
4 2 2
Allocation
1 0 0
4 1 1
2 1 1
0 0 2
Available
2 1 2
*/

5.2 测试截图

5.2.1 初始化

5.2.2 进程1发出资源请求（1，0，1）

5.2.3 进程2发出资源请求（1，0，1）

5.2.4 检查当前状态安全性

欢迎大家在评论区提出自己的疑问，我会在评论区进行回复。
也欢迎批评我写的不足之处，能力范围之内我会进行加强，我们一起共勉👊。