银行家.cpp

银行家算法代码

#include "stdio.h"//华南农业大学06级计机2班李沛平
#include "iostream"
#include "time.h"
using namespace std;
int flag=0;//所有进程是否完成的标志,flag=n表示所有进程已完成
int f[9];//某个进程是否完成的标志，f[0]==1代表进程0已经完成
void wait(int n){//等待时间消耗一秒  
	time_t start,end;   
    start=time(NULL);   
    while(1){   
      end=time(NULL);   
      if(end==start+n) break;
	}
}   
void print(int max[][9],int available[],int need[][9],int allocation[][9],int n){//打印函数，打印各个矩阵
	    int i,j;
		cout<<"max"<<endl;//打印max矩阵
		cout<<"    ";
		for(j=0;j<9;j++) cout<<"R"<<j<<"  ";
		cout<<endl;
		for(i=0;i<n;i++){
			if(f[i]==1) continue;
			cout<<"p"<<i<<"  ";
			for(j=0;j<9;j++){
				cout<<max[i][j]<<"   "; 
			}
			cout<<endl;
		}
		cout<<"allocation"<<endl;//打印allocation矩阵
		cout<<"    ";
		for(j=0;j<9;j++) cout<<"R"<<j<<"  ";
		cout<<endl;
		for(i=0;i<n;i++){
			if(f[i]==1) continue;
			cout<<"p"<<i<<"  ";
			for(j=0;j<9;j++){
				cout<<allocation[i][j]<<"   "; 
			}
			cout<<endl;
		}
		cout<<"need"<<endl;//打印need矩阵
		cout<<"    ";
		for(j=0;j<9;j++) cout<<"R"<<j<<"  ";
		cout<<endl;
		for(i=0;i<n;i++){
			if(f[i]==1) continue;
			cout<<"p"<<i<<"  ";
			for(j=0;j<9;j++){
				cout<<need[i][j]<<"   "; 
			}
			cout<<endl;
		}
		cout<<endl;
		cout<<"available"<<endl;//打印available矩阵
		cout<<"    ";
		for(j=0;j<9;j++) cout<<"R"<<j<<"  ";
		cout<<endl;
		cout<<"    ";
		for(j=0;j<9;j++) cout<<available[j]<<"   ";
		cout<<endl;
}
int safe(int max[][9],int available[],int need[][9],int allocation[][9],int n){//检测安全性算法
	int i,j;
	int work[9];
	int finish[9];
	int sequ[9];//记录安全序列
	int k=0;
	for(i=0;i<n;i++) finish[i]=0;//初始化
	for(j=0;j<9;j++) work[j]=available[j];//初始化
	for(i=0;i<n;){//查找i使其满足finish[i]==0&&need[i][j]<=work[j]
		if(finish[i]==0){
			for(j=0;j<9;j++){
				if(need[i][j]>work[j]) break;
			}
			if(j==9){//满足finish[i]==0&&need[i][j]<=work[j]则试着分配资源(是work不是available)
				for(j=0;j<9;j++) work[j]=work[j]+allocation[i][j];
				finish[i]=1;
                sequ[k++]=i;
				i=0;//重新搜索
			}
			else i++;//不满足finish[i]==0&&need[i][j]<=work[j],搜索其他
		}
		else i++;//finish[i]=1,不需处理
	}
	for(i=0;i<n;i++){//看是否全部finish[i]==1
		if(finish[i]==0) break;
	}
	if(i==n){//全部finish[i]==1
		cout<<"可以找到"<<"<";
		for(j=0;j<k;j++){
			if(f[j]==1) continue;
			cout<<sequ[j];
			if(j!=k-1) cout<<",";
			else cout<<">"<<"安全序列"<<"  ";
		}
		cout<<"系统安全"<<endl;
		return 1;
	}
	else{//不是全部finish[i]==1
		cout<<"系统不安全,请求不接受"<<endl;
		return 0;
	}
}
void alloc(int max[][9],int available[],int need[][9],int allocation[][9],int n){//资源请求算法
	int request[9][9];
	int i,j,k,l=0;
	while(1){//随机选出已存在的进程i,让它提出申请资源
		i=rand()%n;
		if(f[i]==0) break;
	}
	while(1){
		for(j=0;j<9;){
			k=rand()%10;//随机给K一个0~9的整数
		    if(k>=0&&k<=10&&k<=need[i][j]&&k<=available[j]){//控制K的范围
				request[i][j]=k;//填写request序列
			    j++;
				if(k==0) l++;//记录是否request序列全为0
			}
		}
		if(l!=9){//request序列不全为0,request序列有效,(request序列全为0是没意义的)
			l=0;
			break;
		}
	    l=0;
	}
	cout<<"进程"<<i<<"在申请资源.";
	wait(1);//等待1秒
	cout<<".";
	wait(1);//等待1秒
	cout<<".";
	cout<<endl;
	cout<<"request"<<endl;
	cout<<"    ";
	for(j=0;j<9;j++) cout<<"R"<<j<<"  ";
	cout<<endl;
	cout<<"    ";
	for(j=0;j<9;j++) cout<<request[i][j]<<"   ";//输出request
	cout<<endl;
	for(j=0;j<9;j++){//检查request[i]是否<=need[i]	
		if(request[i][j]>need[i][j]) break;
	}
	if(j==9){//request[i]<=need[i]
		for(j=0;j<9;j++){//检查request[i]是否<=available
			if(request[i][j]>available[j]) break;
		}
		if(j==9){//request[i]<=available
			for(j=0;j<9;j++){//正式分配资源
				available[j]=available[j]-request[i][j];
				allocation[i][j]=allocation[i][j]+request[i][j];
			    need[i][j]=need[i][j]-request[i][j];
			}
			if(safe(max,available,need,allocation,n)==1){//当前系统状态安全
				cout<<"p"<<i<<"在运行中.";
				wait(1);
				cout<<".";
				wait(1);
				cout<<".";
				wait(1);
				cout<<endl;
				for(j=0;j<9;j++){//检测进程i是否已完成
					if(need[i][j]!=0) break;
				}
				if(j==9){//进程i已完成
					for(j=0;j<9;j++){//回收所有资源
						available[j]=available[j]+max[i][j];
						max[i][j]=0;
						allocation[i][j]=0;
					}
					cout<<"进程"<<i<<"已经完成"<<endl;
					f[i]=1;//进程i已完成的标志
					flag++;
				}
			}
			else{//当前系统状态不安全
				for(j=0;j<9;j++){//刚分配的资源要收回来
					available[j]=available[j]+request[i][j];
				    allocation[i][j]=allocation[i][j]-request[i][j];
			        need[i][j]=need[i][j]+request[i][j];
				}
			}

		}
		else cout<<"该请求序列大于available"<<endl;
	}
	else cout<<"该请求序列大于Need"<<endl;
}
void main(){
	int max[9][9];
	int i,j,k,n=3;
	int available[9];
	int allocation[9][9];
	int need[9][9];
	for(i=0;i<0;i++) f[i]=0;//初始化,进程未完成
	for(i=0;i<9;){//随机分配available
		k=rand()%10;
		if(k>=5&&k<=10){//在5~10之间
			available[i]=k;
			i++;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<9;){
			allocation[i][j]=0;//初始化
			k=rand()%10;
			if(k>=0&&k<=available[j]){//随机分配max和need
				max[i][j]=k;
				need[i][j]=max[i][j];
				j++;
			}
		}
	}
    print(max,available,need,allocation,n);//打印各矩阵
	if(safe(max,available,need,allocation,n)){//系统安全
		wait(3);
        system("cls");
		while(1){
			i=rand()%10;
			if(i==1){// 1/10机会有新进程加入
				for(j=0;j<9;){//为新进程初始化
					allocation[n][j]=0;
					k=rand()%10;
					if(k>=0&&k<=available[j]){
						max[n][j]=k;
						need[n][j]=max[n][j];
				        j++;
					}
				}
				n++;
			}
			alloc(max,available,need,allocation,n);//分配资源
			print(max,available,need,allocation,n);
			if(flag==n){
				cout<<"所有进程已经完成"<<endl;
				getchar();
				break;
			}
			wait(2);
			system("cls");//清屏
		}
	}
}