网络操作系统课程设计-银行家算法.docVIP

第一章 需求分析 1.1编写目的 在计算机系统中，涉及软件，硬件资源都可能发生死锁。例如：系统中只有一台CD-ROM驱动器和一台打印机，某一个进程占有了CD-ROM驱动器，又申请打印机；另一进程占有了打印机，还申请CD-ROM。结果，两个进程都被阻塞，永远也不能自行解除。银行家算法的编写目的就是解决死锁问题，是每一个程序运行不会收到过多的干涉，使程序运行运行更流畅。解决实际性的问题。 1.2背景 Dijkstra的银行家算法是最有代表性的避免死锁的算法，该算法由于能用于银行系统现金贷款的发放而得名。银行家算法是在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。 该论文在理解和分析了银行家算法的核心思想以及状态的本质涵义的前提下，对算法的实现在总体上进行了设计，包括在对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行测试，最后进行程序的测试，在设计思路上严格按照软件工程的思想执行，确保了设计和实现的可行，可信。代码实现采用C++语言。在多道程序系统中，虽可以借助多个进程的并发执行来改善系统的资源利用率，提高系统吞吐量，但可能发生一种危险——死锁，即多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，将无法再向前推进。如此，寻求一种避免死锁的方法便显得有为重要。死锁的产生一般的原因有两点：竞争资源和进程间推进顺序非法。因此，我们只需在当前的有限资源下，找到一组合法的执行顺序，便能很好的避免死锁，我们称它为安全序列。而银行家算法起源于银行系统的发放贷款，和计算机操作系统的资源分配完全符合，因此可以借鉴该算法的思想，设计出一种有效的算法程序，解决该问题。 1.3 任务概述 运用银行家算法，避免死锁的发生。在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。 问题的关键在于安全性算法，即找安全性序列。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2)顾客可以分歧贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金。 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 1.4开发意图 (1)从键盘输入当前系统的资源信息，包括当前可用资源，每个进程对各类资源的最大需求量，每个进程当前已分配的各个资源量和每个进程尚需要的各个资源量，输出结果显示在DOS界面上； (2)输入进程请求，按照设计好的安全性算法进行检查，得到结果并输出整个执行过程的相关信息和最终结果（主要包括资源分配表和安全序列）； (3)要求 图1-1功能模块图 第二章 总体设计 2.1 模块的划分 由于该算法规模较小，所以选用结构化的设计方法，将该系统划为五块，分别是： （1）主模块，处在整个系统的最高层，负责组织调用其他模块。 （2）初始化模块，负责从键盘读入系统资源和进程状态，并将系统初识资源分配状态打印。 （3）试分配模块，负责处理进程请求，和相应的数据结构的修改，已经特殊情况的处理。 （4）安全性检查，负责试分配后的安全性检查，以及系统不安全时的资源恢复。 2.2 模块调用关系 各模块之间的调用如下图2-1所示： 图2-1 模块调用图 2.3 各模块之间的接口 Flag1：试分配模块Attempt_Allocation与安全性检查Safety_Algorithm之间接口Attempt_Allocation通过检查 flag的真假了判断是否执行。 pro:一个地址， Safety_Algorithm返回给主模块main的信息，不为NULL时表示试分配成功，否则系统转入相应异常处理。 Flag2：Safety_Algorithm与主模块之间的接口，为真则调用打印函数，输出最终结果，否则调用恢复函数，恢复之前系统状，程序流程图如图2-2所示