bankeragorithm.cpp

银行家算法。多个进程动态地共享系统的资源可能会产生死锁现象。死锁的产生

//=============================================================================
#include<iostream>
#include<fstream>
using namespace std;
//=============================================================================
bool isError;//系统内部资源分配错误检查量
//==============================================================================
//初始化各资源矩阵和进程需求矩阵
void initialSource(int Av[3],int(*M)[3],int(*Al)[3],int(*N)[3]);
//输出资源分配表
void displaySourceTable(int Av[3],int(*M)[3],int(*Al)[3],int(*N)[3]);
//为进程i的请求分配资源
void preAssignSource(int i,int R[3],int(*N)[3],int Av[3],int(*Al)[3]);
//撤销预分配
void unDoAssignSource(int i,int R[3],int(*N)[3],int Av[3],int(*Al)[3]);
//安全性检查
bool safetyCheck(bool F[5],int W[3],int Av[3],int (*N)[3],int (*Al)[3]);
//显示安全序列
void displaySafetyOrder(int orderOfF[5],int Av[3],int (*Al)[3],int (*N)[3]);
//显示某次分配后的资源情况
void displaySourceAfterAssign(int Av[3],int (*N)[3],int (*Al)[3]);
//==============================================================================
void main()
{

	int *Available=new int[3];//可利用资源向量
    int (*Max)[3]=new int[5][3];//最大需求矩阵
	int (*Allocation)[3]=new int[5][3];//分配矩阵
	int (*Need)[3]=new int [5][3];//需求矩阵
	int processNum;//进程号
	int *Request =new int[3];//进程资源需求向量
	bool *Finish =new bool[5];
	int *Work=new int [3];
	int i;
 
	//开始界面显示
	cout<<"系统所有资源分为A、B、C，数量分别为10,5,7\n";
	cout<<"系统有0,1、2、3、4五个进程"<<endl;
	initialSource(Available,Max,Allocation,Need);
Begin: 
	cout<<"当前系统资源分配情况:"<<endl;
    displaySourceTable(Available,Max,Allocation,Need);
    
	//申请进程及资源数据输入
Begin2:
	cout<<"请给出要申请资源的进程号和3类资源的数量，\n";
	cout<<"请输入进程号:";
	for(cin>>processNum;processNum>4||processNum<0;)
	{
		cout<<"进程号错误，请重新输入:";
		cin>>processNum;
	}
	cout<<"请输入需要申请的3个资源数量:";
    for(i=0;i<3;++i)
		cin>>Request[i];
    
	isError=0;
	//拟分配
    preAssignSource(processNum,Request,Need,Available,Allocation);
    if(isError)
	{
		goto Begin;
	}
	//安全性检查
	else
	{
		//如果安全
		if(safetyCheck(Finish,Work,Available,Need,Allocation))
		{
			displaySourceAfterAssign(Available,Need,Allocation);
			goto Begin2;
		}
		//如果不安全
		else
		{
			cout<<"非常抱歉,系统无法为您分配,根据银行家算法\n";
			cout<<"此次分配不安全，等待其它进程释放资源再请求\n\n";
			unDoAssignSource(processNum,Request,Need,Available,Allocation);
			goto Begin2;
		}
	}

}
//==============================================================================
void initialSource(int Av[3],int(*M)[3],int(*Al)[3],int(*N)[3])
{
	 ifstream in("Source.txt");
	 int i,j;
	 //输入最大需求矩阵
     for(i=0;i<5;++i)
		 for(j=0;j<3;++j)
		 {
			 in>>M[i][j];
		 }
	//输入分配矩阵
	for(i=0;i<5;++i)
		 for(j=0;j<3;++j)
		 {
			 in>>Al[i][j];
		 }
    //输入需求矩阵
	for(i=0;i<5;++i)
		 for(j=0;j<3;++j)
		 {
			N[i][j]=M[i][j]-Al[i][j];
		 }
	//输入可利用资源向量
    Av[0]=3;
	Av[1]=3;
	Av[2]=2;
}
//=================================================================================
void displaySourceTable(int Av[3],int(*M)[3],int(*Al)[3],int(*N)[3])
{
	cout<<"**********************资源分配表*****************************\n";
	cout<<"资源分配情况"<<"   Max   "<<"   Allocation   "<<"   Need   "<<"   Available   "<<endl;
	cout<<"    进程    "<<" A  B  C "<<"     A  B  C    "<<"  A  B  C "<<"    A  B  C    "<<endl;
	int i,j;
	for(i=0;i<5;++i)
	{
		cout<<"     P"<<i<<"     ";
		//输出最大需求矩阵第i行
		for(j=0;j<3;++j)
		{
       		cout<<" "<<M[i][j]<<" ";
		}
		//输出分配矩阵第i行
		cout<<"    ";
		for(j=0;j<3;++j)
		{
            cout<<" "<<Al[i][j]<<" ";
		}
		cout<<"    ";
		//输出需求矩阵第i行
		for(j=0;j<3;++j)
		{
          cout<<" "<<N[i][j]<<" ";
		}
		//输出可利用资源向量
		if(i==0)
		{
		  cout<<"   ";
		  for(j=0;j<3;++j)
		  {
			 cout<<" "<<Av[j]<<" ";
		  }
		  cout<<"   ";
		}
        cout<<endl;
	}
	cout<<"*************************************************************\n";
	
}
//=============================================================================
void preAssignSource(int i,int R[3],int(*N)[3],int Av[3],int(*Al)[3])
{
	int j;
    for(j=0;j<3;++j)
	{
		if(R[j]>N[i][j])
		{
			cout<<"请求的资源大于最大需求资源，出现错误,请重新分配\n\n";
			isError=1;
			goto end;
		}
	}
    for(j=0;j<3;++j)
	{
		if(R[j]>Av[j])
		{
			cout<<"请求的资源大于可利用资源资源，分配失败,请重新分配\n\n";
			isError=1;
			goto end;
		}
	}
	for(j=0;j<3;++j)
	{
		Av[j]=Av[j]-R[j];
		Al[i][j]=Al[i][j]+R[j];
		N[i][j]=N[i][j]-R[j];
	}
end: ;
} 
//===============================================================================
bool safetyCheck(bool F[5],int W[3],int Av[3],int (*N)[3],int (*Al)[3])
{
	int *orderOfF=new int[5];
	int orderTemp=0;
	bool temp=0;
	int proDoneNum=0;
	int i,j;
	for(j=0;j<5;++j)
		F[j]=0;
	for(j=0;j<3;j++)
		W[j]=Av[j];
    for(j=0;j<5;++j)
		orderOfF[j]=-1;
	//安全性检查算法过程
	for(;orderTemp<5&&proDoneNum<6;)
	{      
		for(i=0;i<5;++i)
		{
			if(F[i]==0)
			{
				for(j=0;j<3;++j)
				{
					if(N[i][j]>W[j])
					{
						temp=1;
					    break;
					}
				}
				
				if(temp==1)
				{
					proDoneNum++;
					temp=0;
				}
				else
				{
					for(j=0;j<3;++j)
					  W[j]=W[j]+Al[i][j];
					F[i]=1;
					orderOfF[orderTemp++]=i;
					proDoneNum=0;
				}
			}
		}
	}
	//输出安全序列
	displaySafetyOrder(orderOfF,Av,Al,N);
	//结果检查
	for(i=0;i<5;++i)
		if(F[i]==0)
			return 0;  
	  return 1;
}
//===========================================================================
void displaySafetyOrder(int orderOfF[5],int Av[3],int (*Al)[3],int (*N)[3])
{

	int i,j;
	int *work=new int[3];
	for(j=0;j<3;j++)
		work[j]=Av[j];
    cout<<"****************本次分配过程的安全序列表********************\n";
	cout<<"资源情况"<<" Work  "<<" Need  "<<" Allocation "<<" Work+Allocation "<<" Finish "<<endl;
    cout<<"  进程  "<<" A B C "<<" A B C "<<"    A B C   "<<"     A  B  C     "<<endl; 
	for(i=0;i<5&&orderOfF[i]!=-1;++i)
	{
		cout<<"   P"<<orderOfF[i]<<"   ";
		//输出work
		for(j=0;j<3;++j)
          cout<<' '<<work[j];
		  cout<<' ';
		//输出need;
		for(j=0;j<3;++j)
          cout<<' '<<N[orderOfF[i]][j];
		  cout<<' ';
        //输出Allocation
		cout<<"   ";
		for(j=0;j<3;j++)
			cout<<' '<<Al[orderOfF[i]][j];
		cout<<"   ";
	    //输出Work+Allocation
		for(j=0;j<3;++j)
			work[j]=work[j]+Al[orderOfF[i]][j];
		cout<<"    ";
        for(j=0;j<3;++j)
          cout<<' '<<work[j]<<' ';
		cout<<"    ";
		//输出Finish
		    cout<<"  true"<<endl;
	}
	cout<<"************************************************************\n";
	
}
//=======================================================================================
void displaySourceAfterAssign(int Av[3],int (*N)[3],int (*Al)[3])
{
    cout<<"********************本次分配后资源情况***************************\n";
	cout<<"资源分配情况"<<"   Allocation   "<<"   Need   "<<"   Available   "<<endl;
	cout<<"    进程    "<<"     A  B  C    "<<"  A  B  C "<<"    A  B  C    "<<endl;
	int i,j;
	for(i=0;i<5;++i)
	{
		cout<<"     P"<<i<<"     ";
		//输出分配矩阵第i行
		cout<<"    ";
		for(j=0;j<3;++j)
		{
            cout<<" "<<Al[i][j]<<" ";
		}
		cout<<"   ";
		//输出需求矩阵第i行
		cout<<' ';
		for(j=0;j<3;++j)
		{
          cout<<' '<<N[i][j]<<' ';
		}
		//输出可利用资源向量
		if(i==0)
		{
		  cout<<"   ";
		  for(j=0;j<3;++j)
		  {
			 cout<<" "<<Av[j]<<" ";
		  }
		  cout<<"   ";
		}
        cout<<endl;
	}
	cout<<"*****************************************************************\n";
}
//========================================================================================
void unDoAssignSource(int i,int R[3],int(*N)[3],int Av[3],int(*Al)[3])
{
	for(int j=0;j<3;++j)
	{
		Av[j]=Av[j]+R[j];
		Al[i][j]=Al[i][j]-R[j];
		N[i][j]=N[i][j]+R[j];
	}
}