银行家算法的实现与应用

银行家算法的实现与应用学生姓名：xxx学号：xxxxxxxxxx学院：网络工程学院专业：网络工程指导老师：xxx职称：副教授摘要：银行家算法是一种能够避免死锁的经典算法，它通过模拟银行借贷系统的分配策略，来确保操作系统的安全运行。本文依据操作系统课程中死锁及银行家算法的相关知识，描述了它的数据结构和算法流程，并使用C语言具体实现了该算法。由于银行家算法中安全检查过程要求严格，导致系统开销过大，效率不高。对此，本文对它的性能做了改进。最后用改进后的银行家算法解决扶贫基金的有效分配问题，试验结果表明，使用该算法对扶贫基金进行分配可使扶贫基金的分配更合理，效率更高效，资产质量更优良。关键字：操作系统；死锁；进程；数据结构；银行家算法;资源分配ImplementationAndApplicationofBanker’sAlgorithmAbstract:Banker’salgorithm,aclassicalalgorithmtoavoiddeadlock,isusetoensurethecomputeroperatingsystemtorunsafelythroughsimulatingtheallocationstrategyofthebankborrowingandlendingsystem.Thedatastructureandflowofworkaredescribedinthepaper,andthealgorithmisimplementedbyClanguageprogramaccordingtotherelevantknowledgeaboutdeadlockandbanker’salgorithm.Asthesafetyinspectionprocessisstrict,itleadstohighsystemoverheadandlowefficiency.Soweimprovetheperformanceofalgorithm.Intheend,theimprovedbanker’salgorithmisappliedtosolvetheeffectivedistributionofpovertyalleviationfund.Theexperienceresultsshowthatusingthealgorithmofthepovertyalleviationfundsallocatedtopovertyalleviationfundallocationmorereasonable,moreefficient,moreexcellentassetquality.KeyWords:TheOperatingSystem;Deadlock;Process;DataStructure;Banker’sAlgorithm;TheAllocationofResources引言研究银行家算法就不得不提到死锁[1]，在操作系统课程中，死锁作为一个重要概念在整个操作系统中占有举足轻重的地位。为了提高资源利用率和系统吞吐量，现代操作系统大量采用多任务并行调度策略[2]，因此死锁在计算机软件和硬件都迅猛发展的当代依然广泛存在。在设计操作系统时，无法回避对死锁问题的考虑和处理。银行家算法作为一种经典的解决死锁问题的方案，其研究的意义和重要性都是不言而喻的。基于相关课程的学习，对银行家算法的具体实现和推广进行研究、分析并加以应用。1.课题研究的目的和意义1.1课题研究的目的就目前而言，尽管人们对银行家算法已经有了相当深入的认识和研究，并已经作为一个经典算法编入教科书。但是，仍然有继续深入研究的价值。就本文而言，通过研究银行家算法的具体实现和现实应用，第一可以更加深入的理解死锁的特性和危害，第二可以更加深刻的掌握处理死锁的策略以及银行家算法的基本思想和流程，第三基于对银行家算法深入的认识可以对它的局限性做一些改进也可以在解决实际问题中灵活地运用它们。1.2课题研究的意义在计算机操作系统中银行家算法有重要的研究意义。第一，利用银行家算法，可以检测系统为进程分配资源的情况，决定系统是否响应某进程的请求并为其分配资源，从而很好的避免了死锁的发生。第二，在三种死锁的处理策略中，避免死锁的方法所施加的限制条件较弱，不需要特别的软硬件资源即可获得令人满意的系统性能。第三，现实生活中资源分配的例子很多，可借助于该算法进行合理分配，达到优化资源的目的。所以研究银行家算法是很有必要的，也是很有现实意义的。2.银行家算法的原理分析2.1银行家算法的基本思想计算机系统中软硬件资源是有限的，而运行进程对资源的要求是非常多的，绝大多数情况下，系统往往不能满足当前运行进程的所有资源需求之和。但可以采取各个击破的方法，在情况允许下先满足部分进程的需求，等这些进程运行结束后，把资源释放给系统，系统再进行分配资源给剩下的进程。最后所有进程都得到满足。银行家算法就是这种思想的具体体现。Dijkstra提出的银行家算法[3]就是在银行发放一笔贷款前，预测该笔贷款是否会引起银行资金周转困难。可以把操作系统看作是银行家，操作系统管理的资源就相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。银行家能预测一笔贷款业务对银行是否安全，也能预测一次资源分配对计算机系统是否安全。要解释银行家算法，必须先解释操作系统中安全状态和不安全状态[4]。安全状态是指：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定没有死锁发生。反之，如果系统中不存在一个安全序列则系统处于不安全状态。当然，不安全状态也并不意味着一定会导致死锁[5]。为了实现银行家算法，系统中必须设置若干数据结构。2.2银行家算法的数据结构和描述（1）数据结构①最大需求矩阵ZD：它是一个s×t的二维数组,它定义了系统中s个进程中的每个进程对t类资源的最大需求。如果ZD[i,j]=K,则表示process[i]需要Rj类资源的最大数目为K。②需求矩阵XQ：它是一个s×t的二维数组,它用来表示每个进程尚需的各类资源数目。如果XQ[i,j]=K,则表示process[i]还需要Rj类资源K个,才能顺利完成任务。③已分配矩阵FP：它是一个s×t的二维数组,它定义了系统中每类资源当前已分配给每个进程的资源数。如果FP[i,j]=K,则表示process[i]当前已分得Rj类资源的数目为K。④当前可用资源集合DQ：它是一个含有t个元素的一维数组,其中的每个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，计算机系统中有处理器资源、存储器资源、I/O设备资源和应用软件、文件系统等资源。如果DQ[j]=K,则表示系统中现有Rj类资源K个。并且上述三个矩阵之间有如下关系：XQ[i,j]=ZD[i,j]—FP[i,j]（2）算法流程描述银行家算法的流程大致分为三步进行，分别是：资源的预分配；系统的安全性检查；资源的正式分配[6]。例如当一个进程Pi发出资源请求后,系统按下述步骤对进程Pi进行检查，银行家算法流程图如图1：①如果进程Pi的请求资源数目是小于等于进程Pi的需求资源数目，就执行第二步；否则认为是非法的。②如果进程Pi的请求资源数目是小于等于进程Pi的当前可用资源数目，就执行第三步；否则就表示当前系统中没有足够的资源供进程i使用，进程i须要阻塞等待。③系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值:DQ[j]=DQ[j]-Requesti[j]；FP[i,j]=FP[i,j]+Requesti[j]；XQ[i,j]=XQ[i,j]-Requesti[j]；其中Requesti[j]表示进程Pi发出的对Rj类资源的请求数目。④预分配后，系统执行安全性检查,安全性检查流程图如图2。检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程,以完成本次分配；否则，将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。系统初始化时资源分配情况表输入进程Pi申请的资源量Requesti[j]XQ[i][j]Requesti[j]DQ[i][j]预分配进行安全性检查NN继续分配（Y）OR退出系统(N)YY图1银行家算法流程图调用check()函数Work[]=DQ[]Finish[]=falseXQ[][]=work[]Finish[]=false?Work[]=work[]+FP[][]Finish[]=trueY调用结束N图2安全性算法流程图3.银行家算法的实现和改进3.1银行家算法的实现（1）开发平台银行家算法是在如下开发环境中实现的：戴尔笔记本个人电脑；Window7操作系统；C语言；MicrosoftVisualC++6.0开发工具；（2）实现过程实现过程分四步进行，它们分别是：数据的输入；预分配；安全性检查；正式分配；①数据的输入：#includestdio.h#defineMaxProcess50/*最大进程数*/#defineMaxResource50/*最大资源数*/intDQ[MaxResource];/*可用资源数组*/intZD[MaxProcess][MaxResource];/*最大需求矩阵*/intFP[MaxProcess][MaxResource];/*分配矩阵*/intXQ[MaxProcess][MaxResource];/*需求矩阵*/intRequest[MaxProcess][MaxResource];/*进程需要资源数*/intn,m,i,j;/*m个资源,n个进程*/②预分配：IntYFP（）/*预分配函数*/{DQ[j]=DQ[j]-Request[j];FP[i][j]=FP[i][j]+Request[j];XQ[i][j]=XQ[i][j]-Request[j];/*系统尝试把资源分配给请求的进程*/}③安全性检查：Voidcheck()/*安全检查函数*/{for(i=0;in;i++)finish[i]=false;/*初始化进程均没有得到足够资源数并完成*/For(j=0;jm;j++)work[j]=DQ[j];/*work[j]表示可提供进程继续运行的各类资源数*/For(i=0;in;i++){If(finish[i]==true)Continue;}Else{For(j=0;jm;j++){If(XQ[i][j]work[j]){Printf(“notenoughresource,process[%d]waiting…\n”,i);Break;}}}If(j==n)/*找到还没有完成且需求数小于可提供进程继续运行的资源数的进程*/{Finish[i]=true;For(j=0;jm;j++)Work[j]+=FP[i][j];}}/*释放该进程已分配的资源*/（3）调试测试下面分三种情况进行演示。①第一种情况：有5个进程，每个进程需要3种资源。当进程P1申请资源向量为（1,0,2）时，利用银行家算法和安全性算法进行检查，系统是安全的，并同意分配请求。如图3所示：图3第一种情况演示图②第二种情况：有4个进程，每个进程需要3种资源。当进程P1申请资源向量为（0,0,1）时，利用银行家算法和安全性算法进行检查[7]，系统是安全的，并同意分配请求。如图4所示：图4第二种情况演示图③第三种情况：有4个进程，每个进程需要3种资源。当进程P0申请资源向量为（0,0,1）时，利用银行家算法和安全性算法进行检查，系统是不安全的，并拒绝分配请求。图5第三种情况演示图3.2银行家算法的改进通过上面的操作很容易看出，银行家算法有个重要优点：不需要像死锁预防那样添加种种限制[8]，也就是所说的不需要破坏死锁产生的四个条件之一，但是银行家算法要求过于严格，在实际运行中很难得到预想的效果，例如，进程必须预先申明需要的资源总量；系统也必须提供固定数量的资源供进程使用；进程之间是相互独立的，它们的执行顺序是取决于系统安全，而不是进程间的同步要求。尤其是，银行