操作系统_银行家算法实验报告

《计算机操作系统》课程设计题目银行家算法分析学院计算机与软件学院专业计算机科学与技术班级学号姓名指导教师起止时间2一、算法综述银行家算法：在进程向系统提出资源分配请求时，算法会先对进程提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。二．算法分析2.1银行家算法中的数据结构为资源的种类i进程的数量j可利用资源向量intAvailable[j]最大需求矩阵intMax[i][j]分配矩阵intAllocation[i][j]需求矩阵intneed[i][j]=Max[i][j]-Allocation[i][j]申请各类资源数量intRequesti[j]i进程申请j资源的数量工作向量intWork[x]intFinish[y]2.2银行家算法设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要k个Rj类型的资源，当Pi发出资源请求后，系统按照下述步骤进行检查：(1)如果Requesti[j]≤Need[j],便转向步骤（2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。(2)如果Requesti[j]≤Available[j]，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。(3)系统试探着将资源分配给进程Pi，并修改下面数据结构中的数值：Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];(4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。2.3安全性检查算法（Check_safe()函数）(1)设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work=Available。3Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=0；当有足够的资源分配给进程时，再令Finish[i]=1。(2)在进程中查找符合以下条件的进程：条件1：Finish[i]=0；条件2：need[i][j]=Work[j]若找到，则执行步骤(3)否则，执行步骤(4)(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]=Work[j]+Allocation[i][j]；Finish[i]=1；gotostep2；(4)如果所有的Finish[i]=1都满足，则表示系统处于安全状态，否则，处于不安全状态。三、算法设计初始化算法流程图：4银行家算法流程图：(1)采用动态输入的方法对进程个数Pnum，资源种类数Stype,资源总数Ssum[],最大需求Max[][],已分配Allocation[][]进行初始化；(2)根据已输入数据计算出需求矩阵Need[][],可用资源数Available[];(3)利用Check_safe()函数对此刻系统的安全性进行检测，如果安全，给出安全序列；(4)进程i提出资源请求，利用Ask_Distribution()函数检测请求是否合理；合理则满足请求，并给出安全序列；不合理则给出错误提示；(5)做出开始界面、选择界面、退出界面，使程序美观、易操作；5四、编码实现（实验的java代码）importjava.util.Scanner;publicclassYinHang{Scannerin=newScanner(System.in);intPnum;//进程个数intStype;//资源种类数int[]Ssum;//各类资源总数int[][]Max;//最大需求矩阵int[][]Allocation;//已分配矩阵int[][]Need;//需求矩阵int[]Available;//可用资源数int[]Work;//Available的试分配向量boolean[]Finish=newboolean[50];//试分配结果标识向量publicYinHang(){start();}publicvoidstart(){System.out.println(***********************************************************);System.out.println(欢迎使用银行家算法);System.out.println(120607124罗巾英);System.out.println(***********************************************************);System.out.println(请选择操作：\n\t1.开始使用\n\t2.退出);inta;a=in.nextInt();if(a==1){input();}else{quit();6}}publicvoidinput(){System.out.println(请输入T0时刻进程个数Pnum：);this.Pnum=in.nextInt();System.out.println(请输入资源种类数Stype:);this.Stype=in.nextInt();this.Ssum=getSsum();this.Max=getMax();this.Allocation=getAllocation();this.Need=getNeed();this.Available=getAvailable(Pnum,Stype);System.out.println(该时刻的资源分配表：);output();this.Check_Safe(Available);this.Ask_Distribution(false);}publicint[]getSsum(){Ssum=newint[Stype];System.out.println(请输入各类资源总数Ssum:);for(inti=0;iStype;i++){Ssum[i]=in.nextInt();}returnSsum;}publicint[][]getMax(){Max=newint[Pnum][Stype];System.out.println(请输入最大需求矩阵Max:);for(inti=0;iPnum;i++){for(intj=0;jStype;j++){Max[i][j]=in.nextInt();}}returnMax;}publicint[][]getAllocation(){Allocation=newint[Pnum][Stype];System.out.println(请输入已分配资源情况矩阵Allocation);for(inti=0;iPnum;i++){7for(intj=0;jStype;j++){Allocation[i][j]=in.nextInt();}}returnAllocation;}publicint[][]getNeed(){Need=newint[Pnum][Stype];for(inti=0;iPnum;i++){for(intj=0;jStype;j++){Need[i][j]=Max[i][j]-Allocation[i][j];}}returnNeed;}publicint[]getAvailable(intx,inty){Available=newint[Stype];Available=Ssum;System.out.println(进程的可用资源Available为：);for(intj=0;jStype;j++){for(inti=0;iPnum;i++){Available[j]=Available[j]-Allocation[i][j];}System.out.print(Available[j]+);}System.out.println();returnAvailable;}publicvoidsetFinish(intx){for(inti=0;iPnum;i++){Finish[i]=false;}}publicbooleanCheck_Safe(intavail[]){booleanboo=false;intk[]=newint[Pnum];inta=0;Work=newint[Stype];for(inti=0;iavail.length;i++){8Work[i]=avail[i];}setFinish(Pnum);for(ints=0;sPnum;s++){for(inti=0;iPnum;i++){if(Finish[i]==false){for(intj=0;jStype;j++){if(Need[i][j]=Work[j]){if(j+1==Stype){Finish[i]=true;k[a]=i;a++;for(intm=0;mStype;m++){Work[m]=Work[m]+Allocation[i][m];}}else{continue;}}else{break;}}}else{continue;}}}if(a==Pnum){System.out.println(此刻系统处于安全状态，存在安全序列为：);for(inti=0;iPnum;i++){System.out.print(P+k[i]+\t);}System.out.println();boo=true;}else{System.out.println(此时系统处于非安全状态);9choice();boo=false;}returnboo;}publicvoidAsk_Distribution(booleanb){inta=0;inta0=0;inta1=0;booleanbo=false;for(inti=0;iStype;i++){Work[i]=Available[i];}System.out.println(请输入请求分配的进程编号：);intm=in.nextInt();System.out.println(请输入请求的各资源数);intdis[]=newint[Stype];for(inti=0;iStype;i++){dis[i]=in.nextInt();}for(inti=0;iStype;i++){if(dis[i]=Need[m][i]){a++;continue;}else{System.out.println(出错！！！请求资源数大于需求资源数!);choice();break;}}if(a==Stype){for(inti=0;iStype;i++){if(dis[i]=Work[i]){a0=a0+1;if(a0==Stype){for(intj=0;jdis.length;j++){Work[j]=Work[j]-dis[j];Allocation[m][j]=Allocation[m][j]+dis[j];Need[m][j]=Need[m][j]-dis[j];}10bo=Check_Safe(Work);}continue;}else{System.out.println(出错！！！请求资源数大于可用资源数!);choice();break;}}}if(bo){for(inti=0;iStype;i++){Available[i]=Available[i]-dis[i];if(Allocation[m][i]==Max[m][i]){a1=a1+1;}while(a1==Stype){System.out.pri