银行家算法课程设计报告样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。操作系统原理课程设计报告1设计目的（1） 进一步了解进程的并发执行（2） 加强对进程死锁的理解（3） 用银行家算法完成死锁检测2设计内容给出进程需求矩阵C、 资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝( 银行家算法) 模拟该进程组的执行情况。3设计要求（1） 初始状态没有进程启动; （2） 计算每次进程申请是否分配, 如: 计算出预分配后的状态情况( 安全状态, 不安全状态) , 如果是安全状态, 输出安全序列; （3） 每次进程申请被允许后, 输出资源分配矩阵A和可用资源向量V; （4） 每次申请情况应可单步查看, 如: 输入一个空格, 继续下个申请。4算法原理4.1银行家算法中的数据结构( 1)可利用资源向量Available它是一个含有m个元素的数组, 其中的每一个元素代表一类可利用的资源数目, 其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Availablej=K,则表示系统中现有Rj类资源K个。( 2)最大需求短阵Max这是个nm的矩阵, 它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i, j)K, 表示进程i需要Rj类资源的最大数目为K。( 3)分配短阵Allocation这是一个nm的矩阵, 它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocation(i,j)K, 表示进程i当前已分得Rj类资源的数目为K。 (4)需求矩阵Need它是一个nm的矩阵, 用以表示每一个进程尚需的各类资源数, 如果Needi,j=K, 则表示进程i还需要Rj类资源k个, 方能完成其任务。上述三个矩阵间存在下述关系: Needi,j=Maxi,j-Allocationi,j4.2银行家算法设Requesti是进程Pi的请求向量。如果Requestijk, 表示进程只需要k个Rj类型的资源。当Pi发出资源请求后, 系统按下述步骤进行检查: (1)如果 Requestij=Needi,j, 则转向步骤2; 否则, 认为出错, 因为它所 3需要的资源数已超过它所宣布的最大值。(2)如果Requestij=Availablej , 则转向步骤3; 否则, 表示系统中尚无足够的资源, Pi必须等待。(3)系统试探把要求的资源分配给进程Pi, 并修改下面数据结构中的数值: Availablej:=Availablej-Requestij; Allocationi,j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij;(4)系统执行安全性算法, 检查此次资源分配后, 系统是否处于安全状态。若安全, 才正式将资源分配给进程Pi, 以完成本次分配; 否则, 将试探分配作废, 恢复原来的资源分配状态, 让进程Pi等待。4.3安全性算法系统所执行的安全性算法可描述如下: (1)设置两个向量、 工作向量Work。它表示系统可提供给进程继续运行所需要的各类资源数目, 它含有m个元素, 执行安全算法开始时, Work = Available。、 Finish。它表示系统是否有足够的资源分配给进程, 使之运行完成, 开始时先做Finishi:=false ; 当有足够资源分配给进程时, 令 Finishi:=true。(2)从进程集合中找到一个能满足下述条件的进程: 、 Finishi=false; 、 Needi,j=Workj;如找到, 执行步骤( 3) ; 否则, 执行步骤( 4) 。(3)当进程Pi获得资源后, 可顺利执行, 直至完成, 并释放出分配给它的资源, 故应执行: Workj:=Worki+Allocationi,j; Finishi:=true;goto step 2; (4)如果所有进程的Finishi:=true, 则表示系统处于安全状态; 否则, 系统处于不安全状态。5设计思路（1） 进程一开始向系统提出最大需求量; （2） 进程每次提出新的需求都统计是否超出它事先提出的最大需求量;( 3) 若正常, 则判断该进程所需剩余量( 包括本次申请) 是否超出系统所掌握的剩余资源量, 若不超出, 则分配, 否则等待。6算法流程图6.1银行家算法流程图 开始 提出进程i的请求 向量Resquest* alloci * +Request*=claim No ERROR i* Yes Request*=available* no ERROR yes available*-=Request* alloci*+=Request* is_safe() No yes available*+=Request* alloc*-=Request* 同意本次分配 拒绝本次分配图1银行家算法流程图6.2银行家算法安全检测流程图 开始 tmp_avail*=available* 寻找进程k满足 Claimk*-allock*tmp_avail* 是否存在这样 返回false 的进程 tmp_avail*+=alloc* 标记进程k 是否所有的进程 都被标记 返回true 图2银行家算法安全检测流程图7银行家算法之列假定系统中有五个进程: P0, P1, P2, P3, P4和三种类型的资源A, B, C, 每一种资源的数量分别为10、 5、 7,在T0时刻的资源分配情况如图3所示。 资源情况 进程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2( 2 3 0) P13 2 22 0 0(3 0 2)1 2 2(0 2 0)P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1图3 T0时刻的资源分配表(1)T0时刻的安全性: 利用安全性算法对T0时刻的资源分配情况进行分析(如图可知, 在T0时刻存在着一个安全序列P1, P3, P4, P2, P0, 故系统是安全的。 资源情况进程WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP13 3 21 2 22 0 05 3 2truetruetruetruetrueP35 3 20 1 12 1 17 4 3P47 4 34 3 10 0 27 4 5P27 4 56 0 03 0 210 4 7P010 4 77 4 30 1 010 5 7图4 T0时刻的安全序列(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+AllocationFinishA B CA B CA B CA B CP12 3 00 2 03 0 25 3 2truetruetruetruetrueP35 3 20 1 12 1 17 4 3P47 4 34 3 10 0 27 4 5P07 4 57 4 30 1 07 5 5P27 5 56 0 03 0 210 5 7图5 P1申请资源时的安全性检查由所进行的安全性检查得知, 能够找到一个安全序列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所示。 资源情况进程AllocationNeedAvailableA B CA B CA B CP00 3 07 3 22 1 0P13 0 20 2 0P23 0 20 0 0P32 1 10 1 1P40 0 24 3 2图6为P0分配资源后的有关资源数据(5) 进行安全性检查: 可用资源Available(2,1,0)已不能满足任何进程的需要, 故系统进入不安全状态, 此时系统不分配资源。8程序测试结果图7图8图9图10源程序清单: #include #include #include #define FALSE 0#define TRUE 1#define W 10#define R 10int M ; int N ; int ALL_RESOURCEW;int MAXWR; int AVAILABLER; int ALLOCATIONWR; int NEEDWR; int RequestR; void output()int i,j;coutendlendl;cout各种资源的总数量:endl;for (j=0;jN;j+)cout 资源j: ALL_RESOURCEj;coutendl;coutendl;cout当前各种资源可利用的数量为:endl;for (j=0;jN;j+)cout 资源j: AVAILABLEj;coutendl;coutendl;cout各进程还需要的资源数量:endlendl;for(i=0;iN;i+)cout 资源i;coutendl;for (i=0;iM;i+)cout进程i: ;for (j=0;jN;j+)coutNEEDij ;coutendl;coutendl;coutendl;cout各进程已经得到的资源量: endlendl;for(i=0;iN;i+)cout 资源i;coutendl;for (i=0;iM;i+)cout进程i: ;for (j=0;jN;j+)coutALLOCATIONij ;coutendl;coutendl;void distribute(int k)int j;for (j=0;jN;j+)AVAILABLEj=AVAILABLEj-Requestj;ALLOCATIONkj=ALLOCATIONkj+Requestj;NEEDkj=NEEDkj-Requestj;void restore(int k)int j;for (j=0;jN;j+)AVAILABLEj=AVAILABLEj+Requestj;ALLOCATIONkj=ALLOCATIONkj-Requestj;NEEDkj=NEEDkj+Requestj;int check()int WORKR,FINISHW;int i,j;for(j=0;jN;j+) WORKj=AVAILABLEj;for(i=0;iM;i+) FINISHi=FALSE;for(i=0;iM;i+)for(j=0;jN;j+)if(FINISHi=FALSE&NEEDij=WORKj)WORKj=WORKi+ALLOCATIONij;FINISHi=TRUE;for(i=0;iM;i+)if(FINISHi=FALSE)coutendl;cout 系统不安全! 本次资源申请不成功!endl;coutendl;return 1;elsecoutendl;cout 经安全性检查, 系统安全, 本次分配成功。endl;coutendl;return 0;void bank() / 银行家算法int i=0,j=0;char flag=Y;while(flag=Y|flag=y)i=-1;while(i=M)coutendl;coutendli;if(i=M) cout 输入的进程号不存在, 重新输入!endl;cout 请输入进程i申请各类资源的数量:endl;for (j=0;jN;j+)cout 资源jRequestj;if(RequestjNEEDij) coutendl 进程i申请的资源数大于进程i还需要j类资源的数量!;cout 若继续执行系统将处于不安全状态!AVAILABLEj)coutendl 进程i申请的资源数大于系统可用j类资源的数量!;cout 若继续执行系统将处于不安全状态!endl;flag=N;break;if(flag=Y|flag=y)distribute(i); if(check() restore(i); output(); else output(); else coutendl;coutflag;void version()coutendl;coutt 银 行 家 算 法 endl;void main() int i=0,j=0,p;version();getchar();coutendlM;coutendlendl;coutN;coutendlendl;cout请输入各类资源总数:(需要输入数为N个);for(i=0;iALL_RESOURCEi;coutendlendl;cout输入各进程所需要的各类资源的最大数量:(需要输入数为M*N个);for (i=0;iM;i+)for (j=0;jMAXij;if (MAXijALL_RESOURCEj)coutendl占有资源超过了声明的该资源总数,请重新输入ALL_RESOURCEj);coutendlendl;cout输入各进程已经占据的各类资源的数量:(需要输入数为M*N个);for (i=0;iM;i+)for (j=0;jALLOCATIONij;if (ALLOCATIONijMAXij)coutendl占有资源超过了声明的最大资源,请重新输入MAXij);for (j=0;jN;j+) p=ALL_RESOURCEj;for (i=0;iM;i+)p=p-ALLOCATIONij;AVAILABLEj=p;if(AVAILABLEj0)AVAILABLEj=0;for (i=0;iM;i+)for(j=0;jN;j+)NEEDij=MAXij-ALLOCATIONij;output();bank();