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

计算机操作系统课程设计 题 目 银行家算法分析 学 院 计算机与软件学院专 业 计算机科学与技术班 级 学 号 姓 名 指导教师 起止时间 1、 算法综述 银行家算法：在进程向系统提出资源分配请求时，算法会先对进程提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。2 算法分析2.1 银行家算法中的数据结构为资源的种类 i进程的数量 j可利用资源向量 int Availablej 最大需求矩阵 int Maxij 分配矩阵 int Allocationij 需求矩阵 int needij= Maxij- Allocationij申请各类资源数量 int Request ij i进程申请j资源的数量工作向量 int Workx int Finishy 2.2银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要k个Rj类型的资源，当Pi发出资源请求后，系统按照下述步骤进行检查：(1)如果RequestijNeedj,便转向步骤（2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。(2)如果RequestijAvailablej，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。(3)系统试探着将资源分配给进程Pi，并修改下面数据结构中的数值：Availablej:=Availablej-Requestij;Allocationi,j:=Allocationi,j+Requestij;Needi,j:=Needi,j-Requestij;(4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。2.3安全性检查算法（Check_safe()函数）(1)设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work= Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=0；当有足够的资源分配给进程时，再令Finishi=1。(2)在进程中查找符合以下条件的进程：条件1：Finishi=0；条件2：needij=Workj若找到，则执行步骤(3)否则，执行步骤(4)(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj= Workj+ Allocationij；Finishi=1；goto step 2；(4) 如果所有的Finishi=1都满足，则表示系统处于安全状态，否则，处于不安全状态。3、 算法设计初始化算法流程图：银行家算法流程图：(1)采用动态输入的方法对进程个数Pnum，资源种类数Stype,资源总数Ssum,最大需求Max,已分配Allocation进行初始化；(2)根据已输入数据计算出需求矩阵Need,可用资源数Available;(3)利用Check_safe()函数对此刻系统的安全性进行检测，如果安全，给出安全序列；(4)进程i提出资源请求，利用Ask_Distribution()函数检测请求是否合理；合理则满足请求，并给出安全序列；不合理则给出错误提示；(5)做出开始界面、选择界面、退出界面，使程序美观、易操作；4、 编码实现（实验的java代码）import java.util.Scanner;public class YinHang Scanner in = new Scanner(System.in);int Pnum; / 进程个数int Stype; / 资源种类数int Ssum;/ 各类资源总数int Max;/ 最大需求矩阵int Allocation;/ 已分配矩阵int Need;/ 需求矩阵int Available; / 可用资源数int Work;/ Available的试分配向量boolean Finish = new boolean50;/ 试分配结果标识向量public YinHang() start();public void start() System.out.println(*);System.out.println( 欢迎使用银行家算法);System.out.println( 120607124 罗巾英 );System.out.println(*);System.out.println(请选择操作：nt1.开始使用nt2.退出);int a;a = in.nextInt();if (a = 1) input(); else quit();public void input() 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);public int getSsum() Ssum = new intStype;System.out.println(请输入各类资源总数Ssum:);for (int i = 0; i Stype; i+) Ssumi = in.nextInt();return Ssum;public int getMax() Max = new intPnumStype;System.out.println(请输入最大需求矩阵Max:);for (int i = 0; i Pnum; i+) for (int j = 0; j Stype; j+) Maxij = in.nextInt();return Max;public int getAllocation() Allocation = new intPnumStype;System.out.println(请输入已分配资源情况矩阵Allocation);for (int i = 0; i Pnum; i+) for (int j = 0; j Stype; j+) Allocationij = in.nextInt();return Allocation;public int getNeed() Need = new intPnumStype;for (int i = 0; i Pnum; i+) for (int j = 0; j Stype; j+) Needij = Maxij - Allocationij;return Need;public int getAvailable(int x, int y) Available = new intStype;Available = Ssum;System.out.println(进程的可用资源Available为：);for (int j = 0; j Stype; j+) for (int i = 0; i Pnum; i+) Availablej = Availablej - Allocationij;System.out.print(Availablej + );System.out.println();return Available;public void setFinish(int x) for (int i = 0; i Pnum; i+) Finishi = false;public boolean Check_Safe(int avail) boolean boo = false;int k = new intPnum;int a = 0;Work = new intStype;for (int i = 0; i avail.length; i+) Worki = availi;setFinish(Pnum);for (int s = 0; s Pnum; s+) for (int i = 0; i Pnum; i+) if (Finishi = false) for (int j = 0; j Stype; j+) if (Needij = Workj) if (j + 1 = Stype) Finishi = true;ka = i;a+;for (int m = 0; m Stype; m+) Workm = Workm + Allocationim; else continue; else break; else continue;if (a = Pnum) System.out.println(此刻系统处于安全状态，存在安全序列为：);for (int i = 0; i Pnum; i+) System.out.print(P + ki + t);System.out.println();boo = true; else System.out.println(此时系统处于非安全状态);choice();boo = false;return boo;public void Ask_Distribution(boolean b) int a = 0;int a0=0;int a1 = 0;boolean bo = false;for (int i = 0; i Stype; i+) Worki = Availablei;System.out.println(请输入请求分配的进程编号：);int m = in.nextInt();System.out.println(请输入请求的各资源数);int dis = new intStype;for (int i = 0; i Stype; i+) disi = in.nextInt();for (int i = 0; i Stype; i+) if (disi = Needmi) a+;continue; else System.out.println(出错！请求资源数大于需求资源数!);choice();break;if (a = Stype) for (int i = 0; i Stype; i+) if (disi = Worki) a0=a0+1;if(a0=Stype)for (int j = 0; j dis.length; j+) Workj = Workj - disj;Allocationmj = Allocationmj + disj;Needmj = Needmj - disj;bo = Check_Safe(Work);continue; else System.out.println(出错！请求资源数大于可用资源数!);choice();break;if (bo) for (int i = 0; i Stype; i+) Availablei = Availablei-disi;if (Allocationmi = Maxmi) a1 = a1 + 1;while (a1 = Stype) System.out.println(进程P+m+对资源的最大需求已满足，对其占有资源进行回收);for (int j = 0; j Stype; j+) Availablej = Availablej + Allocationmj;break;System.out.println(因此可以满足 + m + 进程的请求，分配后的各种变量值更新为:);output();choice();elsefor (int i = 0; i dis.length; i+) Worki = Worki + disi;Allocationmi = Allocationmi - disi;Needmi = Needmi + disi;public void output() System.out.println( 进程 maxttallocationt needttavailable);System.out.print(P0 );for (int i = 0; i Stype; i+) System.out.print(Max0i + );System.out.print( );for (int i = 0; i Stype; i+) System.out.print(Allocation0i + );System.out.print( );for (int i = 0; i Stype; i+) System.out.print(Need0i + );System.out.print( );for (int i = 0; i Stype; i+) System.out.print(Availablei + );System.out.println();for (int i = 1; i Pnum; i+) System.out.print(P + i + );for (int j = 0; j Stype; j+) System.out.print(Maxij + );System.out.print( );for (int j = 0; j Stype; j+) System.out.print(Allocationij + );System.out.print( );for (int j = 0; j Stype; j+) System.out.print(Needij + );System.out.println();public void choice() System.out.println(*);System.out.println(“Y”选择再次输入n“N”返回银行家算法初始位置);System.out.println(*);String str = in.next();if (str.equals(y) Ask_Distribution(false); else new YinHang();public void quit() System.out.println(您确定要退出吗?请选择“Y”