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