银行家算法课程设计

操作系统课程设计报告题目：银行家算法安全性算法院（系）：计算机科学与工程专业：软件工程班级：130608班学生：姚骏川学号：130608118指导教师：姜虹2015年12月28目录摘要.................................................................................................................错误!未定义书签。1绪论...............................................................................................................................................11.1前言.....................................................................................................................................11.2研究意义.............................................................................................................................12需求分析.......................................................................................................................................32.1题目描述............................................................................................................................32.2银行家算法........................................................................................................................32.3基本要求............................................................................................................................32.4目的....................................................................................................................................33概要设计.......................................................................................................................................53.1算法思路：........................................................................................................................53.2银行家算法步骤................................................................................................................53.3安全性算法步骤................................................................................................................53．4数据结构：......................................................................................................................64详细设计.......................................................................................................................................84.1主要函数的核心代码：....................................................................................................84.2系统主要过程流程图........................................................................................................84.3银行家算法流程图............................................................................................................95测试与分析.................................................................................................................................105.1测试数据...........................................................................................................................105.2银行家算法的演示...........................................................................................................105.3分配资源由于大于可利用资源则失败。......................................................................115.4增加一个作业得到不安全序列。.................................................................................115.5分配资源由于大于最大资源则失败。..........................................................................12附录源程序清单...........................................................................................................................15绪论11绪论1.1前言Dijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。1.2研究意义在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环西安工业大学北方信息工程学院路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。需求分析32需求分析2.1题目描述银行家算法是一种最具有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。所谓安全状态，是指系统能按照某种进程顺序{P1,P2,…，Pn}（称{P1,P2,…，Pn}序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。那么，什么是安全序列呢？如果对每一个进程Pi(1in)，它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(jn)所占有的资源量之和，则称此进程序列{P1,P2,…，Pn}是安全的，称作安全序列。2.2银行家算法我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。2.3基本要求（1）设计用来保存：可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need。（2）编写银行家算法，安全性检测算法。要求在不安全时输出错误信息。（3）编写输出函数，能对进程申请后的系统状态进行输出。2.4目的根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序西安工业大学北方信息工程学院要求实现的功能以及限制条件。明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做