操作系统课程设计报告
题目:银行家算法
院 (系):
专 业:
班 级:
学 生:
学 号:
指导教师:
操作系统课程设计报告
摘 要
Dijkstra 提出的银行家算法,是最具代表性的避免死锁的算法。
本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明,
包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。
首先做了需求分析,解释了什么是银行家算法,并指出它在资源分配中的重
要作用。
然后给出了银行家算法的概要设计,包括算法思路、步骤,以及要用到的主
要数据结构、函数模块及其之间的调用关系等。
在概要设计的基础上,又给出了详细的算法设计,实现概要设计中定义的所
有函数,对每个函数写出核心算法,并画出了流程图。
接着对编码进行了测试与分析(并在最后附上 Java 编写的程序代码)。
最后对整个设计过程进行了总结。
关键词:安全状态;安全序列;银行家算法;安全性算法;安全序列;流程
图。
目录
摘要
.....................................................................................................................1
1
绪论
.................................................................................................................4
1.1 前言 ..........................................................................................................................5
1.2 研究意义...................................................................................................................5
1.3 结构安排...................................................................................................................5
2
需求分析
.......................................................................................................4
2.1 题目描述...................................................................................................................5
2.2 银行家算法...............................................................................................................5
2.3 基本要求...................................................................................................................5
2.4 目的 ..........................................................................................................................5
3
概要设计
.......................................................................................................4
3.1 基本思路...................................................................................................................5
3.2 银行家算法步骤 .......................................................................................................5
3.3 安全型算法步骤 .......................................................................................................5
3.4 数据结构...................................................................................................................5
3.4.1 主要用到的数据结构.............................................................................................................6
3.4.2 程序模块 ................................................................................................................................6
3.4.3 各模块间的调用关系.............................................................................................................6
4
详细设计
.......................................................................................................4
4.1 主要函数的核心代码................................................................................................5
4.1 程序流程图...............................................................................................................5
5
测试
.................................................................................................................4
5.1 测试用例...................................................................................................................5
5.1 测试结果分析和截图................................................................................................5
6
总结
.................................................................................................................4
参考文献
...........................................................................................................4
附录:原程序清单
.......................................................................................4
绪论
1
1 绪论
1.1 前言 :
Dijkstra (1965)提出了一种能够避免死锁的调度算法,称为银行家算法。
它的模型基于一个小城镇的银行家,他向一群客户分别承诺了一定的贷款额
度,每个客户都有一个贷款额度,银行家知道不可能所有客户同时都需要最大贷
款额,所以他只保留一定单位的资金来为客户服务,而不是满足所有客户贷款需
求的最大单位。
这里将客户比作进程,贷款比作设备,银行家比作系统。
客户们各自做自己的生意,在某些时刻需要贷款。在某一时刻,客户已获得
的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为
是安全的,其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。
如果忽然所有的客户都申请,希望得到最大贷款额,而银行家无法满足其中任何
一个的要求,则发生死锁。不安全状态并不一定导致死锁,因为客户未必需要其
最大贷款额度,但银行家不敢抱这种侥幸心理。
银行家算法就是对每一个请求进行检查,检查如果满足它是否会导致不安全
状态。若是,则不满足该请求;否则便满足。
检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最
近的客户。如果可以,则这笔投资认为是能够收回的,然后接着检查下一个距最
大需求最近的客户,如此反复下去。
如果所有投资最终都被收回,则该状态是安全的,最初的请求可以批准。
1.2 研究意义 :
在多道程序系统中,多个进程的并发执行来改善系统的资源利用率,提高系
统的吞吐量,但可能发生一种危险——死锁。所谓死锁(Deadlock),是指多个进
程在运行过程中因争夺资源而造成的一种僵局(DeadlyEmbrace),当进程处于这
种状态时,若无外力作用,他们都无法在向前推进。
银行家算法课程设计报告
2
要预防死锁,有摒弃“请求和保持”条件,摒弃“不剥夺”条件,摒弃“环
路等待”条件等方法。
但是,在预防死锁的几种方法之中,都施加了较强的限制条件;而在避免死
锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方
法中把系统状态分为安全状态和不安全状态,便可避免死锁的发生。
而最具代表性的避免死锁的算法,便是 Dijkstra 的银行家算法。
利用银行家算法,我们可以来检测 CPU 为进程分配资源的情况,决定 CPU 是
否响应某进程的的请求并为其分配资源,从而很好避免了死锁的产生。
1.3 结构安排 :
一、绪论: 介绍了题目背景以及研究意义。
二、需求分析: 介绍了题目描述、银行家算法、以及基本要求和所需达到
的目的。
三、概要设计:介绍了基本的算法思路、步骤,以及数据结构和主要的函数
模块及其调用关系。
四、详细设计:介绍了主要函数及其核心代码,以及程序流程图。
五、测试
六、总结
参考文献
附录:原程序清单
评论1