引子

最近上操作系统课学到了银行家算法，起初看课本觉得这个讲的是什么，仔细研究了一下发现这个算法最重要的一点就是安全性检查了。

抽象的过程

先说一下这个算法模拟的是什么过程：
假设有一个银行，里面有人民币、美元、日元、韩币等资源，有许多客户向银行申请贷款。

每个客户都可以发出申请先贷款一部分，也可以发出申请贷款全部，比如有个客户想贷款人民币3元、美元2元、日元1元，那么他每种资源只申请贷款1元也可以，但是只有全部申请够了，客户才会还银行钱，这个业务才完成了。

银行要做的事情就是判断这个客户的申请是否是狮子大开口，贷款的资源超过了他的需求。如果不是，再判断银行是否有分配给这个客户钱的能力，而这里的能力不仅包括现在的资源是否能够满足这个客户的申请，而且还包括满足这个客户的申请后，银行还有没有完成全部业务的能力。这也就是所谓的安全性检查了。

我们用极端的思想想想，如果给一个客户分了太多资源，将有可能导致银行面临一个非常困难的境地——这个客户的贷款业务还没有完成所以银行不能把钱收回来，而现在银行的钱太少了，以至于这个客户和其他客户的业务都完成不了，所以银行现在只能给钱还收不回来（客户会以你没完成我的贷款业务为借口）。

如何进行安全性检查呢？

我们可以假设银行已经把钱借给了这个客户，然后按此情况进行模拟，在这种情况下，银行如果还能够完成全部的业务，那么，这个借钱的行为就是安全的，银行你放心借吧。如果不行，那么银行你千万别借，借了之后就不能完成全部业务了。

如何模拟：
这其实是一个大鱼吃小鱼的游戏（4399、摩尔庄园玩过。。），我们可以把银行现在有的资源看作是一条大鱼，然后把其他客户的业务看作是一条小鱼，银行完成一个客户的业务就能收钱，那么银行就会有更多的资源去完成其他的业务，这也就是一条大鱼，吃了其他小鱼，变得更大，然后就能吃更大的鱼的过程。

需要注意的是，我们并不需要关注大鱼吃的每一条小鱼的顺序，只需要找到比它小的鱼并吃掉就可以了，这既节省时间又不会改变结果（可以自己思考一下为什么）。
如果“大鱼”最后能吃掉全部“鱼”，那么这个系统就是安全的，否则，这个系统就是不安全的。

伪代码

整个算法思路如下：

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
　　(1) 可利用资源向量 available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。
　　(2) 最大需求矩阵Max。这是一个n x m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj 类资源的最大数目为K。
　　(3) 分配矩阵 allocation。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 allocation[i,jl = K，则表示进程i当前己分得j类资源的数目为K。
　　(4) 需求矩阵need.这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果need[i,j] = K，则表示进程i还需要j类资源K个才能完成其业务。
上述三个矩阵间存在下述关系:
　　　　　　　　　　　　　　need[i,j] = Max[i,j] - allocation[i, j]

假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：
（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。

（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，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，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。


安全性算法
（1）设置两个向量：
         工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;
         Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。
（2）从进程集合中找到一个能满足下述条件的进程：
         Finish［i］=false;
         Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。
（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
         Work［j］∶=Work［i］+Allocation［i,j］;
         Finish［i］∶=true;
         go to step 2;
（4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

C++代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int m=3,n=5;				//m为银行资源数目,n为客户数目
int available[m]={ 3,3,2};				//目前可用资源向量
const int Max[n][m]={ { 7,5,3},{ 3,2,2},{ 9,0,2},{ 2,2,2},{ 4,3,3}};			//最大需求矩阵
int allocation[n][m]={ { 0,1,0},{ 2,0,0},{ 3,0,2},{ 2,1,1},{ 0,0,2}};			//分配矩阵，allocation[i][j]=k表示客户[i]已经拿到k个m类资源
int need[n][m]={ { 7,4,3},{ 1,2,2},{ 6,0,0},{ 0,1,1},{ 4,3,1}};					//目前需求矩阵，need[i][j]=Max[i][j]-allocation[i][j]; 
vector<int> safe_series;
 
void showNow()
{ 
	printf("\n-------------------------------\n");
	printf("目前可用资源:\n");
	for(int i=0;i<m;i++)
	{ 
		printf("%2d ",available[i]);
	}
	printf("\n");
	printf("\n最大需求矩阵:\n");
	for(int i=0;i<n;i++)
	{ 
		for(int j=0;j<m;j++)
		{ 
			printf("%2d ",Max[i][j]);
		}
		printf("\n");
	}
	printf("\n分配矩阵:\n");
	for(int i=0;i<n;i++)
	{ 
		for(int j=0;j<m;j++)
		{ 
			printf("%2d ",allocation[i][j]);
		}
		printf("\n");
	}
	printf("\n目前需求矩阵:\n");
	for(int i=0;i<n;i++)
	{ 
		for(int j=0;j<m;j++)
		{ 
			printf("%2d ",need[i][j]);
		}
		printf("\n");
	}
	printf("\n-------------------------------\n");
}

//检查用户的需求向量是否都为0，若都为0,返回true 
bool is_all_zero(int pid)
{ 
	for(int i=0;i<m;i++)
	{ 
		if(need[pid][i]>0)
		{ 
			return false;			//全部为0才算完成 
		}
	}
	return true;
}

//判断当前系统是否安全 
bool is_safe()
{ 
	safe_series.clear();
	int work[m];						//用来存储available信息,不破坏available 
	int finish[n];						//finish[i]=true,代表客户i的业务已经被完成；finish[i]=false，代表客户i的业务还未被完成 
	memset(finish,0,sizeof(finish));	//finish[i]全部设置为false
	 
	//work初始化 
	for(int i=0;i<m;i++)
	{ 
		work[i]=available[i];
	}
	
	int num=0;							//记录已经被完成的业务有多少个 
	//初始化finish 
	for(int i=0;i<n;i++)
	{ 
		if(is_all_zero(i))
		{ 
			finish[i]=true;
			num++;
		}
	}
	
	int index=0;
	
	bool allfinished=false;
	//num==n，全部业务已完成，跳出循环
	while(num!=n)
	{ 
		bool canfind=false;					//记录这次有没有找到新的可完成的业务 
		//查找一个银行可以完成其业务的客户 
		for(int cur=0;cur<n;cur++)
		{ 
			if(finish[cur]==false)		//该客户的业务未被完成 
			{ 
				bool flag=true;
				for(int j=0;j<m;j++)
				{ 
					if(need[cur][j]>work[j])
					{ 
						flag=false;
						break;
					}
				}
				if(!flag)				//银行没有完成其业务的能力 
				{ 
					continue;
				}
				else
				{ 
					for(int j=0;j<n;j++)
					{ 
						work[j]+=allocation[cur][j];
					}
					finish[cur]=true;
					num++;
					canfind=true;
					safe_series.push_back(cur);
					
					if(num==n)
					{ 
						allfinished=true;
						break;
					}
				}
			}
		}
		if(allfinished) break;			//全部业务已完成 
		if(!canfind) break;				//这次不能找到可以完成的业务 
		
	}
	
	if(allfinished)
	{ 
		return true;
	}
	else
	{ 
		return false;
	}
	
}

void print_safe_series()
{ 
	if(is_safe())
	{ 
		printf("本次安全检查发现的安全序列为:\n");
		for(int i=0;i<safe_series.size();i++)
		{ 
				printf("%d ",safe_series[i]);
		}
		printf("\n");
	}
	else
	{ 
		printf("系统不安全！！\n");
	}
}



int main()
{ 
	string str;
	if(is_safe()) printf("该系统是安全的\n");
	else
	{ 
		printf("该系统是不安全的，请重新设置系统变量");
		return 0;
	}
	while(1)
	{ 
		printf("请输入接下来的操作(input为输入请求向量，output为输出目前系统信息，print_safe为输出安全序列，exit为退出系统)：\n");
		cin>>str;
		if(str=="input")
		{ 
			int request[m],pid;
			printf("请输入客户id:\n");
			cin>>pid; 
			printf("请输入该客户的请求向量:\n");
			for(int i=0;i<m;i++)
			{ 
				cin>>request[i];
			}
			
			//检查该客户是否狮子大开口
			bool flag=false;
			for(int i=0;i<m;i++)
			{ 
				if(request[i]>need[pid][i])
				{ 
					flag=true;
					break;
				}
			}
			if(flag)
			{ 
				printf("你要的太多了朋友\n");
				continue;
			}
			//检查银行是否有足够的资源满足该客户 
			flag=false;
			for(int i=0;i<m;i++)
			{ 
				if(available[i]<request[i])
				{ 
					flag=true;
					break;
				}
			}
			if(flag)
			{ 
				printf("银行太穷，没办法满足你\n");
				continue;
			}
			
			//先给客户钱，后面安全检查发现不行，会把钱收回来 
			//更新现在的资源数目 
			for(int i=0;i<m;i++)
			{ 
				available[i]-=request[i];
			}
			//更新该客户已被分配多少money 
			for(int i=0;i<m;i++)
			{ 
				allocation[pid][i]+=request[i]; 
			}
			//更新该客户的需求矩阵
			for(int i=0;i<m;i++)
			{ 
				need[pid][i]-=request[i];	
			}
			
			//该用户的业务已被完成,直接回收资源，若回收资源之后系统还是不安全的，只能说这个银行系统一开始就是不安全的，所以在开头应该对系统进行安全性检查 
			if(is_all_zero(pid))
			{ 
				//回收客户i的全部资源 
				for(int i=0;i<m;i++)
				{ 
					available[i]+=allocation[pid][i];
				} 
				memset(allocation[pid],0,sizeof(allocation[pid]));
				printf("客户%d的业务已被完成\n",pid);
				continue;
			}
			
			
			
			if(!is_safe())			//该请求是不安全的 
			{ 
				//还原现在的资源数目 
				for(int i=0;i<m;i++)
				{ 
					available[i]+=request[i];
				}
				//还原该客户已被分配多少money 
				for(int i=0;i<m;i++)
				{ 
					allocation[pid][i]-=request[i]; 
				}
				//还原该客户的需求矩阵
				for(int i=0;i<m;i++)
				{ 
					need[pid][i]+=request[i];	
				}
				printf("该请求会导致银行系统不安全！\n");
			}
			else
			{ 
				printf("请求成功！");
				printf("本次安全检查发现的安全序列为:\n");
				for(int i=0;i<safe_series.size();i++)
				{ 
					printf("%d ",safe_series[i]);
				}
				printf("\n");
			}
		}
		else if(str=="output")
		{ 
			showNow();
		}
		else if(str=="print_safe")
		{ 
			print_safe_series();
		}
		else if(str=="exit")
		{ 
			break;
		}
		else
		{ 
			printf("您输入的字符有误，请重新输入。\n");
		}
	}
	return 0;
}

运行截图如下：