银行家算法（初学者，简单易懂）

一、背景知识

     银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行，这种算法的提出能保证银行在发送贷款的时候，不会发生不满足所有用户需要的情况。

二、实验内容

1. 银行家算法中的数据结构

（1）可利用资源向量Available。它含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，如果Available[j]=K，则表示系统中现有Rj类资源K个。

（2）最大需求矩阵Max。是一个n×m的矩阵，如果Max(i,j)=K，则表示进程i需要Rj 类资源的最大数目为K。

（3）分配矩阵Allocation。是一个n×m的矩阵，如果Allocation(i,j)=K,则表示进程i当前已分得Rj 类资源的数目为K。

（4）需求矩阵Need。是一个n×m的矩阵，如果Need(i,j)=K，则表示进程i还需要Rj 类资源K个，方能完成其任务。

上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j]

2. 银行家算法

如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

（1）如果Requesti[j]<=Need[i,j]，转步骤（2）；否则出错。

（2）如果Requesti[j]<=Available[j]，转步骤（3）；否则，表示尚无足够资源，Pi须等待。

（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

     Available[j]:= Available[j]-Requesti[j];

     Allocation[i,j]:=Allocation[i,j]+ Requesti[j];

     Need[i,j]:=Need[i,j]- Requesti[j];

(4) 系统执行安全性检查，若安全，则正式分配；否则，本次的试探分配作废，恢复原本的资源分配状态，让进程Pi等待。

3. 安全性检查

(1) 设置两个工作向量WORK:=AVAILABLE；FINISH[i]=FALSE ；

(2) 从进程集合中找到一个满足下述条件的进程 

a. FINISH[i]=FALSE

b. NEED<=WORK

如找到，执行(3)；否则，执行(4)。

(3) 当进程获得资源，可顺利执行，直至完成，从而释放资源。

WORK:=WORK+ALLOCATION ;

FINISH[i]:=TRUE ;

GO TO  (2)

(4) 如所有的进程FINISH[i]=TRUE，则表示安全；否则系统处于不安全状态。

三、设计思想

（1）进行T0时刻的安全性检查，即在T0时刻若能找到一个安全序列，则系统是安全的。

（2）以后若有进程发出资源请求，先要判断其合法性，需满足两个条件。即判断请求的各资源数目是否都小于或者等于该进程执行完成所需的各资源数目，接着再判断请求的各资源数目是否都小于或者等于系统当前可分配的各资源数目。若不满足以上两个条件，系统不分配资源给它，让该进程等待。

（3）若满足步骤(2)的两个条件，则系统假定可为该进程分配资源，并修改该进程的相关参数（最大需求数，已分配资源数，仍需资源数）以及系统当前的资源可分配数。

（4）再利用安全性算法检查此时系统是否安全，如果能找到一个安全序列，则可判定系统是安全的，可以立即将该进程所申请的资源分配给它。否则，系统不分配资源给它，让该进程等待。

（5）循环步骤(2)至步骤(4)，直至各进程都执行完毕

四、代码

 
 
#include<iostream>
#include<vector>
using namespace std;
const int M=5;//进程数
const int N=3;//资源数
int maxRequest [M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//最大需求矩阵
int available [N]= {3,3,2};//可用资源向量 
int allocation [M][N]={{0, 1,0,} ,{2,0,0},{3,0,2}, {2, 1, 1},{0,0,2}};//己分配资源矩阵 
int need[M][N]={{7,4,3}, {1,2,2},{6,0,0}, {0,1,1},{4,3,1}};//需求矩阵矩阵 表示每个进程还需要的各类资源的数目
int request [N]={0, 0, 0} ;//资源请求 
 int work[N];
bool Finish [5];
 void showmaxRequest( ) //显示最大需求矩阵 
{
	cout<<"max"<<endl;
        for(int i=0;i<M;i++)
        {
     	for(int j= 0;j<N;j++)
     	{
     		cout<<maxRequest[i][j]<<" ";
		 }
		 cout<<"    ";
	}
		 cout<<endl;
}
 void showallocation() //显示己分配资源矩阵
{ 
      cout<<"allocation"<<endl;
		for(int i=0;i<M;i++)
        {
     		for(int j= 0;j<N;j++)
     		{
     		cout<<allocation[i][j]<<" ";
			}
		 cout<<"    ";
	  }
		 cout<<endl;
}
void showneed() //显示每个进程还需要的各类资源的数目
{ 
      cout<<"need"<<endl;
		for(int i=0;i<M;i++)
        {
     		for(int j= 0;j<N;j++)
     		{
     		cout<<need[i][j]<<" ";
			}
		 cout<<"    ";
	  }
		 cout<<endl;
}
void show()//显示资源分配情况 
{
	cout<<"可用资源数为："<<endl;
	for(int i=0;i<N;i++)
     {
     	cout<<"资源"<<i<<":"<<available[i]<<endl;
	 }	
	cout<<"当前的分配情况："<<endl;
	cout<<"进程"<<endl;
	for(int i=0;i<5;i++ )//输出5个进程 
	{		
	cout<<"p"<<i<<"        " ;
    }
    cout<<endl;
   	showmaxRequest( );
	showallocation();
	showneed();
}
int Safe()
{//安全性算法(核心算法)
    vector<int>s; 
    int work[N];
    for(int i=0;i<N;i++)
    {
    	work[i]=available[i];
	}
	int i,j;
	int count=0;//记录finish为true的个数 
   	for( i =0;i<M;i++)
   	{
        Finish[i]=false;//finish表示系统是否有足够的资源分配给进程，开始时，先让每个进程置为false 
	 }
    while(count != M)//当count等于进程数M时，表示系统处于安全状态 
	{
      	if(Finish[i]!=true)//查找符合的进程  
         {
            for( j = 0; j < N; j++)
			{
               if(need[i][j] > work[j])
				   	break;
			}
            if(j == N) //资源数与j相等，即need中的数都比work小 
			{
                cout<<"p"<<i<<"释放后 work+allocation"<<endl;
        		Finish[i]=true;//找到符合的进程后，将finish置为true 
        		for(int j= 0;j<N;j++)
			 	{
        		 work[j]=work[j]+allocation[i][j];//进程pi执行完成后，释放分配给它的资源 
                 cout<<work[j]<<"  "; 
				} 
				cout<<endl;
				count++;
        		s.push_back(i);//将finish为true的进程输入到 vector容器中 
        	   
			}
	
		}
		i++;
		if(i>4)
		{//i>4时，进程已遍历一遍，令i=0，重新遍历 
	       i=0;	
		}
	}
	if(count==5)//安全状态 
   {
   	cout<<"安全序列为："<<endl; 
	for(vector<int>::iterator it=s.begin();it!=s.end();it++)
	{
		cout<<"p"<<*it<<"->";
	}
	cout<<endl;
	return 0;
	}
	else 
	{
		cout<<"分配不成功"<<endl; 
		return -1;
	}   
}
bool banker(int i){//银行家算法
    for(int j=0;j<N;j++){
       if(request[j]>need[i][j]||request[j]>available[j])//超过它所需要的资源或超过可利用的资源，都为出错 
			return false;} 
    	for(int j=0;j<N;j++) //系统试探着把资源分配给进程,并修改相应的数据
		{ 
        available[j]=available[j]-request[j];
        allocation[i][j]=allocation[i][j]+request[j];
        need[i][j]=need[i][j]-request[j];
   		 }
    if(Safe() ) return true;//如果安全，则返回 
    else//否则，需将试探后 修改的相应数值恢复为原来的资源分配状态，让进程等待 
	{
        for(int i=0;i<M;i++)
      {
    	for(int j=0;j<N;j++)
		{ 
        available[j]=available[j]+request[j];
        allocation[i][j]=allocation[i][j]-request[j];
        need[i][j]=need[i][j]+request[j];
   		 }
      }
        return false;
    }
}
int main()
{
	show();
	int i,k;
	cout<<" 请输入请求分配的进程"<<endl;
	cin>>i;
	cout<<"请输入请求资源数"<<endl;
	for(int j=0;j<N;j++)
	{
		cin>>k;
		request[j]=k;
	 } 
   banker(i);
	return 0; 
}
 

五、运行结果

六、结论

   通过本次实验，对银行家算法有了更深入的了解。总的来说就是从当前状态出发，逐个检查其安全性，需要的每种资源类型的最大单元数目不应该超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。