银行家算法的实现

实习报告书写参考-----银行家算法的实现一、设计目的：熟悉银行家算法，理解系统产生死锁的原因及避免死锁的方法,加深记忆。二、设计内容设计一个n个并发进程共享m个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。三、开发环境windows环境，VC6.0平台。四、分析设计＜一＞实验原理银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。与预防死锁的几种方法相比较，限制条件少，资源利用程度提高了。缺点：该算法要求客户数保持固定不变，这在多道程序系统中是难以做到的；该算法保证所有客户在有限的时间内得到满足，但实时客户要求快速响应，所以要考虑这个因素；由于要寻找一个安全序列，实际上增加了系统的开销.Bankeralgorithm最重要的一点是：保证操作系统的安全状态！这也是操作系统判断是否分配给一个进程资源的标准！那什么是安全状态？举个小例子，进程P需要申请8个资源（假设都是一样的），已经申请了5个资源，还差3个资源。若这个时候操作系统还剩下2个资源。很显然，这个时候操作系统无论如何都不能再分配资源给进程P了，因为即使全部给了他也不够，还很可能会造成死锁。若这个时候操作系统还有3个资源，无论P这一次申请几个资源，操作系统都可以满足他，因为操作系统可以保证P不死锁，只要他不把剩余的资源分配给别人，进程P就一定能顺利完成任务。为什么银行家算法是可行的呢？这里需要严格的证明一下。不管任何时候，操作系统分配资源的时候都可以保证当前接受资源的进程不会陷入死锁，因为操作系统总是可以满足该进程需要的资源的。假设有n个进程{p1,p2,p3,…pn}，最后一个分配到资源的是pi，pi还需要mi个资源，假设此时操作系统还有m个资源剩余。那么很显然m=mi！而且如果之后操作系统又把资源分配给其他进程了，假设是pj，pj还需要mj个资源，同理可知m=mj！也就是说在所有的进程中，还需要的资源数总是有小于m的！这样就可以保证资源数永远不会为0，即使可能暂时性为0。另外，还需要保证资源数不会减少！而且，-1-所有已经分配到资源的进程总有一天会归还它所拥有的资源！根据操作系统再分配的时候的状态即可判定。＜二＞程序结构当进程pi提出资源申请时，系统执行下列步骤：（1）若Request[i]≤Need[i],转（2）；否则错误返回（2）若Request[i]≤Available,转（3）；否则进程等待(3）假设系统分配了资源，则有：Available:=Available-Request[i];Allocation[i]:=Allocation[i]+Request[i];Need[i]:=Need[i]-Request[i]若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成:第一部分:银行家算法(扫描)1．如果Request=Need,则转向2;否则,出错2．如果Request=Available,则转向3,否则等待3．系统试探分配请求的资源给进程4．系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finish[i]=False&&Need=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finish[i]=true;转24.若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!＜三＞数据结构：假设有M个进程N类资源，则有如下数据结构：MAX[M*N]M个进程对N类资源的最大需求量AVAILABLE[N]系统可用资源数ALLOCATION[M*N]M个进程已经得到N类资源的资源量NEED[M*N]M个进程还需要N类资源的资源量-2-＜四＞程序流程图：-3-五.运行示例及结果分析T0时刻可用资源(Available)A:3,B:3,C:2请求分配时间：14:07:29经测试，可为该进程分配资源。以下为资源分配表资源WorkNeedAllocationWork+AllocFinishIDABCABCABCABCP01030302010202020000050302TRUEP03050302000101020101070403TRUEP00070403070403000100070503TRUEP02070503060000030002100505TRUEP04100505040301000002100507TRUE进程1申请资源A:2,B:1,C:1时的安全性检查请求分配时间：14:07:39进程请求的资源比Need多!!不能为该进程分配资源！系统在T0（Request）时刻是不安全的!!—-尝试进行另外一个分配—-进程1申请资源A:1,B:0,C:2时的安全性检查请求分配时间：14:07:55经测试，可为该进程分配资源。以下为资源分配表资源WorkNeedAllocationWork+AllocFinishIDABCABCABCABCP01020300000200030002050302TRUEP03050302000101020101070403TRUEP00070403070403000100070503TRUEP020705030600000300021005-4-05TRUEP04100505040301000002100507TRUE进程4申请资源A:3,B:3,C:0时的安全性检查请求分配时间：14:09:14进程请求的资源比Avaliable(WORK)多!!不能为该进程分配资源！系统在T0（Request）时刻是不安全的!!—-尝试进行另外一个分配—-进程0申请资源A:0,B:2,C:0时的安全性检查请求分配时间：14:09:23系统进入不安全状态!不能为该进程分配资源！系统在T0（Request）时刻是不安全的!!—-尝试进行另外一个分配—-进程1申请资源A:0,B:0,C:0时的安全性检查请求分配时间：14:09:37经测试，可为该进程分配资源。以下为资源分配表资源WorkNeedAllocationWork+AllocFinishIDABCABCABCABCP01020300000200030002050302TRUEP03050302000101020101070403TRUEP00070403070403000100070503TRUEP02070503060000030002100505TRUEP04100505040301000002100507TRUE六、心得与体会（略）参考文献：1、汤子嬴编：《计算机操作系统》，西安电子科技大学出版社2、张尧学、史美林编：《计算机操作系统教程》，清华大学出版社3、任爱华、王雷编：《操作系统实用教程》，清华大学出版社-5-附录、源程序清单#includeiostreamusingnamespacestd;#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\t---------------------------------------------------endl;cout\t||||endl;cout\t||银行家算法||endl;cout\t||||endl;cout\t||计科04151李宏||endl;cout\t||||endl;cout\t||-6-0415084211||endl;cout\t---------------------------------------------------endl;cout请输入进程的数目:;cinm;cout请输入资源的种类:;cinn;cout请输入每个进程最多所需的各资源数,按照mxn矩阵输入endl;for(i=0;im;i++)for(j=0;jn;j++)cinMAX[i][j];cout请输入每个进程已分配的各资源数,也按照mxn矩阵输入endl;for(i=0;im;i++){for(j=0;jn;j++){cinALLOCATION[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;in;i++){cinAVAILABLE[i];}}voidBank()/*银行家算法*/{inti,cusneed;charagain;while(1){cout请输入要申请资源的进程号(注:第1个进程号为0,依次类推)endl;cincusneed;-7-cout请输入进程所请求的各资源的数量endl;for(i=0;in;i++){cinREQUEST[cusneed][i];}for(i=0;in;i++){if(REQUEST[cusneed][i]NEED[cusneed][i]){cout您输入的请求数超过进程的需求量!请重新输入!endl;continue;}if(REQUEST[cusneed][i]AVAILABLE[i]){cout您输入的请求数超过系统有的资源数!请重新输入!endl;continue;}}for(i=0;in;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;in;i++){AVAILABLE[i]+=REQUEST[cusneed][i];ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];NEED[cusneed][i]+=REQUEST[cusneed][i];}}-8-for(i=0;im;i++){FINISH[i]=false;}cout您还想再次请求分配吗?是请按y/Y,否请按