操作系统课设银行家算法

作者：ZHANGJIAN

仅供个人学习，勿做商业用途

兰州交通大学

操作系统课程设计报告题目：银行家算法

学院：电子与信息过程学院

专业：软件工程

姓名：任海林

学号：201009828

指导老师：张永花

完成时间：2012.12.20

摘要

Dijkstra提出的银行家算法，是最具代表性的避免死锁的算法，该算法由于能用于银行系统现金贷款的发放而得名。银行家算法是在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。在理解和分析了银行家算法的核心思想以及状态的本质涵义的前提下，对算法的实现在总体上进行了设计，包括在对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行测试，最后进行程序的测试，在设计思路上严格按照软件工程的思想执行，确保了设计和实现的可行，可信。

本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明，包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。首先

做了需求分析，解释了什么是银行家算法，并指出它在资源分配中的重要作用。然后给出了银行家算法的概要设计，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等。在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。接着对编码进行了测试与分析，代码实现采用C语言。最后对整个设计过程进行了总结。

关键词：银行家算法；死锁；避免死锁；安全状态；安全性序列；安全性算法。

摘要 (1)

1绪论 (2)

1.1前言 (2)

1.2研究意义 (3)

1.3结构安排 (3)

2需求分析 (4)

2.1题目描述 (4)

2.2银行家算法 (4)

2.3基本要求 (4)

2.4目的 (5)

3概要设计 (6)

3.1基本思路 (6)

3.2银行家算法步骤 (6)

3.3安全型算法步骤 (7)

3.4数据结构 (7)

4详细设计 (8)

4.1主要函数的核心代码 (8)

4.1程序流程图 (9)

5测试 (10)

5.1测试用例 (10)

5.1测试结果分析和截图 (11)

6总结 (12)

参考文献 (14)

附录：原程序清单 (15)

1．1前言：

Dijkstra 提出了一种能够避免死锁的调度算法，称为银行家算法。

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

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

客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。

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

检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。

如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。1．2研究意义：

在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，它们都无法再向前推进。

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

但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。

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

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

1．3结构安排：

一、绪论：介绍了题目背景以及研究意义。

二、需求分析：介绍了题目描述、银行家算法、以及基本要求和所需达到的目的。

三、概要设计：介绍了基本的算法思路、步骤，以及数据结构和主要的函数模块及其调用关系。

四、详细设计：介绍了主要函数及其核心代码，以及程序流程图。

五、测试

六、总结

参考文献

需求分析

2．1题目描述：

银行家算法是一种最具有代表性的避免死锁的算法。

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

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

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

那么，什么是安全序列呢？

如果对每一个进程Pi(0

2．2银行家算法：

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

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

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

2．3基本要求：

（1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。

（2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。

（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况：

A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回。

B . 所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。

C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：

a. 预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回。

b. 与分配后系统进入不安全状态，提示系统不安全并返回。

（4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。2．4目的：

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

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

概要设计

3．1算法思路：

先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。

3．2银行家算法步骤

（1）如果Request[i]＜=Need[i,j],则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

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

（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available[j]=Available[j]-Request[j];

Allocation[i,j]=Allocation[i,j]+Request[j];

Need[i,j]=Need[i,j]-Request[j];

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3．3安全性算法步骤

（1）设置两个向量

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

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

Finish[i]=true。

（2）从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false

②Need[i,j]<=Work[j]

如找到，执行步骤（3）；否则，执行步骤（4）。

（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]=Work[i]+Allocation[i,j];

Finish[i]=true;

转向步骤（2）。

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

3．4数据结构：

（1）可利用资源向量Available

是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。

（2）最大需求矩阵Max

这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m 类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最

大数目为K。

（3）分配矩阵Allocation

这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj 类资源的数目为K。

（4）需求矩阵Need

这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

其中Need[i,j]=Max[i,j]-Allocation[i,j]

详细设计

4．1主要函数的核心代码：

1.void input():用户输入银行家算法初始数据。

2.void output():输出系统当前资源分配情况。

3.void change():当请求资源满足要求时，进行分配，系统资源

发生改变。

4.int check():安全性算法，检查是否存在安全序列。

5.void outputsafe():输出安全序列资源分配表。

4．2程序流程图：

测试

5．1测试结果截图：

1．输入银行家算法初始数据：

图1

2. 显示进程资源分配表：

图2

3. 确认输入数据正确性，如果正确，利用安全算法对资源进行分析，存在安全序列则输出安全序列。

图3

4. 输入请求资源分配的进程，并利用安全性算法检查是否存在安全序列。

图4

5.存在安全序列，则输出安全序列。

图5

6．再次输入请求资源分配的进程，检查是否存在安全序列，不存在。当不再有进程请求资源分配时，退出系统。

图6

总结

在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如最大需求量Max[i][j]、已分配资源数Allocation[i][j]、仍需求资源数Need[i][j]、以及系统可利用的资源数、申请各类资源等数组。

数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。

在本程序代码中，银行家算法用check( )函数来实现。

首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request数组中。

然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资源数，同样，如果大于则报错并返回，如果不大于则调用change( )函数来进行预分配，之后再调用安全型算法check( )检查。最后，无论此次分配是否成功，我们都可以选择继续分配或者退出系统。

安全性检测我们是用check( )函数来实现的。

首先，Finish[i]为布尔型，默认是False，即该进程未完成。而Work[i]即该系统中可以用来工作的资源数——最开始为系统最初可以用的资源数。

然后，我们从第一个进程开始判断该进程未完成且其所需求的资源量不大于该系统中可以用来工作的资源量这个条件是否成立，即Finish[i]=False且Need[i][j]<=Work[i]是否成立。成立的话则将当前在工作的资源量与该进程已分配的资源量相加，存放于当前可用来工作的资源量当中，即Work[j]=Work[i]+Allocation[i,j]，并将Finish[i]的值改为True。否则便将此进程的优先级减一，排在队位，然后开始往后循环。

待所有的进程循环完毕，我们再次判断是否还存在进程的Finish[]=False，如果仍存在，则说明系统没有安全序列，处于不安全状态，不可以进行分配；否则，系统处于安全状态，将预分配变为实际分配，求出安全序列并且将实际分配后的

资源分配情况打印输出。

除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。

这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。

总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。

通过这次的课程设计，我更进一步的了解了银行家算法，并对数据结构的用法理解的更透彻了，在实验的过程中我深刻的体会到了合作的意义，我遇到了一些困难，通过对书上所学的知识反复的思考与理解和与同学之间的相互讨论，最终将银行家算法真正的理解，并且将它用C语言实现。在以后的学习当中我会更加努力的将这一门课程学好。这次课程设计时间上虽说仓促点，但是我依然学到了很多的实用性知识。除了更深的了解这个算法，而且对C语言进行了复习。

参考文献

[1]汤子瀛，哲凤屏，汤小丹.计算机操作系统.西安电子科技大学出版社，2000.

[2]严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006.

[3]谭浩强. C语言程序设计. 北京：清华大学出版社，2005

[4]郑莉，董渊，张瑞丰. C++语言程序设计. 北京：清华大学出版社，2003.

版权申明

本文部分内容，包括文字、图片、以及设计等在网上搜集整理。版权为张俭个人所有

This article includes some parts, including text, pictures, and design. Copyright is Zhang Jian's personal ownership.

用户可将本文的内容或服务用于个人学习、研究或欣赏，以及其他非商业性或非盈利性用途，但同时应遵守著作权法及其他相关法律的规定，不得侵犯本网站及相关权利人的合法权利。除此以外，将本文任何内容或服务用于其他用途时，须征得本人及相关权利人的书面许可，并支付报酬。

Users may use the contents or services of this article for personal study, research or appreciation, and other

non-commercial or non-profit purposes, but at the same time, they shall abide by the provisions of copyright law and other relevant laws, and shall not infringe upon the legitimate rights of this website and its relevant obligees. In addition, when any content or service of this article is used for other purposes, written permission and remuneration shall be obtained from the person concerned and the relevant obligee.

转载或引用本文内容必须是以新闻性或资料性公共免费信息为

使用目的的合理、善意引用，不得对本文内容原意进行曲解、修改，并自负版权等法律责任。

Reproduction or quotation of the content of this article must be reasonable and good-faith citation for the use of news or informative public free information. It shall not misinterpret or modify the original intention of the content of this article, and shall bear legal liability such as copyright.