编程模拟银行家算法实验报告

武汉理工大学华夏学院 课程设计报告书

课程名称：

操作系统原理

题 目： 编程序模拟银行家算法

系 名： 信息工程系

专业班级： 计应2091

姓 名： 王汝平

学 号： 10225509118 指导教师: 苏永红

2011 年 7 月 6 日

课程设计任务书

1

学生姓名： 王汝平 专业班级： 计应2091 指导教师： 苏永红 工作单位： 信息工程系 设计题目：编程序模拟银行家算法 初始条件：

Linux操作系统，GCC编译环境

要求完成的主要任务：

主要任务：

银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

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

设计报告撰写格式要求：

1设计题目与要求 2 设计思想

3系统结构 4 数据结构的说明和模块的算法流程图

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

6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况） 7 自我评价与总结 8 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释；

时间安排

7月 4日 布置课程设计任务；分配题目后，查阅资料、 准备程序； 7月 5 ～7月7 日上机调试程序、书写课程设计报告；

7月8 日 提交课程设计报告及相关文档。

指 导 教 师 签 名： 2011年 7月 2日

系 主 任 签 名： 2011年 7月 3日

2

目录

1.需求分析 ···················································4

1.1课程设计题目

·······································4

1.2课程设计目的··········································4

1.3设计任务·················································4 1.4设计思想·················································4

············································5

2.设计思想和过程

2.1 概要设计·················································5 2.2程序源代码··············································7

3.调试及运行结果··············································13

4.实验心得体会·················································15

5.参考文献························································15

3

1.需求分析

1.1课程设计题目：编程序模拟银行家算法 1.2设计目的

1.2.1银行家算法是避免死锁的一种重要方法，本实验要求用级 语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

1.2.2提高学生的程序设计能力、 提高算法设计质量与程序设计素质 ；

1.3设计任务

银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 1.4思想

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

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

4

2.设计思路和过程

2.1 概要设计

2.1.1 程序流程图

2.1.2设计原理及方法

银行家算法的设计思想是：当用户申请一组资源时，系统必须做出判断；如果把这些资源分出去，系统是否还处于安全装他。若是，就可以分出这些资源；否则，该申请暂不能满足。

实现银行家算法要有若干数据结构，它们用来表示资源分配系统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需要以下数据结构：

5

1. Available是一个长度为m的向量，它表示每类资源可用的数量。Available [j]=k，表示rj类资源可用的数量为k。

2.Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max [i，j]=k，表示进程pi至多可以申请k个rj类资源单位。

3. Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation [i，j]=k，表示进程pi当前分到k个rj类资源。

4. Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i，j]=k，表示进程pi尚需k个rj类资源才能完成其任务。显然Need[i，j]= Max [i，j]- Allocation [i，j]。

这些数据结构的大小和数值随时间推移而改变。 系统所执行的安全性算法描述如下：

1.设置2个向量：工作向量Work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work = Available。

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

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

Finish[i]=flase；Need[i,j]≤Work[j]；若找到，则执行步骤3，否则，执行步骤4。

3.当进程pi获得资源后，可顺利执行，直至完成，并释放分配给它的资源。

6

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

2.2 程序源代码

#include #include #include

using namespace std; #define False 0 #define True 1

int Max[100][100]={0};//各进程所需各类资源的最大需求 int Avaliable[100]={0};//系统可用资源 char name[100]={0};//资源的名称

int Allocation[100][100]={0};//系统已分配资源 int Need[100][100]={0};//还需要资源 int Request[100]={0};//请求资源向量 int temp[100]={0};//存放安全序列

int Work[100]={0};//存放系统可提供资源 int M=100;//作业的最大数为100 int N=100;//资源的最大数为100 void showdata()//显示资源矩阵 {

int i,j;

cout<<\"系统目前可用的资源[Avaliable]:\"<for (j=0;jcout<cout<<\" Max Allocation Need\"<cout<for(i=0;icout<<\" \"<7

cout<cout<cout<int changdata(int i)//进行资源分配 { int j;

for (j=0;jAvaliable[j]=Avaliable[j]-Request[j];

Allocation[i][j]=Allocation[i][j]+Request[j]; Need[i][j]=Need[i][j]-Request[j]; }

return 1; }

int safe()//安全性算法 {

int i,k=0,m,apply,Finish[100]={0}; int j;

int flag=0;

Work[0]=Avaliable[0]; Work[1]=Avaliable[1]; Work[2]=Avaliable[2]; for(i=0;ifor(j=0;jif (Finish[i]==False&&Need[i][j]<=Work[j]){ apply++;

if(apply==N){ for(m=0;mWork[m]=Work[m]+Allocation[i][m];//变分配数 Finish[i]=True; temp[k]=i; i=-1; k++; flag++; } }

8

} }

for(i=0;iif(Finish[i]==False){

cout<<\"系统不安全\"<cout<<\"系统是安全的!\"<for(i=0;i\"; }

cout<void share()//利用银行家算法对申请资源对进行判定 {

char ch; int i=0,j=0; ch='y';

cout<<\"请输入要求分配的资源进程号(0-\"<>i;//输入须申请的资源号

cout<<\"请输入进程 \"<cout<cin>>Request[j];//输入需要申请的资源 }

for (j=0;jif(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出错 {

cout<<\"进程 \"<break; }

else {

if(Request[j]>Avaliable[j])//判断申请是否大于当前资源，若大于则 { //出错

cout<<\"进程\"<9

break; } } }

if(ch=='y') {

changdata(i);//根据进程需求量变换资源 showdata();//根据进程需求量显示变换后的资源 safe();//根据进程需求量进行银行家算法判断 } }

void addresources(){//添加资源 int n,flag;

cout<<\"请输入需要添加资源种类的数量:\"; cin>>n; flag=N; N=N+n;

for(int i=0;i>name[flag]; cout<<\"数量:\";

cin>>Avaliable[flag++]; }

showdata(); safe(); }

void changeresources(){//修改资源函数

cout<<\"系统目前可用的资源[Avaliable]:\"<cout<>Avaliable[0]>>Avaliable[1]>>Avaliable[2]; cout<<\"经修改后的系统可用资源为\"<cout<void delresources(){//删除资源 char ming; int i,flag=1;

cout<<\"请输入需要删除的资源名称：\"; do{

cin>>ming; for(i=0;i10

if(ming==name[i]){ flag=0; break; } if(i==N)

cout<<\"该资源名称不存在，请重新输入：\"; }

while(flag);

for(int j=i;jname[j]=name[j+1];

Avaliable[j]=Avaliable[j+1];

} N=N-1;

showdata(); safe(); }

void addprocess(){//添加作业 int flag=M; M=M+1;

cout<<\"请输入该作业的最大需求量[Max]\"<>Max[flag][i];

Need[flag][i]=Max[flag][i]-Allocation[flag][i]; }

showdata(); safe(); }

int main()//主函数 {

int i,j,number,choice,m,n,flag; char ming;

cout<<\"*****************资源管理系统的设计与实现*****************\"<>n; N=n;

for(i=0;icout<<\"资源\"<>ming;

11

name[i]=ming;

cout<<\"资源的数量:\"; cin>>number;

Avaliable[i]=number; }

cout<cout<<\"请输入作业的数量:\"; cin>>m; M=m;

cout<<\"请输入各进程的最大需求量(\"<>Max[i][j]; do{

flag=0;

cout<<\"请输入各进程已经申请的资源量(\"<cin>>Allocation[i][j];

if(Allocation[i][j]>Max[i][j]) flag=1;

Need[i][j]=Max[i][j]-Allocation[i][j]; }

if(flag)

cout<<\"申请的资源大于最大需求量，请重新输入!\\n\"; }

while(flag);

showdata();//显示各种资源

safe();//用银行家算法判定系统是否安全 while(choice) {

cout<<\"**************银行家算法演示***************\"<cout<<\"*******************************************\"<>choice; switch(choice)

12

3.调试及运行结果

{

case 1: addresources();break; case 2: delresources();break; case 3: changeresources();break; case 4: share();break;

case 5: addprocess();break; case 0: choice=0;break;

default: cout<<\"请正确选择功能号(0-5)!\"<return 1; }

经过调试，改正了越界错误，定义错误，死循环和一些语法错误。程序最终运行成功。检测结果如下：

13

14

4.总结和体会

一周的课程设计结束了。在这一周里，我做一个模拟银行家算法。

我觉得在着手设计前设计的思路是很重要的。只有思路清晰才能进行下一阶段的设计。这样才能完成整个程序的设计，完成整个文报告的书写。

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

5.参考文献

操作系统概念》高等教育出版社 作者：Abaham Silberschatz Peter

Baer Galvin Greg Gagne

《C语言程序设计》清华大学出版社 作者：谭浩强

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

15

设计过程中质疑（或答辩）记载： 指导教师评语： 签名： 年 月 日 16