银行家算法课程设计

1、实验四 银行家算法模拟【开发语言及实现平台或实验环境】C+/C#Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003【实验目的】（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法。（3）理解和掌握安全序列、安全性算法【实验内容】（1）编写安全性算法；（2）编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。【实验原理】一、安全状态指系统能按照某种顺序如<P1,P2,Pn>(称为<P1,P2,Pn>序列为安全序列)，为每个进程分配所需的

2、资源，直至最大需求，使得每个进程都能顺利完成。 二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k。系统按下述步骤进行安全检查：（1）如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果RequestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j

3、-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。三、安全性算法（1）设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程

4、： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Ø Workj=Worki+Allocationi,j;Ø Finishi=true;Ø go to step 2; （4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。【实验步骤】参考实验步骤如下：（1）参考图1-1所示流程图编写安全性算法。NY所有finish都为true？输出安全序列NYN存在Finishi =fa

5、lse&&Needij<= Availablej初始化Work和FinishFinishi=true，Workj=Workj+ Allocationij所有进程都找完了？Y开始 图1-1 安全性算法流程图输出系统不安全（2）编写统一的输出格式。每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。（3）参考图1-2所示流程图编写银行家算法。（4）编写主函数来循环调用银行家算法。【实验思考】（1）在编程中遇到了哪些问题？你是如何解决的？（2）在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？结束 否是申

6、请失败。以上分配作废，恢复原来的分配状态：Availablej = Availablej + RequestijAllocationij= AllocationijRequestijNeedij = Needij+RequestijNYNYRequestij> Needij出错返回：return(error)Requestij> Availablej出错返回：(进程阻塞)return(error)Availablej = Availablej RequestijAllocationij= Allocationij + RequestijNeedij = Needij Request

7、ij假定分配：输入初始参数（资源分配及请求情况）开始 假定分配之后，系统安全吗？申请成功。输出各种数据的变化图1-2银行家算法流程图【参考代码】部分参考代码如下：#include <iostream.h>#include <string.h>#define M 3 /资源的种类数#define N 5 /进程的个数void output(int iMaxNM,int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN); /统一的输出格式bool safety(int iAllocationNM,int iNeed

8、NM,int iAvailableM,char cNameN);bool banker(int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN);void main()int i,j;/当前可用每类资源的资源数int iAvailableM=3,3,2;/系统中N个进程中的每一个进程对M类资源的最大需求int iMaxNM=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/iNeedNM每一个进程尚需的各类资源数/iAllocationNM为系统中每一类资源当前已分配给每一进程的资源数int iNeedNM,iAlloca

9、tionNM=0,1,1,2,0,0,3,0,2,2,1,1,0,0,2;/进程名char cNameN='a','b','c','d','e'bool bExitFlag=true; /退出标记char ch; /接收选择是否继续提出申请时传进来的值bool bSafe; /存放安全与否的标志/计算iNeedNM的值for(i=0;i<N;i+)for(j=0;j<M;j+)iNeedij=iMaxij-iAllocationij;/输出初始值output(iMax,iAllocation,iNeed

10、,iAvailable,cName);/判断当前状态是否安全bSafe=safety(iAllocation,iNeed,iAvailable,cName);/是否继续提出申请while(bExitFlag)cout<<"n"<<"继续提出申请？ny为是；n为否。n"cin>>ch;switch(ch) case 'y': /cout<<"调用银行家算法"bSafe=banker(iAllocation,iNeed,iAvailable,cName);if (bSafe)

11、 /安全，则输出变化后的数据output(iMax,iAllocation,iNeed,iAvailable,cName);break; case 'n': cout<<"退出。n" bExitFlag=false; break; default: cout<<"输入有误，请重新输入：n"/输出void output(int iMaxNM,int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN)int i,j;cout<<"nt Ma

12、x tAllocationt Need t Available"<<endl;cout<<"tA B CtA B CtA B Ct A B C"<<endl;for(i=0;i<N;i+)cout<<cNamei<<"t"for(j=0;j<M;j+)cout<<iMaxij<<" "cout<<"t"for(j=0;j<M;j+)cout<<iAllocationij<&l

13、t;" "cout<<"t"for(j=0;j<M;j+)cout<<iNeedij<<" "cout<<"t"cout<<" "/Available只需要输出一次if (i=0)for(j=0;j<M;j+)cout<<iAvailablej<<" "cout<<endl;/安全性算法，进行安全性检查；安全返回true，并且输出安全序列，不安全返回false，并输出不

14、安全的提示；bool safety(int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN)/请同学们自己完成int i,j,flag,x=0;char NameN;int WorkM;bool FinishN;for(j=0;j<M;j+)Workj=iAvailablej;for(i=0;i<N;i+)Finishi=false;while(true)flag=0;for(i=0;i<N;i+)if(Finishi=false && Work0>=iNeedi0 && Wor

15、k1>=iNeedi1 && Work2>=iNeedi2)for(j=0;j<M;j+)Workj+= iAllocationij ;Finishi=true;flag+;Namex+=cNamei;for(i=0;i<N;i+)if(Finishi=false)i=i;break;if(i=5)cout<<"n"cout<<"当前时刻系统的一个安全序列为："for(x=0;x<N;x+)cout<<Namex<<" "cout<&l

16、t;"n"return true;if(flag=0)cout<<"无安全序列" return false;return true;/安全返回true，不安全返回falsebool banker(int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN)/请同学们自己完成int iMaxNM=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;int i,j,RequestM,checkM;bool f=true;char x;while(f)cout<<"

17、;请输入进程名："cin>>x;for(i=0;i<N;i+)if (cNamei=x)i=i;break;if (i=5)cout<<"n您输入的进程名有误！请重新输入"elsef=false;cout<<"请输入申请各类资源数量：n" for(j=0;j<M;j+)cin>>Requestj;for(j=0;j<M;j+) checkj=Requestj+iAllocationij;for(j=0;j<M;j+)if(iMaxij-checkj)<0)cout&l

18、t;<"n资源申请超过最大需求量！n"return false;for(j=0;j<M;j+) if(iAvailablej-Requestj)<0)cout<<"n不能满足进程！n"return false;for(j=0;j<M;j+)iAvailablej-=Requestj;iAllocationij+=Requestj;iNeedij-=Requestj;safety(iAllocation,iNeed,iAvailable,cName); return true;【参考文献】1、 汤子瀛编.计算机操作系统.北京：西安电子科技大出版社。2、 张尧学等编著.计算机操作系统教程.北京：清华大学出版社。运行结果界面实验结果分析银行家算法