银行家算法

1.1银行家算法的简介我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。1.2银行家算法的用途银行家算法是一种用来避免死锁的算法。1.2.1死锁的定义一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。1.2.2死锁的避免定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。1.2.2死锁的避免安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态一定导致死锁。1.2.2死锁的避免安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)当前占有资源量之和，系统处于安全状态。(安全状态一定是没有死锁发生的)1.3银行家算法n：系统中进程的总数m：资源类总数Available:ARRAY[1..m]ofinteger;Max:ARRAY[1..n,1..m]ofinteger;1.3银行家算法Allocation:ARRAY[1..n,1..m]ofinteger;Need:ARRAY[1..n,1..m]ofinteger;Request:ARRAY[1..n,1..m]ofinteger;1.3银行家算法简记符号：Available[i]Max[i]Allocation[i]Need[i]Request[i]1.3银行家算法当进程pi提出资源申请时，系统执行下列步骤：（1）若Request[i]≤Need[i],转（2）；否则错误返回（2）若Request[i]≤Available,转（3）；否则进程等待1.3银行家算法(3）假设系统分配了资源，则有：Available:=Available-Request[i];Allocation[i]:=Allocation[i]+Request[i];Need[i]:=Need[i]-Request[i]若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待1.3银行家算法为进行安全性检查，定义数据结构：Work:ARRAY[1..m]ofinteger;Finish:ARRAY[1..n]ofBoolean;安全性检查的步骤：(1)Work:=Available;Finish:=false;(2)寻找满足条件的i：a.Finish[i]=false;b.Need[i]≤Work;如果不存在，则转(4)1.3银行家算法3)Work:=Work+Allocation[i];Finish[i]:=true;转(1)(4)若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态1.3银行家算法例题：假设某系统中有4个资源(R1、R2、R3、R4)，在某个时刻系统中共有5个进程，进程P1，P2，P3，P4，P5的最大资源需求数向量和此时已经分配到的资源数向量分别如表所示：系统中当前可用资源向量为（2，1，0，0），问：（1）当前系统是否安全?（2）如果进程p3发出资源请求向量（0，1，0，0），系统能否将资源分配给它？进程已分配资源最大资源需求P10,0,1,20,0,1,2P22,0,0,02,7,5,0P30,0,3,46,6,5,6P42,3,5,44,3,5,6P50,3,3,20,6,5,21.3银行家算法解：（1）调整表格如下：可用资源（2，1，0，0）进程已分配资源最大资源需求仍需要资源P10,0,1,20,0,1,20,0,0,0P22,0,0,02,7,5,00,7,5,0P30,0,3,46,6,5,66,6,2,2P42,3,5,44,3,5,62,0,0,2P50,3,3,20,6,5,20,3,2,01.3银行家算法则存在以下执行序列，执行过程列表如下：进程可用资源数（剩余资源数+已分配资源数）P12，1，1，2P44，4，6，6P54，7，9，8P26，7，9，8P36，7，12，12•则该状态是安全的1.3银行家算法（2）假设P3发出资源请求（0，1，0，0），系统分配给它，则系统还剩余资源（2，0，0，0），并且状态如下表所示：进程已分配资源最大资源需求仍需要资源P10,0,1,20,0,1,20,0,0,0P22,0,0,02,7,5,00,7,5,0P30,,3,46,6,5,66,5,2,2P42,3,5,44,3,5,62,0,0,2P50,3,3,20,6,5,20,3,2,01.3银行家算法则新的执行过程如下表所示：进程可用资源数（剩余资源数+已分配资源数）P12，0，1，2P44，3，6，6P54，6，9，8•P5执行后，不能继续执行下去，则该状态不安全，系统将拒绝资源请求。1.4银行家算法的实现初始化:由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。1.4银行家算法的实现在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程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.4银行家算法的实现安全性检查算法：(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO2(4)如所有的进程Finish=true，则表示安全；否则系统不安全。1.5银行家算法源程序#includeiostreamusingnamespacestd;#defineMAXPROCESS50/*最大进程数*/#defineMAXRESOURCE100/*最大资源数*/intAVAILABLE[MAXRESOURCE];/*可用资源数组*/intMAX[MAXPROCESS][MAXRESOURCE];/*最大需求矩阵*/intALLOCATION[MAXPROCESS][MAXRESOURCE];/*分配矩阵*/intNEED[MAXPROCESS][MAXRESOURCE];/*需求矩阵*/intREQUEST[MAXPROCESS][MAXRESOURCE];/*进程需要资源数*/boolFINISH[MAXPROCESS];/*系统是否有足够的资源分配*/intp[MAXPROCESS];/*记录序列*/intm,n;/*m个进程,n个资源*/1.5银行家算法源程序voidInit();boolSafe();voidBank();intmain(){Init();Safe();Bank();}voidInit()/*初始化算法*/{inti,j;cout请输入进程的数目:;cinm;cout请输入资源的种类:;cinn;cout请输入每个进程最多所需的各资源数,按照mxn矩阵输入endl;1.5银行家算法源程序for(i=0;im;i++)for(j=0;jn;j++)cinMAX[i][j];cout请输入每个进程已分配的各资源数,也按照mxn矩阵输入endl;for(i=0;im;i++){for(j=0;jn;j++){cinALLOCATION[i][j];NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];if(NEED[i][j]0){cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl;1.5银行家算法源程序j--;continue;}}}cout请输入各个资源现有的数目:endl;for(i=0;in;i++){cinAVAILABLE[i];}}voidBank()/*银行家算法*/{inti,cusneed;charagain;1.5银行家算法源程序while(1){cout请输入要申请资源的进程号(注:第1个进程号为0,依次类推)endl;cincusneed;cout请输入进程所请求的各资源的数量endl;for(i=0;in;i++){cinREQUEST[cusneed][i];}for(i=0;in;i++){if(REQUEST[cusneed][i]NEED[cusneed][i]){cout您输入的请求数超过进程的需求量!请重新输入!endl;1.5银行家算法源程序continue;}if(REQUEST[cusneed][i]AVAILABLE[i]){cout您输入的请求数超过系统有的资源数!请重新输入!endl;continue;}}for(i=0;in;i++){AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];}1.5银行家算法源程序if(Safe()){cout同意分配请求!endl;}else{cout您的请求被拒绝!endl;for(i=0;in;i++){AVAILABLE[i]+=REQUEST[cusneed][i];ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];NEED[cusneed][i]+=REQUEST[cusneed][i];}}for(i=0;im;i++){FINISH[i]=false;}1.5银行家算法源程序cout您还想再次请求分配吗?是请按y/Y,否请按其它键endl;cinagain;if(again=='y'||again=='Y'){continue;}break;}}boolSafe()/*安全性算