银行家算法（安全序列）

admin管理员组

文章数量:1341704

前言

要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

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

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

那么什么是安全序列呢？

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

算法思路

参数介绍：

n：系统中进程的总数

m：资源类总数

Available：可用剩余资源

Max：最大需求

Allocation：已分配资源

Need：需求（缺少）资源

安全性检查的步骤：

step (1)

Work=Available;

Finish=false;

step (2)

寻找满足条件的i：

a.Finish==false;

b.Need<=Work;

如果不存在，goto step(4)

step(3)

Work=Work+Allocation;

Finish=true;

goto step(2)

step (4)

若对所有i，Finish=true，则系统处于安全状态，否则处于不安全状态

代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

/*
 *  n：系统中进程的总数
 *  m：资源总数
 */
int n, m;
/*
 *  Available：可用剩余资源
 *  Max：最大需求
 *  Allocation：已分配资源
 *  Need：需求资源
 */
int **Max, **Allocation, **Need, *Avaliable;
/*
 *  Work：动态存储当前Available的值
 *  Finish：判断进程i是否为安全序列之一（0：不是  1：是）
 *  result：存储安全序列
 */
int *Work, *Finish;
vector<int> result;

bool check() {
	Work = new int[m];
	for (int i = 0; i < m; i++) {
		Work[i] = Avaliable[i];
	}
	Finish = new int[n];
	memset(Finish, 0, n * sizeof(Finish));  // 初始化数组为0

	for (int tmp = 0; tmp < n; tmp++) {
		for (int i = 0; i < n; i++) {
			if (Finish[i] == 0) {
				int ans = 0;
				for (int j = 0; j < m; j++) {
					if (Need[i][j] <= Work[j]) {
						ans++;
					}
				}
				if (ans == m) {  // 满足安全序列条件
					for (int j = 0; j < m;j++) {
						Work[j] += Allocation[i][j];
					}
					Finish[i] = 1;
					result.push_back(i);
					break;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (Finish[i] == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	cout << "请输入进程总数n和资源总数m：" << endl;
	cin >> n >> m;
	
	// 动态初始化二维数组
	Max= new int *[n];
	Allocation = new int *[n];
	Need = new int*[n];
	for (int i = 0; i < n; i++) {
		Max[i] = new int [m];
		Allocation[i] = new int [m];
		Need[i] = new int[m];
	}
	Avaliable = new int[m];

	cout << "请输入各个进程已分配的资源数（Allocation）：" << endl;
	for (int i = 0; i < n; i++) {
		cout << "进程" << char('A' + i) << "：";
		for (int j = 0; j < m; j++) {
			cin >> Allocation[i][j];
		}
	}
	cout << "请输入各个进程的最大需求资源数（Max）：" << endl;
	for (int i = 0; i < n; i++) {
		cout << "进程" << char('A' + i) << "：";
		for (int j = 0; j < m; j++) {
			cin >> Max[i][j];
		}
	}
	cout << "请输入当前系统可用剩余资源数（Avaliable）：" << endl;
	for (int i = 0; i < m; i++) {
		cin >> Avaliable[i];
	}
	// 手动计算各个进程缺少的资源数（Need）
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			Need[i][j] = Max[i][j] - Allocation[i][j];
		}
	}

	if (check()) {
		cout << "系统处于安全状态!\n安全序列为：";
		for (int x : result) {
			cout << char('A' + x) << " ";
		}
		cout << endl;
	}
	else {
		cout << "系统处于非安全状态!！" << endl;
	}
	return 0;
}


/*

4 3
1 0 0
5 1 1
2 1 1
0 0 2
3 2 2
6 1 3
3 1 4
4 2 2
1 1 2

*/

本文标签： 银行家序列算法