银行家算法

课程设计说明书（操作系统）题目：银行家算法院系：计算机科学与工程学院专业班级：学号：学生姓名：指导教师：2011年12月25日目录安徽理工大学课程设计（论文）任务书计算机科学与工程学院网络与信息安全系学号学生姓名专业（班级）设计题目银行家算法设计技术参数当进程请求资源时，为了确保系统的安全，需要检验当资源适分配给进程时保证至少存在一个安全序列，通过判断请求资源数是否小于其需要的，然后比较系统可获得的资源数，最后进行安全性算法扫描，验证系统是否达到安全许可即可。设计要求1.银行家问题是一种算法问题，本实验要求用高级语言编写和调试一个简单的银行家问题程序程序。2.从课程设计的观点出发，通过设计工作的各个环节，达到教学要求。3.在分组后，每个学生要完成其相应的工作，在同组中间的文档不得相同，在完成后设计后由老师进行检查。4.在完成电子设计后，要求写一份详细的设计报告。工作量编写代码不少于200行；程设计说明书不少于15页。工作计划1.首先认真研究老师所给的题目，了解题目要求做什么。2.查阅资料，解决难题。3.编写源程序并调试之。4.写课程设计说明书参考资料[1]张尧学，史美林．计算机操作系统教程．清华大学出版社,第2版[2]王素华.操作系统教程．人民邮电出版社[3]屠立德，屠祁.操作系统基础．清华大学出版社[4]汤子瀛.计算机操作系统．西安电子科技大学出版社指导教师签字教研室主任签字2011年12月25日操作系统课程设计报告摘要Dijkstra提出的银行家算法，是最具代表性的避免死锁的算法。本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明，包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。首先做了需求分析，解释了什么是银行家算法，并指出它在资源分配中的重要作用。然后给出了银行家算法的概要设计，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等。在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。接着对编码进行了测试与分析（并在最后附上c#编写的程序代码）。最后对整个设计过程进行了总结。关键词：安全状态；安全序列；银行家算法；安全性算法；安全序列；流程图。银行家算法课程设计报告1目录1绪论..................................................................................................................21．1前言....................................................................................................................21．2研究意义.............................................................................................................21．3结构安排.............................................................................................................32需求分析..........................................................................................................42．1题目描述.............................................................................................................42．2银行家算法.........................................................................................................42．3基本要求.............................................................................................................42．4目的....................................................................................................................53概要设计..........................................................................................................63．1算法思路.............................................................................................................63．2银行家算法步骤..................................................................................................63．3安全性算法步骤..................................................................................................63．4数据结构.............................................................................................................73．4.1主要用到的数据结构.......................................................................................................73．4.2程序模块...........................................................................................................................73．4.3各模块间的调用关系.......................................................................................................74详细设计..........................................................................................................84．1主要函数的核心代码...........................................................................................84．2程序流程图.........................................................................................................85测试.................................................................................................................115．1测试用例...........................................................................................................115．2测试结果截图....................................................................................................116总结.................................................................................................................15参考文献.............................................................................................................17附录：源程序清单（核心代码）........................................................................18银行家算法课程设计报告21绪论1．1前言Dijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。1．2研究意义在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。银行家算法课程设计报告3而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。1．3结构安排一、绪论：介绍了题目背景以及研究意义。二、需求分析：介绍了题目描述、银行家算法、以及基本要求和所需达到的目的。三、概要设计：介绍了基本的算法思路、步骤，以及数据结构和主要的函数模块及其调用关