操作系统课程设计编程序模拟银行家算法

课程设计报告书

课程名称：

操作系统原理

题

目：

编程序模拟银行家算法

系

名：

信息工程系

专业班级：

软件

姓

名：

学

号：

指导教师:

2013年

X

月

X

日

学院信息工程系

课

程

设

计

任

务

书

课程名称：

操作系统原理课程设计

指导教师：

班级名称：

软件

开课系、教研室：

软件与信息安全

一、课程设计目的与任务

操作系统课程设计是《操作系统原理》课程的后续实践课程，旨在通过一周的实践训练，加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提高学生进行分析问题和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。

学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。

二、课程设计的内容与基本要求

1、课程设计题目

编程序模拟银行家算法

2、课程设计内容

本课程设计要求在Linux操作系统，GCC编译环境下开发。

银行家算法是避免死锁的一种重要方法，本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。

3、设计报告撰写格式要求：

1设计题目与要求

设计思想

3系统结构

数据结构的说明和模块的算法流程图

使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明

运行结果和结果分析（其中包括实验的检查结果、程序的运行情况）

自我评价与总结

附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释；

三、课程设计步骤及时间进度和场地安排

本课程设计将安排在第15周,教育技术中心。具体安排如下：

第一天

下发任务书，学生查阅资料

第二天

系统设计和原型开发

第三，四天

系统功能实现

第五天

系统调试

测试

打包和验收

四、课程设计考核及评分标准

课程设计考核将综合考虑学生考勤和参与度，系统设计方案正确性，系统设计和开发效果以及课程设计报告书的质量。具体评分标准如下：

设置六个评分点

（1）设计方案正确，具有可行性、创新性；

25分

（2）系统开发效果较好；

25分

（3）态度认真、刻苦钻研、遵守纪律；

10分

（4）设计报告规范、课程设计报告质量高、参考文献充分

20分

（5）课程设计答辩概念清晰，内容正确

10分

（6）课程设计期间的课堂考勤、答疑与统筹考虑。

10分

按上述六项分别记分后求和，总分按五级记分法记载最后成绩。

优秀（100～90分），良好（80～89分），中等（70～79分），及格（60～69分），不及格（0～59分）

1.题目要求与实验目的1.1

实验目的：

1.1.1进一步理解利用银行家算法避免死锁的问题；

1.1.2在了解和掌握银行家算法。

1.1.3理解和掌握安全序列、安全性算法

1.2

设计题目:

编程序模拟银行家算法

1.3

要求

：

本实验要求用用

c/c语言在Linux

操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

1.4

实验内容

：

1.4.1编写安全性算法；

1.4.2编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。

设计思想

将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。

用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。

3.需求分析

3.1问题描述：利用银行家算法模拟计算机系统分配资源的过程。

3.2要求：

3.2.11、以课本例题中数据为例，模拟资源分配过程。

3.2.2、系统中资源种类，各类资源数目，进程申请资源数目可任意输入，模拟资源分配过程。

4.系统结构

初始化函数init（）开始

输入进程的数目m

输入资源种类n

输入每个进程最多所需的各种资源数

输入每个进程分配的资源数

输入各个资源现有数目

初始化函数init（）结束

输入提示：

输入有误重新输入

图

5.数据结构的说明和模块的算法流程图

5.1

数据结构：

①可利用资源向量

Available

是个含有

m

个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果

AvailablejK，则表示系统中现有

Rj

类资源

K

个。

②最大需求矩阵

Max

这是一个

n×m的矩阵，它定义了系统中

n

个进程中的每一个进程对

m

类资源的最大需求。如果

MaxijK，则表示进程

i

需要

Rj

类资源的最大数目为

K。

③分配矩阵

Allocation

这也是一个

n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果

AllocationijK，则表示进程

i

当前已分得

Rj

类资源的数目为

K。

④需求矩阵

Need。

这也是一个

n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果NeedijK，则表示进程

i

还需要

Rj

类资源

K

个，才可以完成其任务。

5．2

程序流程图：

①、系统主要过程流程

预分配

安全？

实际分配打印输出

退出系统

Request[i]>Available[i]?

Request[i]>need[i]?

提出申请

打印输出此时刻资源分配情况

进入系统

输入：

1.继续分配

2.退出

进入初始化

②、安全性算法流程图

调用safty()函数

Work[]=Available[],Finish[]=False

Need[]<=work[]且Finsh[]=Falsse?

Work[]=work[]+Alloccation[],Finish[]=Ture

所有进程的Finsh[]=Ture?

实际分配输出安全序列并打印出

输出提示系统不安全

调用结束

用户手册

6.1

首先在终端中使用

vi

编辑器建立

c的源文件

6.2

然后使用

gcc

编辑器编译生成可执行文件

6.3

使用命令./当前名字，来执行

7.运行结果和结果分析

7．1

运行结果：

申请成功如图

2，申请失败如图

3：

图

申请金额在需求范围之内同意

图

申请金额在需求范围之外拒绝

7.2

结果分析

首先是自己定义

个用户所需的金额数，银行可以给用户贷款的总金额数是100，用户

Id

号的范围是在0

到

4，超过

之后的id

请求贷款，会显示拒绝提示信息，每个客户的贷款数量必须是在之前定义的范围之内，如果超出，也会出现错误提示，只有在规定的用户

id

和在客户所要求金额的范围之内请求，才会给予贷款，并且输出安全序列号。

8.自我评价与总结

一周的课程设计结束了。在这一周里，我收获很多，以前都是在自己的教室由我们自己的老师进行讲课，这次学校没有这样做，而是请的校外的老师给我们做课程设计，让我们体会一下真正的公司是怎样做业务的。在这一周里我做一个模拟银行家算法。我觉得在着手设计前设计的思路是很重要的。只有思路清晰才能进行下一阶段的设计。这样才能完成整个程序的设计，完成整个文报告的书写。

课程设计这几天学到的东西还真不少。以前不清楚的现在都暴露出来了。以前认为学了没用的东西现在也用到了。这次的课程设计使我进一步了解了调度与死锁的问题。以及有关资源申请的问题、避免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全状态。

经过本周的课程设计，我对操作系统的掌握又进了一步，收获了很多知识。，终于我了由于对

c

语言不够熟练，在试验过程中，进行了反复的修改和调试，解银行家算法的基本原理，并且在此次的课程设计中我又复习了一下

c

语言，加深了对它的了解，而且在课程设计的过程中我们同样学会了如何简单的操作与使用

Linux

操作系统，学习到了许多

Linux

操作系统中常用的一些密令。

这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，先用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量，才和系统所能给的资源相比较.让进程形成一个安全队列看系统是否安全.再利用安全性算法检查此时系统是否安全。

操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。而我本次课程设计就是得用银行家算法来避免“死锁”。银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。

通过这次实验，我体会到银行家算法的重要性，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我来学习借鉴。

附录：

主要源程序

参考文献

[1]

张尧学主编．计算机操作系统教程（第三版）．北京:清华大学出版社，2006

[2]

张尧学编．计算机操作系统教程（第三版）习题解答与实验指导．北京:清华大学出版社，2006

[3]

汤子瀛主编．计算机操作系统（第三版）．西安:西安电子科技大学出版社，2001

[4]

张坤等编．操作系统实验教程．北京:清华大学出版社，2008

[5]

张丽芬等编．操作系统实验教程．北京:清华大学出版社，2006

[6]

屠祁等编.操作系统基础（第三版）．北京:清华大学出版社，2000

[7]

冯耀霖等编.操作系统.西安:西安电子科技大学出版社，2001

[8]

左万历．计算机操作系统教程（第二版）．北京：高等教育出版社，2004

[9]谭浩强.《C语言程序设计》.北京：清华大学出版社2003

[8]

庞丽华.《操作系统原理》（第四版）.北京.华中科技大学出版社

2002

设计过程中质疑（或答辩）记载：

1.银行家算法的主要思想是什么？

答：一个进程进入系统时分配资源之前,判断系统是否是安全的，即看它所请求的资源是否大于它的最大需求量，若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待。

2.银行家算法的主要问题是什么？

答：要求每个进程必须事先知道资源的最大需求量，而且，在系统运行过程中，考查每个进程对各类资源的申请需花费较多的时间。

3.在银行家算法中各个资源存在什么关系？

答：该进程所需要的资源数NEED[m][n]=MAX[m][n](该进程所需要的最多的资源数)-----ALLOCATION[m][n](该进程所占有的资源数)

指导教师评语：

签名：

****年**月**日