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

《计算机操作系统》

题 目

课程设计

银行家算法分析

学 院 计算机与软件学院

专 业 计算机科学与技术 班 级

学 号

姓 名

指导教师

起止时间

一、算法综述

银行家算法：在进程向系统提出资源分配请求时，算法会先对进程提出的请求

进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。

二．算法分析

2.1 银行家算法中的数据结构

为资源的种类 i 进程的数量 j

可利用资源向量 int Available[j] 最大需求矩阵 int Max[i][j] 分配矩阵 int Allocation[i][j]

需求矩阵 int need[i][j]= Max[i][j]- Allocation[i][j] 申请各类资源数量 int Request i[j] i进程申请j资源的数量 工作向量 int Work[x] int Finish[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。

2

Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做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； goto step 2；

(4)如果所有的Finish[i]=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 {

public void start() {

System.out }

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 boolean[50];// 试分配结果标识向量

public YinHang() {

start();

.println(\"*******************************************************

System.out

.println(\" 欢迎使用银行

****\");

家算法\"); System.out \");

.println(\" 120607124 罗巾英

System.out

.println(\"*******************************************************

System.out.println(\"请选择操作：\\n\1.开始使用\\n\2.退出\"); int a;

a = in.nextInt(); if (a == 1) {

input(); quit();

5

****\");

} else {

}

}

public void input() { }

public int[] getSsum() { }

public int[][] getMax() { }

public int[][] getAllocation() {

Allocation = new int[Pnum][Stype];

System.out.println(\"请输入已分配资源情况矩阵Allocation\"); for (int i = 0; i < Pnum; i++) { Max = new int[Pnum][Stype];

System.out.println(\"请输入最大需求矩阵Max:\"); for (int i = 0; i < Pnum; i++) { }

return Max;

for (int j = 0; j < Stype; j++) { }

Max[i][j] = in.nextInt();

Ssum = new int[Stype];

System.out.println(\"请输入各类资源总数Ssum:\"); for (int i = 0; i < Stype; i++) { }

return Ssum;

Ssum[i] = in.nextInt();

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);

6

}

}

for (int j = 0; j < Stype; j++) { }

Allocation[i][j] = in.nextInt();

return Allocation;

public int[][] getNeed() { }

public int[] getAvailable(int x, int y) { }

public void setFinish(int x) { }

public boolean Check_Safe(int avail[]) {

boolean boo = false; int k[] = new int[Pnum]; int a = 0;

Work = new int[Stype];

for (int i = 0; i < avail.length; i++) { for (int i = 0; i < Pnum; i++) { }

Finish[i] = false; Available = new int[Stype]; Available = Ssum;

System.out.println(\"进程的可用资源Available为：\"); for (int j = 0; j < Stype; j++) { }

System.out.println(\"\"); return Available;

for (int i = 0; i < Pnum; i++) { }

System.out.print(Available[j] + \" \");

Available[j] = Available[j] - Allocation[i][j];

Need = new int[Pnum][Stype]; for (int i = 0; i < Pnum; i++) { }

return Need;

for (int j = 0; j < Stype; j++) { }

Need[i][j] = Max[i][j] - Allocation[i][j];

7

}

Work[i] = avail[i];

setFinish(Pnum);

for (int s = 0; s < Pnum; s++) { }

if (a == Pnum) {

System.out.println(\"此刻系统处于安全状态，存在安全序列为：\"); for (int i = 0; i < Pnum; i++) { }

System.out.println(\"\"); boo = true;

System.out.print(\"P\" + k[i] + \"\\"); for (int i = 0; i < Pnum; i++) { }

if (Finish[i] == false) {

for (int j = 0; j < Stype; j++) { }

if (Need[i][j] <= Work[j]) {

if (j + 1 == Stype) {

Finish[i] = true; k[a] = i; a++;

for (int m = 0; m < Stype; m++) { }

Work[m] = Work[m] + Allocation[i][m];

} else { }

continue;

} else { }

break;

} else { }

continue;

} else {

System.out.println(\"此时系统处于非安全状态\");

8

}

}

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++) { }

System.out.println(\"请输入请求分配的进程编号：\"); int m = in.nextInt();

System.out.println(\"请输入请求的各资源数\"); int dis[] = new int[Stype]; for (int i = 0; i < Stype; i++) { }

for (int i = 0; i < Stype; i++) { }

if (a == Stype) {

for (int i = 0; i < Stype; i++) {

if (dis[i] <= Work[i]) {

a0=a0+1; if(a0==Stype){

for (int j = 0; j < dis.length; j++) { }

Work[j] = Work[j] - dis[j];

Allocation[m][j] = Allocation[m][j] + dis[j]; Need[m][j] = Need[m][j] - dis[j];

if (dis[i] <= Need[m][i]) {

a++; continue;

dis[i] = in.nextInt(); Work[i] = Available[i];

} else { }

System.out.println(\"出错请求资源数大于需求资源数!\"); choice(); break;

9

}

}

}

}

bo = Check_Safe(Work);

continue;

System.out.println(\"出错！！！请求资源数大于可用资源数!\"); choice(); break;

} else {

if (bo) {

for (int i = 0; i < Stype; i++) {

Available[i] = Available[i]-dis[i]; if (Allocation[m][i] == Max[m][i]) { }

while (a1 == Stype) {

System.out.println(\"(进程P\"+m+\"对资源的最大需求已满足，对a1 = a1 + 1;

其占有资源进行回收)\"); for (int j = 0; j }

System.out.println(\"因此可以满足\" + m + \"进程的请求，分配后的各种

}

} break;

Available[j] = Available[j] + Allocation[m][j];

变量值更新为:\"); output();

public void output() { }

}

choice();

for (int i = 0; i < dis.length; i++) { }

Work[i] = Work[i] + dis[i];

Allocation[m][i] = Allocation[m][i] - dis[i]; Need[m][i] = Need[m][i] + dis[i];

}else{

10

System.out.println(\" 进程 max\\allocation\ need\\available\");

System.out.println(\"*****************************************\");

System.out.println(\"“Y”选择再次输入\\n“N”返回银行家算法初始位置\"); public void choice() { }

}

System.out.println();

System.out.print(\"P0 \");

for (int i = 0; i < Stype; i++) { }

System.out.print(\" \");

for (int i = 0; i < Stype; i++) { }

System.out.print(\" \");

for (int i = 0; i < Stype; i++) { }

System.out.print(\" \");

for (int i = 0; i < Stype; i++) { }

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(\" \");

for (int j = 0; j < Stype; j++) { }

System.out.print(\" \");

for (int j = 0; j < Stype; j++) { }

System.out.print(Need[i][j] + \" \"); System.out.print(Allocation[i][j] + \" \"); System.out.print(Max[i][j] + \" \"); System.out.print(Available[i] + \" \"); System.out.print(Need[0][i] + \" \"); System.out.print(Allocation[0][i] + \" \"); System.out.print(Max[0][i] + \" \");

11

System.out.println(\"****************************************\"); }

public void quit() {

System.out.println(\"您确定要退出吗?请选择“Y”/“N”\"); String a = in.next(); if (a.equals(\"Y\")) { String str = in.next(); if (str.equals(\"y\")) { }

Ask_Distribution(false); new YinHang(); } else {

System.out.println(\"**************感谢您的使用！**************\"); }

}

public static void main(String[] args) { }

YinHang yh = new YinHang(); } else { }

start();

五、调试结果

12

13

六、实验总结

在这次实验程序的数据结构的设计以及函数设计的过程遇到很多问题。虽然程序的大体结构与思路是对的，但是在很多细节的处理中却出现很多问题。首先，我把实验中用到的一维数组，二维数组都设置成了动态可改变大小的，通过将进程个数、资源种类数作为数组大

14

小的参数来实现的。这样使得程序的实用性提高，当进程个数太少时，不会造成内存资源浪费；当进程个数太多时，也不会出现预定义数组空间不够造成的错误。其次，在把Available的值赋给Work 时，我开始使用了“Work=Available”这样的语句，造成Work值改变时，Available的值会跟着自动改变，后来使用for循环语句进行一一赋值，问题才得到了解决。

七、实验心得

这次实验，我通过将本学期学过的java语言与操作系统的银行家算法结合，编写出了本次实验的代码。从开始程序用到的数据结构的设置到函数的架构都是经过无数次的尝试与改正才得到最终的效果。实验过程中遇到很多细节性的小问题，正是因为这些问题的出现与解决的过程是我感觉收获颇多。这次实验是我真正的将一个算法，或者说是一种思想，通过编码的方式得到体现，是一种理论到实践的转变。自己的动手能力，分析与解决问题的能力得到了很大的提升。

15