死锁-银行家算法实验报告.doc
《死锁-银行家算法实验报告.doc》由会员分享,可在线阅读,更多相关《死锁-银行家算法实验报告.doc(10页珍藏版)》请在冰点文库上搜索。
一、实验目的
银行家算法是避免死锁的一种重要方法。
通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法
二、实验要求
根据银行家算法的基本思想,编写和调试一个实现动态资源分配的模拟程序,并能够有效地防止和避免死锁的发生。
(1)设计思想说明
设计银行家算法是为了避免死锁
三、实验方法内容
1.算法设计思路
银行家算法又称“资源分配拒绝”法,其基本思想是,系统中的所有进程放入进程集合,在安全状态下系统受到进程的请求后试探性的把资源分配给他,现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较,找出剩余资源能满足最大需求量的进程,从而保证进程运行完成后还回全部资源。
这时系统将该进程从进程集合中将其清除。
此时系统中的资源就更多了。
反复执行上面的步骤,最后检查进程的集合为空时就表明本次申请可行,系统处于安全状态,可以实施本次分配,否则,只要进程集合非空,系统便处于不安全状态,本次不能分配给他。
请进程等待
2.算法流程图
3.算法中用到的数据结构
数据结构的说明
1.可利用资源向量AVAILABLE。
这是一个含有M个元素的数组,其中的每一个元素代表一类可利用的资源数目,其3初始值是系统中所配置的该类全部可哦那个资源的数目,其数值随该类资源的分配和回收而动态的改变。
2.最大需求矩阵MAX。
这是一个M*N的矩阵,它定义了系统中N个进程中的每一个进程对M类资源的最大需求。
3.分配矩阵ALLOCATION。
这也是一个M*N的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。
4.需求矩阵NEED。
这也是一个M*N的矩阵,用以表示每一个进程尚需的各类资源数。
5.NEED[R,W]=MAX[R,W]-ALLOCATION[R,W]
4.主要的常量变量
#defineW10//最大进程数W=10
#defineR20//最大资源总数R=20
intAVAILABLE[R];//可利用资源向量
intMAX[W][R];//最大需求矩阵
intALLOCATION[W][R];//分配矩阵
intNEED[W][R];//需求矩阵
intRequest[R];//进程请求向量
voidchangdata(intk);//进程请求资源数据改变
intchksec(ints);//系统安全性的检测
5.主要模块
voidinputdata()
voidshowdata()
voidchangdata(intk)
voidrestoredata(intk)
intchksec(ints)
intchkmax(ints)
四、实验代码
#include
#include
#defineFALSE0
#defineTRUE1
#defineW10//最大进程数W=10
#defineR20//最大资源总数R=20
intM;
intN;
intALL_RESOURCE[W];
intAVAILABLE[R];//可利用资源向量
intMAX[W][R];//最大需求矩阵
intALLOCATION[W][R];//分配矩阵
intNEED[W][R];//需求矩阵
intRequest[R];//进程请求向量
voidinputdata();//数据输入
voidshowdata();//数据显示
voidchangdata(intk);//进程请求资源数据改变
voidrestoredata(intk);//数据恢复
intchksec(ints);//系统安全性的检测
intchkmax(ints);//检测最大需求
voidbank();//检测分配的资源是否合理
voidmain()
{inti,j;
inputdata();
for(i=0;i{ j=chksec(i);
if(j==0)break;
}
if(i>=M)
cout<<"错误提示:
经安全性检查发现,系统的初始状态不安全!
!
!
\n"<else
{cout<<"提示:
经安全性检查发现,系统的初始状态安全!
"< bank();
}
}
voidinputdata()
{ inti=0,j=0,p;
cout<<"请输入总进程数:
"<do{
cin>>M;
if(M>W)cout<"<}while(M>W);
cout<cout<<"请输入资源的种类数:
"<do{cin>>N;
if(N>R)
cout<"<R);
cout<cout<<"请依次输入各类资源的总数量,即设置向量all_resource:
"<for(i=0;i>ALL_RESOURCE[i];
cout<cout<<"请依次输入各进程所需要的最大资源数量,即设置矩阵max:
"<for(i=0;i{
for(j=0;j{
do{cin>>MAX[i][j];
if(MAX[i][j]>ALL_RESOURCE[j])
cout<"<ALL_RESOURCE[j]);
}
}
cout<cout<<"请依次输入各进程已经占据的各类资源数量,即设置矩阵allocation:
"<for(i=0;i{
for(j=0;j {
do{ cin>>ALLOCATION[i][j];
if(ALLOCATION[i][j]>MAX[i][j])
cout<"< }while(ALLOCATION[i][j]>MAX[i][j]);
}
}
cout<for(i=0;i for(j=0;j NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
for(j=0;j{ p=ALL_RESOURCE[j];
for(i=0;i {p=p-ALLOCATION[i][j];
AVAILABLE[j]=p;
if(AVAILABLE[j]<0)
AVAILABLE[j]=0;
}
}
}
voidshowdata()
{inti,j;
cout<<"各种资源的总数量,即向量all_resource为:
"<cout<<"";
for(j=0;j cout<<"资源"<"<cout<cout<<"当前系统中各类资源的可用数量,即向量available为:
"<cout<<"";
for(j=0;j cout<<"资源"<"<cout<cout<<"各进程还需要的资源数量,即矩阵need为:
"<for(i=0;i{cout<<"进程P"<
";
for(j=0;j cout<cout<}
cout<cout<<"各进程已经得到的资源量,即矩阵allocation为:
"<for(i=0;i{ cout<<"进程P"<
";
for(j=0;j cout< cout<}cout<}
voidchangdata(intk)
{ intj;
for(j=0;j {
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];
}
}
voidrestoredata(intk)
{
intj;
for(j=0;j { AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j];
}
}
intchksec(ints)
{
intWORK,FINISH[W];
inti,j,k=0;
for(i=0;i FINISH[i]=FALSE;
for(j=0;j { WORK=AVAILABLE[j];
i=s;
do
{ if(FINISH[i]==FALSE&&NEED[i][j]<=WORK)
{
WORK=WORK+ALLOCATION[i][j];
FINISH[i]=TRUE;
i=0;
}else
{ i++;
}
}while(ifor(i=0;i if(FINISH[i]==FALSE)
{ return1;
}
}return0;
}
intchkmax(ints)
{intj,flag=0;
for(j=0;j {
if(MAX[s][j]==ALLOCATION[s][j])
{flag=1;
AVAILABLE[j]=AVAILABLE[j]+MAX[s][j];
MAX[s][j]=0;
}
} returnflag;
}
c
{
inti=0,j=0;
charflag='Y';
while(flag=='Y'||flag=='y')
{
i=-1;
while(i<0||i>=M)
{cout<<"请输入需申请资源的进程号(从P0到P"<):
";
cout<<"p";
cin>>i;
if(i<0||i>=M)
cout<<"输入的进程号不存在,重新输入!
"< }
cout<<"请输入进程P"<
"< for(j=0;j { cout<<"资源"<";
cin>>Request[j];
if(Request[j]>NEED[i][j])
{cout<<"进程P"<
";
cout<<"申请不合理,出错!
请重新选择!
"< flag='N';
break;
}
else
{ if(Request[j]>AVAILABLE[j])
{cout<<"进程P"<
";
cout<<"申请不合理,出错!
请重新选择!
"< flag='N';
break;
}
}
}
if(flag=='Y'||flag=='y')
{ changdata(i);
if(chksec(i))
{cout< cout<<"该分配会导致系统不安全!
!
!
本次资源申请不成功,不予分配!
!
!
"< cout< restoredata(i);
}
else
{cout< cout<<"经安全性检查,系统安全,本次分配成功,且资源分配状况如下所示:
"< cout< showdata();
if(chkmax(i))
{cout<<"在资源分配成功之后,由于该进程所需的某些资源的最大需求量已经满足,"< cout<<"因此在进程结束后系统将回收这些资源!
"<cout<<"在资源收回之后,各进程的资源需求和分配情况如下所示:
"< showdata();
}
}
}
cout< cout<<"是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示:
";
cin>>flag;}
}
五、实验结果
1.执行结果
2.结果分析
银行家算法就是当接收到一个系统资源的分配后找到一个安全序列,使得进程间不会发生死锁,若发生死锁则让进程等待。
六、实验总结
通过本次银行家算法实验,加深了我对银行家算法的了解,掌握了如何利用银行家算法避免死锁。
实验中遇到点问题,通过查阅资料、询问老师顺利解决。
通过这次的实践,使我的理论知识更加的牢固。