银行家算法.docx
《银行家算法.docx》由会员分享，可在线阅读，更多相关《银行家算法.docx（16页珍藏版）》请在冰点文库上搜索。
银行家算法
目录
1.绪论2
2.设计目的3
3.设计要求4
4.原理分析4
4.1、银行家算法中的数据结构4
4.2、银行家算法5
4.3、安全性算法5
5.具体设计和程序流程图6
6.程序调试和程序实现7
7.程序源代码9
8.设计小结15
9.谢辞16
10.参考文献16
1.绪论
这次课程设计要求完成一个资源管理系统，该系统必须包括资源的添加、删除和修改等功能，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求，然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。
通过课程设计，加深我们对利用银行家算法避免死锁的理解。
在设计中主要的难点是用语言编写银行家算法和安全性算法，使系统资源分配能安全进行，避免系统死锁。
2.设计目的
在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用提高吞吐量，但可能发生一种危险——死锁。
所谓死锁，是指多个进程运行中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都无法再向前推进。
虽然进程在运行过程中，可能发生死锁，但死锁的发生必须同时具备四个条件：
互斥条件、请求和保持条件、不剥夺条件、环路等待条件；防止死锁的机构只须确保上述四个条件之一不出现，则系统不会发生死锁。
系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁。
所谓安全状态，是指系统能按某种进程顺序（P1，P2，…，Pn），来为每个进程Pi分配其所需分配，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。
如果系统无法找到一个这样地安全系列，则称系统处于不安全状态。
在操作系统中研究资源分配策略时也有类似的问题，系统中有限的资源要供多个进程使用，必须保证得到资源的进程能在有限的时间内归还资源，以供它进程使用资源。
如果资源分配不得当就会发生进程循环等待资源，各进程都无法继续执行下去的死锁现象。
而最有代表性的避免死锁的算法，是Dijkstra的银行家算法。
银行家算法是避免死锁的一种重要方法，在课程设计中用C语言编写一个资源管理系统，并要用银行家算法和安全性算法检查是否允许分配资源给进程，避免死锁。
通过课程设计，加深我们对了解有关资源申请、避免死锁等概念，并加深我们对银行家算法理解。
提高了我们分析、解决问题的能力。
3.设计要求
用所学过的语言编程实现一个资源管理系统，该系统必须包括资源的添加、删除和修改等功能，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求，然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。
4.原理分析
在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。
银行家算法是避免死锁的一种重要方法，为实现银行家算法，系统必须设置若干数据结构。
4.1、银行家算法中的数据结构
1）可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。
如果Available［j］=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。
4）需求矩阵Need。
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。
如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j］
4.2、银行家算法
设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。
当Pi发出资源请求后，系统按下述步骤进行检查：
如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布最大值。
1）如果Requesti［j］≤Available［j］，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。
2）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Requesti［j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］;
3）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
4.3、安全性算法
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都满足，则表示系统处于安全状态；否则，系统处于不安全状态
5.具体设计和程序流程图
在程序中设计五个进程，分别为pr0,pr1,pr2,pr3,pr4。
共享三类资源。
在这个资源管理系统中对进程的所需最大资源（Max）、已分配给当前进程资源（Allocation）和系统可用资源（Available）分别进行了初始化了值。
进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。
要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列，若分配不安全，则释放分配的资源，防止使系统进入不安全状态。
显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。
程序还可以实现对系统的修改。
如果修改系统可用资源（Available），和进程分配资源。
程序具体的设计是：
函数voidshowdata（）用来显示资源矩阵，包括系统可用资源数目，进程对资源最大需求数，系统已分配给进程的资源数，进程还需求资源。
通过以上显示，很直观的观察到资源分配和修改的过程。
函数share（）用来利用银行家算法对某个进程申请资源对进行判定。
函数intchangdata（inti）用来实现资源试探分配。
主要执行的步骤是Avaliable[j]=Avaliable[j]-Request[j]，Allocation[i][j]=Allocation[i][j]+Request[j],Need[i][j]=Need[i][j]-
Request[j]。
函数safe（）用来实现安全性算法，对分配后的资源进行计算，若分配资源后，系统是安全的，则资源完成本次分配。
若不安全将本次的试探分配作废，调用shifang（）函数恢复原来的资源分配状态。
资源修改功能用Revision（）来实现。
6.程序调试和程序实现
为了便于检验程序的正确性，这里用了书上的数据进行了初始化。
程序运行时选择1,输入进程pr1的请求向量（1,0,2）经过程序计算，资源分配成功。
资源具体分配过程如下图所示。
得出一个安全序列为pr1,pr3,pr0,pr2,pr4。
这与书上的有点不同，但经过计算，这也是一个正确的安全序列。
对进程提出的请求向量，系统可能存在多个安全序列。
主要是在安全路径的找算法上。
进程pr0请求资源：
pr0发出请求向量（0,2,0），由于Request0不大于Need0,Request0不大于Available0。
系统试探着为它分配资源。
由结果可知，系统不安全。
则系统不分配资源，并回收系统预分配给pr0的资源。
程序运行时选择2,进行系统资源的修改。
这里选择修改系统可用资源。
修改后的Available为（2,3,2）。
资源修改成功。
7.程序源代码
#include
#include
#defineM5//定义进程数
#defineN3//定义资源数
#defineFalse0
#defineTrue1
intMax[][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
intAvaliable[]={3,3,2};//系统可用资源
intAllocation[][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系统已分配资源
intNeed[][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//还需要资源
intRequest[3];
voidshowdata（）//显示资源矩阵
{
inti,j;
printf（"系统可用的资源:
\n"）;
printf（"resouce:
"）;
for（j=0;jprintf（"%d,",Avaliable[j]）;//输出分配资源
printf（"\n"）;
printf（"各进程的资源需求:
\n"）;
for（i=0;iprintf（"pr%d:
",i）;
for（j=0;jprintf（"%d,",Max[i][j]）;//输出最大需求资源数
}
printf（"\n"）;
}
printf（"各进程得到资源:
\n"）;
for（i=0;iprintf（"pr%d:
",i）;
for（j=0;jprintf（"%d,",Allocation[i][j]）;//输出已分配资源数
printf（"\n"）;
}
printf（"各进程还需求资源:
\n"）;
for（i=0;iprintf（"pr%d:
",i）;
for（j=0;jprintf（"%d,",Need[i][j]）;//输出还需要资源数
printf（"\n"）;
}
}
intchangdata（inti）//进行资源分配
{
intj;
for（j=0;jAvaliable[j]=Avaliable[j]-Request[j];
Allocation[i][j]=Allocation[i][j]+Request[j];
Need[i][j]=Need[i][j]-Request[j];
}
return1;
}
intchkerr（）//安全性算法
{
intWork[3],Finish[M]={0},temp[M];
inti,k=0,m,apply;
intj;
Work[0]=Avaliable[0];Work[1]=Avaliable[1];Work[2]=Avaliable[2];
for（i=0;iapply=0;
for（j=0;j<3;j++）{
if（Finish[i]==False&&Need[i][j]<=Work[j]）{
apply++;
if（apply==3）{
for（m=0;m<3;m++）
Work[m]=Work[m]+Allocation[i][m];//变分配数
Finish[i]=True;
temp[k]=i;
i=-1;
k++;
}
}
else
if（Finish[i]==False）{
if（i==M-1）{
printf（"系统不安全\n"）;//不成功系统不安全
return-1;
}
break;
}
}
}
printf（"系统资源分配成功!
"）;//如果安全，输出成功
printf（"分配的序列:
\n"）;
for（i=0;i{
printf（"pr%d",temp[i]）;
}
return0;
}
voidshare（）//利用银行家算法对申请资源对进行判定
{
charch;
inti=0,j=0;
ch='y';
printf（"\n请输入要求分配的资源进程号从（0to4）:
"）;
scanf（"%d",&i）;//输入须申请的资源号
printf（"请输入进程%d申请的资源:
\n",i）;
for（j=0;j<3;j++）
{
printf（"第%d个资源:
",j+1）;
scanf（"%d",&Request[j]）;//输入需要申请的资源
}
for（j=0;jif（Request[j]>Need[i][j]）//判断申请是否大于需求，若大于则出错
{
printf（"进程%d申请的资源大于它需要的资源",i）;
printf（"error!
\n"）;
ch='n';
break;
}
else{
if（Request[j]>Avaliable[j]）//判断申请是否大于当前资源，若大于则
{//出错
printf（"进程%d申请的资源大于available",i）;
printf（"error!
\n"）;
ch='n';
break;
}
}
}
if（ch=='y'）{
changdata（i）;//根据进程需求量变换资源
showdata（）;//根据进程需求量显示变换后的资源
chkerr（）;//根据进程需求量进行银行家算法判断
}
}
voidRevision（）{
printf（"请选择:
1：
修改进程还需要的资源2：
修改进程可用资源"）;
intchoice1;
scanf（"%d",&choice1）;
if（choice1==1）{
printf（"输入要修改的资源号（0~4）"）;
intp;
scanf（"%d",&p）;
printf（"输入修改后进程还需要的资源（1,1,1）\n"）;
scanf（"%d,%d,%d",&Need[p][0],&Need[p][1],&Need[p][2]）;
printf（"经修改后各进程还需求资源:
\n"）;
for（inta=0;aprintf（"pr%d:
",a）;
for（intb=0;bprintf（"%d,",Need[a][b]）;//输出还需要资源数
printf（"\n"）;
}
}
if（choice1==2）
{
printf（"输入系统可用资源EX（1,1,1）\n"）;
scanf（"%d,%d,%d",&Avaliable[0],&Avaliable[1],&Avaliable[2]）;
printf（"经修改后的系统可用资源为\n"）;
for（intk=0;kprintf（"%d,",Avaliable[k]）;
}
}
intmain（）//主函数
{
printf（"****************银行家算法演示*******************\n"）;
printf（"**************唐建锋＆＆＆＆于东洋***************\n"）;
intchoice;
showdata（）;//显示各种资源
chkerr（）;//用银行家算法判定系统是否安全
do{
printf（"\n输入要进行的操作1：
分配资源2：
修改资源3：
离开"）;
scanf（"%d",&choice）;
if（choice==1）
{
share（）;
}
if（choice==2）
{
Revision（）;
}
if（choice==3）
break;
}while（（choice==1）||（choice==2））;
return1;
}
8.设计小结
一周的操作系统课程设计终于结束了，虽然很忙碌很疲劳，但感觉收获还是蛮大的。
我几乎每天的专注和辛劳，唤回了我对操作系统的重新的认识，在编写程序不断出现错误和改正的过程序中加深了我对银行家算法的理解。
这个系统的功能基本能满足要求，完成了对资源的修改还有用银行家算法和安全性算法来检查是否允许分配资源给进程。
在课程设计的过程中，通过与同组人的相互讨论，很多问题迎刃而解。
让我从中体会到是小组合作的力量。
设计主要由两部分组成。
第一部分:
银行家算法（扫描）
1.如果Request<=Need,则转向2;否则,出错
2.如果Request<=Available,则转向3,否则等待
3.系统试探分配请求的资源给进程
4.系统执行安全性算法
安全性算法
1.设置两个向量
（1）.工作向量:
Work=Available（表示系统可提供给进程继续运行所需要的各类资源数目）
（2）.Finish:
表示系统是否有足够资源分配给进程（True:
有;False:
没有）.初始化为False
2.若Finish[i]=False&&Need<=Work,则执行3;否则执行4（I为资源类别）
3.进程P获得第i类资源,则顺利执行直至完成!
并释放资源:
Work=Work+Allocation;Finish[i]=true;转2
4.若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!
第二部分主要是进行资源的修改。
在这里可以修改资源的可用资源和资源还需求资源。
由于时间有限，还不是很完善，系统还有许多不尽人意的地方。
这些都有待进一步改善
9.谢辞
在操作系统课程的一个星期里,我受到了指导老师张爱萍老师的细心指导,对我能准时完成任务有很大的帮助。
张爱萍严谨的指导态度与深厚的理论知识都让我受益非浅,从她身上我学到了很多的东西,无论是理论还是实践都使我的知识有很大的提高.借此我特提出感谢.我能够顺利地完成本系统的开发.也要感谢本组的于东洋同学,并在程序编写和论文写作过程中提出宝贵的意见和给予无私的帮助，没有他的合作就不会现在的系统。
10.参考文献
[1]汤子赢，哲凤屏，汤小丹.计算机操作系统［M］.西安：
西安电子科技大学出版社，2001.
[2]任满杰，刘树刚，李军红.操作系统原理实用教程［M］.北京：
电子工业出版社，2006.
[3]潭浩强.C程序设计［M］.北京：
清华大学出版社，1999.
升级会员 