编程模拟银行家算法

操作系统课程设计报告闽江学院计算机学院08级网络专业题目编程模拟银行家算法学生大熊学号56指导教师徐向英2010年7月2日设计题目：编程序模拟银行家算法设计目的1、银行家算法是避免死锁的一种重要方法，本实验要求用级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。2、提高学生的程序设计能力、提高算法设计质量与程序设计素质；设计任务一、要求1．复习银行家算法，设计一个具有若干（不少于3种）资源和若干（不少于5个）进程的系统。2．定义系统的初始状态，即进程获得的资源数，还需要的资源数以及系统可用的资源数。3．以用户输入的方式提出资源请求，并用银行家算法避免可能发生的死锁，若系统安全，允许用户继续申请资源。4．设计的系统要求结构清晰，与用户的交互界面友好，能动态地实现资源的申请和分配。二、思想将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。设计思路和过程1.概要设计1.1程序流程图1.2设计原理及方法银行家算法的设计思想是：当用户申请一组资源时，系统必须做出判断；如果把这些资源分出去，系统是否还处于安全装他。若是，就可以分出这些资源；否则，该申请暂不能满足。实现银行家算法要有若干数据结构，它们用来表示资源分配系统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需要以下数据结构：1.Available是一个长度为m的向量，它表示每类资源可用的数量。Available[j]=k，表示rj类资源可用的数量为k。2.Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max[i，j]=k，表示进程pi至多可以申请k个rj类资源单位。3.Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation[i，j]=k，表示进程pi当前分到k个rj类资源。4.Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i，j]=k，表示进程pi尚需k个rj类资源才能完成其任务。显然Need[i，j]=Max[i，j]-Allocation[i，j]。这些数据结构的大小和数值随时间推移而改变。系统所执行的安全性算法描述如下：1.设置2个向量：工作向量Work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available。Finish[i]：它表示系统是否有足够的资源分配给进程，使之完成运行。开始时先做Finish[i]=true。2.从进程集合中找到一个满足下述条件的进程：Finish[i]=flase；Need[i,j]≤Work[j]；若找到，则执行步骤3，否则，执行步骤4。3.当进程pi获得资源后，可顺利执行，直至完成，并释放分配给它的资源。4.如果所有进程的Finish[i]=true都满足。则表示系统处于安全状态；否则，系统处于不安全状态。2.详细设计2.1程序源代码#includeiostream#includestring#includestdiousingnamespacestd;#defineFalse0#defineTrue1intMax[100][100]={0};//各进程所需各类资源的最大需求intAvaliable[100]={0};//系统可用资源charname[100]={0};//资源的名称intAllocation[100][100]={0};//系统已分配资源intNeed[100][100]={0};//还需要资源intRequest[100]={0};//请求资源向量inttemp[100]={0};//存放安全序列intWork[100]={0};//存放系统可提供资源intM=100;//作业的最大数为100intN=100;//资源的最大数为100voidshowdata()//显示资源矩阵{inti,j;cout系统目前可用的资源[Avaliable]:endl;for(i=0;iN;i++)coutname[i];coutendl;for(j=0;jN;j++)coutAvaliable[j];//输出分配资源coutendl;coutMaxAllocationNeedendl;cout进程名;for(j=0;j3;j++){for(i=0;iN;i++)coutname[i];cout;}coutendl;for(i=0;iM;i++){couti;for(j=0;jN;j++)coutMax[i][j];cout;for(j=0;jN;j++)coutAllocation[i][j];cout;for(j=0;jN;j++)coutNeed[i][j];coutendl;}}intchangdata(inti)//进行资源分配{intj;for(j=0;jM;j++){Avaliable[j]=Avaliable[j]-Request[j];Allocation[i][j]=Allocation[i][j]+Request[j];Need[i][j]=Need[i][j]-Request[j];}return1;}intsafe()//安全性算法{inti,k=0,m,apply,Finish[100]={0};intj;intflag=0;Work[0]=Avaliable[0];Work[1]=Avaliable[1];Work[2]=Avaliable[2];for(i=0;iM;i++){apply=0;for(j=0;jN;j++){if(Finish[i]==False&&Need[i][j]=Work[j]){apply++;if(apply==N){for(m=0;mN;m++)Work[m]=Work[m]+Allocation[i][m];//变分配数Finish[i]=True;temp[k]=i;i=-1;k++;flag++;}}}}for(i=0;iM;i++){if(Finish[i]==False){cout系统不安全endl;//不成功系统不安全return-1;}}cout系统是安全的!endl;//如果安全，输出成功cout分配的序列:;for(i=0;iM;i++){//输出运行进程数组couttemp[i];if(iM-1)cout-;}coutendl;return0;}voidshare()//利用银行家算法对申请资源对进行判定{charch;inti=0,j=0;ch='y';cout请输入要求分配的资源进程号(0-M-1):;cini;//输入须申请的资源号cout请输入进程i申请的资源:endl;for(j=0;jN;j++){coutname[j]:;cinRequest[j];//输入需要申请的资源}for(j=0;jN;j++){if(Request[j]Need[i][j])//判断申请是否大于需求，若大于则出错{cout进程i申请的资源大于它需要的资源;cout分配不合理，不予分配！endl;ch='n';break;}else{if(Request[j]Avaliable[j])//判断申请是否大于当前资源，若大于则{//出错cout进程i申请的资源大于系统现在可利用的资源;cout分配出错，不予分配!endl;ch='n';break;}}}if(ch=='y'){changdata(i);//根据进程需求量变换资源showdata();//根据进程需求量显示变换后的资源safe();//根据进程需求量进行银行家算法判断}}voidaddresources(){//添加资源intn,flag;cout请输入需要添加资源种类的数量:;cinn;flag=N;N=N+n;for(inti=0;in;i++){cout名称:;cinname[flag];cout数量:;cinAvaliable[flag++];}showdata();safe();}voidchangeresources(){//修改资源函数cout系统目前可用的资源[Avaliable]:endl;for(inti=0;iN;i++)coutname[i]:Avaliable[i]endl;cout输入系统可用资源[Avaliable]:endl;cinAvaliable[0]Avaliable[1]Avaliable[2];cout经修改后的系统可用资源为endl;for(intk=0;kN;k++)coutname[k]:Avaliable[k]endl;showdata();safe();}voiddelresources(){//删除资源charming;inti,flag=1;cout请输入需要删除的资源名称：;do{cinming;for(i=0;iN;i++)if(ming==name[i]){flag=0;break;}if(i==N)cout该资源名称不存在，请重新输入：;}while(flag);for(intj=i;jN-1;j++){name[j]=name[j+1];Avaliable[j]=Avaliable[j+1];}N=N-1;showdata();safe();}voidaddprocess(){//添加作业intflag=M;M=M+1;cout请输入该作业的最大需求量[Max]endl;for(inti=0;iN;i++){coutname[i]:;cinMax[flag][i];Need[flag][i]=Max[flag][i]-Allocation[flag][i];}showdata();safe();}intmain()//主函数{inti,j,number,choice,m,n,flag;charming;cout*****************资源管理系统的设计与实现*****************endl;cout请首先输入系统可供资源种类的数量:;cinn;N=n;for(i=0;in;i++){cout资源i+1的名称:;cinming;name[i]=ming;cout资源的数量:;cinnumber;Avaliable[i]=number;}coutendl;cout请输入作业的数量:;cinm;M=m;cout请输入各进程的最大需求量(m*n矩阵)[Max]:endl;for(i=0;im;i++)for(j=0;jn;j++)cinMax[i][j];do{flag=0;cout请输入各进程已经申请的资源量(m*n矩阵)[Allocation]:endl;for(i=0;im;i++)for(j=0;jn;j++){cinAllocation[i][j];if(Allocation[i][j]Max[i][j])flag=1;N