银行家算法实验报告格式.docx
《银行家算法实验报告格式.docx》由会员分享，可在线阅读，更多相关《银行家算法实验报告格式.docx（18页珍藏版）》请在冰点文库上搜索。
银行家算法实验报告格式
2011-2012学年第一学期
计算机操作系统实验报告
专业：
软件工程
班级：
0910XX班
学号：
XXXXXXXX
姓名：
XXX
提交日期：
201X年XX月
实验三银行家算法模拟
【开发语言及实现平台或实验环境】
C++/C#
MicrosoftVisualStudio6.0/MicrosoftVisualStudio.NET2003
【实验目的】
（1）进一步理解利用银行家算法避免死锁的问题；
（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。
（3）理解和掌握安全序列、安全性算法
【实验要求】
（1）了解和理解死锁；
（2）理解利用银行家算法避免死锁的原理；
（3）会使用某种编程语言。
【实验原理】
一、安全状态
指系统能按照某种顺序如（称为序列为安全序列），为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。
二、银行家算法
假设在进程并发执行时进程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;
Øgotostep2;
（4）如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
【实验步骤】
参考实验步骤如下：
（1）参考图1-1所示流程图编写安全性算法。
（2）编写统一的输出格式。
每次提出申请之后输出申请成功与否的结果。
如果成功还需要输出变化前后的各种数据，并且输出安全序列。
（3）参考图1-2所示流程图编写银行家算法。
（4）编写主函数来循环调用银行家算法。
【思考题】
（1）在编程中遇到了哪些问题？
你是如何解决的？
（2）在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？
答：
Available是当前各资源的剩余序列，work将收集满足finished[i]为true归还的各类资源
【模拟代码】
#include
#include
#defineM3//资源的种类数
#defineN5//进程的个数
voidoutput（intiMax[N][M],intiAllocation[N][M],intiNeed[N][M],intiAvailable[M],charcName[N]）;//统一的输出格式
boolsafety（intiAllocation[N][M],intiNeed[N][M],intiAvailable[M],charcName[N]）;
boolbanker（intiAllocation[N][M],intiNeed[N][M],intiAvailable[M],charcName[N]）;
intrequest（charcName[N],intiRequest[M]）;
intmain（）
{
inti,j;
//当前可用每类资源的资源数
intiAvailable[M]={3,3,2};
//系统中N个进程中的每一个进程对M类资源的最大需求
intiMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
//iNeed[N][M]每一个进程尚需的各类资源数
//iAllocation[N][M]为系统中每一类资源当前已分配给每一进程的资源数
intiNeed[N][M],iAllocation[N][M]={{0,1,1},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
//进程名
charcName[N]={'a','b','c','d','e'};
boolbExitFlag=true;//退出标记
charch;//接收选择是否继续提出申请时传进来的值
boolbSafe;//存放安全与否的标志
//计算iNeed[N][M]的值
for（i=0;ifor（j=0;jiNeed[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";
}
}
return0;
}
//输出
voidoutput（intiMax[N][M],intiAllocation[N][M],intiNeed[N][M],intiAvailable[M],charcName[N]）
{
inti,j;
cout<<"\n\tMax\tAllocation\tNeed\tAvailable"<cout<<"\tABC\tABC\tABC\tABC"<for（i=0;i{
cout<for（j=0;jcout<cout<<"\t";
for（j=0;jcout<cout<<"\t";
for（j=0;jcout<cout<<"\t";
cout<<"";
//Available只需要输出一次
if（i==0）
for（j=0;jcout<cout<}
}
//安全性算法，进行安全性检查；安全返回true，并且输出安全序列，不安全返回false，并输出不安全的提示；
boolsafety（intiAllocation[N][M],intiNeed[N][M],intiAvailable[M],charcName[N]）
{
intbflag=0;//能够有足够资源分配的进程个数
intcount=0;//安全性序列的数组下标
intiWork[M];//系统可提供给进程继续运行所需的各类资源数目数组
for（inta=0;aintiFinish[N]={0,0,0,0,0};//Finish[N]它表示系统是否有足够的资源分配给进程，使之运行完成,开始时先令Finish=false
intn=N;
while（n--）//循环判断，最多循环N（进程数）次
{
for（inti=0;i{
intflag=1;
if（iFinish[i]==0）
{
for（intj=0;j{
if（iNeed[i][j]>iWork[j]）
{
flag=0;
break;
}
}
if（flag）
{
for（intj=0;jiWork[j]=iWork[j]+iAllocation[i][j];
iFinish[i]=1;
switch（i）//判断安全序列
{
case0:
{cName[count]='a';count++;break;}
case1:
{cName[count]='b';count++;break;}
case2:
{cName[count]='c';count++;break;}
case3:
{cName[count]='d';count++;break;}
case4:
{cName[count]='e';count++;break;}
}
}
}
}
}
for（inti=0;i<=N;i++）//判断iFinish是不是全为true
{
if（iFinish[i]==0）
bflag++;
}
if（bflag==0）
{
cout<<"当前系统状态安全，找到的安全序列为：
"<for（intm=0;mcout<cout<returntrue;
}
else
{
cout<<"未找到安全序列，系统处于不安全状态！
"<returnfalse;
}
}
boolbanker（intiAllocation[N][M],intiNeed[N][M],intiAvailable[M],charcName[N]）
{
intflag=1;//安全标志
intiRequest[M];
intna=request（cName,iRequest）;
for（intj=0;j{
if（iRequest[j]>iNeed[na][j]）
{
flag=0;break;
}
}
if（flag）
{
for（intj=0;j{
if（iRequest[j]>iAvailable[j]）
{flag=0;break;}
}
}
if（flag）//系统试探着把资源分配给进程i
{
for（intj=0;j{
iAvailable[j]=iAvailable[j]-iRequest[j];
iAllocation[na][j]=iAllocation[na][j]+iRequest[j];
iNeed[na][j]=iNeed[na][j]-iRequest[j];
}
if（safety（iAllocation,iNeed,iAvailable,cName））//执行安全性算法
{//cout<<"申请成功"<//output（iMax,iAllocation,iNeed,iAvailable,cName）;
returntrue;
}
else
{
cout<<"申请不成功,资源恢复原来的分配状态"<for（intj=0;j{
iAvailable[j]=iAvailable[j]+iRequest[j];
iAllocation[na][j]=iAllocation[na][j]-iRequest[j];
iNeed[na][j]=iNeed[na][j]+iRequest[j];
}
//output（iMax,iAllocation,iNeed,iAvailable,cName）;
returnfalse;
}
}
else
{
cout<<"申请不成功,资源恢复原来的分配状态"<///output（iMax,iAllocation,iNeed,iAvailable,cName）;
returnfalse;
}
}
intlocate（charcName[N],charch）
{
inti;
for（i=0;iif（cName[i]==ch）//找到
returni;
//未找到
return-1;
}
//提出申请,返回提出申请的进程名对应的下标
intrequest（charcName[N],intiRequest[M]）
{
inti,loc;
charch;
boolbFlag=true;
//判断输入的进程名是否有误
while（bFlag）
{
//输出进程名
for（i=0;icout<//输入提出申请的进程名
cout<<"\n输入提出资源申请的进程名：
\n";
cin>>ch;
//定位ch对应的进程名在进程名数组中的位置
loc=locate（cName,ch）;
//没找到，重新输入
if（loc==-1）
cout<<"\n您输入的进程名有误！
请重新输入";
//找到，退出循环
else
bFlag=false;
}
//输入提出申请的资源数
cout<<"输入申请各类资源的数量：
\n";
for（i=0;icin>>iRequest[i];
//返回提出申请的进程名对应的下标
returnloc;
}
【实验结果】
实验运行时,当前系统状态安全,且找到了一个安全序列（bdeac）,再执行银行家算法，模拟进程b提出资源请求（各资源序列为（1,1,1）），如图，此时又得到一个安全序列（debca）,如下图：
再在此基础上模拟e进程申请（2,2,1）资源序列，看到申请资源不成功。
不存在安全序列，返回到申请前状态，如图：
又尝试模拟d进程申请（0,1,1）的资源序列，此时存在一个安全序列（bdeac）,如图：
升级会员 