银行家算法

操作系统原理课程设计题目银行家算法学院专业姓名年级2013年12月25日摘要银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源，如果不是安全状态，则不能为申请资源的进程分配资源。银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。关键字：可用资源最大需求矩阵分配矩阵需求矩阵请求向量试分配安全性算法安全序列目录绪论.............................................................................................................1一算法原理………………………………………………………….....1二算法思想...............................................................................................22.1安全性算法的算法思想.........................................................................22.1.1设置两个向量......................................................................................22.1.2安全性检测.........................................................................................22.2银行家算法的算法思想.........................................................................22.2.1银行家算法的思路...............................................................................42.2.2银行家算法........................................................................................32.2.3安全性检查算法..................................................................................3三详细设计...............................................................................................43.1银行家算法中用到的主要数据结构设计..................................................43.2算法整体设计与调用.............................................................................53.3模块设计与时间复杂度分析...................................................................63.3.1intcheck_distribution(int*p,intk)函数......................................................63.3.2intcheck_safe()银行家算法...................................................................63.3.3voidprint()输出函数............................................................................63.4程序流程图...........................................................................................73.4.1主函数voidmain（）函数流程图............................................................73.4.2判断试分配函数intcheck_distribution(int*p,intk)流程图..................83.4.3银行家算法intcheck_safe()流程图............................................................83.4.4输出函数voidprint()流程图..................................................................9四程序调试、分析与修改....................................................................94.1分模块调试与分析.................................................................................94.1.1进程信息的输入与输出调试....................................................................94.1.2进程请求资源输入出错提示信息处理.....................................................114.1.3判断试分配函数intcheck_distribution(int*p,intk)......................................114.1.4求安全序列函数intcheck_safe()............................................................11五结论.....................................................................................................12附录（源代码）......................................................................................14参考文献...................................................................................................24绪论银行家算法是避免死锁的一种重要方法。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。现在的大部分系统都没有采用这个算法，也没有任何关于死锁的检查。银行家算法一、银行家算法原理银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。二算法思想2.1安全性算法的算法思想思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。2.1.1设置两个向量（1）工作向量Work[m]:它表示系统可提供给进程继续运行所需的各类资源数目，Work初∶=Available;（2）Finish[n]:它表示系统是否有足够的资源分配给进程，使之运行完成。false表示未完成，true表示完成。2.1.2安全性检测2.2银行家算法的算法思想2.2.1银行家算法的思路Work＝Available寻找进程i，满足Finish[i]＝false返回安全状态yWork=work+AllocationiFinish[i]＝true找到所有进程的没找到n返回不安全状态先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。2.2.2银行家算法进程i发出申请资源请求：(1)调用check_distribution(int*p,intk)检查申请量是否不大于需求量再检查检查申请量是否小于系统中的可利用资源数量：若条件不符重新输入，不允许申请大于需求量。(2)若以上条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Available[i,j]=Available[i,j]-Requesti[j]；Allocation[i][j]=Allocation[i][j]+Requesti[j]；need[i][j]=need[i][j]-Requesti[j]；(3)进行试分配，执行安全性检查，调用check_safe()函数检查此次资源试分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(4)用while循环语句实现输