淮海工学院计算机科学系
实验报告书
课程名:《操作系统原理》
题 目: 银行家算法
班 级: 网络092
学 号:
姓 名:
操作系统原理实验——银行家算法实验报告
1目的与要求:
1)本实验目的是通过使用银行家算法实现系统资源的分配和安全性检查模拟,提高学生对操作系统资源分配功能的深刻理解,并培养学生对操作系统开发的兴趣与应用能力;
2)实验前必须认真阅读和理解银行家算法的基本原理和实现方法;
3)独立使用C或VC++编程语言编写银行家算法模拟程序;
4)按照实验题目要求独立正确地完成实验内容(编写、调试算法程序,提交程序清单及及相关实验数据与运行结果)
5)于20##年11月1日以前提交本次实验报告(含电子和纸质报告,由学习委员以班为单位统一打包提交)。
2 实验内容或题目
1)设计五个进程{P0,P1,P2,P3,P4}共享三类资源{A,B,C}的系统,{A,B,C}的资源总数量分别为10,5,7。(参考书上用例)
2)并行进程可动态地申请资源和释放资源(程序交互输入申请或释放资源数量),系统按各进程的申请动态地分配资源。
3)每当进程动态申请资源或释放资源时,模拟程序应能及时显示或打印各个进程在此时刻的资源分配表、系统可用资源量和安全序列等资源分配信息和安全检查信息。
4)本次实验内容(项目)的详细说明以及要求请参见实验指导书。
3 实验步骤与源程序
实验步骤:
1.银行家算法
设Requesti表示进程Pi的资源申请向量。如Requesti[j]= k,表示进程Pi动态申请k个Rj类资源。当进程Pi申请资源时,就执行下列动作(试探性分配):
① 若Requesti[j]>Need[i,j],产生出错条件,因为进程Pi对资源的请求量已超过其说明的最大数量;否则,转到步骤②。
② 如果Requesti[j]>Available[j],则进程Pi必须等待,这是因为系统现在没有可用的资源;否则,转到步骤③。
③ 如果系统可以给进程Pi分配所请求的资源,则应对有关数据结构进行修改:
Available[j] = Available[j]-Requesti[j]; (j=1,2,……,n)
Allocation[i,j] = Allocation[i,j] + Requesti[j]; (i=1,2,……,m)
Need[i,j] = Need[i,j] - Requesti[j];
④ 系统执行安全性检查,查看此时系统状态是否安全。如果安全,就给进程Pi 实际分配资源;否则,即系统是不安全的,则Pi等待,作废本次试探性分配,并且把资源分配状态恢复成③之前的情况。
2. 安全检查算法
设置两个向量:工作向量Work:表示系统可提供给进程继续运行所需要的各类资源数目,长度为n;进程完成标志向量Finish:长度为m,表示各个进程是否能够得到足够的资源并运行完成。两个向量初始化:Work=Available,Finish[i]=false (i=1,2,…m)。
从进程集合中搜寻满足下列条件的进程(找安全进程序列):
Finish[i] ==false且Need[i,j]≤Work[j]。
如果找到这样的进程,执行③;否则,则转向步骤④。
修改数据值:
Work[j]=Work[j] + Allocation[i,j](进程Pi释放所占的全部资源);
Finish[i]=true;
返回步骤②;
安全与不安全判定:如果所有进程的Finish[i] ==true都成立(找着安全序列),则系统处于安全状态;否则,系统处于不安全状态。
源程序
#include "iostream.h"
#define M 5
#define N 3
#define FALSE 0;
#define TRUE 1;
int AVAILABLE[N]={3,3,2};
int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
int ALLOCATION[M][N]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
int NEED[M][N],p[M];
int Request[N]={0,0,0};
//显示资源分配情况
void displaydata()
{
int i,j;
cout<<" 系统可用的资源数为:"<<endl<<endl;
for (j=0;j<N;j++)
cout<<" 资源"<<j<<": "<<AVAILABLE[j];
cout<<endl;
cout<<endl;
cout<<" 各进程还需要的资源量:"<<endl<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<":";
for (j=0;j<N;j++){cout<<" 资源"<<j<<": "<<MAX[i][j]-ALLOCATION[i][j];
NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];}
cout<<endl; }
cout<<endl;
cout<<" 各进程已经得到的资源量: "<<endl<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<":";
for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<ALLOCATION[i][j];
cout<<endl; } }
//为进程k分配请求的资源数量
void changedata(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j]; } }
//恢复已分配的数据为分配前状态
void restoredata(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j]; } }
//安全检查过程中判断进程需求资源是否大于现有资源
int compare(int need[ ],int work[ ])
{
int j;
for(j=0;j<N;j++)
{
if(need[j]>work[j])
{ return FALSE;} }
return TRUE;}
//安全检查
int isSecurity(int available[N],int need[M][N],int allocation[M][N])
{
int i,j,k=0,flag,finish[M],work[N];
for(i=0;i<M;i++)
{
finish[i]=FALSE; }
for(j=0;j<N;j++)
{
work[j]=available[j]; }
while(1) //寻找安全进程序列
{ flag=FALSE;
for(i=0;i<M;i++)
{ //每一趟循环将找到当前可分配资源的进程,并回收其已分配资源
if(finish[i]==0&&compare(need[i],work)==1)
{
for(j=0;j<N;j++)
work[j]+=allocation[i][j];
finish[i]=TRUE;
p[k++]=i;
flag=TRUE;
break; //结束FOR循环,表示WORK中资源满足某一进程的资源需求,并执行while } }
if(flag==0) //只要有一个进程全部资源得到满足,则继续while(TRUE)循环
{
for(i=0;i<M;i++)
{
if(finish[i]==0)
return FALSE; //遇到某一进程的finish[i]不成立,则不安全 }
return TRUE; //对所有进程检查后,finish[i]均为TRUE,则有安全序列}} }
void yihangjia()
{
int k;
int flag=1;
int flag1=1;
displaydata();
cout<<endl;
cout<<" 请输入你需要提供资源的进程号:"<<endl;
cin>>k;
cout<<endl;
cout<<" 请输入你需要申请的个资源的个数:"<<endl;
for(int j=0;j<N;j++)
cin>>Request[j];
for(j=0;j<N;j++)
{
if(NEED[k][j]<Request[j])
{
cout<<"申请的资源已超过需要的资源!"<<endl;
flag=0;break;} }
if( flag==1)
{
for(j=0;j<N;j++)
{if(AVAILABLE[j]<Request[j]) {
cout<<"申请的资源已超过现有的资源 ! 请等待 !"<<endl;
flag1=0; break;}}
if(flag1==1)
{
changedata(k);
if(isSecurity(AVAILABLE, NEED, ALLOCATION)==1)
{ cout<<"一个安全序列: ";
for(int i=0;i<M;i++)
{ cout<<p[i];
cout<<" "; } }
else
{ restoredata( k) ;
cout<<" 该申请资源不安全!"<<endl<<endl; } }}}
int main()
{ char a;
A: yihangjia();
cout<<endl;
cout<<"继续请按 Y !"<<endl;
cin>>a;
if(a=='Y'||a=='y')
goto A;
else return 0;}
4 测试数据与实验结果(可以抓图粘贴)
5 结果分析与实验体会
在编银行家算法的时候,由于老师都把主要的程序段给我们了,我们只要组织一下就可以了,感觉没有什么难度,但是自己在做的时候,还是遇到了许多的问题,比如说怎么样让程序重复的运行,怎么样实现在资源请求的时候,做Request的判断等等。总得来说,比上一个程序比较有成就感,毕竟是自己组织的吧!我想这次程序弄的这么快,还是因为我把银行家算法的意思清楚了,明白了,所以以后在编程序的时候,应该先弄清楚程序的目的和最终要实现的功能了解了,在动手编程序会有事半功倍的效果。这次应该值得鼓励一下!
第二篇:银行家算法实验报告
计算机学院《操作系统》课程设计报告
设计题目:银行家算法的实现
姓名:
学号:
班级: 06网络工程班
完成日期: 2009年 6 月13 日
银行家算法分析、设计与实现
一、 设计理论描述
本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并采用适当的算法,有效地防止和避免死锁地发生。要求如下:
(1) 模拟一个银行家算法;
(2) 初始化时让系统拥有一定的资源;
(3) 用键盘输入的方式申请资源;
(4) 如果预分配后,系统处于安全状态,则修改系统的资源分配情况;
(5) 如果预分配后,系统处于不安全状态,则提示不能满足请求,
设计的主要内容是模拟实现动态资源分配。同时编写和调试一个系统动态资源的简单模拟程序,观察死锁产生的条件,并使用适当的算法,有效的防止和避免死锁的发生。
银行家算法. 顾名思义是来源于银行的借贷业务,一定数量的本金要应多个客户的借贷周转,为了防止银行加资金无法周转而倒闭,对每一笔贷款,必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题,系统中有限的资源要供多个进程使用,必须保证得到的资源的进程能在有限的时间内归还资源,以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源,则进程都无法继续执行下去的死锁现象。
把一个进程需要和已占有资源的情况记录在进程控制中,假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时,表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然,,每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.
二、算法描述及数据结构模型
1.银行家算法:
设进程i提出请求Request[n],则银行家算法按如下规则进行判断。
(1)如果Request[n]>Need[i,n],则报错返回。
(2)如果Request[n]>Available,则进程i进入等待资源状态,返回。
(3)假设进程i的申请已获批准,于是修改系统状态:
Available=Available-Request
Allocation=Allocation+Request
Need=Need-Request
(4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。
2.安全性检查
(1)设置两个工作向量Work=Available;Finish[M]=False
(2)从进程集合中找到一个满足下述条件的进程,
Finish [i]=False
Need<=Work
如找到,执行(3);否则,执行(4)
(3)设进程获得资源,可顺利执行,直至完成,从而释放资源。
Work=Work+Allocation
Finish=True
GO TO 2
(4)如所有的进程Finish[M]=true,则表示安全;否则系统不安全。
3.数据结构
#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()//显示资源矩阵
三、源代码
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#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]:"<<endl;
for(i=0;i<N;i++)
cout<<name[i]<<" ";
cout<<endl;
for (j=0;j<N;j++)
cout<<Avaliable[j]<<" ";//输出分配资源
cout<<endl;
cout<<" Max Allocation Need"<<endl;
cout<<"进程名 ";
for(j=0;j<3;j++){
for(i=0;i<N;i++)
cout<<name[i]<<" ";
cout<<" ";
}
cout<<endl;
for(i=0;i<M;i++){
cout<<" "<<i<<" ";
for(j=0;j<N;j++)
cout<<Max[i][j]<<" ";
cout<<" ";
for(j=0;j<N;j++)
cout<<Allocation[i][j]<<" ";
cout<<" ";
for(j=0;j<N;j++)
cout<<Need[i][j]<<" ";
cout<<endl;
}
}
int changdata(int i)//进行资源分配
{
int j;
for (j=0;j<M;j++) {
Avaliable[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;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){
cout<<"系统不安全"<<endl;//不成功系统不安全
return -1;
}
}
cout<<"系统是安全的!"<<endl;//如果安全,输出成功
cout<<"分配的序列:";
for(i=0;i<M;i++){//输出运行进程数组
cout<<temp[i];
if(i<M-1) cout<<"->";
}
cout<<endl;
return 0;
}
void share()//利用银行家算法对申请资源对进行判定
{
char ch;
int i=0,j=0;
ch='y';
cout<<"请输入要求分配的资源进程号(0-"<<M-1<<"):";
cin>>i;//输入须申请的资源号
cout<<"请输入进程 "<<i<<" 申请的资源:"<<endl;
for(j=0;j<N;j++)
{
cout<<name[j]<<":";
cin>>Request[j];//输入需要申请的资源
}
for (j=0;j<N;j++){
if(Request[j]>Need[i][j])//判断申请是否大于需求,若大于则出错
{
cout<<"进程 "<<i<<"申请的资源大于它需要的资源";
cout<<" 分配不合理,不予分配!"<<endl;
ch='n';
break;
}
else {
if(Request[j]>Avaliable[j])//判断申请是否大于当前资源,若大于则
{ //出错
cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源";
cout<<" 分配出错,不予分配!"<<endl;
ch='n';
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<n;i++){
cout<<"名称:";
cin>>name[flag];
cout<<"数量:";
cin>>Avaliable[flag++];
}
showdata();
safe();
}
void delresources(){//删除资源
char ming;
int i,flag=1;
cout<<"请输入需要删除的资源名称:";
do{
cin>>ming;
for(i=0;i<N;i++)
if(ming==name[i]){
flag=0;
break;
}
if(i==N)
cout<<"该资源名称不存在,请重新输入:";
}
while(flag);
for(int j=i;j<N-1;j++)
{
name[j]=name[j+1];
Avaliable[j]=Avaliable[j+1];
}
N=N-1;
showdata();
safe();
}
void changeresources(){//修改资源函数
cout<<"系统目前可用的资源[Avaliable]:"<<endl;
for(int i=0;i<N;i++)
cout<<name[i]<<":"<<Avaliable[i]<<endl;
cout<<"输入系统可用资源[Avaliable]:"<<endl;
cin>>Avaliable[0]>>Avaliable[1]>>Avaliable[2];
cout<<"经修改后的系统可用资源为"<<endl;
for (int k=0;k<N;k++)
cout<<name[k]<<":"<<Avaliable[k]<<endl;
showdata();
safe();
}
void addprocess(){//添加作业
int flag=M;
M=M+1;
cout<<"请输入该作业的最打需求量[Max]"<<endl;
for(int i=0;i<N;i++){
cout<<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;
cout<<"*****************单处理机系统进程调度实现*****************"<<endl;
cout<<"请首先输入系统可供资源种类的数量:";
cin>>n;
N=n;
for(i=0;i<n;i++)
{
cout<<"资源"<<i+1<<"的名称:";
cin>>ming;
name[i]=ming;
cout<<"资源的数量:";
cin>>number;
Avaliable[i]=number;
}
cout<<endl;
cout<<"请输入作业的数量:";
cin>>m;
M=m;
cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)[Max]:"<<endl;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
cin>>Max[i][j];
do{
flag=0;
cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵)[Allocation]:"<<endl;
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)
cout<<"申请的资源大于最大需求量,请重新输入!\n";
}
while(flag);
showdata();//显示各种资源
safe();//用银行家算法判定系统是否安全
while(choice)
{
cout<<"**************银行家算法演示***************"<<endl;
cout<<" 1:增加资源 "<<endl;
cout<<" 2:删除资源 "<<endl;
cout<<" 3:修改资源 "<<endl;
cout<<" 4:分配资源 "<<endl;
cout<<" 5:增加作业 "<<endl;
cout<<" 0:离开 "<<endl;
cout<<"*******************************************"<<endl;
cout<<"请选择功能号:";
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: cout<<"请正确选择功能号(0-5)!"<<endl;break;
}
}
return 1;
}
四、程序运行结果及分析
T0 时刻的资源分配表(各种资源的数量分别为:10、5、7)
运行结果
五、课程设计心得与体会
银行家算法是避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。死锁的产生,必须同时满足四个条件,即一个资源每次只能由一个进程;第二个为等待条件,即一个进程请求资源不能满足时,它必须等待,但它仍继续保持已得到的所有其他资源;第三个为非剥夺条件,即在出现死锁的系统中一定有不可剥夺使用的资源;第四个为循环等待条件,系统中存在若干个循环等待的进程,即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会发生死锁。
六.参考文献:
[1]《计算机操作系统》汤子瀛等:西安电子科技大学出版社
[2]《高级语言c++程序设计》刘璟等:高等教育出版社