main.cpp

完成操作系统课程中的经典防止死锁的有效算法--银行家算法

#include <stdio.h>
#include <stdlib.h>
#define m 3
#define n 5
int MaxAvialable[m]={10,5,7};
int Available[m];
int MAX[n][m]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
int Allocation[n][m]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
int Need[n][m];
struct Request{
	int p;
	int k[m];
};
char SecurityCheck();
void Banker(Request r);
char SecurityCheck(){
	char finish[n]={0};
	int i_out=0,i=0,j=0,j_in=0,work[m]={0};

	for( ; j<m ; j++)
		work[j]=Available[j];

	for( ; i_out<n ; i_out++){
	for(i=0 ; i<n ; i++){
		if(!finish[i]){
			for(j=0 ; j<m ; j++)
				if(Need[i][j]>work[j])
					break;
			if(j == m){
				for(j_in=0 ; j_in<m ; j_in++){
					work[j_in]+=Allocation[i][j_in];
					finish[i]=1;
					////////////////////
					printf("Process%d is running ...Using resource%d\n",i,j_in);
				}
			}
		}
	}
	}
	for(i=0 ; i<n ; i++)
		if(!finish[i])
			break;
	if(i == n)
		return 1;
	else{
		puts("Deadlock\n");
		return 0;
	}
}
void Banker(Request r){
	int i=0,j=0;
	for(;i<n;i++)
		for(j=0;j<m;j++)
			Need[i][j]=MAX[i][j] - Allocation[i][j];

	for(j=0 ; j<m ; j++)
		Available[j] = MaxAvialable[j];

	for(i=0 ; i<n ; i++)
		for(j=0 ; j<m ; j++)
			Available[j]-=Allocation[i][j];

	for(j=0 ; j<m ; j++){
		if(r.k[j] > Need[r.p][j])
			break;
	}

	if(j<m){
		puts("The process needs the resource is over the MAX resource...\n");
		exit(1);
	}
	else{
		for(j=0 ; j<m ; j++)
			if(r.k[j] > Available[r.p])
				break;
		if(j<m)
			printf("The resource is not enough...Process%d wait...",r.p);
		else{
			for(j=0 ; j<m ; j++){
				Available[j]-=r.k[j];
				Allocation[r.p][j]+=r.k[j];
				Need[r.p][j]-=r.k[j];
			}
		}
		//安全性检查
		if(SecurityCheck())
			puts("Safe...\n");
		else{
			for(j=0 ; j<m ; j++){
				Available[j]+=r.k[i];
				Allocation[r.p][j]-=r.k[j];
 				Need[r.p][j]+=r.k[j];
			}
		}
	}
}
int main()
{
	int i = 0 , TempVar = 0;
	Request r;
	puts("Please enter the request process: ");
	scanf("%d",&TempVar);
	printf("\n");
	r.p = TempVar;
	puts("Please enter the process's request resource");
	for(;i<m;i++){
		scanf("%d",&TempVar);
		r.k[i]=TempVar;
	}
	Banker(r);
	return 0;
}