操作系统 实验二 死锁的避免-银行家算法

//************************************************************************//
//*                  实验二 死锁的避免――银行家算法                      	 *//
//*																  	     *//
//*本程序需要预先设置三个文件：Available_list.txt，Max_list.txt，Allocation_list.txt *//
//*  各文件格式如下：      					    					     *//
//*  Available_list.txt		 											 *//
//*  3        //表示共有3类资源					   					     *//
//*  10 5 7   //表示各类资源的初始可用个数，即Available[0]=10, Available[1]=5        *//
//*																	     *//
//*																         *//
//*  Max_list.txt		  												 *//
//*  5        //表示共有5个进程		 								     *//
//*  7 5 3   //表示各个进程需要各类资源的最大数目，即Max[0][0]=7, Max[0][1]=5	*//
//*  3 2 2																  	*//
//*  9 0 2																  	*//
//*  2 2 2																  	*//
//*  4 3 3																  	*//
//*	  																	  	*//
//*	  																	  	*//
//*  Allocation_list.txt													*//
//*  0 1 0 //表示各个进程已分配各类资源的数目                               	*//
//*  2 0 0																  	*//
//*  3 0 2																  	*//
//*  2 1 1																  	*//
//*  0 0 2																  	*//
//*  																	  	*//
//*	  																      	*//
//***************************************************************************//

#include <iostream>
#include <stdio.h>
#include <windows.h>

#define MAX_PROCESS 32              	//最大进程数
#define MAX_RESOURCE 64             	//最大资源类别

int PROCESS_NUM;              							//实际总进程数
int RESOURCE_NUM;              							//实际资源类别数
int Available[MAX_RESOURCE];                 			//可利用资源向量
int Max[MAX_PROCESS][MAX_RESOURCE];          			//最大需求矩阵
int Allocation[MAX_PROCESS][MAX_RESOURCE];   			//分配矩阵
int Need[MAX_PROCESS][MAX_RESOURCE];         			//需求矩阵

int Request_PROCESS;                       				//发出请求的进程
int Request_RESOURCE_NEMBER[MAX_RESOURCE];     			//请求资源数

void Read_Available_list();      						//读入可用资源Available
void Read_Max_list();           						//读入最大需求矩阵Max
void Read_Allocation_list();    						//读入已分配矩阵Allocation
void PrintInfo();               						//打印各数据结构信息
void Read_Request();									//输入请求向量
void Allocate_Source();         						//开始正式分配资源（修改Allocation_list.txt）
void Recover_TryAllocate();     						//恢复试分配前状态
int Test_Safty();               						//安全性检测
void RunBanker();               						//执行银行家算法

using namespace std; 

//读入可用资源Available
void Read_Available_list()      
{
	FILE *fp;
	if((fp=fopen("Available_list.txt","r"))==NULL)			//检查文件是否存在
	{ 
		cout<<"错误,文件打不开,请检查文件名"<<endl; 
		exit(0);
	}
	fscanf(fp,"%d",&RESOURCE_NUM);							//读入可分配的资源类别的数目
	int i=0;
	while(!feof(fp))										//读入各个可分配资源的数目
	{
		fscanf(fp,"%d",&Available[i]);
		i++;
	}	
	fclose(fp);												//关闭文件
}

//读入最大需求矩阵Max
void Read_Max_list()      
{
	FILE *fp;
	if((fp=fopen("Max_list.txt","r"))==NULL)			//检查文件是否存在
	{ 
		cout<<"错误,文件打不开,请检查文件名"<<endl; 
		exit(0);
	}
	fscanf(fp,"%d",&PROCESS_NUM);						//读入总进程数
	for(int i=0;i<PROCESS_NUM;i++)						//读入每个进程
		for(int j=0;j<RESOURCE_NUM;j++)					//读入每个进程总的所需的各个资源的数目
			fscanf(fp,"%d",&Max[i][j]);
	fclose(fp);											//关闭文件
}

//读入已分配矩阵Allocation
void Read_Allocation_list()      
{
	FILE *fp;
	if((fp=fopen("Allocation_list.txt","r"))==NULL)		//检查文件是否存在
	{ 
		cout<<"错误,文件打不开,请检查文件名"<<endl; 
		exit(0);
	}
	for(int i=0;i<PROCESS_NUM;i++)						//读入每个进程
		for(int j=0;j<RESOURCE_NUM;j++)
			fscanf(fp,"%d",&Allocation[i][j]);			//读入每个进程已经分配的资源数
	fclose(fp);
}

//设置需求矩阵Need
void Set_Need_Available()					
{                 
	for(int i=0;i<PROCESS_NUM;i++)						//每个进程
		for(int j=0;j<RESOURCE_NUM;j++)
		{
			Need[i][j]=Max[i][j]-Allocation[i][j];				//计算每个进程完成还需要的资源数
			Available[j]=Available[j]-Allocation[i][j];		//计算可利用资源与完成该进程还需要的资源数，用于判断能否安全分配
		}
}

//打印各数据结构信息
void PrintInfo()
{
	cout<<"进程个数： "<<PROCESS_NUM<<"\t"<<"资源个数： "<<RESOURCE_NUM<<endl;	//打印进程个数和资源类别数
	cout<<"可用资源向量Available："<<endl;
	int i,j;
	for(i=0;i<RESOURCE_NUM;i++)						//打印剩余可用资源
		cout<<Available[i]<<"\t";
	cout<<endl;
	cout<<"最大需求矩阵Max："<<endl;
	for(i=0;i<PROCESS_NUM;i++)						//打印各个进程所需的最大资源数
	{
		for(j=0;j<RESOURCE_NUM;j++)
			cout<<Max[i][j]<<"\t";
		cout<<endl;
	}
	cout<<"已分配矩阵Allocation："<<endl;
	for(i=0;i<PROCESS_NUM;i++)						//打印每个进程已经分配的资源数
	{
		for(j=0;j<RESOURCE_NUM;j++)
			cout<<Allocation[i][j]<<"\t";
		cout<<endl;
	}
	cout<<"需求矩阵Need："<<endl;
	for(i=0;i<PROCESS_NUM;i++)						//打印每个进程完成还需要的资源数
	{
		for(j=0;j<RESOURCE_NUM;j++)
			cout<<Need[i][j]<<"\t";
		cout<<endl;
	}
}

//输入请求向量
void Read_Request()			 
{                          
	cout<<"输入发起请求的进程（0－"<<PROCESS_NUM-1<<")：";
	cin>>Request_PROCESS;							//输入发起资源请求的进程号

	cout<<"输入请求资源的数目：按照这样的格式输入 x x x：";
	for(int i=0; i<RESOURCE_NUM; i++)				//输入该进程请求的各个资源的数目
		cin>>Request_RESOURCE_NEMBER[i];
}

//开始正式分配资源（修改Allocation_list.txt）
void Allocate_Source()
{                       
	cout<<'\n'<<"开始给第"<<Request_PROCESS<<"个进程分配资源..."<<endl;
	FILE *fp;
	if((fp=fopen("Allocation_list.txt","w"))==NULL)			//检查文件是否存在
	{ 
		cout<<"错误,文件打不开,请检查文件名"<<endl; 
		exit(0);
	}
	for(int i=0;i<PROCESS_NUM;i++)
	{
		for(int j=0;j<RESOURCE_NUM;j++)						//修改
			fprintf(fp,"%d  ",Allocation[i][j]);
		fprintf(fp,"\n");
	}
	cout<<"分配完成，已更新Allocation_list.txt"<<endl;
	fclose(fp);
}

//恢复试分配前状态
void Recover_TryAllocate()
{
	for(int i=0;i<RESOURCE_NUM;i++)				//不安全，将该进程的资源从预分配（试分配）状态退回未分配（分配前）状态
	{
		Available[i]=Available[i]+Request_RESOURCE_NEMBER[i];				//可分配资源增加（资源退回）
		Allocation[Request_PROCESS][i]=Allocation[Request_PROCESS][i]-Request_RESOURCE_NEMBER[i];	//该进程所请求的对应的资源类别的数目置为预分配前的状态
	   	Need[Request_PROCESS][i]=Need[Request_PROCESS][i]+Request_RESOURCE_NEMBER[i];		//该进程完成所需的资源数置为预分配前的状态
	}
}

//安全性检测
//返回值：0：未通过安全性测试； 1：通过安全性测试
int Test_Safty()
{                        
	//请完成安全性检测算法的编程
	int i,j;
	int Work[MAX_RESOURCE];	//定义工作向量
	for(i=0;i<RESOURCE_NUM;i++){
		Work[i]=Available[i];
	}
	bool Finish[MAX_PROCESS];	// 定义布尔向量
	for(i=0;i<PROCESS_NUM;i++){
		Finish[i]=false;
	} 
	int safe[MAX_RESOURCE];	// 用于保存安全序列
	bool found=false;	//判断在一轮查找中是否找到符合条件的进程 
	int FinishCount=0;		//找到满足条件的进程	i 的数目 
	while(FinishCount<5){
		for(i=0;i<PROCESS_NUM;i++){
			if(Finish[i]==true){ //	检查是否满足条件		Finish[i]==false 
				continue;
			} 
			bool HasResource=true;
			for(j=0;j<RESOURCE_NUM;j++){	// 检查是否满足条件	Need[i]<=Work 
				if(Need[i][j]>Work[j]){
					HasResource=false;
				} 
				if(HasResource){
					for(j=0;j<RESOURCE_NUM;j++){
						Work[j]=Work[j]+Allocation[i][j];
					} 
					Finish[i]=true;
					safe[FinishCount]=i;
					FinishCount++; 
					found=true;
				}
			} 
		}
		if(found){
			found=false;
		}
		else{
			break;
		} 	
	}
	for(i=0;i<PROCESS_NUM;i++){	// 判断是否所有进程满足	Finish[i]==true
		if(Finish[i]==true){
			continue;
		} 
		else{
			cout<<" 未通过安全性测试，不分配	"<<endl;
			return 0;
		}
	}
	cout<<'\n'<<" 找到一个安全序列	:";
	for(i=0;i<PROCESS_NUM;i++){		//打印安全序列
		cout<<"P"<<safe[i]; 
		if(i!=PROCESS_NUM-1){
			cout<<"--->";
		} 	
	}
	cout<<'\n'<<" 已通过安全性测试	!"<<endl;
	return 1;
}


void RunBanker(){              //执行银行家算法
	cout<<endl;
	cout<<"开始执行银行家算法..."<<endl;


	for(int i=0;i<RESOURCE_NUM;i++)  //检查是否满足条件Request<=Need
		if(Request_RESOURCE_NEMBER[i]>Need[Request_PROCESS][i])
		{
			cout<<"\n第"<<Request_PROCESS<<"个进程请求资源不成功"<<endl;
			cout<<"原因：超出该进程尚需的资源的最大数量!"<<endl;
			return;
		}
	for(int i=0;i<RESOURCE_NUM;i++)   //检查是否满足条件Request<=Available
		if(Request_RESOURCE_NEMBER[i]>Available[i])
		{
			cout<<"\n第"<<Request_PROCESS<<"个进程请求资源不成功"<<endl;
			cout<<"原因：系统中无足够的资源!"<<endl;
			return;
		}
		else{
			//试分配，更新各相关数据结构
			Available[i]=Available[i]-Request_RESOURCE_NEMBER[i];
		    Allocation[Request_PROCESS][i]=Allocation[Request_PROCESS][i]+Request_RESOURCE_NEMBER[i];
	   	    Need[Request_PROCESS][i]=Need[Request_PROCESS][i]-Request_RESOURCE_NEMBER[i];
		}
	cout<<endl<<"试分配完成..."<<endl;

	if(Test_Safty())    //使用安全性算法检查，若满足，则正式分配
		Allocate_Source();
	else                //否则恢复试分配前状态
		Recover_TryAllocate();
}


 
int main()
{
	char c;
	Read_Available_list();
	Read_Max_list();
	Read_Allocation_list();
	Set_Need_Available();
	PrintInfo();
	while(1)
	{
		Read_Request();
		RunBanker();
		cout<<"\n\n需要继续吗？（y-继续；n-终止）";
		cin>>c;
		if(c=='n')
			break;
		cout<<endl<<endl;
		PrintInfo();
	}
	return 0;
}