银行家算法

一 概念

银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

---

二 算法流程及数据结构

当用户申请一组资源时，系统必须做出判断，如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。 1．数据结构 假设有M个进程N类资源，则有如下数据结构： MAX[M*N] M个进程对N类资源的最大需求量 AVAILABLE[N] 系统可用资源数 ALLOCATION[M*N] M个进程已经得到N类资源的资源量 NEED[M*N] M个进程还需要N类资源的资源量 2．银行家算法 设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。 (1)如果Request[N]<=NEED[I，N]，则转(2)；否则，出错。 (2)如果Request[N]<=AVAILABLE，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 3．安全性检查 (1)设置两个工作向量WORK=AVAILABLE；FINISH[M]=FALSE (2)从进程集合中找到一个满足下述条件的进程， FINISH[i]=FALSE NEED<=WORK 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 WORK=WORK+ALLOCATION FINISH=TRUE GO TO 2 (4)如所有的进程Finish[M]=true，则表示安全；否则系统不安全。

---

代码

import java.util.Scanner; public class BankerAlgorithm { private int ProcessNum; //进程数 private int ResourceNum; //资源数 private int[] Available; //每类资源可用数 private int[][] Max; //每个进程度资源的最大需求数 private int[][] Need; //每个进程还缺少的资源数 private int[][] Allocation; //每个进程分到的资源数 public BankerAlgorithm(int processNum, int resourceNum) { //构造方法 System.out.println("请初始化数据："); ProcessNum = processNum; ResourceNum = resourceNum; Allocation = new int[ProcessNum+1][ResourceNum+1]; Available = new int[ResourceNum+1]; Max = new int[ProcessNum+1][ResourceNum+1]; Need = new int[ProcessNum+1][ResourceNum+1]; Scanner input = new Scanner(System.in); for ( int i = 1 ; i <= ProcessNum ; i++){ System.out.println("初始化进程"+i+"的数据："); System.out.println("Max向量初始化:"); for ( int j = 1 ; j <= ResourceNum ; j++){ Max[i][j] = input.nextInt(); } System.out.println("Allocation向量初始化："); for ( int j = 1 ; j <= ResourceNum ; j++){ Allocation[i][j] = input.nextInt(); Need[i][j] = Max[i][j] - Allocation[i][j]; } } System.out.println("Available向量初始化："); for ( int i = 1 ; i <= ResourceNum ; i++){ Available[i] = input.nextInt(); } input.close(); } public int getProcessNum() { return ProcessNum; } public void setProcessNum(int processNum) { ProcessNum = processNum; } public int getResourceNum() { return ResourceNum; } public void setResourceNum(int resourceNum) { ResourceNum = resourceNum; } public int[][] getNeed() { return Need; } public int[] getAvailable() { return Available; } public int[][] getAllocation() { return Allocation; } public void Print(){ //打印当前资源分配表 System.out.println(" 资源分配表"); System.out.println(" Allocation Max Need Available"); System.out.println(" r1 r2 r3 r1 r2 r3 r1 r2 r3 r1 r2 r3"); for ( int i = 1 ; i <= ProcessNum ; i++){ System.out.print(i+" "); for ( int j = 1 ; j <= ResourceNum ; j++){ System.out.print(" "+Allocation[i][j]); } System.out.print(" "); for ( int j = 1 ; j <= ResourceNum ; j++){ System.out.print(" "+Max[i][j]); } System.out.print(" "); for ( int j = 1 ; j <= ResourceNum ; j++){ System.out.print(" "+Need[i][j]); } System.out.print(" "); for ( int j = 1 ; j <= ResourceNum ; j++){ System.out.print(" "+Available[j]); } System.out.println(); } } public int[] Apply_Request(){ //申请Request向量 Scanner in = new Scanner(System.in); System.out.println("请输入Request向量"); int[] Request = new int[this.getResourceNum()+1]; for ( int i = 1 ; i <= getResourceNum() ; i++){ Request[i] = in.nextInt(); } return Request; } public int Apply_Process(){ //输入要申请资源的进程 Scanner in = new Scanner(System.in); System.out.println("请输入需要申请进程数(1-"+this.getProcessNum()+"):"); int process = in.nextInt(); return process; } public int Compare(int[] A , int[] B){ //判断A向量是否小于等于B向量 int flag = 1; if ( A.length == B.length){ for ( int i = 0 ; i < A.length ; i++){ if ( A[i] > B[i]){ flag = 0; break; } } } return flag; } public int Judge_Request(int[] Request ,int process){ //判断Ruqest向量是否大于Need向量或Available向量 int flag = 1; for ( int i = 1 ; i <= this.getResourceNum() ; i++){ if ( Request[i] > this.getNeed()[process][i]){ flag = -1; break; } } if ( flag != -1){ flag = this.Compare(Request, this.Available); } return flag; } public void CarryOut(int flag ,int[] Request , int process){ //修改对应进程的资源分配 if ( flag == -1 ){ System.out.println("申请的Request向量出错!"); } else{ if ( flag == 0){ System.out.println("进程"+process+"进入等待!"); } else{ for ( int i = 1 ; i <= this.getResourceNum() ; i++){ this.getAvailable()[i] -= Request[i]; this.getAllocation()[process][i] += Request[i]; this.getNeed()[process][i] -= Request[i]; } } } } public boolean IsAllTrue(boolean[] Finish){ //判断Finish向量是否全为真 boolean flag = true; for ( int i = 1 ; i < Finish.length ; i++){ if ( !Finish[i]){ flag = false; break; } } return flag; } public boolean Is_Safe(int process){ //安全性算法以及安全序列 int[] Work = new int[this.getResourceNum()+1]; boolean[] Finish = new boolean[this.getProcessNum()+1]; int[] SafeSequence = new int[this.getProcessNum()+1]; int count = 1; //Finish的下标计数器 int j = process; //当前进程 for ( int i = 1 ; i <= this.getResourceNum() ; i++){ //对Work进行初始化 Work[i] = this.getAvailable()[i]; } while( j <= this.getProcessNum()){ //判断安全性以及找出安全序列 for ( int i = 1 ; i <= this.getResourceNum() ; i++){ if ( Finish[j]){ j++; break; } else if ( this.getNeed()[j][i] > Work[i]){ j++; break; } else if( i == this.getResourceNum()){ for ( int m = 1; m <= this.getResourceNum() ; m++){ Work[m] += this.getAllocation()[j][m]; } Finish[j] = true; SafeSequence[count++] = j; j = 1; } } } boolean issafe; if (this.IsAllTrue(Finish)){ //输出安全序列 System.out.println("资源申请成功,安全序列为:"); System.out.print(SafeSequence[1]); for ( int q = 2 ; q <= this.getProcessNum() ; q++){ System.out.print("->"+SafeSequence[q]); } System.out.println(); issafe = true; } else{ System.out.println("系统不安全，资源申请失败！"); issafe = false; } return issafe; } public void Rollback(int process , int[] Request){ //当不安全是资源分配回滚 if ( !this.Is_Safe(process)){ for ( int i = 1 ; i <= this.getResourceNum() ; i++){ this.getAvailable()[i] += Request[i]; this.getAllocation()[process][i] -= Request[i]; this.getNeed()[process][i] += Request[i]; } } } public void clear(int process){ for ( int i = 1 ; i <= this.getResourceNum() ; i++ ){ this.Available[i] += this.getAllocation()[process][i]; this.getAllocation()[process][i] = 0; } } public void CarryBankerAlgorithm(){ Scanner in = new Scanner(System.in); boolean SafeFlag = this.Is_Safe(1); //初始化要申请资源的进程 int process =this.Apply_Process(); //初始化申请向量 int[] Request = this.Apply_Request(); //判断申请向量是否出错 int RequestFlag = this.Judge_Request(Request, process); //进行修改相关数据 this.CarryOut(RequestFlag, Request, process); //判断是否安全 SafeFlag = this.Is_Safe(process); if ( !SafeFlag ){ //不安全就回复原来状态 this.Rollback(process, Request); } System.out.println("新时刻的资源分配表为："); this.Print(); } public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); System.out.println("请输入进程数与资源数："); //初始化进程数与资源数 int n = in.nextInt(); int m = in.nextInt(); //初始化数据 BankerAlgorithm bankeralgorithm = new BankerAlgorithm(n,m); bankeralgorithm.Print(); //执行银行家算法 bankeralgorithm.CarryBankerAlgorithm(); in.close(); } }