ba.cpp

操作系统中广泛应用的用于避免死锁的银行家算法的程序实现

//
//程序名称：银行家算法的实现
//程序作者：张焕人
//作者邮箱: [e-mail]
//          [e-mail]
//作者QQ：27949278
//
//
//


#include <stdio.h>
#include<iostream.h>
#define M 5  //设置M个process，N个resource
#define N 3
int available[N]={10,5,7},  //可用资源向量：代表一类可利用的资源数目
    work[N]={3,2,2},    //工作向量： 表示系统可提供给进程继续运行所需要的各类资源数目
    max[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}},   //最大需求矩阵：m个进程中的每一个对n类资源的最大需求
    allocation[M][N]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}},   //分配矩阵：每一类资源当前已分配给每一进程的资源数
	need[M][N],   //需求矩阵：每一进程尚需的各类资源数
	request[N],    //请求向量：表示当前进程需要的各类资源数
	which;
int sp[M];  //用来记录安全队列的数组

void input()
{
  int i,j;
  for(j=0;j<N;j++)  //设置总量
  {
      cout<<"请输入resouce["<<j<<"]的可用资源数目: ";
      cin>>available[j];
  }
  for(i=0;i<M;i++) //设置所有进程对各类资源的最大数目
  {
    for(j=0;j<N;j++)
    {
		cout<<"请输入process["<<i<<"]总共需要的resource["<<j<<"]的数目: " ;
        cin>>max[i][j];
    }
  }

  for(i=0;i<M;i++)  //设置已经分配的数目
  {
    for(j=0;j<N;j++)
    {
      cout<<"请输入process["<<i<<"]当前已分配的resource["<<j<<"]的数目: ";
      cin>>allocation[i][j]; 
	  while(allocation[i][j]>max[i][j])
      {
		  cout<<"输入有误(allocation[i][j]>max[i][j])!"<<endl;
		  cout<<"请输入process["<<i<<"]当前已分配的resource["<<j<<"]的数目: ";
          cin>>allocation[i][j]; 
	  }  
    }
  } 
}

bool compare(int *x,int *y) //比较一维数组函数, 要求x<=y为真
{ int j;
  for(j=0;j<N;j++)
  {
    if(x[j]>y[j])
    return false;
  }
  return true;
}

/*bool compare2(int *x,int *y) //比较一维数组和二维数组指定行函数 要求X<=Y为真
{ int j;
  for(j=0;j<N;j++)
  {
    if(x[j]>y[j])
    return false;
  }
  return true;
}  */

/*
bool compareg(int *x,int *y) //比较一维数组和二维数组指定行函数 要求X>Y为真
{ int j;
  for(j=0;j<N;j++)
  {
    if(x[j]<y[j])
    return false;
  }
  return true;
}  */

int safecheck()  //安全检查函数
{
  int work[N];
  bool finish[M];
  bool flag=true;   //判断是否存在安全队列
  int i,j,k,safe=0;
  
  for(i=1;i<M;i++)  //安全数组的初始化
	  sp[i]=-1;

  for(j=0;j<N;j++)
    work[j]=available[j];
  for(i=0;i<M;i++)
    finish[i]=false;
  
  for(k=0;k<M;k++)
    for(i=0;i<M;i++)
    { 
		if(!finish[i]&&compare(need[i],work))  //如果finish=false且此进程的各类NEED<=WORK
		{ 
			for(j=0;j<N;j++)
			{
				work[j]+=allocation[i][j];
			}
			finish[i]=true;
			sp[safe++]=i;	
		}
    }

  for(i=0;i<M;i++)
		if(!finish[i]) 
		{ flag=false; break;}
		
  if(flag) //所有的都能安全完成
  {
	cout<<"安全队列：";
	for(i=0;i<M&&sp[i]!=-1;i++)
			cout<<"process["<<sp[i]<<"] ";
	cout<<endl;
	return 1;
  }
  else
	  return 0;
}

void output()
{
	int i,j;
	cout<<"当前资源分配情况:"<<endl;
	for(i=0;i<M;i++)  //输出需求矩阵max
	{
		for(j=0;j<N;j++)
		{
			cout<<"    max["<<i<<"]["<<j<<"]="<<max[i][j]<<" ";
		}
		cout<<endl;
	}

	for(i=0;i<M;i++)  //输出需求矩阵allocation
	{
		for(j=0;j<N;j++)
		{
			cout<<"    allocation["<<i<<"]["<<j<<"]="<<allocation[i][j]<<" ";
		}
		cout<<endl;
	}

	for(i=0;i<M;i++)  //输出需求矩阵need
	{
		for(j=0;j<N;j++)
		{
			cout<<"    need["<<i<<"]["<<j<<"]="<<need[i][j]<<" ";
		}
		cout<<endl;
	}

	for(i=0;i<N;i++)  //输出需求矩阵available
	{
		cout<<"    available["<<i<<"]="<<available[i]<<" ";		
	}
	cout<<endl<<endl;
}

main()
{   
	int i,j;
	char again;
	char ch;

	int temp1[N],temp2[N],temp3[N]; 

	cout<<"使用默认数据(y/n)?  ";
	cin>>ch;
	while(ch=='n')
	{   
		input(); /*初始化*/
        if(safecheck()==0)
           cout<<"初始数据会发生死锁! 请重新输入!"<<endl;
        else
          break;
	}
    
	for(j=0;j<N;j++) //设置可用资源向量available
	{
		for(i=0;i<M;i++)
			available[j]-=allocation[i][j];
	}
	for(i=0;i<M;i++) //设置需求矩阵need
	{
		for(j=0;j<N;j++)
		{
			need[i][j]=max[i][j]-allocation[i][j];
		}
	}
	
	
	
	while(1)
	{
	  output();  //输出当前资源分配情况
      cout<<"请输入发出请求的进程号(0-"<<M-1<<"): "; //确定哪个进程发出请求
      cin>>which;
      cout<<"请输入该进程的请求向量: ";
      for(i=0;i<N;i++)
        cin>>request[i];  //输入某个进程的请求向量
    
	 
	  if(compare(request,need[which]))  //判断是否大于需要的最大值
	  {   
		//printf("need pass\n");
		if(compare(request,available)) //判断是否有足够的数目 request<=available
		{ 
			// printf("Available pass\n");
			for(j=0;j<N;j++) //尝试分配前先将原始数据保存
			{
				temp1[j]=available[j];
				temp2[j]=allocation[which][j];
				temp3[j]=need[which][j];
			}
			for(j=0;j<N;j++)
			{
				available[j]-=request[j];   //尝试分配
				allocation[which][j]+=request[j];
				need[which][j]-=request[j];
			}
			
			if(safecheck())  //安全检测
			{	// printf("safe\n");
				for(j=0;j<N;j++)
				{
					if(need[which][j]!=0) //如果此进程的所有NEED得到满足
						break;
				}
				if(j>=N)
				{
					for(j=0;j<N;j++) //安全执行完毕，释放此进程所有资源并将要求和拥有置0
					{
						available[j]+=allocation[which][j];
						allocation[which][j]=0;
						need[which][j]=0;
					}
				}
			}
			else
			{
				for(j=0;j<N;j++)
				{
					available[j]=temp1[j];  //不安全则收回
					allocation[which][j]=temp2[j];
					need[which][j]=temp3[j];
				}
				cout<<"资源申请不安全! 恢复申请前状态."<<endl;
				
			}
		}
		else
			cout<<"申请资源数目不够!"<<endl;
	  }
	  else
		  cout<<"申请资源数目超过此进程需要!";
	}
  getchar();
}