/* 死锁避免——银行家算法的模拟实现
本题目的简化假设是：
1、程序运行开始时，资源全部可用。
资源种类约10种（现设为4种)，每种资源数目为1~5 。
2、可以不断手工输入新的 "进程资源需求向量"，并填写到最大需求矩阵
3、在各进程的最大需求数量范围内（需作是否超出范围的检验）为各进程手工输入资源请求。经银行家算法后输出系统是否安全的信息,并输出一安全序列。当一个进程的资源请求全部发完后, 认为它结束。同时回收系统资源.
*/
#include "iostream.h"
#define P 5 //系统允许最多进程数
#define N 4 //系统资源种类数
#define FALSE 0
#define TRUE 1
int M=5; //系统初始状态的进程数
int AVAILABLE[N]={1,5,2,0}; //系统可用资源数
int MAX[P][N]={{7,5,3,2},{2,3,4,3},{4,3,3,2},{5,2,3,4},{3,5,3,2}};
//M个进程对 N类 资源最大资源需求量 （即最大需求矩阵）
int ALLOCATION[P][N]={{0},{0},{0},{0}};
//M个进程已经得到N类资源的资源量 初始化为0
int NEED[P][N]={{0,0,0,2},{0,7,5,0},{1,0,0,2},{0,0,2,0},{1,6,4,2}};
//M个进程还需要N类资源的资源量
int Request[N]={0,0,0,0}; //申请资源向量
void showdata( )
{ int i,j,t;
cout<<" 系统可用的资源数: "<<endl<<endl;
cout<<" ";
for (i=0;i<M;i++)
{ for (j=0;j<N;j++)
if (NEED[i][j]!=0)
break;
if(j==N)
for(t=0;t<N;t++)
AVAILABLE[t]= AVAILABLE[t]+MAX[i][t];
} //若有进程得到所需的全部资源，则认为它结束，并回收资源
for (j=0;j<N;j++)
cout<<" 资源"<<j<<":"<<AVAILABLE[j];
cout<<" "<<endl<<endl;
cout<<" 各进程资源最大需求量:"<<endl<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<":";
for (j=0;j<N;j++)
{ if (NEED[i][j]!=0)
break;
}
if (j==N ) cout<<"该进程已结束" ;
else for (j=0;j<N;j++)
cout<<" 资源"<<j<<":"<<MAX[i][j];
cout<<endl;
}
cout<<endl;
cout<<" 各进程尚需要的资源量:"<<endl<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<":";
for (j=0;j<N;j++)
{ if(NEED[i][j]!=0)
break;
}
if(j==N ) cout<<"该进程已结束" ;
else for (j=0;j<N;j++)
cout<<" 资源"<<j<<":"<<NEED[i][j];
cout<<endl;
}
cout<<endl;
cout<<" 各进程已得到的资源量: "<<endl<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<":";
for (j=0;j<N;j++)
{ if (NEED[i][j]!=0)
break;
}
if(j==N ) cout<<"该进程已结束" ;
else for (j=0;j<N;j++)
cout<<" 资源"<<j<<":"<<ALLOCATION[i][j];
cout<<endl;
}
cout<<endl;
}
void changdata(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];
}
}
void comebackdata(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j];
}
}
int check(int s) /*安全性算法（子算法）*/
{
int WORK,FINISH[P],temp[P];
int i,j,k=0;
for(i=0;i<M;i++)
FINISH[i]=FALSE;
for(j=0;j<N;j++)
{
WORK=AVAILABLE[j];
i=s;
while(i<M)
{
if (FINISH[i]==FALSE&&NEED[i][j]<=WORK)
{ WORK=WORK+ALLOCATION[i][j];
FINISH[i]=TRUE;
temp[k]=i;
k++;
i=0;
}
else i++;
}
for(i=0;i<M;i++)
if(FINISH[i]==FALSE)
{
cout<<endl;
cout<<" 系统不安全!!!本次资源申请不成功!!!"<<endl<<endl;
return 1;
}
}
cout<<endl;
cout<<" 经安全性检查，系统安全，本次分配成功。"<<endl<<endl;
cout<<" 本次安全序列：";
for(i=0;i<M;i++)
cout<<"进程"<<temp[i]<<"->";
cout<<endl<<endl;
return 0;
}
void main()
{
int i,j,a;
char flag='Y';
char hold='y';
while (hold=='y'||hold=='Y')
{ cout<<"功能选择："<<endl;
cout<<" 1. 输入新的进程资源需求向量"<<endl;
cout<<" 2. 为某进程申请资源,并检测是否是安全状态"<<endl;
cout<<" 3. 查看系统资源及各进程情况"<<endl;
cout<<" 4. 退出银行家算法的模拟实验"<<endl;
cout<<" 请选择: 【 】\b\b";
cin>>a;
switch (a)
{ case 1 : cout<<"进程"<<M<<"各类资源最大需求量 "<<endl;
for (j=0;j<N;j++)
{ cout<<" 资源"<<j<<": ";
cin>>MAX[M][j];
NEED[M][j]=MAX[M][j];
if(MAX[M][j]>AVAILABLE[j])
{
cout<<" 进程"<<M<<"资源最大需求量大于"<<j<<"类资源的资源量!";
cout<<endl<<" 申请不合理，出错!请重新选择!"<<endl<<endl;
flag='N';
M--;
break;
}
}/*end for*/
M++;
break;
case 2: i=-1;
while(i<0||i>=M)
{
cout<<" 请输入需申请资源的进程（从0到"<<M-1<<"，否则重输入!）:";
cin>>i;
if(i<0||i>=M) cout<<" 输入的进程号不存在，重新输入!"<<endl;
}
cout<<" 请输入进程"<<i<<"申请的资源数"<<endl;
for (j=0;j<N;j++)
{ cout<<" 资源"<<j<<": ";
cin>>Request[j];
if(Request[j]>NEED[i][j])
{
cout<<" 进程"<<i<<"申请的资源数大于进程"<<i<<"还需要"<<j<<"类资源的资源量!";
cout<<endl<<" 申请不合理，出错!请重新选择!"<<endl<<endl;
flag='N';
break;
}
else
{ if(Request[j]>AVAILABLE[j])
{
cout<<" 进程"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!";
cout<<" 申请不合理，出错!请重新选择!"<<endl<<endl;
flag='N';
break;
}
}
} /*end for*/
if(flag=='Y'||flag=='y')
{
changdata(i);
if(check(i))
{
comebackdata(i);
showdata( );
}
else
showdata( );
}
break;
case 3 : showdata(); break;
case 4 : hold='n'; break;
default :cout <<" 输入错误，请重新输入!!!"<<endl;
} //end case
}
}
