银行家算法+银行家算法流程图+具体代码转.docx
《银行家算法+银行家算法流程图+具体代码转.docx》由会员分享，可在线阅读，更多相关《银行家算法+银行家算法流程图+具体代码转.docx（15页珍藏版）》请在冰点文库上搜索。
银行家算法+银行家算法流程图+具体代码转
计算机操作系统>;一书中详细有解.
1.安全状态:
在某时刻系统中所有进程可以排列一个安全序列:
{P1,P2,`````Pn},刚称此时,系统是安全的.
所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi（j<;i）所占的资源之和.
2.不安全状态可能产生死锁.
目前状态最大需求尚需
P1396
P25105
P3242
在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.
3.银行家算法的思路:
1）,进程一开始向系统提出最大需求量.
2）,进程每次提出新的需求（分期贷款）都统计是否超出它事先提出的最大需求量.
3）,若正常,则判断该进程所需剩余剩余量（包括本次申请）是否超出系统所掌握的
剩余资源量,若不超出,则分配,否则等待.
4.银行家算法的数据结构.
1）,系统剩余资源量A[n],其中A[n]表示第I类资源剩余量.
2）,各进程最大需求量,B[m][n],其中B[j][i]表示进程j对i
类资源最大需求.
3）,已分配资源量C[m][n],其中C[j][i]表示系统j程已得到的第i资源的数量.
4）,剩余需求量.D[m][n],其中D[j][i]对第i资源尚需的数目.
5.银行家算法流程:
当某时刻,某进程时,提出新的资源申请,系统作以下操作:
1）,判定E[n]是否大于D[j][n],若大于,表示出错.
2）,判定E[n]是否大于系统剩余量A[n],若大于,则该进程等待.
3）,若以上两步没有问题,尝试分配,即各变量作调整.
4）,按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待.
6.";安全性检测";算法
1）,先定义两个变量,用来表示推算过程的数据.
F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.
J[n]=False表示推算过程中各进程是否假设";已完成";
2）,流程:
在";剩余";的进程中（在推算）过程中,一些进程假设已完成,查找D[j][n]<;=F[n]的进程,找到后令J[j]=True
（假设该进程完成）,F[n]+D[j][n]（该进程所占资源释放）,如此循环执行.
若最后,所有的F[n]=True（在推算过程中,所有进程均可以完成）,则表示（分配过后）系统是安全的,否则系统是不安全的.
算法的实现
一、初始化
由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
二、银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
它是最具有代表性的避免死锁的算法。
设进程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）系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
三、安全性检查算法
（1）设置两个工作向量Work=AVAILABLE;FINISH
（2）从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<;=Work;
如找到，执行（3）；否则，执行（4）
（3）设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work+=ALLOCATION;
Finish=true;
GOTO2
（4）如所有的进程Finish=true，则表示安全；否则系统不安全。
初始化算法流程图：
银行家算法流程图：
安全性算法流程图：
源程序清单
#include<;iostream>;
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<;<;";请输入每个进程最多所需的各资源数,按照";<;<;m<;<;";x";<;<;n<;<;";矩阵输入";<;<;endl;
for（i=0;i<;m;i++）
for（j=0;j<;n;j++）
cin>;>;MAX[i][j];
cout<;<;";请输入每个进程已分配的各资源数,也按照";<;<;m<;<;";x";<;<;n<;<;";矩阵输入";<;<;endl;
for（i=0;i<;m;i++）
{
for（j=0;j<;n;j++）
{
cin>;>;ALLOCATION[i][j];
NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
if（NEED[i][j]<;0）
{
cout<;<;";您输入的第";<;<;i+1<;<;";个进程所拥有的第";<;<;j+1<;<;";个资源数错误,请重新输入:
";<;<;endl;
j--;
continue;
}
}
}
cout<;<;";请输入各个资源现有的数目:
";<;<;endl;
for（i=0;i<;n;i++）
{
cin>;>;AVAILABLE[i];
}
}voidBank（）/*银行家算法*/
{
inti,cusneed;
charagain;
while
（1）
{
cout<;<;";请输入要申请资源的进程号（注:
第1个进程号为0,依次类推）";<;<;endl;
cin>;>;cusneed;
cout<;<;";请输入进程所请求的各资源的数量";<;<;endl;
for（i=0;i<;n;i++）
{
cin>;>;REQUEST[cusneed][i];
}
for（i=0;i<;n;i++）
{
if（REQUEST[cusneed][i]>;NEED[cusneed][i]）
{
cout<;<;";您输入的请求数超过进程的需求量!
请重新输入!
";<;<;endl;
continue;
}
if（REQUEST[cusneed][i]>;AVAILABLE[i]）
{
cout<;<;";您输入的请求数超过系统有的资源数!
请重新输入!
";<;<;endl;
continue;
}
}
for（i=0;i<;n;i++）
{
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
}
if（Safe（））
{
cout<;<;";同意分配请求!
";<;<;endl;
}
else
{
cout<;<;";您的请求被拒绝!
";<;<;endl;
for（i=0;i<;n;i++）
{
AVAILABLE[i]+=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];
NEED[cusneed][i]+=REQUEST[cusneed][i];
}
}
for（i=0;i<;m;i++）
{
FINISH[i]=false;
}
cout<;<;";您还想再次请求分配吗?
是请按y/Y,否请按其它键";<;<;endl;
cin>;>;again;
if（again=='y'||again=='Y'）
{
continue;
}
break;
}
}boolSafe（）/*安全性算法*/
{
inti,j,k,l=0;
intWork[MAXRESOURCE];/*工作数组*/
for（i=0;i<;n;i++）
Work[i]=AVAILABLE[i];
for（i=0;i<;m;i++）
{
FINISH[i]=false;
}
for（i=0;i<;m;i++）
{
if（FINISH[i]==true）
{
continue;
}
else
{
for（j=0;j<;n;j++）
{
if（NEED[i][j]>;Work[j]）
{
break;
}
}
if（j==n）
{
FINISH[i]=true;
for（k=0;k<;n;k++）
{
Work[k]+=ALLOCATION[i][k];
}
p[l++]=i;
i=-1;
}
else
{
continue;
}
}
if（l==m）
{
cout<;<;";系统是安全的";<;<;endl;
cout<;<;";安全序列:
";<;<;endl;
for（i=0;i<;l;i++）
{
cout<;<;p[i];
if（i!
=l-1）
{
cout<;<;";-->;";;
}
}
cout<;<;";";<;<;endl;
returntrue;
}
}
cout<;<;";系统是不安全的";<;<;endl;
returnfalse;
V一．课程设计目的
1.加深对死锁概念的理解。
2.能够利用银行家算法，有效避免死锁的发生，或检测死锁的存在。
二．课程设计摘要
银行家算法：
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。
当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
三．开发环境
系统软件硬件环境
软件：
WindowsXP;VC++6.0
硬件：
Pentium（R）4CPU2.40GHz;512MB内存
四．课程设计原理分析
在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。
所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。
为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防死锁。
最有代表性的避免死锁的方法，是Dijkstra的银行家算法。
银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。
死锁的产生，必须同时满足四个条件，第一个为互斥条件，即一个资源每次只能由一个进程占用；第二个为请求和保持条件，指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。
防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。
通过这个算法可以用来解决生活中的实际问题，如银行贷款等。
银行家算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。
在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。
如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。
把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。
当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。
“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。
显然，，每个进程的资源需求总量不能超过系统拥有的资源总数,银行算法进行资源分配可以避免死锁.
五．银行家算法流程图
图片找不到了，嘿嘿
六．银行家算法中的数据结构
（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个，方能完成其任务。
七．算法描述
1.银行家算法:
设进程i提出请求Request[j]，则银行家算法按如下规则进行判断。
（1）如果Request[j]≤Need[i,j]，则转向
（2），否则认为出错。
（2）如果Request[j]≤Available[j]，则转向（3）；否则表示尚无足够资源，Pi需等待。
（3）假设进程i的申请已获批准，于是修改系统状态：
Available[j]=Available[j]-Request[i]
Allocation[i,j]=Allocation[i,j]+Request[j]
Need[i,j]=Need[i,j]-Request[j]
（4）系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
2.安全性检查
（1）设置两个工作向量Work=Available；Finish[i]=False
（2）从进程集合中找到一个满足下述条件的进程，
Finish[i]=False;
Need[i,j]≤Work[j];
如找到，执行（3）；否则，执行（4）
（3）设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work[j]=Work[i]+Allocation[i,j];
Finish[i]=True;
gotostep2;
（4）如所有的进程Finish[i]=true，则表示安全；否则系统不安全。
八．课程设计内容
利用银行家算法，写一个程序，判定系统的安全性。
已知某系统有5个进程p0，p1，p2，p3，p4，，三类资源A，B，C，资源类A共有17个资源，资源类B共有5个资源，资源类C共有20个资源。
死锁检测程序工作时各进程对资源的需求和占用情况如下表所示：
资源
请求进程最大需求量（Max）已分配资源AllocationABCABCP0559212P1536402P24011405P3425204P4424314
这两天熬夜，从开始写代码的顺利到后来调试时候的繁琐。
我都坚持下来了，上一次做生产者消费者的时候，我最终没有坚持自己独立编写代码，在网上找了一部分的代码作参考。
但是这次，我下定决心要自己独立完成。
终于，完成了。
很欣慰，虽然有点小题大做，但是我觉得学习就得这样。
从基本做起，脚踏实地。
不会就自己钻研。
再不会也要坚持思考。
直到你真的坚持不下来的时候，往往你就能想出解决方法了。
代码写完了，异常处理没怎么去做。
也暂时不想了。
水平只能先暂时到这儿。
代码贴上来，水平有限，欢迎批评指正。
就算被喷口水我也愿意听。
初始化数据需要键入的有（按顺序输入）：
Available:
332
Max:
753322902222433
Allocation:
010200302211002
（1）P1发出请求Request（1,0,2）
（2）P4发出请求Request（3,3,0）
（3）P0发出请求Request（0,2,0）
十．调试数据结果
请输入总进程数：
5
请输入总资源种类：
3
请输入总资源数：
17
5
20
依次输入各进程所需要的最大资源数量：
559
536
4011
425
424
依次输入各进程已经占据的资源数量：
212
402
405
204
214
各种资源的总数量：
资源：
17资源1：
5资源2：
20
系统目前各种资源可用的数为：
资源：
2资源1：
3资源2：
3
各进程还需要的资源量：
资源资源1资源2
进程p0：
347
进程p1：
134
进程p2：
006
进程p3：
221
进程p4：
110
各进程已经得到的资源量:
资源资源1资源2
进程p0：
212
进程p1：
402
进程p2：
405
进程p3：
204
进程p4：
314
请输入需申请资源的进程号（从p0到p4，否则重输入！
）：
p2
请输入进行p2申请的资源数：
资源：
资源1：
3
进程p2申请的资源数大于进程p2还需要一类资源的资源量！
申请不合理，出错！
请重新选择！
各进程还需要的资源量：
资源资源1资源2
进程p0：
347
进程p1：
134
进程p2：
006
进程p3：
221
进程p4：
110
各进程已经得到的资源量:
资源资源1资源2
进程p0：
212
进程p1：
402
进程p2：
405
进程p3：
204
进程p4：
314
是否继续银行家算法演示，按’Y’或’y’键继续，按’N’或’n’键推出演示：
y
请输入需申请资源的进程号（从p0到p4，否则重输入！
）：
p2
请输入进行p2申请的资源数：
资源：
资源1：
资源2：
2
经安全性检查，系统安全，本次分配成功。
十一．心得体会
看到课程设计的题目是银行家算法，首先就先给自己整理了下这次课程设计的计划，因为要编程，所以在网上、书本上查了很多与银行家算法相关的资料，比如资源分配，随机分配算法。
这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，了解到一些书本上没有的知识，也知道要做一个课程设计，如果知识面只是停留在书本上，是不可能把课成设计完全地做好。
用VC++6.0编程，感觉自己有点力不从心，很多C语言的知识都忘了，只好翻出以前的C语言课本和数据结构来复习。
其实如果不经常动手实践学习的话，对于像这种编程类的设计是很难熟练掌握的，从每次的课程设计中虽然都能将以前的知识顺便再复习一遍，但如果平时不训练积累的话还是很容易忘的，课程设计是给了我们一个机会去复习，同时也是提醒我们应该注重平时的积累。
从课程设计以后还是要多多的动手，在实践中体会理论知识，这样才不会在要做实验和设计时，觉得无从下手。
在这次编程中，我得到了很多。
遇到问题时，和同学一块商量，一起努力！
也了解到同学的想法，大家的思想都得到了交流。
本次课程设计最大的体会是动手能力有了很大的提高，希望我能在今后的学习和实践中能更加熟练掌握编程能力。
升级会员 