银行家算法实验报告

计算机操作系统实验报告何美西109253030212一、实验名称：银行家算法二、实验目的：银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。三、问题分析与设计：1、算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。2、银行家算法步骤：（1）如果Requesti＜or=Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：Available=Available-Request[i];Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3、安全性算法步骤：（1）设置两个向量①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。（2）从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false②Needor=Work如找到，执行步骤（3）；否则，执行步骤（4）。（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work=Work+Allocation;Finish[i]=true;转向步骤（2）。（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。4、流程图：系统主要过程流程图银行家算法流程图安全性算法流程图四、实验代码：#includeiostream.h#includestring.h#includestdio.h#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};//存放系统可提供资源intp[100]={0};intq[100][100]={0};intz[100][100]={0};intM=100;//作业的最大数为100intN=100;//资源的最大数为100intgg=1;voidshowdata()//显示资源矩阵{inti,j;coutendl此时刻的资源分配情况为：endl;coutMaxAllocationNeedAvaliableendl;cout进程名;for(j=0;j4;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];if(i==0){cout;for(j=0;jN;j++)coutAvaliable[j];//输出分配资源}coutendl;}}intchangdata(inti)//进行资源分配{intj;for(j=0;jM;j++){//p[j]=Avaliable[j];Avaliable[j]=Avaliable[j]-Request[j];//q[i][j]=Allocation[i][j];Allocation[i][j]=Allocation[i][j]+Request[j];//z[i][j]=Need[i][j];Need[i][j]=Need[i][j]-Request[j];}return1;}intsafe()//安全性算法{inti,d,k=0,m,h,s,apply,Finish[100]={0};intj;intflag=0;for(i=0;iN;i++)Work[i]=Avaliable[i];coutendl安全性检查endl;coutWorkNeedAllocationWork+AllocationFinishendl;cout进程名;for(h=0;h4;h++){for(s=0;sN;s++)coutname[s];cout;}coutendl;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){couti;for(d=0;dN;d++)coutWork[d];cout;for(d=0;dN;d++)coutNeed[i][d];cout;for(d=0;dN;d++)coutAllocation[i][d];cout;for(m=0;mN;m++){Work[m]=Work[m]+Allocation[i][m];coutWork[m];}//变分配数Finish[i]=True;temp[k]=i;cout;couttrue;coutendl;i=-1;k++;flag++;}}}}for(i=0;iM;i++){if(Finish[i]==False){for(j=0;jN;j++){Avaliable[j]=Avaliable[j]+Request[j];;Allocation[i][j]=Allocation[i][j]-Request[j];;Need[i][j]=Need[i][j]+Request[j];}coutendl系统进入不安全状态！此时系统不分配资源！endl;//不成功系统不安全return0;}}coutendl此时系统是安全的!endl;//如果安全，输出成功cout安全序列为:;for(i=0;iM;i++){//输出运行进程数组couttemp[i];if(iM-1)cout-;}coutendl;return0;}voidshare()//利用银行家算法对申请资源对进行判定{charch;inti=0,j=0;ch='y';coutendl请输入要求分配的资源进程号(0-M-1):;cini;//输入须申请的资源号coutendl请输入进程i申请的资源:endl;for(j=0;jN;j++){coutname[j]:;cinRequest[j];//输入需要申请的资源}for(j=0;jN;j++){if(Request[j]Need[i][j])//判断申请是否大于需求，若大于则出错{coutendl进程i申请的资源大于它需要的资源;cout分配不合理，不予分配！endl;ch='n';break;}else{if(Request[j]Avaliable[j])//判断申请是否大于当前资源，若大于则{//出错coutendl进程i申请的资源大于系统现在可利用的资源;cout分配出错，不予分配!endl;ch='n';break;}}}if(ch=='y'){changdata(i);//根据进程需求量变换资源showdata();//根据进程需求量显示变换后的资源safe();//根据进程需求量进行银行家算法判断}}intmain()//主函数{intt=1,i,j,number,choice,m,n,flag;charming;cout*****************银行家算法的设计与实现*****************endl;coutendl请首先输入系统可供资源种类的数量:;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;coutendl请输入各进程的最大需求量(m*n矩阵)[Max]:endl;for(i=0;im;i++)for(j=0;jn;j++)cinMax[i][j];do{flag=0;coutendl请输入各进程已经申请的资源量(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;Need[i][j]=Max[i][j]-Allocation[i][j];}if(flag)coutendl申请的资源大于最大需求量，请重新输入!\nendl;}while(flag);showdata();//显示各种资源safe();//用银行家算法判定系统是否安全while(1){if(t==1){coutendl利用银行家算法预分配资源endl;share();t=0;}elsebreak;coutendl是否继续银行家算法？(按1键继续,按其它任意键退出):;cint;coutendl;}return1;}五、程序执行结果：六、实验总结多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。09信管（2）班何美西109253030212