操作系统实习

职业生涯规划学生姓名：学号：中国地质大学信息工程学院2014年12月28日实习题目：银行家算法设计实现【需求规格说明】如果存在一个由系统中所有进程构成的安全序列P1，…Pn，则系统处于安全状态。一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)当前占有资源量之和，系统处于安全状态(安全状态一定是没有死锁发生的).不存在一个安全序列就一定导致死锁。本程序就是判断是否存在一个安全序列【算法设计】（1）设计思想1．可利用资源向量Available它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。最大需求短阵Max，这是—个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i，j)＝K，表示进程i需要j类资源的最大数目为K。需求矩阵Need，它是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数，如果Need[i,j]=K，则表示进程i还需要Rj类资源k个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j]Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]:=false；当有足够资源分配给进程时，令Finish[i]:=true。（2）从进程集合中找到一个能满足下述条件的进程：①、Finish[i]=false;②、Need[i,j]=Work[j];如找到，执行步骤（3）；否则，执行步骤（4）（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]:=Work[i]+Allocation[i,j];Finish[i]:=true;gotostep2；（4）如果所有进程的Finish[i]:=true，则表示系统处于安全状态；否则，系统处于不安全状态（2）设计表示：voidshowdata();//主要用来输出资源分配情况intchangdata(inti);//主要用改变资源分配后后的情况intsafe();//银行家分配算法的安全检查【调试报告】【附录】#includestdafx.h#includeiostream#includestring.h#includestdio.husingnamespacestd;#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;}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();//用银行家算法判定系统是否安全system(pause);return1;}