资源描述：
《银行家算法的虚拟实现.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、银行家算法的虚拟实现一．设计目的在计算机操作系统中，最有代表的避免死锁的算法，是Dijkstra银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名的。为了加深对该算法的认识和掌握，进而在计算机上实现。为了实现银行家算法，系统中必须设置若干数据结构。二．设计内容银行家算法的解释和给出的初步数组定义为依据，假设系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10，5，7，在T0时刻的资源分配情况如下图所示：资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753
2、322322322P1322200122P2902302600P3222211011P4433002431然后进行T0时刻的安全性检测,进程资源的请求,再次检测系统的安全性等.三．设计要求以人性化的设计要求,使进入该程序的用户得到一的简单明了的界面.可以出现一些提示,让用户作出选择.先输入五个进程和三类资源的数值,然后输入要请求资源的进程号,对其作出判断,进行安全性检测,然后按步骤进行,可选择继续新的进程请求或退出,其中要打印输出多次输入和输出结果.四．算法及流程图1．银行家算法中的数据结构(1)可利用资源向量Available.这是一个含有m个元素的数
3、组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变.(2)最大需求矩阵Max.这是n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求.(3)分配矩阵Allocation.这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数.(4)需求矩阵Need.这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数.上述三个矩阵间存在下述关系:Need[i,j]=Max[i,j]-Allocation[i,j]2．银行家算法设Reques
4、ti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Pj类型的资源.当Pi发出资源请求后,系统按下述步骤进行检查:(1)如果Requesti[j]<=Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超出它所宣布的最大值.(1)如果Requesti[j]<=Available[i,j],便转向步骤3;否则,表示尚无足够资源,Pi须等待.(2)系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:
5、=Allocation[i,j]+Requesti[j]Need[i,j]:=Need[i,j]-Requesti[j];(3)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态.若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待.2．安全性算法系统所执行的安全性算法可描述如下:(1)设置两个向量:1工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work:=Available;2Finish:它表示系统是否有足够的资源
6、分配给进程,使之运行完成.开始时先做Finish[i]:=false;当有足够资源分配给进程时,再令Finish[i]:=true.(2)从进程集合中找到一个能满足下述条件的进程:1Finish[i]:=false;2Need[i,j]<=Work[j];若找到,执行步骤3,否则,执行步骤4.(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:Work[j]:=Work[j]+Allocation[i,j];Finish[i]:=true;gotostep2;(4)如果所有进程的Finish[i]:=true都满足,则表示
7、系统处于安全状态;否则,系统处于不安全状态.五．流程图和输入数据及输出结果（以下四幅图为：五个进程和三类资源的输入，进程请求资源后的结果输出，得到的安全序列和结果输出。）六．程序清单#include#defineN5structbank//定义数结构体{charnum[6];//进程编号intmax[3];//最大需求矩阵intallocation[3];//分配矩阵intneed[3];//需求矩阵intavailable[3];//可利用资源向量intwork[3];//工作向量intwa[3];//work+allocationc
8、harfinish;}bank[N];main(){inti,j,k,numbe
