[C++知识库]用C语言或C++编写一个简单的银行家算法模拟程序

1.问题描述

银行家算法是操作系统中避免死锁的典型算法。用C语言或C++编写一个简单的银行家算法模拟程序，实现多个进程争用系统临界资源时的分配过程。要求程序实现：
1.当一进程请求一组资源时，先确定是否有足够的资源分配给该进程。如果有，再进一步计算在将这些资源分配给进程后，系统是否处于不安全状态。如果安全，显示安全序列，将资源分配给该进程，否则进程等待。
2.可以显示当前时刻各进程的的资源分配情况。

2.问题分析

①相关概念
死锁：指多个并发进程彼此等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而使得各进程不能继续向前推前。

避免死锁（动态预防）：允许进程动态地申请资源，但系统在进行资源分配之前，应先计算这次资源分配的安全性。若这次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待
银行家算法是一种用来避免操作系统死锁出现的有效算法。为实现银行家算法，系统必须设置若干数据结构，同时要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全状态：是指系统能按某种进程顺序(P1,P2,…,Pn) (称<P1,P2,…,Pn>序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

②银行家算法中的数据结构：

可利用资源向量 Available[m]
最大需求矩阵 Max[n][m]
分配矩阵 Allocation[n][m]
需求矩阵 Need[n][m]
进程Pi的请求向量 Request[m]
其中， Need［i,j］=Max［i,j］-Allocation［i,j］

银行家算法描述：

(1) If (Requesti［j］≤Need［i,j］)   转(2)；
 	else  出错处理。
(2) If (Requesti［j］≤Available［j］)，转(3)；
    else  Pi等待。 
(3) 系统试着把资源分配给进程Pi，即修改下面数据结构中的数值：
	Available［j］= Available［j］-Requesti［j］;
	Allocation［i,j］= Allocation［i,j］+Requesti［j］;
	Need［i,j］= Need［i,j］-Requesti［j］;
(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
	If(安全)正式将资源分配给进程Pi;
	else  将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

③安全性算法中的数据结构：

Work[m]：工作向量，表示系统可提供给进程继续运行所需的各类资源数目，在执行安全算法开始时，Work=Available
Finish[n]：它表示系统是否有足够的资源分配给进程、使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true

安全性算法描述：

(1)从进程集合中找到一个能满足下述条件的进程Pi：
	(Finish［i］=false && Need［i,j］≤Work［j])
	如果找到，转(2)，否则，转(3)；
(2)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
	Work［j］= Work［j］+Allocation［i,j］;
	Finish［i］= true;
	转(1);
(3) If(所有进程的Finish［i］= true)系统处于安全状态；
    else  系统处于不安全状态。

3、问题解决

#include<unistd.h>
#include<stdio.h>
#include<stdlib.h>

#define RESOURCES_MAX 5//系统最多拥有5种资源
#define PROCESS_MAX 5//系统最多拥有的进程数
#define true 1
#define false 0
typedef int bool;

int available[RESOURCES_MAX];//可利用资源向量
int maxRequest[PROCESS_MAX][RESOURCES_MAX];//最大需求矩阵
int allocation[PROCESS_MAX][RESOURCES_MAX];//分配矩阵
int need[PROCESS_MAX][RESOURCES_MAX];//需求矩阵
bool Finish[PROCESS_MAX];
int safeSeries[PROCESS_MAX];//记录安全序列
int request[RESOURCES_MAX];//进程Pi的请求向量Requesti[j]

int resource_num;//输入的资源数量种类数
int process_num;//输入的进程数量
#define name_size 5 //资源名称的字符长度
char resource_name[RESOURCES_MAX][name_size];//记录各资源名称

void showInfo();/*显示系统目前可用的资源*/
bool isSafe();//安全性算法的实现
void showSafe();//安全序列的信息

int main() {
	/**输入，初始化各矩阵**/
	printf("输入资源种类：");
	scanf("%d", &resource_num);//输入的资源种类数
	for (int i = 0; i < resource_num; i++) {//每种资源的数量
		printf("输入资源%d的名称:", i + 1);
		scanf("%s", resource_name[i]);
		printf("输入资源%d的数量:", i + 1);
		scanf("%d", &available[i]); //可利用资源向量available[]

	}
	printf("输入进程的数量：");//输入的进程数
	scanf("%d", &process_num);
	printf("输入各进程的最大需求量(5*3矩阵)[maxRequest]:\n");
	for (int i = 0; i < process_num; i++)
		for (int j = 0; j < resource_num; j++)
			scanf("%d", &maxRequest[i][j]);//最大需求矩阵maxRequest

	printf("输入各进程已经申请的资源量(5*3矩阵)[allocation]:\n");
	for (int i = 0; i < process_num; i++)
		for (int j = 0; j < resource_num; j++)
			scanf("%d", &allocation[i][j]);//已分配矩阵allocation

	/*计算需求矩阵need，need[i,j]=maxRequest[i,j]-allocation[i,j]*/
	for (int i = 0; i < process_num; i++)
		for (int j = 0; j < resource_num; j++)
			need[i][j] = maxRequest[i][j] - allocation[i][j];//需求矩阵need

	/*显示系统目前可用的资源*/
	showInfo();

	/**判断系统是否安全**/
	isSafe();

	while (1) {
		printf("***********************************\n");
		printf("1:分配资源\n2:显示分配情况\n0:离开\n");
		printf("***********************************\n");
		printf("请选择功能号：");
		int choice;
		scanf("%d", &choice);

		if (choice == 0) {//离开
			printf("已离开!\n");
			break;
		}
		if (choice == 2) {//显示分配情况
			showInfo();//显示系统目前可用的资源
			continue;
		}
		if (choice == 1) {//分配资源
			int processID;//要求分配的资源进程号
			printf("请输入要求分配的资源进程号(0-4):");
			scanf("%d", &processID);
			printf("请输入进程 %d 申请的资源:\n", processID);
			for (int i = 0; i < resource_num; i++) {
				printf("%s:", resource_name[i]);
				scanf("%d", &request[i]);
			}

			//检查request[i]与该进程的need[][i],available[i]
			for (int i = 0; i < resource_num; i++) {
				if ((request[i] > need[processID][i]) || (request[i] > available[i])) {
					printf("没有足够的资源分配给该进程!\n");
					continue;
				}
			}

			//假设可以分配资源,修改available,allocation,need
			for (int i = 0; i < resource_num; i++) {
				available[i] = available[i] - request[i];
				allocation[processID][i] += request[i];
				need[processID][i] -= request[i];
			}

			/**判断系统是否安全**/
			if (isSafe())continue;
			else {//系统不安全,不予分配
				for (int i = 0; i < resource_num; i++) {
					available[i] += request[i];
					allocation[processID][i] -= request[i];
					need[processID][i] += request[i];
				}
			}
		}//if(choice==1)
	}//while
	return 0;
}

void showInfo() {
	/*显示系统目前可用的资源*/
	printf("\n系统目前可用的资源[avaliable]:\n");
	for (int i = 0; i < resource_num; i++) {
		printf("%s\t", resource_name[i]);
	}
	printf("\n");
	for (int i = 0; i < resource_num; i++) {
		printf("%d\t", available[i]);
	}
	printf("\n");

	printf("\tMax  Allocation  Need\n");
	printf("进程");
	for (int i = 0; i < 3; i++) {
		printf("\t");
		for (int i = 0; i < resource_num; i++) {
			printf("%s ", resource_name[i]);
		}
	}
	printf("\n");
	for (int i = 0; i < process_num; i++) {
		printf("%d\t", i);//进程i
		for (int j = 0; j < resource_num; j++) {
			printf("%d ", maxRequest[i][j]);
		}
		printf("\t");
		for (int j = 0; j < resource_num; j++) {
			printf("%d ", allocation[i][j]);
		}
		printf("\t");
		for (int j = 0; j < resource_num; j++) {
			printf("%d ", need[i][j]);
		}
		printf("\n");
	}
}

/*安全性算法的实现*/
bool isSafe() {
	int work[RESOURCES_MAX];//工作向量,表示系统可提供给进程继续运行所需的各类资源数目
	for (int i = 0; i < resource_num; i++)//在执行安全算法开始时，Work=Available
		work[i] = available[i];

	for (int i = 0; i < process_num; i++)//初始时未分配够资源
		Finish[i] = false;

	int safeIndex = 0;//安全序列下标
	int tempIndex = 0;//记录上次 从进程0遍历完所有进程时，安全序列的下标
	int i = 0;//进程下标
	while (1) {
		if (Finish[i] == false) {//进程i还未加入安全序列
			int j = 0;
			for (j = 0; j < resource_num; j++) {
				if (need[i][j] > work[j])//need:5*3 work 1*3
					break;
			}
			if (j == resource_num) {// 每个need[i][j]<=work[j]，可以给进程i分配资源
				Finish[i] = true;
				safeSeries[safeIndex] = i;//进程i放入安全序列
				safeIndex++;
				for (int k = 0; k < resource_num; k++)
					work[k] = work[k] + allocation[i][k];
			}
		}

		if (safeIndex == process_num) {//所有进程的Finish[i]=true,存在安全序列safeSeries[],系统处于安全状态
			showSafe();//安全序列信息
			printf("系统是安全的!\n");
			for (int i = 0; i < process_num; i++) {
				printf("%d", safeSeries[i]);
				if (i != (process_num - 1))printf("->");
			}
			printf("\n");
			return true;
		}
		i++;//下一个进程
		if (i == process_num) {//已经从头遍历所有进程
			if (tempIndex == safeIndex) {//安全序列没有新增进程
				printf("系统不存在安全序列，不予分配！\n");
				return false;
			}
			else {//安全序列新增进程
				tempIndex = safeIndex;
				i = i % process_num;//下一个进程
			}
		}
	}//while(1)
}

void showSafe() {
	int work[RESOURCES_MAX];//工作向量
	for (int i = 0; i < resource_num; i++)//开始时，Work=Available
		work[i] = available[i];
	printf("\tWork  Allocation  Need\n");
	printf("进程");
	for (int i = 0; i < 3; i++) {
		printf("\t");
		for (int i = 0; i < resource_num; i++)
			printf("%s ", resource_name[i]);
	}
	printf("\n");
	int processID;
	for (int i = 0; i < process_num; i++) {
		processID = safeSeries[i];
		printf("%d\t", processID);//进程safeSeries[i]
		for (int j = 0; j < resource_num; j++)
			printf("%d ", work[j]);
		printf("\t");
		for (int j = 0; j < resource_num; j++)
			printf("%d ", allocation[processID][j]);
		printf("\t");
		for (int j = 0; j < resource_num; j++)
			printf("%d ", need[processID][j]);
		printf("\n");
		for (int j = 0; j < resource_num; j++)
			work[j] += allocation[processID][j];//释放出分配给它的资源
	}
}

测试：