银行家算法

admin管理员组

文章数量:1531451

银行家算法

进程申请资源时，系统通过一定的算法判断本次申请是否不可能产生死锁（处于安全状态）。若可能产生死锁（处于不安全状态），则暂不进行本次资源分配，以避免死锁。算法有著名的银行家算法。
1、什么是系统的安全状态和不安全状态？
所谓安全状态，是指如果系统中存在某种进程序列＜P1，P2，…，Pn＞，系统按该序列为每个进程分配其所需要的资源，直至最大需求，则最终能使每个进程都可顺利完成，称该进程序列＜P1，P2，…，Pn，＞为安全序列。
如果不存在这样的安全序列，则称系统处于不安全状态。
2、银行家算法
把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定:
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量;
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金。

操作系统按照银行家制定的规则设计的银行家算法为：
（1）进程首次申请资源的分配：如果系统现存资源可以满足该进程的最大需求量，则按当前的申请量分配资源，否则推迟分配。
（2）进程在执行中继续申请资源的分配：若该进程已占用的资源与本次申请的资源之和不超过对资源的最大需求量，且现存资源能满足该进程尚需的最大资源量，则按当前申请量分配资源，否则推迟分配。
（3）至少一个进程能完成：在任何时刻保证至少有一个进程能得到所需的全部资源而执行到结束。
银行家算法通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源，并能在确保系统处于安全状态时才把资源分配给申请者，从而避免系统发生死锁。

1、银行家算法流程图；

安全算法流程图：

2、对算法所用的数据结构进行说明；
available[j]：一维数组，表示j类资源可用数目，随机赋值
Max[i][j]：ij矩阵，表示进程i对资源j的最大需求，随机赋值
allocation[i][j]：ij矩阵，表示进程i已经分配到资源j的数目，随机赋值
need[i][j]:ij矩阵表示进程i还需要资源j的数目，且need[i][j]=Max[i][j]-allocation[i][j]
Request[i][j]：ij矩阵，表示进程i对资源j的请求数量
Work[j]：一维数组，表示工作向量，即可向正在运行的进程分配的资源量
Finish[i]：一维数组，表示进程是否完成安全检测
safe[securityPid]：一维数组，用于记录当前进行安全检测的进程号
3、随机生成数据；
4、 编写程序并调试；
5、 多次测试程序，截屏输出实验结果；
6、根据实验结果与理论课讲述的原理进行实验分析。

源代码

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

int processnum;   //进程数
int resourcenum;  //资源数
int *available=NULL;	 //可用资源数
int *safe=NULL;	 //记录安全序列
int **Max=NULL;	 //最大资源需求数
int **allocation=NULL; //已分配资源数
int **need=NULL;	//还需要的资源数

void initData(){  //初始化数据
	int i,j,flag=1,flag1;
	srand((unsigned int)time(0));
	resourcenum=(rand()%4)+4;	//资源类数初始化为4-7个
	int resource[resourcenum];
	processnum=rand()%4+3;         //进程数初始化为3-6个
	while(flag==1){		
		for(i=0;i<resourcenum;i++){
			resource[i]=(rand()%6)+4;   //初始化每类资源的数目为4-9个
		}
		//动态分配内存
		allocation = (int**)malloc(sizeof(int*)*processnum);
		Max = (int**)malloc(sizeof(int*)*processnum); 
		need = (int**)malloc(sizeof(int*)*processnum);
		for(i=0;i<processnum;i++){
			allocation[i]=(int*)malloc(sizeof(int) * resourcenum);
			Max[i]=(int*)malloc(sizeof(int) * resourcenum);
			need[i]=(int*)malloc(sizeof(int) * resourcenum);
		}
		for(i=0;i<processnum;i++){
			for(j=0;j<resourcenum;j++){
				int temp=rand()%5;  //创建临时变量
				allocation[i][j]=temp;  //已分配的各类资源数，初始化为0-4个
				Max[i][j]=temp+rand()%3;  /*最大资源需求数，此处确保了最大资源需求数大于等于已分配的资源数*/
				need[i][j]=Max[i][j]-allocation[i][j];  //需求资源数
			}
		}
		available=(int*)malloc(sizeof(int)*resourcenum);
		for(i=0;i<resourcenum;i++){
			available[i]=resource[i];  
			for(j=0;j<processnum;j++){
				available[i]=available[i]-allocation[j][i];  //目前可用的资源数
			}
		}
		for(i=0;i<processnum;i++){ //保证可以让至少一个进程能得到全部资源到结束
			flag1 = 1;
			for(j=0;j<resourcenum;j++)
				if(available[j]<need[i][j]){ //可用资源数少于需求的资源数
					flag1 = 0;
					break;
				}
				if(flag1==1){  //该进程能安全运行
					flag=0;
					break;
				}
		}
	}
			
	printf("****************************************************************\n");
	printf("当前系统各类可用资源:");
	for (int i = 0; i < resourcenum; i++){
		printf("%d ",resource[i]);
	}
	printf("\n");
	printf("当前各进程对各种资源需求情况:\n");
	printf("PID\tMax\t\tAllocation\t\tNeed\n");  
	for (int i = 0; i < processnum; i++){  //输出各种资源和进程间的状况
		printf("P%d\t",i);
		for (int j = 0; j < resourcenum; j++){ //输出最大需求资源数
			printf("%d ",Max[i][j]);
		}
		printf("\t");
		for (int j = 0; j < resourcenum; j++){
			printf("%d ",allocation[i][j]);  //输出已分配资源数
		}
		printf("\t\t");
		for (int j = 0; j < resourcenum; j++){
			printf("%d ",need[i][j]);  //输出所需资源数
		}
	         printf("\n");
	}
	printf("剩余各类可用资源数为:");
	for(i=0;i<resourcenum;i++){  //输出剩余可用资源数
		printf("%d ",available[i]);
	}
	printf("\n");
							
}

int satisfy1(int n){ //可分配的资源是否能满足该进程的请求
	int flag = 1;
	for (int i = 0; i <resourcenum; i++)
		if (need[n][i] > available[i]){  //不安全
			flag = 0; 
			break;
		}
	return flag;
}

int satisfy2(int n, int work[]){ //可分配的资源是否能满足该进程的请求
	int i,flag = 1;
	for (i = 0; i < resourcenum; i++)
		if (need[n][i] > work[i]){  //不安全
			flag = 0; 
			break;
		}
	return flag;
}

int isSafe(int num){
	int i,j,flag;
	int securityPid=0;//记录当前可执行的进程号
	int work[resourcenum]; //工作向量
	int finish[processnum];  //标记是否完成
	safe=(int*)malloc(sizeof(int)*processnum);  //动态分配内存
	for(i=0;i<resourcenum;i++){  //预分配
		work[i]=available[i];
	}
	for(i=0;i<processnum;i++){
		finish[i]=0;  //初始化为未完成
	}
	finish[num]=1;
	for(i=0;i<resourcenum;i++){
		work[i]=work[i]+allocation[num][i];  //回收资源
	}
	while(1){
		flag=1;
		int tag=0;
		for(i=0;i<processnum;i++){
			if(finish[i]==0&&satisfy2(i,work)==1){  //该进程能安全运行
				for(j=0;j<resourcenum;j++){
					work[j]=work[j]+allocation[i][j];  //回收资源		 			
				}
				securityPid++;
				safe[i]=securityPid;   //记录进程号
				finish[i]=1;
				flag=0;
				break;
			}
		}
		if(flag==1) break;  //无满足条件的进程
	}
	flag=1;
	for(i=0;i<processnum;i++){
		if(finish[i]==0) flag=0;
	}
	return flag;
}
	
void banker(){ //银行家算法
	int num,i,j,request[resourcenum];//记录进程几
	while(1){  //选取进程进行试分配，不满足则推迟分配
		num=rand()%processnum;
		if(satisfy1(num)==1)
		break;
	}
	printf("\n假设将资源分配给P%d",num);
	for(j=0;j<resourcenum;j++){
		request[j]=need[num][j];  //请求资源数等于需要的资源数
		available[j]=available[j]-request[j];  //剩余可用资源数
		allocation[num][j]=allocation[num][j]+request[j];  //更新已分配的资源数
		need[num][j]=need[num][j]-request[j];  //更新所需资源数
	}
	printf("\n分配后各进程对资源需求情况为：\n");//
	printf("PID\tMax\t\tAllocation\t\tNeed\n");  
	for (int i = 0; i < processnum; i++){  //输出各种资源和进程间的状况
		printf("P%d\t",i);
		for (int j = 0; j < resourcenum; j++){ //输出最大需求资源数
			printf("%d ",Max[i][j]);
		}
		printf("\t");
		for (int j = 0; j < resourcenum; j++){
			printf("%d ",allocation[i][j]);  //输出已分配资源数
		}
		printf("\t\t");
		for (int j = 0; j < resourcenum; j++){
			printf("%d ",need[i][j]);  //输出所需资源数
		}
	         printf("\n");
	}///
	int flag=isSafe(num);
	if(flag==0){
		printf("\n分配资源后系统处于不安全状态，不分配资源！");
		for(i=0;i<resourcenum;i++){  //回收资源
			available[i]=available[i]+request[i];
			allocation[num][i]=allocation[num][i]-request[i];
			need[num][i]=need[num][i]+request[i];
		}
	}
	else{
		printf("\n分配资源后系统仍处于安全状态，可找到的安全序列为：");
		for(i=0;i<processnum;i++){
			for(j=0;j<processnum;j++){
				if(safe[j]==i){
					printf("->P%d",j);break;  //输出安全序列
				}
			}
		}
	}
	printf("\n");
}

void release() //进程完成，释放资源
{
	free(available);
	for (int i = 0; i < processnum; i++)
	{
		free(Max[i]);
		free(allocation[i]);
		free(need[i]);
	}
	free(Max);
	free(allocation);
	free(need);
	printf("\n程序运行完成，内存已释放！\n");
}			

int main(){
	initData();
	banker();
	release();
}

七、实验结果分析（截屏的实验结果，与实验结果对应的实验分析）
结果1：

结果2：

结果3：

结果4：

结果5：

结果6：

实验分析：
可以看到程序能实现系统安全性的判断，也能输出安全序列。除此之外，因为我使用的是for循环语句来对每个进程进行安全检测，再者就是使用随机生成数据会存在很多不确定性，所以可以看到基本上输出第一个进程后后面的进程号都是递增序列。当然也可以用选择随机算法来选择进程进行检测来消除这个规律，但是这样一来就会让代码的复杂性增加，所以我选择了最简单的循环算法，毕竟能输出安全序列就行了。程序可以自动检测数据是否符合规范，所以这个程序的健壮性还是较好的。但是在鲁棒性方面，由于实验要求要用随机生成数据，所以我的程序中使用了较多的全局变量，这些变量在程序开始运行之前的初始化阶段就诞生，到整个程序结束退出的时候才死亡，始终占用数据段上的空间，一定程度上造成了内存浪费，所以该程序的鲁棒性不佳。除此之外这些变量在任何地方都可以被更改，程序的安全性也就无法得到保证。

思考题：
1、如何设计程序的输入模块才能满足实验要求，请举例说明；
由于要求各种数据都要随机生成，所以不再需要手动进行输入。但是为了便于观察和满足特定的要求，要对数据进行一些限制。首先要将进程数和资源种类数确定下来，以便于后面数据的分配。进程数和资源种类数不宜太多，也不能过少。在程序中我设置的是进程数为3-6个，资源类数为4-7个。随后要将resource确定下来，即确定好初始的资源数。随后把Max，allocation，need数确定下来，在这里要注意Max即最大需求数要大于或等于allocation即已分配资源数，在程序中我的做法是让Max值等于allocation值加上一个随机数，need的值可以由Max-allocation求出。还要注意的是初始系统拥有的资源数不能比各进程已分配的各类资源数之和多。
2、银行家算法在实现过程中必须注意哪些资源分配细节才能避免死锁？
（1）初始化的系统拥有的资源数不能比已分配的资源数之和少。
（2）进程需要的资源数不能多于系统拥有的资源数。
（3）在进程请求资源分配时候要先判断是否有足够的资源进行分配，假如资源不足则不进行分配，即要在安全状态下才进行资源分配。

本文标签： 银行家算法