操作系统原理与linux-银行家算法实验报告

PAGEPAGE1成绩评阅人评阅日期计算机科学与技术系实验报告课程名称：操作系统原理与linux实验名称：银行家算法2011年04月实验三银行家算法一、实验目的：（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。（3）理解和掌握安全序列、安全性算法二、实验内容：（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；（3）会使用某种编程语言。三、实验作业：一、安全状态指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，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等待。三、安全性算法（1）设置两个向量：①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;②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都满足，则表示系统处于安全状态；否则，系统处于不安全状态。【实验步骤】 参考实验步骤如下：（1）参考图1-1所示流程图编写安全性算法。YY所有finish都为true？输出安全序列NYN存在Finish[i]=false&&Need[i][j]<Available[j]初始化Work和FinishFinish[i]=true，Work[j]=Work[j]+Allocation[j]所有进程都找完了？Y开始图1-1安全性算法流程图（2）编写统一的输出格式。 每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。（3）参考图1-2所示流程图编写银行家算法。（4）编写主函数来循环调用银行家算法。【思考题】（1）在编程中遇到了哪些问题？你是如何解决的？（2）在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？四、实验代码：/////////////////////////////////////////////////////////////////////////////////////author：黄秋鑫////////////////////////////////////////////objective：实现银行家算法///////////////////////////time：2011/4/6//////////////////////////////////////////////////////////////////////////////////////////////////////packagecom.mmc.hqx.os;importjava.util.Scanner;publicclassbacker{ privateintProcess=0;//定义最大进程数目 privateintResource=0;//定义最大资源类数 privateintAvailable[];//定义当前可用资源 privateintWork[];//定义系统可提供给进程继续运行所需的各类资源数目 privateintMAX[][];//定义进程最大资源需求 privateintAllocation[][];//定义进程当前已用资源数目 privateintneed[][];//定义进程需要资源数目 privateintRequest[][];//定义进程请求资源向量 privatebooleanfinish[];//定义进程完成标志 privateintP[]; privateScannerin=newScanner(System.in);//定义全局输入流 //关闭输入流 publicvoidclose() { in.close(); } //构造函数，初始化各向量 publicbacker()throwsException{ inti,j; System.out.print("请输入当前进程的个数:"); Process=in.nextInt(); System.out.print("请输入系统资源种类的类数:"); Resource=in.nextInt(); //初始化各个数组 Available=newint[Resource]; Work=newint[Resource]; MAX=newint[Process][Resource]; Allocation=newint[Process][Resource]; need=newint[Process][Resource]; Request=newint[Process][Resource]; finish=newboolean[Process]; P=newint[Process]; //System.out.println("请输入每个进程最大资源需求量,按照"+Process+"x"+Resource+"矩阵输入"); for(i=0;i<Process;i++){ System.out.print("请输入P"+(i+1)+"进程各类资源最大需求量:"); for(j=0;j<Resource;j++) MAX[i][j]=in.nextInt(); } //System.out.println("请输入每个进程已分配的各资源数,也按照"+Process+"x"+Resource+"矩阵输入"); for(i=0;i<Process;i++){ System.out.print("请输入P"+(i+1)+"进程各类资源已分配的资源数:"); for(j=0;j<Resource;j++){ Allocation[i][j]=in.nextInt(); need[i][j]=MAX[i][j]-Allocation[i][j]; if(need[i][j]<0){ System.out.println("您输入的第"+(i+1)+"个进程所拥有的第"+(j+1) +"个资源数错误,请重新输入:"); j--; continue; } } } System.out.print("请输入系统各类资源可用的数目:"); for(i=0;i<Resource;i++){ Available[i]=in.nextInt(); } }//银行家算法 publicvoidBank()throwsException { intj,i; inttempAvailable[]=newint[Resource]; inttempAllocation[]=newint[Resource]; inttempNeed[]=newint[Resource]; System.out.println(""); System.out.print("请输入要申请资源的进程号(当前共有"+Process +"个进程,如为进程P1申请，请输入1，以此类推)"); i=in.nextInt()-1; System.out.print("请输入P"+(i+1)+"进程申请的各资源的数量"); for(j=0;j<Resource;j++){ Request[i][j]=in.nextInt(); } for(j=0;j<Resource;j++){ if(Request[i][j]>need[i][j]){ System.out.println("您输入的申请的资源数超过进程的需求量!请重新输入!"); continue; } if(Request[i][j]>Available[j]){ System.out.println("您输入的申请数超过系统可用的资源数!请重新输入!"); continue; } } for(j=0;j<Resource;j++){ tempAvailable[j]=Available[j]; tempAllocation[j]=Allocation[i][j]; tempNeed[j]=need[i][j]; Available[j]=Available[j]-Request[i][j]; Allocation[i][j]=Allocation[i][j]+Request[i][j]; need[i][j]=need[i][j]-Request[i][j]; } if(Safe()){ System.out.println("分配给P"+i+"进程成功!"); System.out.print("分配前系统可用资源："); for(intk=0;k<Resource;k++) System.out.print(tempAvailable[k]+""); System.out.print("\n分配前进程P"+i+"各类资源已分配数量:"); for(intk=0;k<Resource;k++) System.out.print(tempAllocation[k]+""); System.out.print("\n分配前进程P"+i+"各类资源需求数量:"); for(intk=0;k<Resource;k++) System.out.print(tempNeed[k]+""); System.out.print("\n分配后系统可用资源："); for(intk=0;k<Resource;k++) System.out.print(Available[k]+""); System.out.print("\n分配后进程P"+i+"各类资源已分配数量:"); for(intk=0;k<Resource;k++) System.out.print(Allocation[i][k]+""); System.out.print("\n分配后进程P"+i+"各类资源需求数量:"); for(intk=0;k<Resource;k++) System.out.print(need[i][k]+""); System.out.println(); }else{ System.out.println("申请资源失败!"); for(j=0;j<Resource;j++){ Available[j]=Available[j]+Request[i][j]; Allocation[i][j]=Allocation[i][j]-Request[i][j]; need[i][j]=need[i][j]+Request[i][j]; } } for(i=0;i<Process;i++){ finish[i]=false; } } //安全性算法 publicbooleanSafe(){ inti,j,k,t=0; Work=newint[Resource]; for(i=0;i<Resource;i++) Work[i]=Available[i]; for(i=0;i<Process;i++){ finish[i]=false; } for(i=0;i<Process;i++){ if(finish[i]==true){ continue; }else{ for(j=0;j<Resource;j++){ if(need[i][j]>Work[j]){ break; } } if(j==Resource){ finish[i]=true; for(k=0;k<Resource;k++){ Work[k]+=Allocation[i][k]; } P[t++]=i; i=-1; }else{ continue; } } if(t==Process){ System.out.print("当前系统是安全的,存在一安全序列:"); for(i=0;i<t;i++){ System.out.print("P"+P[i]); if(i!=t-1){ System.out.print(""); } } System.out.println(); returntrue; } } System.out.println("当前系统是不安全的，不存在安全序列");