没有合适的资源?快使用搜索试试~ 我知道了~
计算机相关专业毕业论文“银行家算法的改进及其C语言程序实现”
4星 · 超过85%的资源 需积分: 9 16 下载量 58 浏览量
2011-06-26
11:11:10
上传
评论 1
收藏 191KB DOC 举报
温馨提示
试读
16页
本文详细书写了对银行家算法的改进,以及用c语言实现改进后的算法,包括源代码也包含在内。
资源推荐
资源详情
资源评论
目 录
摘要………………………………………………………………………………………… 1
ABSTRACT ……………………………………………………………………………… 1
第一章 绪 论 ………………………………………………………………………… 2
1.1 本课题研究的背景………………………………………………………………… 2
第二章 算 法…………………………………………………………………………… 3
2.1 算法和算法复杂度分析 ………………………………………………………… 3
2.1.1 什么是算法 …………………………………………………………………… 3
2.1.2 算法的时间复杂度…………………………………………………………… 4
2.1.3 提高算法效率的方法………………………………………………………… 4
第三章 新银行家算法分析 ……………………………………………………… 4
3.1 银行家算法简介 …………………………………………………………………… 4
3.1.1 算法简介 ……………………………………………………………………… 4
3.1.2 银行家算法中的数据结构 ………………………………………………… 5
3.2 银行家算法分析 …………………………………………………………………… 6
3.2.1 算法实现步骤 ………………………………………………………………… 6
3.2.2 算法安全性检查 ……………………………………………………………… 6
3.3 银行家算法实例 …………………………………………………………………… 7
第四章 c 语言实现改进后的算法 ……………………………………………… 9
4.1 程序编写的数据结构 ……………………………………………………………… 9
4.1.1 定义数据结构 ………………………………………………………………… 9
4.1.2 算法功能介绍……………………………………………………………………10
4.2 算法用 c 语言实现 ………………………………………………………………… 10
4.2.1 程序实现源代码 ……………………………………………………………… 10
4.2.2 程序测试结果 ………………………………………………………………… 15
结 论………………………………………………………………………………………… 17
参考文献…………………………………………………………………………………… 17
致 谢………………………………………………………………………………………… 18
银行家算法的改进及其 C 语言程序实现
×××
×××学院×××专业×××级 指导教师:×××
摘 要:银行家算法是一种最有代表性的避免死锁的算法。本文对传统银行家算
法进行了分析并得出结论:传统银行家算法要求逐条输入所需进程数,但由于
计算机执行速度较快,在输入进程数的过程中,如果有其他进程申请资源,计
算机可分配的资源可能会发生一定的改变,使得原本安全的系统变得不安全,
本文就这一问题对银行家算法进行改进,在系统把需求的资源分配给进程并修
改数据结构值以前,对需求进程与可利用资源重新进行比较,如果系统将资源
分配给该进程后系统能够安全运行,试探性分配资源给该进程,再依次判断其
他进程,如果所有进程都能安全运行,则可以分配资源给该进程;再通过同样
的方法将资源分配给其他进程,最终得出系统运行的一个安全系列,这样就确
保系统在安全条件下进行资源分配。并用C语言程序实现了改进后的算法;应
用改进后的算法可以更有效的判断出进程管理或资源分配系统是否处于安全状
态,避免死锁问题的发生。
关键词:银行家算法;死锁;安全状态
The Bankers algorithm realized the improvements and C language
program
×××
××××××××××××××××××
Grade: ××× Istructor: ×××
Abstract: Banker's algorithm is one of the most representative algorithm to avoid
deadlock. This paper analyzes the traditional banker's algorithm and concluded that:
the traditional banker's algorithm requires the number of processes required to enter
one by one, but due to the implementation of faster computers, the process of the
input process number, if there are other processes for resources, computer resources
can be allocated certain changes may occur, making an already safe system to become
unsafe, the paper on the issue of banker's algorithm is improved demand in the system
to allocate resources to process and modify the value before the data structure of
1
needs to re-process and compare the available resources, if the system resources
allocated to the process to the safe operation of the system after a tentative allocation
of resources to the process, then in turn determine the other processes, can be safe if
all the processes running, you can allocate resources to the process; and then through
the same method to allocate resources to other processes, and ultimately obtained a
security system running series, so ensure that the system of resource allocation under
conditions of safety. And with the C language program to achieve the improved
algorithm; application improved algorithm can determine more effective process
management or resource allocation system is in safe condition, to avoid deadlock
problems.
Key words:Bankers algorithm;the dead lock;safety state
第一章 绪论
1.1 本课题研究的背景
随着现代科学技术的飞速发展,人们对计算机的依赖性越来越强,对计算机
的性能要求也越来越高,因此人们在使用计算机时希望能够同时完成多项工作,
进而提高工作效率。在计算机系统中,安全问题一直为用户所关注。资源分
配如果可以保证所有进程在有效时间内得到所要资源则称其为安全。当两个
或两个以上的并发进程在执行过程中,彼此互相等待对方所拥有的资源,且这
些并发进程在得到对方的资源之前不会释放自己所拥有的资源,从而造成大
家都想得到资源而又都得不到资源,各并发进程不能继续向前推进的状态,
这就产生了一种特殊现象死锁。解决系统死锁有很多方法,当检测到系统中已
发生死锁时,须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂
起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进
程,使之转为就绪状态,以继续运行。死锁的检测和解除措施,有可能使系
统获得较好的资源利用率和吞吐量,但在实现上难度也最大。这时就需要用相
应的算法进行解决。银行家算法是一种最有代表性的避免死锁的算法。
银行家算法是针对计算机系统中的安全问题进行设计的,它提出的思想
是:把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资
金,进程向操作系统申请分配资源相当于用户向银行家贷款。操作系统按照
银行家的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资
源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的
申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先检
查该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源
的最大需求量。若超过则拒绝分配资源,若没有超过则测试系统现存的资源
能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,
2
否则也要推迟分配。根据该思想可以判断新申请的进程是否安全,避免死锁
问题的发生。
第二章 算法
2.1 算法和算法复杂度分析
2.1.1 什么是算法
算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一
条指令表示一个或多个操作;算法是一系列解决问题的清晰指令,也就是说,
能够对一定规范的输入,在有限时间内获得所要求的输出。算法常常含有重复
的步骤和一些比较或逻辑判断。如果一个算法有缺陷,或不适合于某个问题,
执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效
率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点
说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程
序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。
一个算法应该具有以下五个重要的特征:
1、有穷性: 一个算法必须保证执行有限步之后结束;
2、确切性: 算法的每一步骤必须有确切的定义;
3、输入:一个算法有 0 个或多个输入,以刻画运算对象的初始情况,所
谓 0 个输入是指算法本身定出了初始条件;
4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的;
5、可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运
算后即可完成。
2.1.2 算法的时间复杂度
算法的时间复杂度表示执行完一个算法所用的时间,称做算法的渐近时间复
杂度(asymptotic time complexity),简称时间复杂度。 常见的时间复杂
度有: O(1)常数阶;O(logn)对数阶;O(n)线性阶;O(n^2)平方
阶
若算法 A 的规模为 n,时间复杂度用
表示,公式如下(2.1)。
(2.1)
由以上定义可知,时间复杂度就是算法 A 对大小为 n 的所有实例运行所需时
间的最大值,显然时间复杂度是 n 的函数。时间复杂度的大小直接关系算法的
优劣。要提高算法的效率就有必要对算法的时间复杂度进行优化。
3
剩余15页未读,继续阅读
资源评论
- yanxuan232012-04-24很好,就是不能由用户设定初始系统的资源总数。
- l0602037612012-11-26论文的内容很详细,很实用,学习了很多
ladder_of_love
- 粉丝: 63
- 资源: 42
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- kernel-ml-6.8.8-1.el7.elrepo.x86-64.rpm
- Labview基本框架之状态机
- HM2309B-VB一款P-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- Git安全实践:保护你的代码仓库个人学习笔记.md
- 自动驾驶定位系列教程九:后端优化.pdf
- 三国志5威力加强版-windows
- HM2309A-VB一款P-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- HM2306-VB一款N-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- Git进阶技巧:提升团队协作效率个人学习笔记.md
- 自动驾驶定位系列教程八:建图系统结构优化.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功