银行家算法

银行家算法是一个用来避免死锁的算法。
下面我们通过一个例题来解释怎么使用

实例

假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型资源{A、B、C}，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下 所示。

试问：
一、T0时刻是否安全？

二、T0之后的T1时刻P1请求资源Request1(1,0,2)是否允许？

三、T1之后的T2时刻P4请求资源Request4(3,3,0)是否允许？

四、T2之后的T3时刻P0请求资源Request0(0,2,0)是否允许？
解：一、T0时刻是否安全？
工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目
(1) T0时刻安全性分析

存在安全序列{P1, P3, P0, P2, P4}，系统安全。
二、T0之后的T1时刻P1请求资源Request1(1,0,2)可否允许？
① Request1(1,0,2) ≤ Need1(1,2,2)，P1请求在最大需求范围内;
② Request1(1,0,2) ≤ Available1(3,3,2)，可用资源可满足P1请求需要;
③ 假定可为P1分配，修改Available,Allocation1,Need1向量。 Available(2,3,0) = Available(3,3,2)-Request1(1,0,2); Need1(0,2,0) = Need1(1,2,2)-Request1(1,0,2); Allocation1(3,0,2) =Allocation1(2,0,0)+Request1(1,0,2);
④ 利用安全性算法检查试探将资源分配后状态的安全性

存在安全序列{P1, P3, P0, P2, P4}，所以试探将资源分配给进程P1后的状态是安全的，可将资源分配给进程P1。
三、
T1之后的T2时刻P4请求资源Request4(3,3,0)是否允许？
Request4(3,3,0)≤Need4(4,3,1)，P4请求在最大需求范围内。 Request4(3,3,0)≤Available(2,3,0)不成立，即可用资源暂不能满足P4请求资源需要，P4阻塞等待。 P4请求资源Request4(3,3,0)不允许。
四、
T2之后的T3时刻P0请求资源Request0(0,2,0)是否允许？
Request0(0，2，0)≤Need0(7，4，3)； Request0(0，2，0)≤Available(2，3，0)； 系统暂时先假定可为P0分配资源，并修改有关数据，如下图所示。

进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。 如果在银行家算法中，把P0发出的请求向量改为Request0(0，1，0)，系统是否能将资源分配给它，请考虑。
程序代码如下
`package com.lzl.bank;

import java.util.Scanner;

public class BankerClass {

int[] Available = {10, 8, 7};
int[][] Max = new int[3][3];
int[][] Alloction = new int[3][3];
int[][] Need = new int[3][3];
int[][] Request = new int[3][3];
int[] Work = new int[3];

int num = 0;//进程编号
Scanner in = new Scanner(System.in);

public BankerClass() {
    // Max={{6,3,2},{5,6,1},{2,3,2}};

}
public void setSystemVariable(){//设置各初始系统变量，并判断是否处于安全状态。
    setMax();
    setAlloction();
    printSystemVariable();
    SecurityAlgorithm();
}

public void setMax() {//设置Max矩阵
    System.out.println("请设置各进程的最大需求矩阵Max：");
    for (int i = 0; i < 3; i++) {
        System.out.println("请输入进程P" + i + "的最大资源需求量：");
        for (int j = 0; j < 3; j++) {
            Max[i][j] = in.nextInt();
        }
    }
}

public void setAlloction() {//设置已分配矩阵Alloction
    System.out.println("请设置请各进程分配矩阵Alloction：");
    for (int i = 0; i < 3; i++) {
        System.out.println("晴输入进程P" + i + "的分配资源量：");
        for (int j = 0; j < 3; j++) {
            Alloction[i][j] = in.nextInt();
        }
    }
    System.out.println("Available=Available-Alloction.");
    System.out.println("Need=Max-Alloction.");
    for (int i = 0; i < 3; i++) {//设置Alloction矩阵
        for (int j = 0; j < 3; j++) {
            Available[i] = Available[i] - Alloction[j][i];
        }
    }
    for (int i = 0; i < 3; i++) {//设置Need矩阵
        for (int j = 0; j < 3; j++) {
            Need[i][j] = Max[i][j] - Alloction[i][j];
        }
    }
}

public void printSystemVariable(){
    System.out.println("此时资源分配量如下：");
    System.out.println("进程  "+"   Max   "+"   Alloction "+"    Need  "+"     Available ");
    for(int i=0;i<3;i++){
        System.out.print("P"+i+"  ");
        for(int j=0;j<3;j++){
           System.out.print(Max[i][j]+"  "); 
        }
        System.out.print("|  ");
        for(int j=0;j<3;j++){
           System.out.print(Alloction[i][j]+"  "); 
        }
        System.out.print("|  ");
        for(int j=0;j<3;j++){
           System.out.print(Need[i][j]+"  "); 
        }
        System.out.print("|  ");
        if(i==0){
            for(int j=0;j<3;j++){
                System.out.print(Available[j]+"  ");
            }
        }
        System.out.println();
    }
}

public void setRequest() {//设置请求资源量Request


    System.out.println("请输入请求资源的进程编号：");
    num= in.nextInt();//设置全局变量进程编号num
    System.out.println("请输入请求各资源的数量：");
    for (int j = 0; j < 3; j++) {
        Request[num][j] = in.nextInt();
    }
    System.out.println("即进程P" + num + "对各资源请求Request：(" + Request[num][0] + "," + Request[num][1] + "," + Request[num][2] + ").");

    BankerAlgorithm();
}

public void BankerAlgorithm() {//银行家算法
    boolean T=true;

    if (Request[num][0] <= Need[num][0] && Request[num][1] <= Need[num][1] && Request[num][2] <= Need[num][2]) {//判断Request是否小于Need
        if (Request[num][0] <= Available[0] && Request[num][1] <= Available[1] && Request[num][2] <= Available[2]) {//判断Request是否小于Alloction
            for (int i = 0; i < 3; i++) {
                Available[i] -= Request[num][i];
                Alloction[num][i] += Request[num][i];
                Need[num][i] -= Request[num][i];
            }

        } else {
            System.out.println("当前没有足够的资源可分配，进程P" + num + "需等待。");
           T=false;
        }
    } else {
        System.out.println("进程P" + num + "请求已经超出最大需求量Need.");
        T=false;
    }

   if(T==true){
    printSystemVariable(); 
    System.out.println("现在进入安全算法：");
    SecurityAlgorithm();
   }
}


public void SecurityAlgorithm() {//安全算法
    boolean[] Finish = {false, false, false};//初始化Finish
    int count = 0;//完成进程数
    int circle=0;//循环圈数
    int[] S=new int[3];//安全序列
    for (int i = 0; i < 3; i++) {//设置工作向量
        Work[i] = Available[i];
    }
    boolean flag = true;
    while (count < 3) {
        if(flag){
            System.out.println("进程  "+"   Work  "+"   Alloction "+"    Need  "+"     Work+Alloction ");
            flag = false;
        }
        for (int i = 0; i < 3; i++) {

            if (Finish[i]==false&&Need[i][0]<=Work[0]&&Need[i][1]<=Work[1]&&Need[i][2]<=Work[2]) {//判断条件
                System.out.print("P"+i+"  ");
                for (int k = 0; k < 3; k++){
                    System.out.print(Work[k]+"  ");
                }
                System.out.print("|  ");
                for (int j = 0; j<3;j++){
                Work[j]+=Alloction[i][j];
                }
                Finish[i]=true;//当当前进程能满足时
                S[count]=i;//设置当前序列排号

                count++;//满足进程数加1
                for(int j=0;j<3;j++){
                   System.out.print(Alloction[i][j]+"  "); 
                }
                System.out.print("|  ");
                for(int j=0;j<3;j++){
                   System.out.print(Need[i][j]+"  "); 
                }
                System.out.print("|  ");
                for(int j=0;j<3;j++){
                   System.out.print(Work[j]+"  "); 
                }
                System.out.println();
            }

        }
        circle++;//循环圈数加1

        if(count==3){//判断是否满足所有进程需要
            System.out.print("此时存在一个安全序列：");
            for (int i = 0; i<3;i++){//输出安全序列
                System.out.print("P"+S[i]+" ");
            }
            System.out.println("故当前可分配！");
            break;//跳出循环
        }
        if(count<circle){//判断完成进程数是否小于循环圈数
            count=5;
            System.out.println("当前系统处于不安全状态，故不存在安全序列。");
            break;//跳出循环
        }
    }
}

}`

测试代码
`package com.lzl.bank;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class ProcessToo {
public String name;// 进程名
public int run;// 已经运行的时间

public ProcessToo(String name, int run, int needtime) {
this.name = name;
this.run = run;
this.needtime = needtime;
}

public int needtime;// 所需要的时间

}

public class Test1 {

public static void main(String[] args) {
List<String> listname=new ArrayList<>();//记录淘汰的进程名
List<Integer> listtime=new ArrayList<>();//记录淘汰的进程的淘汰时间
int cputime = 0;// CPU运行时间

Scanner in = new Scanner(System.in);
System.out.println("请输入进程个数：");
int n = in.nextInt();
String name;
int ttime;
int needtime;
List<ProcessToo> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
    System.out.println("请输入第"+(i+1)+"进程名：");
    name = in.next();
    System.out.println("请输入第"+(i+1)+"运行时间：");
    needtime = in.nextInt();
    ProcessToo pcb = new ProcessToo(name, 0, needtime);// 运行时间初始化为0
    list.add(pcb);
}

for (int i = 0; i < list.size(); i++) {
    cputime++;
    System.out.println("CPU时刻：" + cputime);
    System.out.println("正在运行的进程："+list.get(i).name);
    System.out.println("Name   run  req  status");
    list.get(i).run++;//当前进程的运行时间+1
    for(int j = 0;j <list.size();j ++) {
    System.out.print(list.get(j).name+"   "+list.get(j).run+"   "+list.get(j).needtime+"   ");
    System.out.println(list.get(j).run==list.get(j).needtime?"E":"R");
    }
    if(list.get(i).needtime==list.get(i).run) {
    listtime.add(cputime);
    listname.add(list.get(i).name);
    list.remove(i);
    i--;
    }else {
    if (i == (list.size() - 1)) {
        i = -1;
        }
    }
}
for(int i =0;i < n;i ++) {
    System.out.println(listname.get(i)+"的周转时间："+listtime.get(i)+"ms");
}

}

}`
运行结果如下