银行家算法课程设计报告(毕业论文格式)

操作系统课程设计报告题目：银行家算法的设计与实现院（系）：计算机科学与工程学院专业：班级：学生：翟晓岩学号：指导教师：2010年12月操作系统课程设计报告关键路径的算法设计与实现摘要Dijkstra的银行家算法是最有代表性的避免死锁的算法，该算法由于能用于银行系统现金贷款的发放而得名。银行家算法是在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。该论文在理解和分析了银行家算法的核心思想以及状态的本质涵义的前提下，对算法的实现在总体上进行了设计，包括在对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行测试，最后进行程序的测试，在设计思路上严格按照软件工程的思想执行，确保了设计和实现的可行，可信。代码实现采用C语言。关键词：银行家算法；死锁；避免死锁；安全性序列操作系统课程设计报告I目录中文摘要...................................................................................................I1绪论.......................................................................................................11.1课题背景.........................................................................................................11.2课题意义…………………………………………………………………….11.3银行家算法.....................................................................................................11.4死锁.................................................................................................................21.5安全性序列.....................................................................................................22需求分析...............................................................................................32.1问题描述.........................................................................................................32.2基本要求.........................................................................................................32.3数据流模型.....................................................................................................33概要设计...............................................................................................43.1模块的划分......................................................................................................43.2模块调用关系..................................................................................................43.3各模块之间的接口..........................................................................................43.4程序流程图......................................................................................................54详细设计................................................................................................64.1数据结构选取分析...........................................................................................64.2数据结构设计...................................................................................................64.3算法整体设计与调用.......................................................................................64.4模块设计与时间复杂度分析...........................................................................74.4.1系统资源初始化函数Init_process.........................................................74.4.2安全性算法Safety_Algorithm................................................................74.4.3接受进程请求试分配Attempt_Allocation;............................................74.4.4对试分配后的系统进行安全性检查Safety_Algorithm……………….84.5程序流图............................................................................................8操作系统课程设计报告II4.5.1系统以及进程资源初始化Init_process的程序流程图………………..84.5.2安全性算法Safety_Algorithm的程序流程图.........................................94.5.3接受进程请求试分配Attempt_Allocation的程序流程图......................94.5.4对试分配后的系统进行安全性检查Safety_Algorithm的程序流程图.95程序分析测试………..........................................................................105.1分模块分析与测试.........................................................................................105.1.1初始化系统资源模块Init_process的测试……………………………105.1.2试分配模块Attempt_Allocation的测试………………………………115.1.3安全模块Safety_Algorithm的调试…………………………………...115.2集成测试..........................................................................................................126小结......................................................................................................13参考文献..................................................................................................14附录（源代码）......................................................................................151绪论11绪论1.1课题背景在多道程序系统中，虽可以借助多个进程的并发执行来改善系统的资源利用率，提高系统吞吐量，但可能发生一种危险——死锁，即多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，将无法再向前推进。如此，寻求一种避免死锁的方法便显得有为重要。死锁的产生一般的原因有两点：竞争资源和进程间推进顺序非法。因此，我们只需在当前的有限资源下，找到一组合法的执行顺序，便能很好的避免死锁，我们称它为安全序列。而银行家算法起源于银行系统的发放贷款，和计算机操作系统的资源分配完全符合，因此可以借鉴该算法的思想，设计出一种有效的算法程序，解决该问题。1.2课题意义（1）运用软件工程的方法指导设计和实现，即是对这学期刚刚学过的软件工程课的复习，又是一次实战演练，从而提高自己的分析问题，解决问题和动手能力；（2）通过整个算法的设计与实现进一步加深了对算法的理解和多道程序下的计算机系统资源分配现状，为以后进一步的学习打下了良好的基础。1.3银行家算法我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定:(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;操作系统课程设计报告2(2)顾客可以分歧贷款,但贷款的总数不能超过最大需求量;(3)当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;(4)当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。1.4死锁死锁是进程死锁的简称，是由Dijkstra于1965年研究银行家算法时首先提出来的。是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那麽死锁涉及到的各个进程都将永远处于封锁状态。它是计算机操作系统乃至并发程序设计中最难处理的问题之一。实际上，死锁问题不仅在计算机系统中存在，在我们