编程序模拟银行家算法1. 引言为了提高资源利用率,应采用动态分配资源的方法。
但是，为了避免可能产生的死锁，在进行资源分配时，应采用某种算法来预测是否有可能发生死锁，若存在可能性，就拒绝企图获得资源的请求。
预防死锁和避免死锁的不同在于，前者所采用的分配策略本身就否定了必要条件之一，这样就保证死锁不可能发生；而后者是在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能引起死锁的其个资源请求，银行家算法是避免死锁的一种重要方法。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
它是最具有代表性的避免死锁的算法。
2. 算法的原理银行家算法是一种最有代表性的避免死锁的算法。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。
安全状态一定是没有死锁发生。
不安全状态:不存在一个安全序列。
不安全状态不一定导致死锁。
那么什么是安全序列呢？安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i ≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i ) 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。
当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
3．算法的实现3.1 初始化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵M AX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
3.2 算法思想在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则出错。
(3)系统试探分配资源，修改相关数据：AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
3.5 定义全局变量int Available[x]; //各种资源可利用的数量int Allocation[y][y]; //各进程当前已分配的资源数量int Max[y][y]; //各进程对各类资源的最大需求数int Need[y][y]; //还需求矩阵int Request[x]; //申请各类资源的数量int Work[x]; //工作向量，表系统可提供给进程运行所需各类资源数量int Finish[y]; //表系统是否有足够的资源分配给进程，0为否，1为是4. 程序代码#include <iostream>using namespace std;#define MAXPROCESS 50 / *最大进程数*/#define MAXRESOURCE 100 /*最大资源数*/int AVAILABLE[MAXRESOURCE]; /*可用资源数组*/int MAX[MAXPROCESS][MAXRESOURCE]; /*最大需求矩阵*/int ALLOCATION[MAXPROCESS][MAXRESOURCE]; /*分配矩阵*/int NEED[MAXPROCESS][MAXRESOURCE]; /*需求矩阵*/ int REQUEST[MAXPROCESS][MAXRESOURCE]; /*进程需要资源数* /bool FINISH[MAXPROCESS]; /*系统是否有足够的资源分配*/int p[MAXPROCESS]; /*记录序列*/int m,n;/*m个进程,n个资源*/void Init();bool Safe();void Bank();int main(){ Init();Safe();Bank();}void Init() /*初始化算法*/{ int i,j;cout<<"请输入进程的数目:";cin>>m;cout<<"请输入资源的种类:";cin>>n;cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++)cin>>MAX[i][j];cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl;for(i=0;i<m;i++){ for(j=0;j<n;j++){ cin>>ALLOCATION[i][j];NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];if(NEED[i][j]<0){ cout<<"您输入的第"<<i+1<<"个进程所拥有的第" <<j+1<<"个资源数错误,请重新输入:"<<endl;j--;continue;}}}cout<<"请输入各个资源现有的数目:"<<endl;for(i=0;i<n;i++){ cin>>AVAILABLE[i];}}void Bank() /*银行家算法*/{ int i,cusneed;char again;while(1){ cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl;cin>>cusneed;cout<<"请输入进程所请求的各资源的数量"<<endl;for(i=0;i<n;i++){ cin>>REQUEST[cusneed][i];}for(i=0;i<n;i++){ if(REQUEST[cusneed][i]>NEED[cusneed][i]){ cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl;continue;}if(REQUEST[cusneed][i]>AVAILABLE[i]){cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl; continue;}}for(i=0;i<n;i++){ AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];}if(Safe()){ cout<<"同意分配请求!"<<endl;}else{ cout<<"您的请求被拒绝!"<<endl;for(i=0;i<n;i++){ AVAILABLE[i]+=REQUEST[cusneed][i];ALLOCATION[cusneed][i]-=REQUEST[cusnee d][i];NEED[cusneed][i]+=REQUEST[cusneed][i];}}for(i=0;i<m;i++){ FINISH[i]=false;}cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<< endl;cin>>again;if(again=='y'||again=='Y'){ continue;}break;}}bool Safe()/*安全性算法*/{int i,j,k,l=0;int Work[MAXRESOURCE]; / *工作数组*/for(i=0;i<n;i++)Work[i]=AVAILABLE[i];for(i=0;i<m;i++){FINISH[i]=false;}for(i=0;i<m;i++){if(FINISH[i]==true)if(NEED[i][j]>Work[j]){break;}}if(j==n){FINISH[i]=true;for(k=0;k<n;k++){Work[k]+=ALLOCATION[i][k];}p[l++]=i;i=-1;}else{ continue;}}if(l==m){ cout<<"系统是安全的"<<endl;cout<<"安全序列:"<<endl;for(i=0;i<l;i++){cout<<p[i];if(i!=l-1){cout<<"-->";}}cout<<""<<endl;return true;}}cout<<"系统是不安全的"<<endl;return false;}4. 程序测试5. 设计体会经过几天的自己动手练习，对操作系统的掌握又进了一步，收获了很多课堂上和书上未出现过的或老师未讲到的一些知识。