银行家算法.doc

实 验 报 告
题 目

名 称
死锁避免（银行家算法）

院 系

信息科学与工程学院

班 级

1006402

完成时间

2012-4-24

指导老师

肖赛男
本次实验成绩

组长

联系电话
刘建平

13337377983

邮件地址

602552087@
组员（姓名，
学号）
刘建平
10006402-27

主要任务
算法的组织，综合调度，程序运行界面的实现

组员（姓名，
学号）
孟文斌
1006402-25

主要任务

算法的实现，测试，实验报告的完成
主
要
原
理
及
所
参
考
的
资
料
（
包
括
实
验
内
容
及
条
件
）
实验原理：
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
　　为保证资金的安全,银行家规定:
　（1）当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
　（2）顾客可以分期贷款,但贷款的总数不能超过最大需求量;
　（3）当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
　 (4）当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.
主要参考书
（1）黄干平，陈洛资，等 计算机操作系统。北京:科学出版社，1989。
（2）计算机操作系统原理 西安大学出版社 汤子瀛主编
（3）操作系统 电子工业出版社 William Stallings著
（4）冯耀霖，杜瞬国。操作系统。西安：西安电子科技大学出版社，1989
（5）李勇，刘恩林。计算机体系结构。长沙：国防科技大学出版社。1987
（6）孟庆昌。操作系统教程。北京：电子工业出版社，2004

函数调用流程图
调用check()函数
work[]=available[]
finish[]=false
need[][]<=work[]
finish[]=false ?

work[]=work[]+allocation[][]
finish[]=true
Y
N
所有进程的finish[]==true?
Y
N
输出安全序列，并打印出当前资源分配情况
输出提示：系统不安全
调用结束
Y
N
Y
N
Y
N
Y
N
系统初始化
输入进程个数no1
输入资源类数no2
输入进程最大需求矩阵Max、已分配矩阵Allocation和可利用资源矩阵Available
打印输出此时资源分配情况表
Need[][]=Max[][]-Allocation[][]
输入欲申请资源进程号
输入是否合法
输入该进程申请的资源量
Request[]>Need[][]?

继续分配(Y)?
or
退出(N)?
Request[]>Available[][]?

预分配
调用check()函数进行安全性检查
退出系统
银行家算法流程图

实验说明
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
本次实验的算法思路来自于《计算机操作系统》教材中的银行家算法，算法首先用安全性算法检查输入的各项矩阵数据。如果输入数据状态不是安全的状态，则提示数据不安全，要求用户重新输入数据；如果数据时安全的,则继续要求用户输入需要发送请求的进程及其所请求的资源，然后再判断资源数是否满足分配条件，如果不满足，则提示不满足条件，请求失败；如果满足，则备份当前各进程的状态，预分配进程资源，再进行安全性检查。如果状态安全，则系统正式为发送请求的进程分配资源，若状态不安全，则提示用户为进程分配资源后系统处于不安全状态，并还原各进程状态。

主
要
算
法
流
程
图
（
包
括
实
验
步
骤
）
本
实
验
涉
及
的
主
要
算
法
细
节
说
明
（
包
括
数
据
结
构
）
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#define False 0
#define True 1
int Max[100][100]={0}; //各进程所需各类资源的最大需求
int Available[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;
count<<"系统目前可用的资源[Available]:"<<end;
for(i=0;i<N;i++)
count<<name[i]<<" ";
count<<end;
for (j=0;j<N;j++)
count<<Available[j]<<" "; //输出分配资源
count<<end;
count<<" Max Allocation Need"<<end;
count<<"进程名:\t ";
for(j=0;j<3;j++){
for(i=0;i<N;i++)
count<<name[i]<<" ";
count<<" ";
}
count<<end;
for(i=0;i<M;i++){
count<<" "<<i<<" ";
for(j=0;j<N;j++)
count<<Max[i][j]<<" ";
count<<" ";
for(j=0;j<N;j++)
count<<Allocation[i][j]<<" ";
count<<" ";
for(j=0;j<N;j++)
count<<Need[i][j]<<" ";
count<<end;
}
}

int changdata(int i) //进行资源分配
{
int j;
for (j=0;j<M;j++) {
Available[j]=Available[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]=Available[0];
Work[1]=Available[1];
Work[2]=Available[2];
for(i=0;i<M;i++){
apply=0;
for(j=0;j<N;j++){
if (Finish[i]==False&&Need[i][j]<=Work[j])
{
apply++;
if(apply==N){
for(m=0;m<N;m++)
Work[m]=Work[m]+Allocation[i][m]; //变分配数
Finish[i]=True;
temp[k]=i;
i=-1;
k++;
flag++;
}
}
}
}
for(i=0;i<M;i++){
if(Finish[i]==False){
count<<"系统不安全"<<end; //不成功系统不安全
return -1;
}
}
count<<"系统是安全的!"<<end; //如果安全，输出成功提示
count<<"分配的序列:";
for(i=0;i<M;i++)
{ //输出运行进程数组
count<<temp[i];
if(i<M-1) count<<"->";
}
count<<end;
return 0;
}
void share() //利用银行家算法对申请资源对进行判定
{
char ch;
int i=0,j=0;
ch='y';
count<<"请输入要求分配的资源进程号(0-"<<M-1<<"):";
cin>>i; //输入须申请的资源号
count<<"请输入进程 "<<i<<" 申请的资源:"<<end;
for(j=0;j<N;j++)
{
count<<name[j]<<":";
cin>>Request[j]; //输入需要申请的资源
}
for (j=0;j<N;j++){
if(Request[j]>Need[i][j]) //判断申请是否大于需求，若大于则出错
{
count<<"进程 "<<i<<"申请的资源大于它需要的资源";
cout<<" 分配不合理，不予以分配！"<<endl;
ch='n';
break;
}
else {
if(Request[j]>Available[j]) //判断申请是否大于当前资源，若大于则出错
{
count<<"进程"<<i<<"申请的资源大于系统现在可利用的资源";
count<<" 分配出错，不予分配!"<<end;
ch='n';
break;
}
}
}
if(ch=='y') {
changdata(i); //根据进程需求量变换资源
showdata(); //根据进程需求量显示变换后的资源
safe(); //根据进程需求量进行银行家算法判断
}
}
void addresources() //添加资源
{
int n,flag;
count<<"请输入需要添加资源种类的数量:";
cin>>n;
flag=N;
N=N+n;
for(int i=0;i<n;i++){
count<<"名称:";
cin>>name[flag];
count<<"数量:";
cin>>Available[flag++];
}
showdata();
safe();
}
void delresources() //释放资源
{
char ming;
int i,flag=1;
count<<"请输入需要释放的资源名称：";
do{
cin>>ming;
for(i=0;i<N;i++)
if(ming==name[i]){
flag=0;
break;
}
if(i==N)
count<<"该资源名称不存在，请重新输入：";
}
while(flag);
for(int j=i;j<N-1;j++)
{
name[j]=name[j+1];
Available[j]=Available[j+1];

}
N=N-1;
showdata();
safe();
}
void changeresources() //修改资源函数
{
count<<"系统目前可用的资源[Available]:"<<end;
for(int i=0;i<N;i++)
count<<name[i]<<":"<<Available[i]<<end;
count<<"输入系统可用资源[Available]:"<<end;
cin>>Available[0]>>Available[1]>>Available[2];
count<<"经修改后的系统可用资源为"<<end;
for (int k=0;k<N;k++)
count<<name[k]<<":"<<Available[k]<<end;
showdata();
safe();
}
void addprocess() //添加作业
{
int flag=M;
M=M+1;
count<<"请输入该作业的最大需求量[Max]"<<end;
for(int i=0;i<N;i++){
count<<name[i]<<":";
cin>>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;
count<<"\t **************资源管理系统的设计与实现*************"<<end;
count<<"\t ********************银行家算法设计*****************"<<end;
count<<"\t\t 请输入系统可供资源种类的数量:";
cin>>n;
N=n;
for(i=0;i<n;i++)
{
count<<"资源"<<i+1<<"的名称:";
cin>>ming;
name[i]=ming;
count<<"资源"<<i+1<<"的数量:";
cin>>number;
Available[i]=number;
}
count<<end;
count<<"请输入作业的数量:";
cin>>m;
M=m;
count<<"\t\t请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)[Max]:"<<end;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
cin>>Max[i][j];
do{
flag=0;
count<<"\t\t请输入各进程已申请的资源量("<<m<<"*"<<n<<"矩阵)[Allocation]:"<<end;
for(i=0;i<m;i++)
for(j=0;j<n;j++){
cin>>Allocation[i][j];
if(Allocation[i][j]>Max[i][j])
flag=1;
Need[i][j]=Max[i][j]-Allocation[i][j];
}
if(flag)
count<<"申请的资源大于最大需求量，请重新输入!\n";
}
while(flag);

showdata(); //显示各种资源
safe(); //用银行家算法判定系统是否安全
while(choice)
{
count<<"**************银行家算法演示***************"<<end;
count<<" 1:增加资源 "<<end;
count<<" 2:释放资源 "<<end;
count<<" 3:修改资源 "<<end;
count<<" 4:分配资源 "<<end;
count<<" 5:增加作业 "<<end;
count<<" 0:退出系统 "<<end;
count<<"*******************************************"<<end;
count<<"请选择你的操作:";
cin>>choice;
switch(choice)
{
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: count<<"请正确选择操作(0-5)!"<<end;break;
}
}
return 1;
}

主要算法细节说明
（1）设置两个向量：
工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，开始时，Work=Available；Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时Finish[i]=false；当有足够资源分配给进程时，再另Finish[i]=true
（2从进程集合中找到一个能满足下述条件的进程：
Finish[i]=false;Need[i,j]<=Work[j]:若找到，则执行（3），否则执行（4）。
（3） 当进程P获得资源后，可顺利执行，直至完成，并且释放出分配给它的资源，执行Work[j]=Work[j]+Allocation[i,j];
Finish[i]=true;
Go to step 2;
（4） 如果所有的进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
注：Available为可利用的资源向量；Max为最大需求；Allocation为当前已分配的资源数

。
本次实践计划、进度安排及完成情况
4月10号
商讨如何实现本次实验以及同学之间的分工.
4月10号~4月24号
基本完成程序.
4月22号~10月24号
修改完善程序.代码测试.
4月24号~5月2号
完成实验报告.
主要测试方法及测试数据，包括测试结果及测试人
测试数据：
5
3
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3

0 1 0
2 0 0
3 0 2
2 1 1
0 0 2

3 3 2

发送请求：
1
1 0 2
4
3 3 0
0
0 2 0
0
0 1 0
步骤：
1、 运行程序进入初始化界面

2、 输入测试数据

3、 程序对初始化的进程状态进行安全性检查

4、 输入发送请求的进程及请求的资源数

5、 数据测试成功，得到其安全序列，继续测试...

第二次请求：进程4 请求3 3 0 失败！
6、 程序运行正确，继续测试下一组数据...

分配后系统处于不安全状态，还原进程状态！

本次实验的心得体会（每位同学一段）

刘建平
经过本次实验，我深刻的认识到银行家算法在避免死锁上起到了重要的作用。
在做银行家算法的课程设计时，首先给自己整理了下这次课程设计的计划，因为要编程，所以在网上、书本上查了很多与银行家算法相关的资料，比如资源分配，随机分配算法。这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，了解到一些书本上没有的知识，也知道要做一个课程设计，如果知识面只是停留在书本上，是不可能把课成设计完全地做好。其实如果不经常动手实学习的话，对于像这种编程类的设计是很难熟练掌握的，从每次的课程设计中虽然都能将以前的知识顺便再复习一遍，但如果平时不训练积累的话还是很容易忘的，课程设计是给了我们一个机会去复习，同时也是提醒我们应该注重平时的积累。从课程设计以后还是要多多的动手，在实践中体会理论知识，这样才不会在要做实验和设计时，觉得无从下手。在这次编程中，我得到了很多。遇到问题时，和同学一块商量，一起努力！也了解到同学的想法，大家的思想都得到了交流。本次课程设计最大的体会是动手能力有了很大的提高，希望我能在今后的学习和实践中能更加熟练掌握编程能力。
孟文斌
在本次实现银行家算法的实验中有很大收获，首先，我在这次实验中主要负责算法的实现，测试，实验报告的完成,在写代码中也遇到了很多不懂的或是以前忽略了的知识，参考别人的代码得到了很多启示。其实我对真正的编程实现一些功能还没有什么经验，所以这次的算法实现让我感觉到对编程的认识又进了一步。在测试的过程中，还发现好多平时不注意的细节，有是代码是正确的，但就是不能执行，就是因为平时不注意这方面，这次得到警醒。还有就是在这次试验显现出了团队合作的效率，大家分工合作，相互讨论交流，是我们的实验在很短的时间内就能完成的原因之一。还是那句话：理论不如实践，只有动手才能学好。实验过程中虽然遇到很多困难，但是收获也是令人满意的，下次我想会做得更好。