操作系统银行家算法实验报告.doc

2011-2012学年第一学期
计算机操作系统实验报告

专 业：软件工程
班 级：091031
学 号：09103130
姓 名：李若
提交日期：2011年12月6日

实验三 银行家算法模拟

【开发语言及实现平台或实验环境】
C++/C#
Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003

【实验目的】
（1）进一步理解利用银行家算法避免死锁的问题；
（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。
（3）理解和掌握安全序列、安全性算法

【实验要求】
（1）了解和理解死锁；
（2）理解利用银行家算法避免死锁的原理；
（3）会使用某种编程语言。

【实验原理】
一、安全状态
指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。
二、银行家算法
假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：
（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。
（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。
（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Requesti[j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］;
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
三、安全性算法
（1）设置两个向量：
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;
② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。
（2）从进程集合中找到一个能满足下述条件的进程：
① Finish［i］=false;
② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。
（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Ø Work［j］∶=Work［i］+Allocation［i,j］;
Ø Finish［i］∶=true;
Ø go to step 2;
（4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

【实验步骤】
参考实验步骤如下：
（1）参考图1-1所示流程图编写安全性算法。
N
Y
所有finish都为true？
输出安全序列
N
Y
N
存在Finish[i] =false
&&Need[i][j]<= Available[j]
初始化Work和Finish
Finish[i]=true，Work[j]=Work[j]+ Allocation[i][j]
所有进程都找完了？
Y
开始
图1-1 安全性算法流程图
输出系统不安全

（2）编写统一的输出格式。
每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。
（3）参考图1-2所示流程图编写银行家算法。
（4）编写主函数来循环调用银行家算法。

【思考题】
（1）在编程中遇到了哪些问题？你是如何解决的？
在本次编程的过程中，在实现安全性算法和银行家算法的问题上遇到了困难，但是通过对各个算法的进一步理解克服了这些困难。
（2）在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？
设置一个临时变量就是为了在不安全的情况下破坏数据原值。如果不安全的话就不改变Available的值，这样就能使程序更加安全。

结束
否
是
申请失败。
以上分配作废，恢复原来的分配状态：
Available[j] = Available[j] + Requesti[j]
Allocation[i][j]= Allocation[i][j]－Requesti[j]
Need[i][j] = Need[i][j]+Requesti[j]

N
Y
N
Y
Requesti[j]> Need[i][j]
出错返回：return(error)
Requesti[j]> Available[j]
出错返回：(进程阻塞)
return(error)
Available[j] = Available[j] – Requesti[j]
Allocation[i][j]= Allocation[i][j] + Requesti[j]
Need[i][j] = Need[i][j] – Requesti[j]
假定分配：
输入初始参数（资源分配及请求情况）
开始
假定分配之后，系统安全吗？
申请成功。输出各种数据的变化
图1-2银行家算法流程图

【参考代码】
部分参考代码如下：
#include <iostream.h>
#include <string.h>

#define M 3 //资源的种类数
#define N 5 //进程的个数

void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]); //统一的输出格式
bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);
bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);

void main()
{
int i,j;
//当前可用每类资源的资源数
int iAvailable[M]={3,3,2};
//系统中N个进程中的每一个进程对M类资源的最大需求
int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
//iNeed[N][M]每一个进程尚需的各类资源数
//iAllocation[N][M]为系统中每一类资源当前已分配给每一进程的资源数
int iNeed[N][M],iAllocation[N][M]={{0,1,1},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
//进程名
char cName[N]={'a','b','c','d','e'};
bool bExitFlag=true; //退出标记
char ch; //接收选择是否继续提出申请时传进来的值

bool bSafe; //存放安全与否的标志
//计算iNeed[N][M]的值
for(i=0;i<N;i++)
for(j=0;j<M;j++)
iNeed[i][j]=iMax[i][j]-iAllocation[i][j];
//输出初始值
output(iMax,iAllocation,iNeed,iAvailable,cName);
//判断当前状态是否安全
bSafe=safety(iAllocation,iNeed,iAvailable,cName);

//是否继续提出申请
while(bExitFlag)
{
cout<<"\n"<<"继续提出申请？\ny为是；n为否。\n";
cin>>ch;
switch(ch)
{
case 'y':
//cout<<"调用银行家算法";
bSafe=banker(iAllocation,iNeed,iAvailable,cName);
if (bSafe) //安全，则输出变化后的数据
output(iMax,iAllocation,iNeed,iAvailable,cName);
break;
case 'n':
cout<<"退出。\n";
bExitFlag=false;
break;
default:
cout<<"输入有误，请重新输入：\n";
}
}
}

//输出
void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])
{
int i,j;

cout<<"\n\t Max \tAllocation\t Need \t Available"<<endl;
cout<<"\tA B C\tA B C\tA B C\t A B C"<<endl;

for(i=0;i<N;i++)
{
cout<<cName[i]<<"\t";

for(j=0;j<M;j++)
cout<<iMax[i][j]<<" ";
cout<<"\t";

for(j=0;j<M;j++)
cout<<iAllocation[i][j]<<" ";
cout<<"\t";

for(j=0;j<M;j++)
cout<<iNeed[i][j]<<" ";
cout<<"\t";
cout<<" ";

//Available只需要输出一次
if (i==0)
for(j=0;j<M;j++)
cout<<iAvailable[j]<<" ";

cout<<endl;
}
}

//安全性算法，进行安全性检查；安全返回true，并且输出安全序列，不安全返回false，并输出不安全的提示；
bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])
{
int i,j,flag,x=0;
char num[5];
int Work[M];
bool Finish[N]; //定义基本变量

for(j=0;j<3;j++)
Work[j]=iAvailable[j]; //将iAvailable的值赋给Work

for(i=0;i<5;i++) //将Finish全部置为False
Finish[i]=false;

while(true) //执行无限循环，满足条件时跳出
{
flag=0; //每次循环开始时将记录本次循环中是否有使有满足条件iAllocation的标志置为0，若为0表示不存在，若不为0表示存在
for(i=0;i<5;i++) //执行循环，看有没有满足条件的iAllocation
{
if(Finish[i]==false&&Work[0]>=iNeed[i][0]&&Work[1]>=iNeed[i][1]&&Work[2]>=iNeed[i][2])
{
for(j=0;j<3;j++)
{
Work[j]+= iAllocation[i][j] ; //Work[j]+= Work[j]+iAllocation[i][j]
}
Finish[i]=true; //将 Finish置true
flag++; //标志加1
num[x++]=cName[i]; //将该序列名赋给数组num[]
}
}

if(flag==0)
{
cout<<"无安全序列"; //标志为0，证明已无满足条件iAllocation ，退出循环，返回false
return false;
}

if(Finish[0]==true&&Finish[1]==true&&Finish[2]==true&&Finish[3]==true&&Finish[4]==true) //若所有Finish置为true，输出安全数列，返回True
{
cout<<"\n";
cout<<"安全序列为：";
for(x=0;x<5;x++)
cout<<num[x]<<" ";
cout<<"\n";
return true;
}

}
return true;
}

//安全返回true，不安全返回false
bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])
{
int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
int t,i,Request[3],check_1[3];
char x; //定义变量

cout<<"请输入进程名："; //输入进程名
cin>>x;
if(x=='a')i=0;
if(x=='b')i=1;
if(x=='c')i=2;
if(x=='d')i=3;
if(x=='e')i=4;

cout<<"请输入各资源数量："; //输入变量名
for(t=0;t<3;t++)
cin>>Request[t];

for(t=0;t<3;t++) //检查数值
{
check_1[t]=Request[t]+iAllocation[i][t];
}
for(t=0;t<3;t++)
{
if((iMax[i][t]-check_1[t])<0)
{
cout<<"\n资源申请超过最大需求量！！！\n";
return false;
}
}

for(t=0;t<3;t++) //检查数值
{
if((iAvailable[t]-Request[t])<0)
{
cout<<"\n不能满足进程！！！\n";
return false;
}
}

for(t=0;t<3;t++) //将该变量的 iAvailable、iAllocation、iNeed重新赋值
{
iAvailable[t]-=Request[t];
iAllocation[i][t]+=Request[t];
iNeed[i][t]-=Request[t];
}
safety(iAllocation,iNeed,iAvailable,cName); //执行安全数列算法
return true;
return true;
}

【参考界面】