毕业论文银行家算法避免死锁的研究与实现

长治学院2013届学士学位毕业论文银行家算法避免死锁的研究与实现学号：09407227姓名：王子丹指导教师：陕粉丽专业：计算机科学与技术系别：计算机系完成时间：2013年5月长治学院学士学位论文(设计)I银行家算法避免死锁的研究与实现专业：计算机科学与技术姓名：王子丹学号：09407227指导教师：陕粉丽摘要：Dijkstra的银行家算法是最有代表性的避免死锁的算法，该算法由于能用于银行系统现金贷款的发放而得名。银行家算法是在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。该论文在理解和分析了银行家算法的核心思想以及状态的本质含义的前提下，对算法的实现在总体上进行了设计，包括对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行测试，最后进行程序的测试，在设计思路上严格按照软件工程的思想执行，确保了设计和实现的可行性。关键词：银行家算法；死锁；避免死锁；安全性序列银行家算法避免死锁的研究与实现II目录1前言.................................................................11.1课题背景........................................................11.2死锁............................................................11.3系统安全状态....................................................21.4银行家算法......................................................22需求分析.............................................................32.1问题描述........................................................32.2基本要求........................................................32.3数据流模型......................................................33概要设计.............................................................43.1模块的划分......................................................43.2模块调用关系....................................................43.3各模块之间的接口................................................43.4程序流程图......................................................54详细设计.............................................................54.1数据结构选取分析................................................64.2数据结构设计....................................................64.3算法整体设计与调用..............................................64.4程序流图........................................................75程序分析测试.........................................................95.1分模块分析与测试................................................95.2集成测试.......................................................116结论................................................................12参考文献..............................................................12致谢..................................................................14附录..................................................................15长治学院学士学位论文(设计)1银行家算法避免死锁的研究与实现1前言1.1课题背景在多道程序系统中，虽可以借助多个进程的并发执行来改善系统的资源利用率，提高系统吞吐量，但可能发生一种危险——死锁。如此，寻求一种避免死锁的方法便显得很重要。死锁产生的一般原因有两点：竞争资源和进程间推进顺序非法。因此，我们只需在当前的有限资源下，找到一组合法的执行顺序，便能很好的避免死锁。而银行家算法起源于银行系统的发放贷款，和计算机操作系统的资源分配完全符合，因此可以借鉴该算法的思想，设计出一种有效的算法程序，解决该问题。1.2死锁死锁是进程死锁的简称，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那么死锁涉及到的各个进程都将永远处于封锁状态。虽然进程在运行过程中会产生死锁，但死锁的发生也必须具备四个条件：（1）互斥条件；（2）请求与保持条件；（3）不剥夺条件；（4）环路与等待条件。为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防发生死锁。目前，预防死锁的方法可归结为以下两种：（1）预防死锁。它是通过设置某些限制条件。去破坏产生死锁的四个条件中的一个或几个条件，来预防发生死锁。（2）避免死锁。同样是实现预防的策略但是他并不是实现采取各种限制措施去破坏产生死锁的四个条件，而是在资源分配过程中，用某种方法去防止系统进入不安全的状态，从而避免死锁。（3）检测死锁。这种方法并不须事先采取任何限制性措施，也不需检查系统是否进入不安全区，而是允许系统在运行过程中发生死锁。通过系统设置的检测机构，及时的检测出死锁的发生。然后，采取适当的手段，将死锁清除掉。（4）解除死锁。与检测死锁相配套，当系统发生死锁的时候，将进程从死锁中解除出来。银行家算法避免死锁的研究与实现21.3系统安全状态预防死锁和解除死锁都是通过施加条件限制，来预防发生死锁。但预防死锁所施加的条件较严格，这往往会影响进程的并发执行，而避免死锁所施加的限制条件则较宽松，这给进程的运行提供了较宽松的环境，有利于进程的并发执行。要想避免死锁，就必须考虑进程是否处于安全状态，只要处于安全状态就可以避免死锁。所谓的安全状态就是指系统按某种进程顺序（P1，P2，……，Pn）（称P1，P2，……，Pn为安全序列），来为某种进程分配资源，直至满足每个进程对资源的最大需求，使每个进程都能够顺利完成。但如果系统无法找到这样一个安全序列，则称系统处于不安全状态。1.4银行家算法银行家算法是最具有代表性的避免死锁的算法，是由于该算法能用于银行系统现金贷款的发放而得名。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定：（1）当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；（2）顾客可以分次贷款,但贷款的总数不能超过最大需求量；（3）当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款；（4）当顾客得到所需的资金后,一定能在有限的时间里归还所有的资金。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。那么，安全序列在银行家算法中的实际意义在于：系统每次进行资源分配后，如果对于系统中新的资源状况，存在一个安全序列，则至少存在一条确保系统不长治学院学士学位论文(设计)3会进入死锁的路径。2需求分析2.1问题描述运用银行家算法避免死锁的发生是在确保当前系统安全的前提下推进的，对进程请求先进行安全性检查来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。问题的关键在于安全性算法，即查找安全性序列。2.2基本要求（1）从键盘输入当前系统的资源信息，包括当前可用资源，每个进程对各类资源的最大需求量，每个进程当前已分配的各个资源量和每个进程尚需要的各个资源量；（2）输入进程请求，按照设计好的安全性算法进行检查，得到结果并输出整个执行过程的相关信息和最终结果；（3）要求要有各种异常的处理，程序的可控制性和可连续性执行。包括对进程的存在有无检查，请求向量的不合法检查，试分配失败后的数据恢复和重新接受进程请求等。2.3数据流模型用键盘输入信息，对系统资源初始化，输入进程请求，用安全性算法进行安全性检查，系统安全的话就进行试分配，再进行安全性检查；如果试分配失败则恢复系统。如图1所示。图1数据流模型试分配安全性检查输入信息输出结果安全性检查初始化银行家算法避免死锁的研究与实现43概要设计3.1模块的划分由于该算法规模较小，所以选用结构化的设计方法，将该系统划为四块，分别是：（1）主模块，处在整个系统的最高层，负责组织调用其他模块；（2）初始化模块，负责从键盘读入系统资源和进程状态，并将系统初识资源分配状态打印；（3）试分配模块，负责处理进程请求和相应的数据结构的修改，以及特殊情况的处理；（4）安全性检查，负责试分配后的安全性检查，以及系统不安全时的资源恢复。3.2模块调用关系银行家算法系统有四个模块，各模块之间的调用关系如图2所示：图2模块调用关系图3.3各模块之间的接口系统的四个模块用到三个接口。分别为Flag1，pro，Flag2。它们的功能介绍如下：Flag1：试分配模块Attempt_Allocation与安全性检查Safety_Algorithm之间接口Attempt_Allocation通过检查flag的真假了判断是否执行。Pro：一个地址，Safety_Algorithm返回给主模块main的信息，不为NULL时表示试分配成功，否则系统转入相应异常处理。Flag2：Safety_Algorithm与主模块之间的接口，为真则调用打印函数，输出主模块Main（）初始化Init_process（）试分配Attempt_Allocation（）安全性检查Safety_Algorithm（）长治学院学士学位论文（设计）5最终结果，否则调用恢复函数，恢复之前系统状态。3.4程序流程图假设Request是进程的请求向量，Need是需求向量，Available是可利用资源向量。如果Request[j]≥Need[i,j]，则认为出错，进入等待状态。因为它所需要的资源数已经超得过最大值，否则判断Request[j]，Available[j]。如果Request[j]≥Available[j]，则表示尚无足够资源，进程需要等待。接着，系统试探