banker.cpp

改进的安全性算法！ 有效实现资源回收！ 5个进程

#include "iostream.h"
#include "stdlib.h"
#define FALSE 0
#define TRUE 1
#define M 5     //总进程数
#define N 3     //总资源数

//M个进程对N类资源最大资源需求量
int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
//系统可用资源数
int AVAILABLE[M]={3,3,2};
//M个进程已经得到N类资源的资源量
int ALLOCATION[M][N]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
//M个进程还需要N类资源的资源量
int NEED[M][N];
//单个进程请求资源量
int Request[N];
//安全性工作向量
int WORK[M][N];
//判定安全向量
int FINISH[M];
//暂存WORK向量的中间向量
int WA[M][N];
//进程序列向量
int temp[M];
//ALLOCATION备份
int temp2[M][N]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
//MAX备份
int temp3[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};

void main()
{
	int sel;
	void clear();
    void initdata();
	int menu();
	void sys();
	void request();
    void recly();
    initdata();
	clear();
	while(1)
	{
	  sel=menu();
      switch(sel)
	  {
         case 1:sys();clear();break;
         case 2:request();clear();break;
         case 3:return;
	  }
	}
}

void clear()  //清屏
{
	char a;
	cout<<endl;
	cout<<"Press any key to continue!!!";
	cin>>a;
	system("cls");
};

int menu()   //菜单
{
	int i;
	cout<<"1、judge the system security"<<endl;
    cout<<"2、judge the request security"<<endl;
    cout<<"3、quit"<<endl;
	cout<<"Select(1-3):";
	cin>>i;
	while(i<1||i>3)
	{
		cout<<"Input error!"<<endl;
		cin>>i;
	}
	return(i);
};

void initdata()//初始化
{
	int i=0,j=0,k=0;
	cout<<"Input the type of resource and number of customer:"<<endl;
    cout<<N<<" "<<M<<endl;
    cout<<"Input the amount of resource (maximum , allocated) of each customer:"<<endl;
    for(;k<M;k++)
	{
       cout<<"p"<<k<<" ";
       for(j=0;j<N-1;j++)
	      cout<<MAX[i][j]<<",";
	   cout<<MAX[i][j]<<"  ";
	   for(j=0;j<N-1;j++)
		  cout<<ALLOCATION[i][j]<<",";
	   cout<<ALLOCATION[i][j]<<endl;
	   for(j=0;j<N;j++)
	      NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];  //求得需求向量
       i++;
	}
	cout<<"Input the amount of resource (available):"<<endl;
	for(j=0;j<N-1;j++)
	{
		cout<<AVAILABLE[j]<<",";
		Request[j]=0;
	}
	cout<<AVAILABLE[j];
	Request[j]=0;
};

void sys()  //判定系统安全
{
	int sec;
	int chkerr(int);
	void showdata1(int);
	void recly();
	void rstore();
	recly();
	rstore();
	sec=chkerr(0);
	showdata1(sec);
};

void request()  //判定单个进程请求安全
{
int i=0,j=0,sec,k;
char flag='Y';
void showdata2(int,int);
void changdata(int);
void rstordata(int);
void recly();
void rstore();
int chkerr(int);

  i=-1;
  while(i<0||i>=M)  //输入请求向量
  {
    cout<<" Please input the customer's name and request:"<<endl;
    cout<<"p";
	cin>>i;
    if(i<0||i>=M) cout<<"the customer's name is not exist! Please input again!"<<endl;
	k=i;
  }
  for(j=0;j<N;j++)
  {
    cout<<"R"<<j<<":";
    cin>>Request[j];
    if(Request[j]>NEED[i][j])  //请求大于需求，不符合条件
    {
      cout<<"RESOURCE INSUFFICIENT!!!"<<endl;
      cout<<"CUSTOMER "<<"P"<<k<<" CAN NOT  OBTAIN RESOURCES IMMEDIATELY."<<endl;
      flag='N';
      break;
    }
    else
    {
      if(Request[j]>AVAILABLE[j])  //请求大于可用，不符合条件
      {
       cout<<"RESOURCE INSUFFICIENT!!!"<<endl;
       cout<<"CUSTOMER "<<"P"<<k<<" CAN NOT  OBTAIN RESOURCES IMMEDIATELY."<<endl;
       flag='N';
       break;
      }
    }
  }

  if(flag=='Y'||flag=='y')
  {
   rstore();
   changdata(k);  //试探资源分配
   
   sec=chkerr(k);  //安全性检测
   if(sec)
   {
	   
     rstordata(i);  //恢复数据 
	 recly();
	   showdata2(sec,k);
   }
   else
     showdata2(sec,k);
  }
   
};

void showdata1(int s)  //显示系统安全检测结果
{
int i,j;
if(s)
{ 	
  cout<<"SYSTEM NOT SECURITY!!!"<<endl;
}
else
{
  cout<<"      Work       Need     Allocation    Work+ Allocation    Finish"<<endl;
  for(i=0;i<M;i++)
  {
   cout<<"p"<<temp[i];
         cout<<"    ";
	     for(j=0;j<N;j++)
	     cout<<WORK[i][j]<<" ";
		 cout<<"    ";
	     for(j=0;j<N;j++)
	     cout<<" "<<NEED[temp[i]][j];
		 cout<<"    ";
         for(j=0;j<N;j++)
		 cout<<" "<<ALLOCATION[temp[i]][j];
		 cout<<"         ";
         for(j=0;j<N;j++)
		 cout<<" "<<WORK[i][j]+ALLOCATION[temp[i]][j];
		 cout<<"               ";
    if(FINISH[i]) cout<<"T";
	else cout<<"F";
	cout<<endl;
  }
  cout<<"SYSTEM SECURITY!!!"<<endl;
}
};

void showdata2(int s,int k)  //显示单个进程安全性检测结果
{
int i,j;
if(s)
{ 	
  cout<<"RESOURCE INSUFFICIENT!!!"<<endl;
  cout<<"CUSTOMER "<<"P"<<k<<" CAN NOT  OBTAIN RESOURCES IMMEDIATELY."<<endl;
}
else
{
   cout<<"      Work       Need     Allocation    Work+ Allocation    Finish"<<endl;
  for(i=0;i<M;i++)
  {
   cout<<"p"<<temp[i];
         cout<<"    ";
	     for(j=0;j<N;j++)
	     cout<<WORK[i][j]<<" ";
		 cout<<"    ";
	     for(j=0;j<N;j++)
	     cout<<" "<<NEED[temp[i]][j];
		 cout<<"    ";
         for(j=0;j<N;j++)
		 cout<<" "<<ALLOCATION[temp[i]][j];
		 cout<<"         ";
         for(j=0;j<N;j++)
		 cout<<" "<<WORK[i][j]+ALLOCATION[temp[i]][j];
		 cout<<"               ";
    if(FINISH[i]) cout<<"T";
	else cout<<"F";
	cout<<endl;
  }
  cout<<"SYSTEM SECURITY!!!"<<endl;
  cout<<"CUSTOMER "<<"P"<<k<<" CAN GET RESOURCES IMMEDIATELY."<<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 rstordata(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 rstore()  //资源恢复
{
	int i,j,zero[5]={0,0,0,0,0},rsort=0,r;
	for(i=0;i<M;i++)
	{
	   for(j=0;j<N;j++)
          if(ALLOCATION[i][j]==0)  zero[i]++;
	      if(zero[i]==3)  {rsort=1;r=i;}
	}
	if(rsort==1)
	{
		for(j=0;j<N;j++)
		{
		   ALLOCATION[r][j]=temp2[r][j];
		   MAX[r][j]=temp3[r][j];
		   NEED[r][j]=MAX[r][j]-ALLOCATION[r][j];
		   AVAILABLE[j]=AVAILABLE[j]-ALLOCATION[r][j];
		}
	}
};

void recly()  //资源回收
{
	int i,j,zero[5]={0,0,0,0,0},rsort=0,r;
	for(i=0;i<M;i++)
	{
	   for(j=0;j<N;j++)
          if(NEED[i][j]==0)  zero[i]++;
	      if(zero[i]==3)  {rsort=1;r=i;}
	}
	if(rsort==1)
	{
       for(j=0;j<N;j++)
	   {
		  AVAILABLE[j]=AVAILABLE[j]+ALLOCATION[r][j]; //初始WORK向量
	      ALLOCATION[r][j]=0;
	   }
	}
};


int chkerr(int s)  //安全性试探分配
{
	int p=0,q,flag=0;
int i,j,k=0;
for(i=0;i<M;i++) FINISH[i]=FALSE;
for(j=0;j<N;j++)
   WORK[p][j]=AVAILABLE[j]; //初始WORK向量	
i=s;
while(i<M+1)
{
  for(j=0;j<N;j++)
  {
     if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[p][j]) //比较NEED与WORK
     flag++;
  }
  if(flag==3)
  {
	 for(j=0;j<N;j++)
	     WA[p][j]=WORK[p][j]+ALLOCATION[i][j];  //满足条件则产生新的WORK
	 q=p;
	 p++;
	 for(j=0;j<N;j++)
		 WORK[p][j]=WA[q][j];
     FINISH[i]=TRUE;   //置安全标志为TRUE
     temp[k]=i;  //存储进程序列
     k++;
     i=0;  //向下一个进程继续试探
	 flag=0;
  }
  else
  {
	  i++;
	  flag=0;
  }
}
for(i=0;i<M;i++)   
    if(FINISH[i]==FALSE)
    {
      cout<<endl;
      return 1;
    }
  cout<<endl;
  return 0;
};