毕业设计-操作系统原理银行家算法.doc

操作系统课程设计报告

银行家算法

院 系： 计算机科学技术学院

2015年7月2日

操作系统原理课程设计任务书

一、题目：银行家算法
二、设计要求
（1）张金星（组长）、赵飞负责设计与实现。
（2）查阅相关资料，自学具体课题中涉及到的新知识。
（3）采用结构化、模块化程序设计方法，功能要完善，具有一定的创新。
（4）所设计的程序应有输入、输出。
（5）按要求写出课程设计报告，并于设计结束后1周内提交。其主要内容包括：封皮、课程设计任务书，指导教师评语与成绩、目录、概述、软件总体设计、详细设计、软件的调试、总结、谢启、附录：带中文注释的程序清单、参考文献。报告一律用A4纸打印，中文字体为宋体，西文字体用Time New Roma，一律用小四号字，行距采用“固定值”18磅，首行缩进2字符。总体设计应配合软件总体模块结构图来说明软件应具有的功能。详细设计应用传统或N-S流程图和屏幕抓图说明，调试的叙述应配合出错场景的抓图来说明出现了哪些错误，如何解决的。
三、课程设计工作量
由于是设计小组团结协作完成设计任务，一般每人的程序量在200行有效程序行左右，不得抄袭。
四、课程设计工作计划
2015年6月23日，指导教师讲课，学生根据题目准备资料；
2015年6月24日，进行总体方案设计；
2015年6月25日～2015年6月29日，完成程序模块并通过独立编译；
2015年6月30日～2015年7月1日，将各模块集成为一个完整的系统，并录入足够的数据进行调试运行；
2015年7月2日～2015年7月5日，验收、撰写报告；

指导教师签章：
教研室主任签章
概要设计
操作系统原理课程设计指导教师评语与成绩

指导教师评语：

课程设计表现成绩：
课程设计验收成绩：
课程设计报告成绩：
课程设计 总成绩：

指导教师签章
2015年7 月 5日

目录

一 概述 2

二 总体方案设计 3

三 详细设计 4

四 程序的调试与运行结果说明 7

五 课程设计总结 9

六 后记 10

八 附录 11

九 参考文献 18

一 概述
一、课程设计的目的。
1．使学生更深入地理解和掌握该课程中的有关基本概念。
2．培养学生综合运用所学知识独立完成课题的能力。
3．培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。
4．提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的基本素质。
5．培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性。
6．对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。
二、课程设计的要求。
（1）学生自由组成课程设计小组，建议每组最多不超过3个学生。
（2）选择课程设计题目中的一个课题，每组独立完成。
（3）查阅相关资料，自学具体课题中涉及到的新知识。
（4）采用结构化程序设计方法或面向对象程序设计方法进行设计，功能要完善，具有一定创新。
银行家算法是操作系统当中为避免锁死的算法，并且是最具有代表性的避免锁死的算法，能够有效的在资源分配的过程中，对系统的安全性进行检测。整个算法的计算步骤为对输入的数据进行试分配，并对安全性进行检测，当系统为安全的时，依照安全序列执行程序，如果不安全则进入阻塞状态。银行家算法的来源是在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
在避免死锁的方法中，所施加的简直条件比在预防死锁的方法中限制条件要弱，有可能获得令人满意的系统性能。在该方法中，把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，就可避免死锁的发生。
所谓安全状态与不安全状态是指如果所有过程有可能完成执行（终止），则一个状态被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。
三、程序的主要设计思想。
在多道程序系统中，虽然能够借助于多个进程的并发执行，来改善系统资源的利用率，提高系统的吞吐量，但是依然有风险存在，那就是——锁死。所谓锁死是指，多个进程在运行中因争夺资源而造成的一种僵局，当进程的这种僵持状态时，若无外力作用，它们将无法再向前推进。一组程序中，每个进程都无限等待被该组进程中的另一进程所占有的资源，因而永远无法得到资源，这种现象就叫做进程死锁。

二 总体方案设计
一、 程序模块
本程序包括了四个基本模块： 主函数、试分配、安全性测试、数据的输入与输出。
1、主函数
主函数用于输出系统的主要操作界面，以及调用其他的函数，完成银行家算法。
2、试分配：
对输入的进程的Max、Available、Allocation以及Request进行分配，判断是否可以正常分配。
3 、安全性测试：
当试分配完成时，通过安全性测试来对系统的安全性进行检测，安全时输出安全序列，不安全时进行提醒，并且恢复到初始化时输入的数据。

二、模块之间关系
主函数可以调用系统的所有函数，以及输出功能界面，将试分配函数，安全性测试函数和输入输出函数定义在主函数当中，在需要时通过相应的选项进行调用。而试分配与安全性测试是并列的两个函数，存在执行试分配后需对安全序列进行判断。
输入输出函数，确定数值，并将相对应的数据输入到对应的模块，来进行计算。

三、 数据结构
程序当中需要四种数据结构。
1、可利用资源矩阵（Available），当Available[]=k时，这表示系统中有该类资源k个。
2、最大需求矩阵（Max），当Max[][]=k时，则表示进程需要的资源为k个。

4

3、分配矩阵（Allocation），当Allocation[][]=k时，则表示进程当前已被分得k个资源。
4、需求矩阵（Need），当Need[][]=k时，则表示进程还需要k个资源才能够完成。

四、算法思想
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

三 详细设计

一、程序模块划分：
1. 数据的初始化：
根据提示输入最大需求矩阵（Max），可利用资源量（Available），分配矩阵（Allocation）所需的数据。
2. 输出所对应的矩阵：
根据输入的数据输出对应的矩阵，并且计算出需求矩阵（Need），将完整的算法需要的数据呈现给操作者。
3. 试分配：
根据操作者所输入的进程号已经请求，对系统进行时分配。
4.安全测试
当试分配完成时可进行安全性测试，当进程间是安全的时候则可以输出相应的安全序列。如果错误，则可以回到数据的初始化状态。

二、数据判断
当输入的数据不符合规定时，可以对该数据进行判断，不符合条件重新输入，例如：if(!(0<=in&&in<=t-1))，在程序中，用于判断所输入的进程号是否满足要求，如果不满足要求通过该语句输出“cout<<"该进程不存在,重新输入"<<endl;”。

三、 函数调用
1.通过switch语句对所调用的函数进行判断。
switch(choice)
{
case 1: Input();break;//输入相关数据函数
case 2: Print();break;//打印输出相关数据表函数
case 3: cout<<"请输入有请求的进程号:" break；
case 4: checksafe(in); break;//安全性检查
case 5: refenpei(in); break;//恢复数据
}提示输入有误！
输入可利用资源数
数据初始化结束
True
输出更改后的各资源数

5
算法分析课程设计报告

2.输入函数Input();
void Input()
{
int j,n,m;
cout<<"输入 可利用资源:"<<endl;
for(j=0;j<c;j++)
{
//cout<<"请输入 Available["<<j<<"]:";
while(cin>>Available[j])
{
if(Available[j]<0)
cout<<"输入数字无效，请重新输入"<<endl;
else break;
};
}
cout<<"输入 最大需求:"<<endl;
for(n=0;n<t;n++)//各个进程循环输入
{
for(m=0;m<c;m++)//c个类资源ABC循环输入
{
while(cin>>Max[n][m])
{
if(Max[n][m]<0)
cout<<"输入数字无效，请重新输入"<<endl;
else break;
};
}
}
cout<<"输入 占有资源:"<<endl;
for(n=0;n<t;n++)//各个进程循环输入
{
for(m=0;m<c;m++)//c个类资源ABC循环输入
{
while(cin>>Allocation[n][m])
if(Allocation[n][m]<0)
cout<<"输入数字无效，请重新输入"<<endl;
else break;
Need[n][m]=Max[n][m]-Allocation[n][m];
}
}
cout<<"初始化完成!..."<<endl;
}/*----------------------输入函数结束----------------------*/

3. 输出函数Print();

5

算法分析课程设计报告
/*-------------------------输出函数------------------------*/
void Print()
{
int i,j;
cout<<"|*****|*************|*************|**********|*************|"<<endl;
cout<<"|*****| | | | |"<<endl;
cout<<"| 进程| Max | Allocation | Need | Available |"<<endl;
cout<<"|*****|*************|*************|**********|*************|"<<endl;
for(i=0;i<t;i++)
{
cout<<"| p"<<i<<" | ";
for(j=0;j<c;j++)
{
cout<<Max[i][j]<<" ";
}
cout<<"| ";
for(j=0;j<c;j++)
{
cout<<Allocation[i][j]<<" ";
}
cout<<"| ";
for(j=0;j<c;j++)
{
cout<<Need[i][j]<<" ";
}
cout<<"| ";
if(i==0)
{
for(j=0;j<c;j++)
{
cout<<Available[j]<<" ";
}
cout<<"| ";
}
if(i>0)
{
cout<<" |";
}
cout<<endl;
}
cout<<"|*****|*************|*************|**********|*************|"<<endl;
}/*--------------------输出函数结束--------------------------*/

四 程序的调试与运行结果说明
一、程序调试:
1、在数据初始化当中要考虑到输入进程数是否为负数，是否为字符。
2、在安全性算法当中要考虑到当不安全时，数据能否恢复，是否可以重新进行分配。当输入的Request大于Need或者大于Available的情况，当大于是需要重新输入。

二、程序测试:
1.输入初始化：

2.矩阵输出

8

3. 安全序列输出

4.进程不安全时

1
7
实验心得

12

算法分析课程设计报告

五 课程设计总结
操作系统是计算系组成当中最为重要的系统软件，只有操作系统的存在在能够使得计算机能够有正常有序的进行工作，操作系统对于计算机来说是各项活动的组织者和指挥者。而银行家算法的存在则是为了保证这个系统能够正常的安全的进行工作的保证。我们可以把操作系统看成是银行，而银行家算法则可以看成是银行的管理者，而各类资源则可以看成时银行的资金，而进程则是客户。作为管理者的银行家算法则需要使得在银行的资金，即操作系统的资源进行正常有序的分配，以保证操作系统能够正常运转。并保证在进程有足够的资源进行运转。
操作系统按照银行家制定的规则进行资源分配，当进程首次申请资源是，要测试进程对最远的最大需求是多少，如果系统现有的资源能够满足，则最该进程分配资源，否则推迟分配。当进程在执行过程，依然要求分配资源时，则先测试该进程已占用的资源数与需求数是否超过了该进程的最大需求。若超过，应该拒绝分配资源。
银行家算法作为系统资源的保障，起着举足轻重的作用，所以多银行家算法必须有深入的了解，从而认识操作系统的工作过程。

六 后记
在我们这个小组从选择这个程序到编写程序再到程序的调试再到最后的验收，都使我学到了许多的东西，有的根本就是书本上学不到的！在我看来，这次课程设计也可以看作是我们在社会上工作时候的一场小小的模拟！跟我们在以后的工作学习中有很多地方相像之处！
不光是在程序的学习上！而且还在人际关系上，我也学到了很多的东西！因为在这次课程设计中，我被任命了我们小组的组长，虽然只是一个小小的组长，但是我并没有轻视它的地位，作为我们组的小组长，我不能拈轻怕重，应该主动把难的地方，比较累得地方给我，还应该照顾到我们组的组员的情况，看他们是否能接受他们所分得的模块，如果不能，在进行重新分配，以解决他们的难题！在承担我们组的小组长的过程中我学到了不少的东西！
这次的课程设计让我学到的东西还有很多，例如：遇到困难应该自己独立解决，不能遇到困难就找老师，或者一决不振，不想再继续了，在这个时候我们应该调整我们的心态，冷静一下。不应该烦躁，试想在以后的工作中如果遇到了类似的更难得问题时，那时候我们可不能再找老师或者不想干了，那样是不行的！
还有就是我学到了有的错误是以前从没犯过的，最后知道了，也增加了我的经验！为以后的学习奠定基础！
虽然我们的程序已经基本完事了，一些基本的功能已经基本实现但是还是有不足之处，因为这次得时间有限，所以以后应该进一步学习！以增加自己的学习经验！
非常感谢胡老师在实验的的过程中耐心的帮助我修改程序的错误，并给我讲解是为什么错的，并如何改正，这样使我学到了很多课本上学不到的东西！还有我要感谢我们组的成员，这样使我懂得了什么叫团队合作精神,他们给予我的帮助也是很巨大的，如果没有我们组的共同努力，我们的这个“磁盘调度”也不会运行成功！
在此我再一次对以上等人表示由衷的感谢！！！

八 附录
#include <iostream.h>

#define M 10 //资源类数
#define N 50 //进程数

void Input(); //用于输入的函数
void Print(); //用于打印输出表格的函数
void tryfenpei(int i);//试分配函数
void checksafe(int x);//安全检测函数
void refenpei(int i);//恢复数据函数

//定义初始化数组
int Available[M],
Max[N][M],
Allocation[N][M],
Need[N][M],
Request[M];
int c,t;//资源进程
int in;//用户选择的进程号
/*----------------------------------------------------------------*/
void main( )
{
int choice;
char ch='Y';

cout<<"输入资源数：";
cin>>c;
cout<<"输入进程数：";
cin>>t;
do
{
if(ch=='Y'||ch=='y')
{
cout<<"银行家算法"<<endl;
cout<<"1:输入所需数据 "<<endl;
cout<<"2:显示矩阵 "<<endl;
cout<<"3:试分配 "<<endl;
cout<<"4:检查安全性 "<<endl;
cout<<"5:恢复数据到初始状态 "<<endl;
cout<<"**********************"<<endl;
cout<<"请选择操作序号：";
cin>>choice;
switch(choice)
{
case 1: Input();//输入相关数据函数
break;
case 2: Print();//打印输出相关数据表函数
break;
case 3: cout<<"请输入有请求的进程号:";
while(cin>>in)
{
if(!(0<=in&&in<=t-1))
{
cout<<"该进程不存在,重新输入"<<endl;
}
else break;
}
tryfenpei(in);//试分配
break;
case 4: checksafe(in);//安全性检查
break;
case 5: refenpei(in);//恢复数据
break;
default: cout<<"请(1-5)中选择正确的操作序号!"<<endl;
break;
}
cout<<"要继续进行吗?（y-是 n否）";
}
else if(ch=='N'||ch=='n')
{
cout<<"正在退出..."<<endl;
break;
}
else
{
cout<<"输入无效!重新输入..."<<endl;
}
}while(cin>>ch);
}/*---------------------main函数结束----------------------------------*/

/*--------------------------输入函数----------------------------------*/

算法分析课程设计报告

void Input()
{
int j,n,m;
cout<<"输入 可利用资源:"<<endl;
for(j=0;j<c;j++)
{
//cout<<"请输入 Available["<<j<<"]:";
while(cin>>Available[j])
{
if(Available[j]<0)
cout<<"输入数字无效，请重新输入"<<endl;
else break;
};
}
cout<<"输入 最大需求:"<<endl;
for(n=0;n<t;n++)//各个进程循环输入
{
for(m=0;m<c;m++)//c个类资源ABC循环输入
{

while(cin>>Max[n][m])
{
if(Max[n][m]<0)
cout<<"输入数字无效，请重新输入"<<endl;
else break;
};
}
}
cout<<"输入 占有资源:"<<endl;
for(n=0;n<t;n++)//各个进程循环输入
{
for(m=0;m<c;m++)//c个类资源ABC循环输入
{
while(cin>>Allocation[n][m])
if(Allocation[n][m]<0)
cout<<"输入数字无效，请重新输入"<<endl;
else break;
Need[n][m]=Max[n][m]-Allocation[n][m];
}
}
cout<<"初始化完成!..."<<endl;
}/*-------------------------输入函数结束----------------------------------*/

13

算法分析课程设计报告

/*-------------------------输出函数----------------------------------*/
void Print()
{
int i,j;
cout<<"|*****|*************|*************|**********|*************|"<<endl;
cout<<"|*****| | | | |"<<endl;
cout<<"| 进程| Max | Allocation | Need | Available |"<<endl;
cout<<"|*****|*************|*************|**********|*************|"<<endl;
for(i=0;i<t;i++)
{
cout<<"| p"<<i<<" | ";
for(j=0;j<c;j++)
{
cout<<Max[i][j]<<" ";
}
cout<<"| ";
for(j=0;j<c;j++)
{
cout<<Allocation[i][j]<<" ";
}
cout<<"| ";
for(j=0;j<c;j++)
{
cout<<Need[i][j]<<" ";
}
cout<<"| ";
if(i==0)
{
for(j=0;j<c;j++)
{
cout<<Available[j]<<" ";
}
cout<<"| ";
}
if(i>0)
{
cout<<" |";
}

14

cout<<endl;
}
cout<<"|*****|*************|*************|**********|*************|"<<endl;
}/*-------------------------输出函数结束--------------------------------*/

/*-------------------------试分配函数----------------------------------*/
void tryfenpei(int n)
{
int i;
cout<<"您输入的是 "<<"p["<<n<<"]"<<" 进程"<<endl;
cout<<"该进程需求量为： ";
for(i=0;i<c;i++)
cout<<Need[n][i]<<" ";
cout<<endl;
cout<<"请输入请求资源的数目:";
for(i=0;i<c;i++)
{
while(cin>>Request[i])
{
if (Request[i]<0)
{
cout<<"!!输入的数字无效."<<endl;
}
else if (Request[i]>Need[n][i])
{
cout<<"!!超出进程需求量"<<endl<<endl;
}
else if (Request[i]>Available[i])
{
cout<<"!!系统没有足够的可用资源量满足进程需要"<<endl<<endl;
}
else break;
}
}
cout<<"输入成功，输入的是：";
for(int f=0;f<c;f++)
cout<<Request[f]<<" ";
cout<<endl;
cout<<"执行银行家算法，进行试分配..."<<endl;

15

for( f=0;f<c;f++)
{
Available[f] = Available[f] - Request[f];
Allocation[n][f] = Allocation[n][f] + Request[f];
Need[n][f] = Need[n][f]-Request[f];
}
cout<<"试分配完成!"<<endl;
}/*-------------------------试分配函数结束----------------------------------*/

/*-------------------------安全检测函数----------------------------------*/
void checksafe(int x)
{
cout<<"进入安全性检测..."<<endl;
int i,m,apply,j,k=0,flag=0;
int Work[M],temp[N];
bool Finish[N]; //t为进程数
for(i=0;i<c;++i)
{
Work[i]=Available[i];
}
for(i=0;i<t;i++)
{
Finish[i]=false;
}
for(i=0;i<t;i++)
{
apply=0;
for(j=0;j<c;j++)
{
if (false==Finish[i] && Need[i][j]<=Work[j])
{
apply++;//标记是否所需的资源都得到满足
if(apply==c)
{
for(m=0;m<c;m++)
{
Work[m]=Work[m]+Allocation[i][m];//变分配数 w=w+a
}
Finish[i]=true;
temp[k++]=i;//将满足的进程号存入temp[]数组中

18

参考文献

i=-1; //若有进程满足条件则从头开始寻找
}
}
}
}
for(i=0;i<t;i++)
{
if(Finish[i]==false)
{
cout<<"试分配后系统不安全!!! 本次资源申请不成功!!!"<<endl;
cout<<"等待恢复原来的数据..."<<endl;
refenpei(in);
return ;
}
}
cout<<"安全序列："<<endl;
cout<<"分配的序列:";
for(i=0;i<t-1;i++)
{
cout<<"P"<<temp[i]<<"-->";
}
cout<<"P"<<temp[t-1]<<endl;
cout<<"已通过安全性测试!"<<endl;
cout<<"开始给第 "<<"p["<<in<<"]"<<"进程分配资源..."<<endl;
cout<<"分配完成!等待打印输出..."<<endl;
Print();
return ;
}/*-------------------------安全性检查函数结束----------------------------------*/

/*-------------------------恢复数据函数----------------------------------*/
void refenpei(int i)
{
for(int f=0;f<c;f++)
{
Available[f] = Available[f] + Request[f];
Allocation[i][f] = Allocation[i][f] - Request[f];
Need[i][f] = Need[i][f] + Request[f];
}
cout<<"数据已恢复初始状态..."<<endl;
Print();
}

九 参考文献
[1] 计算机操作系统（第三版） 汤小丹 梁红兵 哲凤屏 汤子瀛 编著 西安电子科技大学出版社
[2] 软件工程 王长元 李晋惠 等编著 西安地图出版社
[3] 操作系统原理 孟庆昌 等编著 机械工业出版社