一、说明

死锁的处理策略之避免死锁 –

银行家算法

+

安全性算法


1. 假设：系统中有 n 个进程，m 种资源。
2. 银行家算法：
   
   ①检查此次申请是否超过了之前声明的最大需求数。
   
   ②检查此时系统剩余的可用资源是否还能满足这次请求。
   
   ③试探着分配，更改各数据结构。
   
   ④用安全性算法检查此次分配是否会导致系统进入不安全状态。
3. 安全性算法： 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。

二、代码

//bankAlgorithm.h
#ifndef BANKALGORITHM_H
#define BANKALGORITHM_H

//进程数
const int processNum = 5;
//资源数
const int resourceNum = 3;

class bankAlgorithm {
public:
	//构造函数
	bankAlgorithm() = default;
	//资源申请函数
	void sendRequest();
	//安全检查函数
	bool safetyCheck();
	//菜单函数
	void display();
private:
	//可利用资源向量
	int available[resourceNum] = { 3,3,2 };
	//最大需求矩阵
	int max[processNum][resourceNum] = { {7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3} };
	//分配矩阵
	int allocation[processNum][resourceNum] = { {0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2} };
	//需求矩阵
	int need[processNum][resourceNum] = { {7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1} };
	//请求向量
	int request[resourceNum] = { 0,0,0 };
};
#endif // !BANKALGORITHM_H

//bankAlgorithm.cpp
#include "bankAlgorithm.h"
#include <iostream>
#include <string>
using namespace std;

//资源申请函数
void bankAlgorithm::sendRequest() {
	//当前向系统申请资源的进程号
	int processID;
	cout << "请输入向系统申请资源的进程号： ";
	cin >> processID;
	cout << "请输入该进程向系统申请的资源量： ";
	cin >> request[0] >> request[1] >> request[2];
	//①检查此次申请是否超过之前声明的最大需求数
	if (need[processID][0] >= request[0] && need[processID][1] >= request[1] && need[processID][2] >= request[2]) {
		//②检查此时系统剩余的可用资源是否还能满足这次请求
		if (request[0] <= available[0] && request[1] <= available[1] && request[2] <= available[2]) {
			cout << "安全性检查结果：";
			int oldAvailable[resourceNum];
			int oldAllocation[resourceNum];
			int oldNeed[resourceNum];
			//③系统试探着把资源分配给进程，并修改相应的数据
			for (int i = 0; i != resourceNum; ++i) {
				//将旧allocation数组存起来
				oldAllocation[i] = allocation[processID][i];
				//为其分配资源
				allocation[processID][i] = allocation[processID][i] + request[i];

				//将旧need数组存起来
				oldNeed[i] = need[processID][i];
				//为其分配资源
				need[processID][i] = need[processID][i] - request[i];

				//将旧available数组存起来
				oldAvailable[i] = available[i];
				//为其分配资源
				available[i] = available[i] - request[i];
			}
			if (!safetyCheck()) {
				cout << "系统将处于不安全状态，请该进程阻塞等待！" << endl;
				//④系统处于不安全状态。恢复相应数据，让该进程阻塞等待
				for (int i = 0; i != resourceNum; ++i) {
					allocation[processID][i] = oldAllocation[i];
					need[processID][i] = oldNeed[i];
					available[i] = oldAvailable[i];
				}
			}
			else {
				//④系统处于安全状态
				if (need[processID][0] == 0 && need[processID][1] == 0 && need[processID][2] == 0) {
					for (int i = 0; i != resourceNum; ++i)
						available[i] = available[i] + max[processID][i];
				}
				cout << "系统仍处于安全状态，资源申请成功！" << endl;
			}
		}
		else {
			cout << "系统无足够的资源满足该进程的申请！" << endl;
		}
	}
	else {
		cout << "进程所需要的资源数超过它所宣布的最大值！" << endl;
	}
}

//安全检查函数
bool bankAlgorithm::safetyCheck() {
	//辅助标志
	bool flag = true;
	//从表尾循环检查各进程
	int process = processNum - 1;
	//初始化完成数组
	bool finish[processNum];
	for (int i = 0; i != processNum; ++i) { 
		finish[i] = false; 
	}
	//初始化分配数组
	int work[resourceNum];
	for (int i = 0; i != resourceNum; ++i) {
		work[i] = available[i]; 
	}
	//安全序列
	string safety;

	while (process >= 0) {
		//第一步：找到一个未完成且need < work的进程
		if (!finish[process]) {
			for (int i = 0; i != resourceNum; ++i) {
				if (work[i] < need[process][i]) {
					flag = false;
					break;
				}
			}
			//第二步：完成状态设置为true，且将进程的资源归还给work
			if (flag) {
				for (int i = 0; i != resourceNum; ++i) {
					work[i] = work[i] + allocation[process][i];
				}
				finish[process] = true;
				safety += "P" + to_string(process) + " ";
				//重新回到表尾
				process = processNum;
			}
			flag = true;
		}
		--process;
	}

	//第三步，检查各进程是否全部完成
	for (int i = 0; i != processNum; ++i) {
		if (!finish[i]) {
			return false;
		}
	}
	cout << "安全序列为：" << safety << endl;
	return true;
}

void bankAlgorithm::display() {
	cout << "____________________________________________________" << endl;
	cout << "|  资源|   Max   | Allocation |  Need  | Available  |" << endl;
	cout << "----------------------------------------------------" << endl;
	for (int i = 0; i != processNum; ++i) {
		cout << "|  " << "P" << i << "  |";
		cout << " " << max[i][0] << "  " << max[i][1] << "  " << max[i][2] << " |";
		cout << " " << allocation[i][0] << "   " << allocation[i][1] << "   " << allocation[i][2] << "  |";
		cout << "  " << need[i][0] << " " << need[i][1] << " " << need[i][2] << " |";
		if (i == 0) {
			cout << "  " << available[0] << "  " << available[1] << "  " << available[2] << "   |" << endl;
		}
		else {
			cout << "            |" << endl;
		}
	}
}

//main.cpp
#include "bankAlgorithm.h"
#include <iostream>
using namespace std;

int main() {
	bankAlgorithm demo = bankAlgorithm();
	demo.display();

	char c;
	while (true) {
		demo.sendRequest();
		demo.display();

		cout << "是否请求再次分配【Y/N】: ";
		cin >> c;
		if (c == 'Y' || c == 'y')
			continue;
		else if(c == 'N' || c == 'n')
			break;
	}
	
	system("pause");
	return 0;
}