实习报告书写参考-----银行家算法的实现.docx
实习报告书写参考银行家算法的实现一、设计目的：熟悉银行家算法，理解系统产生死锁的原因及避免死锁的方法,加深记忆。二、设计内容设计一个n个并发进程共享m个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。三、开发环境WilKk)WS环境,VC6.O平台。四、分析设计V>实验原理银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。与预防死锁的儿种方法相比较，限制条件少，资源利用程度提高了。缺点：该算法要求客户数保持固定不变，这在多道程序系统中是难以做到的；该算法保证所有客户在有限的时间内得到满足，但实时客户要求快速响应，所以要考虑这个因素；由于要寻找一个安全序列，实际上增加了系统的开销.Bankeralgorithm最重要的一点是：保证操作系统的安全状态！这也是操作系统判断是否分配给一个进程资源的标准！那什么是安全状态？举个小例子，进程P需要申请8个资源(假设都是一样的)，已经申请了5个资源，还差3个资源。若这个时候操作系统还剩下2个资源。很显然，这个时候操作系统无论如何都不能再分配资源给进程P了，因为即使全部给了他也不够，还很可能会造成死锁。若这个时候操作系统还有3个资源，无论P这一次申请几个资源，操作系统都可以满足他，因为操作系统可以保证P不死锁，只要他不把剩余的资源分配给别人，进程P就一定能顺利完成任务。为什么银行家算法是可行的呢？这里需要严格的证明一下。不管任何时候，操作系统分配资源的时候都可以保证当前接受资源的进程不会陷入死锁，因为操作系统总是可以满足该进程需要的资源的。假设有n个进程pl,p2,p3,-pn,最后一个分配到资源的是pi,pi还需要mi个资源，假设此时操作系统还有m个资源剩余。那么很显然m>=mi!而且如果之后操作系统又把资源分配给其他进程了，假设是pj,pj还需要mj个资源，同理可知m>=mj!也就是说在所有的进程中，还需要的资源数总是有小于m的！这样就可以保证资源数永远不会为0,即使可能暂时性为0。另外，还需要保证资源数不会减少！而且，所有己经分配到资源的进程总有一天会归还它所拥有的资源！根据操作系统再分配的时候的状态即可判定。V二>程序结构当进程Pi提出资源申请时，系统执行下列步骤：(1)若ReqUeStiWNeedi,转(2)；否则错误返回(2)若ReqUeStiWAvailable,转(3)；否则进程等待(3)假设系统分配了资源，则有：Avai!able:=AvaiIable-Rcquesti;Allocationi:=Allocationi+Rcquesti;Needi:=Needi-Requesti若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢更原状态，进程等待模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成：第一部分:银行家算法(扫描)1 .如果RequcstCNced,则转向2;否则，出错2 .如果Requcst<=AvaiIablc,则转向3,否则等待3 .系统试探分配请求的资源给进程4 .系统执行安全性算法第二部分:安全性算法1 .设置两个向量(D.工作向量:%rk=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2) .FiniSh:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2 .若Finishi=Falsc&&Nccd<=Work,则执行3;否则执行4(1为资源类别)3 .进程P获得第i类资源,则顺利执行直至完成!并释放资源：Work=Work+Allocation;FiniShi=truc;转24 .若所有进程的Finishi=true,则表示系统安全;否则,不安全！V三>数据结构：假设有U个进程N类资源，则有如下数据结构：MAXM*NM个进程对N类资源的最大需求量AVAILABLEN系统可用资源数ALLOCATIONM*NM个进程己经得到N类资源的资源量NEEDM*NM个进程还需要N类资源的资源量V四>程序流程图：五.运行示例及结果分析TO时刻可用资源(AVailabIe)A:3,B:3,C:2请求分配时间：14:07:29经测试，可为该进程分配资源。以下为资源分配表资源WorkNeedAllocationWork+AIlocIDPOlFinishABC03030201A02BC020200AB00C0503A02BCTRUEP03050302000101020101070403TRUEPOO070403070403000100070503TRUEP02070503060000030002100505TRUEP04100505040301000002100507TRUE进程1申请资源A:2,B:l,C:1时的安全性检查请求分配时间：14:07:39进程请求的资源比Need多！不能为该进程分配资源！系统在TO(Request)时刻是不安全的！一尝试进行另外一个分配一进程1申请资源A:l,B:0,C:2时的安全性检查请求分配时间：14:07:55经测试，可为该进程分配资源。以下为资源分配表资源WorkNeedAllocationWork+AHocFinishIDABCABCABCAPOl020300000200030002050302BCTRUEP03050302000101020101070403TRUEP00070403070403000100070503TRUEP02070503060000030002100505TRUEP04100505040301000002100507TRUE进程4申请资源A:3,B:3,C:0时的安全性检查请求分配时间：14:09:14进程请求的资源比AVaIiabIe(WORK)多！不能为该进程分配资源!系统在TO(Request)时刻是不安全的！-尝试进行另外一个分配-一进程0申请资源A:0,B:2,C:0时的安全性检查请求分配时间：14:09:23系统进入不安全状态!不能为该进程分配资源！系统在TO(Request)时刻是不安全的！一尝试进行另外一个分配一进程1申请资源A:0,B:0,C:0时的安全性检查请求分配时间：14:09:37经测试，资源可为该进程分配资源。以下为资源分配表WorkNeedAllocationWork+AIlocIDFinishABCABCABCABCPOl020300000200030002050302TRUEP03050302000101020101070403TRUEPOO070403070403000100070503TRUEP02070503060000030002100505TRUEP04六、心得与体会参考文献：1005(略)05040301000002100507TRUE1、汤子嬴编：计算机操作系统，西安电子科技大学出版社2、张尧学、史美林编：计算机操作系统教程，清华大学出版社3、任爱华、王雷编：操作系统实用教程，清华大学出版社附录、源程序清单include<iostream>usingnamespace std;define MAXPROCESS 50define MAXRESOURCE 100int AVAILABLEMAXRESOURCE;int MAXMAXPROCESSMAXRESOURCE;int ALLOCATIONMAXPROCESSMAXRESOURCE;int NEEDMAXPROCESSMAXRESOURCE;int REQUESTMAXPROCESSMAXRESOURCE;*最大进程数*/*最大资源数*/*可用资源数组*/*最大需求矩阵*/*分配矩阵*/*需求矩阵*/*进程需要资源数*/boolFINISHMAXPROCESS;/*系统是否有足够的资源分配*/intpMAXPROCESS;intm, n;资源*/void Init ();/*记录序列*/*m个进程,n个boolSafeO； void Bank O; int main() IInitO;SafeO;Bank O ;void InitO*初始化算法*/inti,j;cout<<*t-*<<endl;COUt<<*tIcout<<*tI11*<<endl;银行家算法11*<<endl;cout<<*tI11*<<endl;cout<<*tI计科04151李宏11*<<endl;cout<<*tI11*<<endl;cout<<*tI0415084211I*<<endl;cout<<*t*<<endl;COUt<，请输入进程的数目：”；cin>>m;CoUt<<"请输入资源的种类:“；cin>>n;COUt<<“请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>MAXij;CoUt<<“请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)(cin>>ALLOCATIONij;NEEDij=MAXij-ALLOCATIONtij;if(NEEDij<O)CoUt您输入的第"<<i+l<<"个进程所拥有的第"<<j+k<”个资源数错误,请重新输入:"<<endl;j-；continue;)COUt<<“请输入各个资源现有的数目："<<endl;for(i=0;i<n;i+)cin>>AVAILABLEi;voidBankO*银行家算法*/inti,cusneed;charagain;while(l)CoUt<<"请输入要中清资源的进程号(注:第1个进程号为0,依次类推)"<<endl;cin>>cusneed;COUt<<"请输入进程所请求的各资源的数量"<<endl;for(i=0;i<n;i+)(cin>>REQUESTcusneedi;)for(i=0;i<n;i+)(if(REQUESTLcusneedi>NEEDcusneedi)(CoUt«”您输入的请求数超过进程的需求量!请重新输入!z,<<endl;continue;)if(REQUESTLcusneedi>AVAILABLEi)CoUt您输入的请求数超过系统有的资源数!请重新输入!"Gendl;continue;)for(i=0;i<n;i+)(AVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;)if(SafeO)CoUt同意分配请求！"<<endl;)elseCOUtx”您的请求被拒绝!”<<endl;for(i=0;i<n;i+)(AVAILABLEi+=REQUESTcusneedi;AI,LOCATIONcusneedi-=REQUESTcusneedi;NEEDcusneedi+=REQUESTcusneedi;)for(i=0;i<m;i+)FINISHi=false;)CoUt<<"您还想再次请求分配吗?是请按yY,否请按其它键"<<endl;cin>>again;if(again=*y,again=*Y,)continue;)break;)*安全性算boolSafeO法*/Iinti,j,k,1=0;intWorkEMAXRESOURCE;*工作数组*/for(i=0;i<n;i+)Worki=AVAILABLEi;for(i=0;i<m;i+)(INISIIi=false;)for(i=0;i<m;i+)(if(FINISIIi=true)continue;)elsefor(j=0;j<n;j+)if(NEEDij>Workj)break;)if(j=n)FINISHi=true;for(k=0;k<n;k+)Workk+=ALLOCATIONtik;)pl+=i;i=-l;)else(continue;)if(l=m)(CoUt<<”系统是安全的”<<endl;CoUtx<"安全序列:*<<endl;for(i=0;i<l;i+)(cout<<pi;if(i!=l-l)cout<<*>*;)cout<<*<<endl;returntrue;)COUt<<”系统是不安全的"<<endl;returnfalse;
