银行家算法.docx
《银行家算法.docx》由会员分享,可在线阅读,更多相关《银行家算法.docx(12页珍藏版)》请在冰点文库上搜索。
银行家算法
编程序模拟银行家算法
1.引言
为了提高资源利用率,应采用动态分配资源的方法。
但是,为了避免可能产生的死锁,在进行资源分配时,应采用某种算法来预测是否有可能发生死锁,若存在可能性,就拒绝企图获得资源的请求。
预防死锁和避免死锁的不同在于,前者所采用的分配策略本身就否定了必要条件之一,这样就保证死锁不可能发生;而后者是在动态分配资源的策略下采用某种算法来预防可能发生的死锁,从而拒绝可能引起死锁的其个资源请求,银行家算法是避免死锁的一种重要方法。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
它是最具有代表性的避免死锁的算法。
2.算法的原理
银行家算法是一种最有代表性的避免死锁的算法。
要解释银行家算法,必须先解释操作系统安全状态和不安全状态。
安全状态:
如果存在一个由系统中所有进程构成的安全序列P1,…,Pn,则系统处于安全状态。
安全状态一定是没有死锁发生。
不安全状态:
不存在一个安全序列。
不安全状态不一定导致死锁。
那么什么是安全序列呢?
安全序列:
一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j
操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。
当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。
3.算法的实现
3.1初始化
由用户输入数据,分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
3.2算法思想
在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST[i],则银行家算法按如下规则进行判断。
(1)如果REQUEST[cusneed][i]<=NEED[cusneed][i],则转
(2);否则出错。
(2)如果REQUEST[cusneed][i]<=AVAILABLE[cusneed][i],则转(3);否则出错。
(3)系统试探分配资源,修改相关数据:
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。
3.3程序流程图
3.4安全性检查算法
(1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程,
FINISH==false;
NEED<=Work;
如找到,执行(3);否则,执行(4)
(3)设进程获得资源,可顺利执行,直至完成,从而释放资源。
Work+=ALLOCATION;
Finish=true;
GOTO2
(4)如所有的进程Finish=true,则表示安全;否则系统不安全。
3.5定义全局变量
intAvailable[x];//各种资源可利用的数量
intAllocation[y][y];//各进程当前已分配的资源数量
intMax[y][y];//各进程对各类资源的最大需求数
intNeed[y][y];//还需求矩阵
intRequest[x];//申请各类资源的数量
intWork[x];//工作向量,表系统可提供给进程运行所需各类资源数量
intFinish[y];//表系统是否有足够的资源分配给进程,0为否,1为是
4.程序代码
#include
usingnamespacestd;
#defineMAXPROCESS50 /*最大进程数*/
#defineMAXRESOURCE100 /*最大资源数*/
intAVAILABLE[MAXRESOURCE]; /*可用资源数组*/
intMAX[MAXPROCESS][MAXRESOURCE]; /*最大需求矩阵*/
intALLOCATION[MAXPROCESS][MAXRESOURCE]; /*分配矩阵*/
intNEED[MAXPROCESS][MAXRESOURCE]; /*需求矩阵*/
intREQUEST[MAXPROCESS][MAXRESOURCE]; /*进程需要资源数*/
boolFINISH[MAXPROCESS]; /*系统是否有足够的资源分配*/
intp[MAXPROCESS]; /*记录序列*/
intm,n; /*m个进程,n个资源*/
voidInit();
boolSafe();
voidBank();
intmain()
{ Init();
Safe();
Bank();
}
voidInit() /*初始化算法*/
{ inti,j;
cout<<"请输入进程的数目:
";
cin>>m;
cout<<"请输入资源的种类:
";
cin>>n;
cout<<"请输入每个进程最多所需的各资源数,按照"< for(i=0;i for(j=0;j cin>>MAX[i][j];
cout<<"请输入每个进程已分配的各资源数,也按照"< for(i=0;i { for(j=0;j {cin>>ALLOCATION[i][j];
NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
if(NEED[i][j]<0)
{cout<<"您输入的第"<
"< j--;
continue;
}
}
}
cout<<"请输入各个资源现有的数目:
"< for(i=0;i {cin>>AVAILABLE[i];
}
}
voidBank() /*银行家算法*/
{inti,cusneed;
charagain;
while
(1)
{cout<<"请输入要申请资源的进程号(注:
第1个进程号为0,依次类推)"< cin>>cusneed;
cout<<"请输入进程所请求的各资源的数量"< for(i=0;i {cin>>REQUEST[cusneed][i];
}
for(i=0;i {if(REQUEST[cusneed][i]>NEED[cusneed][i])
{cout<<"您输入的请求数超过进程的需求量!
请重新输入!
"< continue;
}
if(REQUEST[cusneed][i]>AVAILABLE[i])
{cout<<"您输入的请求数超过系统有的资源数!
请重新输入!
"< }
}
for(i=0;i { AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
}
if(Safe())
{cout<<"同意分配请求!
"< }
else
{cout<<"您的请求被拒绝!
"< for(i=0;i {AVAILABLE[i]+=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];
NEED[cusneed][i]+=REQUEST[cusneed][i];
}
}
for(i=0;i {FINISH[i]=false;
}
cout<<"您还想再次请求分配吗?
是请按y/Y,否请按其它键"< cin>>again;
if(again=='y'||again=='Y')
{continue;
}
break;
}
}
boolSafe() /*安全性算法*/
{
inti,j,k,l=0;
intWork[MAXRESOURCE]; /*工作数组*/
for(i=0;i Work[i]=AVAILABLE[i];
for(i=0;i {
FINISH[i]=false;
}
for(i=0;i {
if(FINISH[i]==true)
if(NEED[i][j]>Work[j])
{
break;
}
}
if(j==n)
{
FINISH[i]=true;
for(k=0;k {
Work[k]+=ALLOCATION[i][k];
}
p[l++]=i;
i=-1;
}
else
{continue;
}
}
if(l==m)
{cout<<"系统是安全的"< cout<<"安全序列:
"< for(i=0;i {
cout<
if(i!
=l-1)
{
cout<<"-->";
}
}
cout<<""< returntrue;
}
}
cout<<"系统是不安全的"< returnfalse;
}
4.程序测试
5.设计体会
经过几天的自己动手练习,对操作系统的掌握又进了一步,收获了很多课堂上和书上未出现过的或老师未讲到的一些知识。
在完成实验的过程中,进行了反复的修改和调试,这次实验,让我基本上明白了银行家算法的基本原理,加深了对课堂上知识的理解,也懂得了如何让银行家算法实现,但编程功底的原因使程序很是繁琐。
这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题,先用银行家算法给其中一个进程分配资源,看它所请求的资源是否大于它的需求量,才和系统所能给的资源相比较.让进程形成一个安全队列,看系统是否安全.再利用安全性算法检查此时系统是否安全。
要做一个课程设计,如果知识面只是停留在书本上,是不可能把课成设计完全地做好。
用VC++6.0编程,感觉自己有点力不从心,很多C语言的知识都忘了,只好翻出以前的C语言课本和数据结构来复习。
每次的课程设计中都能将以前的知识顺便再复习一遍,课程设计是给了我们一个机会去动手和主动复习,同时也是提醒我们应该注重平时的积累。
从课程设计以后还是要多多的动手,在实践中体会理论知识,这样才不会在要做实验和设计时,觉得无从下手。
感谢赵老师一周的幸苦指导。
参考文献
[1]庞丽萍.《操作系统原理》[M].武汉:
华中科技大学出版社,2008
[2]杨树青,王欢.《Linux环境下C编程指南》[M].北京:
清华大学出版社,2007
[3]陈维兴,林小茶.《C++面对对象程序设计教程》[M].北京:
清华大学出版社,2004
[4]杨路明.《C语言程序设计教程》[M].北京:
北京邮电大学出版社,2005
设计过程中质疑(或答辩)记载:
1.银行家算法的主要问题是什么?
答:
要求每个进程必须事先知道资源的最大需求量,而且,在系统运行过程中,考查每个进程对各类资源的申请需花费较多的时间。
2.银行家算法的主要思想是什么?
答:
一个进程进入系统时分配资源之前,判断系统是否是安全的,即看它所请求的资源是否大于它的最大需求量,若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待。
3.系统已分配资源、可利用资源和还需求资源之间的关系
答:
Available[i]=available[i]-request[i]
Allocation[i]=allocation[i]+request[i]
Need[i]=need[i]-request[i]
指导教师评语:
签名:
年月日