银行家算法课程设计报告

《操作系统原理》课程设计报告1设计目的（1）进一步了解进程的并发执行（2）加强对进程死锁的理解（3）用银行家算法完成死锁检测2设计内容给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。3设计要求（1）初始状态没有进程启动；（2）计算每次进程申请是否分配，如：计算出预分配后的状态情况（安全状态，不安全状态），如果是安全状态，输出安全序列；（3）每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V；（4）每次申请情况应可单步查看，如：输入一个空格，继续下个申请。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，表示进程只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1)如果Requesti[j]=Need[i,j]，则转向步骤2；否则，认为出错，因为它所3需要的资源数已超过它所宣布的最大值。(2)如果Requesti[j]=Available[j]，则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待。(3)系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程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设计思路（1）进程一开始向系统提出最大需求量；（2）进程每次提出新的需求都统计是否超出它事先提出的最大需求量;（3）若正常，则判断该进程所需剩余量（包括本次申请）是否超出系统所掌握的剩余资源量，若不超出，则分配，否则等待。6算法流程图6.1银行家算法流程图开始提出进程i的请求向量Resquest[*]alloc[i][*]+Request[*}=claimNoERROR[i][*]YesRequest[*]=available[*]noERRORyesavailable[*]-=Request[*]alloc[i][*]+=Request[*]is_safe()Noyesavailable[*]+=Request[*]alloc[*]-=Request[*]同意本次分配拒绝本次分配图1银行家算法流程图6.2银行家算法安全检测流程图开始tmp_avail[*]=available[*]寻找进程k满足Claim[k][*]-alloc[k][*]tmp_avail[*]是否存在这样返回false的进程tmp_avail[*]+=alloc[*]标记进程k是否所有的进程都被标记返回true图2银行家算法安全检测流程图7银行家算法之列假定系统中有五个进程：{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图3所示。资源情况进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332（230）P1322200(302)122(020)P2902302600P3222211011P4433002431图3T0时刻的资源分配表(1)T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(如图可知，在T0时刻存在着一个安全序列｛P1，P3，P4，P2，P0｝，故系统是安全的。资源情况进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1332122200532truetruetruetruetrueP3532011211743P4743431002745P27456003021047P010477430101057图4T0时刻的安全序列(2)P1请求资源：P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查：①Request1(1,0,2)=Need1(1,2,2)②Request1(1,0,2)=Available1(3,3,2)③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成资源变化情况如图1中的圆括号所示。④再利用安全性算法检查此时系统是否安全。如图5所示资源情况进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532truetruetruetruetrueP3532011211743P4743431002745P0745743010755P27556003021057图5P1申请资源时的安全性检查由所进行的安全性检查得知，可以找到一个安全序列｛P1,P3,P4,P2,P0}。因此系统是安全的，可以立即将P1所申请的资源分配给它。(3)P4请求资源：P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)不小于等于Available(2,3,0),让P4等待。(4)P0请求资源：P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查。①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系统暂时先假定可为P0分配资源，并修改有关数据，如图6所示。资源情况进程AllocationNeedAvailableABCABCABCP0030732210P1302020P2302000P3211011P4002432图6为P0分配资源后的有关资源数据(5)进行安全性检查：可用资源Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。8程序测试结果图7图8图9图10源程序清单：#includestring.h#includestdio.h#includeiostream.h#defineFALSE0#defineTRUE1#defineW10#defineR10intM;intN;intALL_RESOURCE[W];intMAX[W][R];intAVAILABLE[R];intALLOCATION[W][R];intNEED[W][R];intRequest[R];voidoutput(){inti,j;coutendl━━━━━━━━━━━━━━━━━━endl;cout各种资源的总数量:endl;for(j=0;jN;j++)cout资源j:ALL_RESOURCE[j];coutendl;cout━━━━━━━━━━━━━━━━━━endl;cout目前各种资源可利用的数量为:endl;for(j=0;jN;j++)cout资源j:AVAILABLE[j];coutendl;cout━━━━━━━━━━━━━━━━━━endl;cout各进程还需要的资源数量:endlendl;for(i=0;iN;i++)cout资源i;coutendl;for(i=0;iM;i++){cout进程i:;for(j=0;jN;j++)coutNEED[i][j];coutendl;}coutendl;cout━━━━━━━━━━━━━━━━━━endl;cout各进程已经得到的资源量:endlendl;for(i=0;iN;i++)cout资源i;coutendl;for(i=0;iM;i++){cout进程i:;for(j=0;jN;j++)coutALLOCATION[i][j];coutendl;}coutendl;}voiddistribute(intk){intj;for(j=0;jN;j++){AVAILABLE[j]=AVAILABLE[j]-Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];NEED[k][j]=NEED[k][j]-Request[j];}}voidrestore(intk){intj;for(j=0;jN;j++){AVAILABLE[j]=AVAILABLE[j]+Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];NEED[k][j]=NEED[k][j]+Request[j];}}intcheck(){intWORK[R],FINISH[W];inti,j;for(j=0;jN;j++)WORK[j]=AVAILABLE[j];for(i=0;iM;i++)FINISH[i]=FALSE;for(i=0;iM;i++){for(j=0;jN;j++){if(FINISH[i]==FALSE&&NEED[i][j]=WORK[j]){WORK[j]=WORK[i]+ALLOCATION[i][j];}}FINISH[i]=TRUE;}for(i=0;iM;i++){if(FINISH[i]==FALSE){coutendl;cout系统不安全!!!本次资源申请不成功!!!endl;coutendl;return1;}else{coutendl;cout经安全性检查，系统