CC++实现银行家算法

admin 管理员组

文章数量: 887017

银行家算法C/C++实现

• 概念
• • 死锁
  • • 条件
  • 安全序列
  • 安全状态
  • 不安全状态
  • 数据结构
  • • 关系
• 过程图
• 例子
• 代码实现
• • DFS安全序列
  • • 思路
    • 问题
    • 代码
  • 全部代码
• 参考

概念

银行家算法是一种用来避免操作系统死锁出现的有效算法，所以在引入银行家算法的解释之前，有必要简单介绍下死锁的概念。

死锁

是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

条件

死锁的发生必须具备以下四个必要条件：

1. 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
3. 不抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4. 循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

避免死锁算法中最有代表性的算法就是Dijkstra E.W 于1968年提出的银行家算法，银行家算法是避免死锁的一种重要方法，防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。

为实现银行家算法，系统必须设置若干数据结构，同时要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

安全序列

是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

安全状态

如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态

不存在一个安全序列。不安全状态不一定导致死锁。

数据结构

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]

过程图

例子

在银行家算法中，若出现下述资源分配情况：

注：题中共四种资源，P0的Allocation为（0，0，3，2）表示已分配给P0的第一种资源和第二种资源为0个，第三种资源3个，第四种资源2个。

（1）该状态是否安全？ （2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

（1）利用安全性算法对上面的状态进行分析（见下表），找到了一个安全序列{P0,P3,P4,P1,P2}，故系统是安全的。

（2）P2发出请求向量Request(1,2,2,2),系统按银行家算法进行检查：

①Request2(1,2,2,2)<=Need2(2,3,5,6)
②Request2(1,2,2,2)<=Available(1,6,2,2)
③系统先假定可为P2分配资源，并修改Available，Allocation2和Need2向量：
Available=(0,4,0,0)
Allocation2=(2,5,7,6)
Need2=(1,1,3,4)
此时再进行安全性检查，发现 Available=(0,4,0,0) 不能满足任何一个进程，所以判定系统进入不安全状态，即不能分配给P2相应的Request(1,2,2,2)。

代码实现

DFS安全序列

思路

递归从N个进程里选一个满足条件的进程作为一个安全序列的第一个元素，之后再各自从剩下的进程中选择满足条件的作为第二个元素……以此类推

问题

由于确定每一个安全序列、以及确定安全序列的每一个元素的过程中is_Finish和work[j]都在变化，所以需要一个撤回操作的步骤(回溯）

代码

// 深搜找安全序列
void isSafe(int v) {
	// 递归出口
	// 如果v等于进程个数，打印，存储安全序列
	if (v == n) {
		safe.push_back(lsafe);
		return;
	}
	// 遍历寻找合适的开始进程
	for (int i = 0; i < n; i++) {
		// 判断进程是否处理完成
		if (!processes[i].is_Finish) {
			// 判断进程是否可以处理
			if (resource_compare(processes[i].need)) {
				// 暂时放入安全序列
				processes[i].is_Finish = true;
				lsafe.push_back(processes[i]);
				for (int j = 0; j < m; j++)
					work[j] += processes[i].allocation[j];
				isSafe(v + 1); // 搜索下一个运行进程
				// 回溯
				lsafe.pop_back();
				for (int j = 0; j < m; j++)
					work[j] -= processes[i].allocation[j];
				processes[i].is_Finish = 0;
			}
		}
	}
}

全部代码

#define MAXPROCESS 255
#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 进程类定义
class Process
{
public:
	// 进程名字
	string name;
	// 资源种类数目
	int allocation_and_need_size;
	// 已分配资源
	int *allocation;
	// 需求资源
	int *need;
	// 是否完成
	bool is_Finish = false;

	Process(int allocation_and_need_size, string name);
	Process();


};
// 构造函数初始化
Process::Process(int allocation_and_need_size, string name) {
	Process::allocation_and_need_size = allocation_and_need_size;
	Process::name = name;
	// 初始化数组
	allocation = new int[allocation_and_need_size];
	need = new int[allocation_and_need_size];
}
// 默认构造函数，用于动态分配内存
Process::Process() {}

// 系统剩余资源
int *work;
// n：进程个数  m：资源种类
int n, m;
// 进程
Process *processes;
// 安全序列
vector<vector<Process>> safe;
vector<Process> lsafe;

void print_table() {
	printf("Process\t\tAllocatioin\tNeed\t\tAvailable\n");
	for (int i = 0; i < n; i++) {
		cout << processes[i].name;
		printf("\t\t");
		for (int j = 0; j < processes[i].allocation_and_need_size; j++) {
			if (j) cout << " ";
			printf("%d", processes[i].allocation[j]);
		}
		printf("\t\t");
		for (int j = 0; j < processes[i].allocation_and_need_size; j++) {
			if (j) cout << " ";
			printf("%d", processes[i].need[j]);
		}
		printf("\t\t");
		for (int j = 0; j < m; j++) {
			if (j) cout << " ";
			printf("%d", work[j]);
		}
		printf("\n");
	}
}

bool resource_compare(int *compare) {
	for (int i = 0; i < m; i++) {
		if (compare[i] > work[i]) return false;
	}
	return true;
}

// 深搜找安全序列
void isSafe(int v) {
	// 递归出口
	// 如果v等于进程个数，打印，存储安全序列
	if (v == n) {
		safe.push_back(lsafe);
		return;
	}
	// 遍历寻找合适的开始进程
	for (int i = 0; i < n; i++) {
		// 判断进程是否处理完成
		if (!processes[i].is_Finish) {
			// 判断进程是否可以处理
			if (resource_compare(processes[i].need)) {
				// 暂时放入安全序列
				processes[i].is_Finish = true;
				lsafe.push_back(processes[i]);
				for (int j = 0; j < m; j++)
					work[j] += processes[i].allocation[j];
				isSafe(v + 1); // 搜索下一个运行进程
				// 回溯
				lsafe.pop_back();
				for (int j = 0; j < m; j++)
					work[j] -= processes[i].allocation[j];
				processes[i].is_Finish = 0;
			}
		}
	}
}

void printSafe() {
	for (vector<Process> lsafe : safe) {
		for (Process process : lsafe) {
			cout << process.name << " ";
		}
		cout << endl;
	}
}

int main() {
	// 测试文本
	FILE *stream;
	freopen_s(&stream, "test.txt", "r", stdin);

	cout << "请输入进程个数：";
	cin >> n;
	// 对进程数组初始化
	processes = new Process[n];
	// 读入进程名
	for (int i = 0; i < n; i++) {
		cout << "请输入第" << i + 1 << "个进程名：";
		string name;
		cin >> name;
		processes[i].name = name;
	}
	cout << "请输入资源种类数：";
	cin >> m;
	// 读入已分配资源数
	cout << "空格分隔两个数字" << endl;
	for (int i = 0; i < n; i++) {
		cout << "请输入" << processes[i].name << "的已分配资源数：";
		processes[i].allocation_and_need_size = m;
		processes[i].allocation = new int[m];
		for (int j = 0; j < m; j++) {
			cin >> processes[i].allocation[j];
		}
	}
	// 读入还需资源数
	cout << "空格分隔两个数字" << endl;
	for (int i = 0; i < n; i++) {
		cout << "请输入" << processes[i].name << "的还需资源数：";
		processes[i].need = new int[m];
		for (int j = 0; j < m; j++) {
			cin >> processes[i].need[j];
		}
	}

	// 读入空闲资源数
	cout << "请输入空闲资源数：";
	work = new int[m];
	for (int i = 0; i < m; i++) {
		cin >> work[i];
	}

	cout << endl;
	// 打印当前系统中资源状况
	print_table();
	isSafe(0);
	// 判断当前系统状态是否安全
	if (safe.size() == 0) {
		cout << "当前系统状态不安全！无任何安全序列，无法避免死锁！" << endl;
	}
	else {
		cout << "当前系统状态安全！" << endl << "安全序列有：" << endl;
		printSafe();
	}

	// 判断进程发成请求后的安全序列与状态
	string process_name;
	int *req = new int[m];
	cout << "请输入发出请求的进程名：";
	cin >> process_name;
	cout << "请输入请求的资源数：";
	for (int i = 0; i < m; i++) {
		cin >> req[i];
	}

	// 请求后的系统状态
	lsafe.clear();
	safe.clear();
	for (int i = 0; i < m; i++) {
		work[i] -= req[i];
	}
	for (int i = 0; i < n; i++) {
		if (processes[i].name == process_name) {
			for (int j = 0; j < m; j++) {
				processes[i].allocation[j] += req[j];
				processes[i].need[j] -= req[j];
			}
		}
	}
	print_table();

	// 安全性检测
	isSafe(0);
	if (safe.size()) {
		cout << process_name << "可以请求该数量资源！" << endl << "安全序列为：" << endl;
		printSafe();
	}
	else {
		cout << process_name << "不可以请求该数量资源！" << endl;
	}

	// 还原系统状态
	lsafe.clear();
	safe.clear();
	for (int i = 0; i < m; i++) {
		work[i] += req[i];
	}
	for (int i = 0; i < n; i++) {
		if (processes[i].name == process_name) {
			for (int j = 0; j < m; j++) {
				processes[i].allocation[j] -= req[j];
				processes[i].need[j] += req[j];
			}
		}
	}
}

参考

一句话+一张图说清楚——银行家算法
银行家算法---------概念&举例
银行家算法——输出所有安全序列

本文标签： 银行家 算法