操作系统实验：银行家算法（C语言）

实验内容：

某系统中进程P1、P2、P3……Pn，同时请求资源R1、R2、R3……Rn，已知t0时刻资源分配情况（参考下表）。
（1）编写程序，分析当前系统状态是否安全，若系统安全，请输出安全序列。
（2）在系统安全的情况下，若有进程提出资源请求（如t1时刻进程P2提出请求Rq(1，2，2，2)），分析系统可否响应该请求。

实验目的：

1.加深了解有关资源申请、避免死锁等概念；
2.体会和了解死锁和避免死锁的具体实施方法；
3.掌握银行家算法，设计实验数据验证其分配策略。

实验原理：问题分析及算法设计（流程图）

问题：如何寻找安全分配策略
使用递归算法，判断当前进程是否能获取资源，能则标记当前进程访问过，递归判断未访问的进程，如果所有进程访问完成返回true，如果都不能获取资源返回false

实验代码：

#include "stdio.h"
#include "string.h"
typedef struct resource_allocation{
	char name[10]; 
	int Work[10]; 
	int Max[10];
	int Allocation[10];
	int Need[10];
	int Work_Allocation[10];
}RA;

int visited[10];
RA ra1[10];
int ra1_count = 0;
bool check_security(RA* ra,int* Init_Available,int resourse_count,int process_count,int count){
	if(count == process_count){
		return true;
	}
	for(int i = 0; i < process_count; i++){
		if(visited[i] == 1){
			continue;
		}
		int flag = 1;
		//判断当前进程是否满足条件 
		for(int j = 0; j < resourse_count; j++){
			if(ra[i].Need[j] > Init_Available[j]){
				flag = 0;
				break; 
			}
		} 
		if(flag == 1){
			visited[i] = 1;
			for(int j = 0; j < resourse_count; j++){
				ra[i].Work_Allocation[j] = ra[i].Allocation[j]+Init_Available[j];
				ra[i].Work[j] = Init_Available[j];
				Init_Available[j] = ra[i].Work_Allocation[j];
			}
			//按顺序存储在ra1中 
			ra1[count] = ra[i];
			//判断是否有安全进程,有则返回true,没有则继续查找 
			if(check_security(ra,Init_Available,resourse_count,process_count,count+1)){
				return true;
			}else{
				visited[i] = 0;
				for(int j = 0; j < resourse_count; j++){
					Init_Available[j] = ra[i].Work[j];
				}
			}
		}
	}
	return false;
}

void Print(int process_count, int resourse_count){
	printf("能找到一个安全序列:");
		for(int i = 0 ; i <  process_count; i++){
			printf("%s ",ra1[i].name);
		}
		printf("\n");
		printf("资源\tWork\t\tNeed\t\tAllocation\tWork+Allocation\t\tfinish\n");
		printf("进程\tA B C D\t\tA B C D\t\tA B C D\t\tA B C D\t\tA B C D\n");
		for(int i = 0; i < process_count; i++){
			printf("%s\t",ra1[i].name);
			for(int j = 0; j < resourse_count; j++){
				printf("%d ",ra1[i].Work[j]);
			} 
			printf("\t");
			for(int j = 0; j < resourse_count; j++){
				printf("%d ",ra1[i].Need[j]);
			} 
			printf("\t");
			for(int j = 0; j < resourse_count; j++){
				printf("%d ",ra1[i].Allocation[j]);
			} 
			printf("\t");
			for(int j = 0; j < resourse_count; j++){
				printf("%d ",ra1[i].Work_Allocation[j]);
			} 
			printf("\ttrue\n");
		}
}

int main(){
	//1.
	int resourse_count;
	printf("请输入资源数:"); 
	scanf("%d",&resourse_count);
	int process_count;
	printf("请输入进程数:") ;
	scanf("%d",&process_count);
	RA ra[10];//资源分配 
	int Init_Available[10];//初始总资源
	printf("请输入总资源:") ;
	for(int i = 0; i < resourse_count; i++){
		scanf("%d",&Init_Available[i]);
	}
	printf("请输入各进程分配的资源:\n"); 
	for(int i = 0; i < process_count; i++){
		getchar(); 
		printf("请输入进程名:");
		scanf("%s",ra[i].name);
		printf("请输入%s资源MAX:",ra[i].name); 
		for(int j = 0; j <resourse_count; j++){
			scanf("%d",&ra[i].Max[j]);
		}
		printf("请输入%s资源Allocation:",ra[i].name); 
		for(int j = 0; j <resourse_count; j++){
			scanf("%d",&ra[i].Allocation[j]);
		}
		printf("请输入%s资源Need:",ra[i].name); 
		for(int j = 0; j <resourse_count; j++){
			scanf("%d",&ra[i].Need[j]);
		}
	}
	//检测
	if(check_security(ra,Init_Available,resourse_count,process_count,0)){
		Print(process_count, resourse_count);
	}else{
		printf("不能找到一个安全序列\n"); 
	}
	
	//2.
	printf("是否要修改系统分配资源(Y/N):");
	char a;
	getchar();
	scanf("%c",&a);
	if(a == 'Y'){
		printf("输入请求资源的进程:");
	 	int p;
	 	scanf("%d",&p);
	 	for(int i = 0; i < resourse_count; i++){
	 		int req;
	 		scanf("%d",&req);
	 		Init_Available[i] -= req;
	 		ra[p].Need[i] -= req;
	 		ra[p].Allocation[i] += req;
		}
		if(check_security(ra,Init_Available,resourse_count,process_count,0)){
			Print(process_count, resourse_count);
		}else{
			printf("不能找到一个安全序列\n"); 
		}
	} 
}
/*
4
5
1 6 2 2
P0
0 0 4 4
0 0 3 2
0 0 1 2
P1
2 7 5 0
1 0 0 0
1 7 5 0
P2
3 6 10 10
1 3 5 4
2 3 5 6
P3
0 9 8 5
0 3 3 3
0 6 5 2
P4
0 6 6 10
0 0 1 4
0 6 5 6
Y
2
1 2 2 2
*/

实验结果：（截图）

实验总结：（心得体会）

通过此次实验对安全检查的思路有了更深的理解，对死锁的机制，资源申请的有关概念更加熟悉。