银行家算法避免死锁的研究与实现

《银行家算法避免死锁的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、长治学院学士学位论文(设计)长治学院2013届学士学位毕业论文银行家算法避免死锁的研究与实现学号：姓名：王子丹指导教师：陕粉丽专业：计算机科学与技术系别：计算机系完成时间：2013年5月长治学院学士学位论文(设计)银行家算法避免死锁的研究与实现专业：计算机科学与技术姓名：王子丹学号：指导教师：陕粉丽摘要：Dijkstra的银行家算法是最有代表性的避免死锁的算法，该算法由于能用于银行系统现金贷款的发放而得名。银行家算法是在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。该论文在理解和分析了银行

2、家算法的核心思想以及状态的本质含义的前提下，对算法的实现在总体上进行了设计，包括对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行测试，最后进行程序的测试，在设计思路上严格按照软件工程的思想执行，确保了设计和实现的可行性。关键词：银行家算法；死锁；避免死锁；安全性序列I长治学院学士学位论文(设计)目录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详细设计64.

3、1数据结构选取分析64.2数据结构设计64.3算法整体设计与调用64.4程序流图75程序分析测试95.1分模块分析与测试95.2集成测试116结论12参考文献12致谢14附录15II长治学院学士学位论文(设计)银行家算法避免死锁的研究与实现1前言1.1课题背景在多道程序系统中，虽可以借助多个进程的并发执行来改善系统的资源利用率，提高系统吞吐量，但可能发生一种危险——死锁。如此，寻求一种避免死锁的方法便显得很重要。死锁产生的一般原因有两点：竞争资源和进程间推进顺序非法。因此，我们只需在当前的有限资源下，找到一组合法的执行顺序，便能很好的避免死锁。而银行家算法起源于银行

4、系统的发放贷款，和计算机操作系统的资源分配完全符合，因此可以借鉴该算法的思想，设计出一种有效的算法程序，解决该问题。1.2死锁死锁是进程死锁的简称，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那么死锁涉及到的各个进程都将永远处于封锁状态。虽然进程在运行过程中会产生死锁，但死锁的发生也必须具备四个条件：（1）互斥条件；（2）请求与保持条件；（3）不剥夺条件；（4）环路与等待条件。为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防发生死锁。目前，预防死锁的方法可归结为以下两种：（1）预防死锁。它是通过设置某些限制条件。

5、去破坏产生死锁的四个条件中的一个或几个条件，来预防发生死锁。（2）避免死锁。同样是实现预防的策略但是他并不是实现采取各种限制措施去破坏产生死锁的四个条件，而是在资源分配过程中，用某种方法去防止系统进入不安全的状态，从而避免死锁。（3）检测死锁。这种方法并不须事先采取任何限制性措施，也不需检查系统是否进入不安全区，而是允许系统在运行过程中发生死锁。通过系统设置的检测机构，及时的检测出死锁的发生。然后，采取适当的手段，将死锁清除掉。（4）解除死锁。与检测死锁相配套，当系统发生死锁的时候，将进程从死锁中解除出来。29长治学院学士学位论文(设计)1.3系统安全状态预防死锁和

6、解除死锁都是通过施加条件限制，来预防发生死锁。但预防死锁所施加的条件较严格，这往往会影响进程的并发执行，而避免死锁所施加的限制条件则较宽松，这给进程的运行提供了较宽松的环境，有利于进程的并发执行。要想避免死锁，就必须考虑进程是否处于安全状态，只要处于安全状态就可以避免死锁。所谓的安全状态就是指系统按某种进程顺序（P1，P2，……，Pn）（称为安全序列），来为某种进程分配资源，直至满足每个进程对资源的最大需求，使每个进程都能够顺利完成。但如果系统无法找到这样一个安全序列，则称系统处于不安全状态。1.4银行家算法银行家算法是最具有代表性的避免死

7、锁的算法，是由于该算法能用于银行系统现金贷款的发放而得名。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定：（1）当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；（2）顾客可以分次贷款,但贷款的总数不能超过最大需求量；（3）当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款；（4）当顾客得到所需的资金后,一定能在有限的时间里归还所有的资金。操作系统按照银行家制定的规则为进程分配资源，当