操作系统课程设计报告题目：银行家算法安全性算法院（系）：计算机科学与工程专业：软件工程班级：130608班学生：姚骏川学号：*********指导教师：***2015年12月28目录摘要 .................................................................................................................错误!未定义书签。

1 绪论 (1)1.1前言 (1)1.2研究意义 (1)2 需求分析 (3)2.1题目描述 (3)2.2银行家算法 (3)2.3基本要求 (3)2.4目的 (3)3 概要设计 (5)3.1算法思路： (5)3.2银行家算法步骤 (5)3.3安全性算法步骤 (5)3．4数据结构： (6)4 详细设计 (8)4.1主要函数的核心代码： (8)4.2系统主要过程流程图 (8)4.3银行家算法流程图 (9)5 测试与分析 (10)5.1测试数据 (10)5.2银行家算法的演示 (10)5.3分配资源由于大于可利用资源则失败。

(11)5.4 增加一个作业得到不安全序列。

(11)5.5分配资源由于大于最大资源则失败。

(12)附录源程序清单 (15)1 绪论1.1前言Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。

它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。

这里将客户比作进程，贷款比作设备，银行家比作系统。

客户们各自做自己的生意，在某些时刻需要贷款。

在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。

一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。

如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。

不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。

银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。

若是，则不满足该请求；否则便满足。

检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。

如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。

如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。

1.2研究意义在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。

所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。

要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环1路等待”条件等方法。

但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。

在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。

而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。

利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。

2 需求分析2.1题目描述银行家算法是一种最具有代表性的避免死锁的算法。

要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。

所谓安全状态，是指系统能按照某种进程顺序{P1,P2,…，Pn}（称{P1,P2,…，Pn }序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。

安全状态一定没有死锁发生。

如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

那么，什么是安全序列呢？如果对每一个进程Pi(1<i<n)，它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(j<n)所占有的资源量之和，则称此进程序列{P1,P2,…，Pn}是安全的，称作安全序列。

2.2银行家算法我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。

操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。

当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。

若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。

2.3基本要求（1）设计用来保存：可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation 、需求矩阵Need。

（2）编写银行家算法，安全性检测算法。

要求在不安全时输出错误信息。

（3）编写输出函数，能对进程申请后的系统状态进行输出。

2.4目的根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序3要求实现的功能以及限制条件。

明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。

3 概要设计3.1算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。

若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。

若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。

3.2银行家算法步骤（1）如果Requesti＜=Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。

（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：Available=Available-Request[i];Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

3.3安全性算法步骤（1）设置两个向量①工作向量Work。

它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;5②布尔向量Finish。

它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。

（2）从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false②Need< =Work;如找到，执行步骤（3）；否则，执行步骤（4）。

（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work=Work+Allocation;Finish[i]=true; 转向步骤（2）。

（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。

3．4数据结构：3.4.1主要用到的数据结构：(1)最大需求矩阵Max[][](2)已分配矩阵Allocation[][](3)仍需求矩阵Need[][]=Max[][]-Allocation[][](4)可利用资源向量Available[](5)申请各类资源向量Request[](6)工作向量 work[] , Finish[]（7）存放安全序列 temp[](8)存放系统可提供资源 work[](9)资源的名字 name[]3.4.2程序模块：int main()//主函数void showdata()//显示资源矩阵int changdata(int i)//进行资源分配int safe()//安全性算法void share()//利用银行家算法对申请资源对进行判定void addresources(){//添加资源void changeresources(){//修改资源函数void addprocess(){//添加作业3.4.3各模块间的调用关系：主函数void main()要调用： showdata()，safe()，addresources()，addprocess(),changeresources(),changdata(int i)安全性检测函数safe()银行家算法函数share()要调用 changdata(int i), showdata(),safe()74 详细设计4.1主要函数的核心代码：1.进行初始化输入的函数2.输出的函数3.利用安全性算法进行检测的函数4.进行资源分配的函数5.利用银行家算法进行判定的函数4.2系统主要过程流程图图4.1 主要流程图4.3银行家算法流程图图4.2 银行家流程图5 测试与分析5.1测试数据本次测试一共5个进程，分别为p0、p1、p2、p3、p4.，资源分配情况如下表：资源情况进程MaxA B CAllocationA B CNeedA B CAvailableA B CP0 7 5 3 0 1 0 7 4 3 3 3 2P1 3 2 2 2 0 0 1 2 2P2 0 9 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1结果截图：图5.15.2银行家算法的演示进行资源的分配，为进程1分配了（1，0，2），进行安全算法得到如下的结果。

图5.25.3分配资源由于大于可利用资源则失败。

图5.35.4 增加一个作业得到不安全序列。

图5.45.5分配资源由于大于最大资源则失败。

图5.56 总结操作系统的基本特征是并发与共享。

系统允许多个进程并发执行，并且共享系统的软、硬件资源。

为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。

而我本次课程设计就是得用银行家算法来避免“死锁”。

银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。

此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。

在程序当中，我们也得强调一下对输入的合法性的判断。