银行家算法

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

目的

银行家算法是由Dijkstra设计的最具有代表性的避免死锁的算法。本实验通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。

思路

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

内容

设置数据结构：
可利用资源向量（Availiable）
最大需求矩阵（Max），分配矩阵（Allocation），需求矩阵（Need）
设计安全性算法：
设置工作向量Work 表示系统可提供进程继续运行可利用资源数目,Finish 表示系统是否有足够的资源分配给进程
寻找安全序列
设计银行家算法:
用键盘输入的方式申请资源；
如果预分配后，系统处于安全状态，则修改系统的资源分配情况；
如果预分配后，系统处于不安全状态，则提示不能满足请求。

主要数据结构

可利用资源向量 int Available[m] m为资源种类

最大需求矩阵 int Max[n][m] n为进程的数量

分配矩阵 int Allocation[n][m]

还需资源矩阵 int need[i][j]= Max[i][j]- Allocation[i][j]

申请资源数量 int Request [m]

工作向量 int Work[m] int Finish[n]

实例

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

试问：

scss复制代码 一、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)，系统是否能将资源分配给它，请考虑。

程序代码如下

java复制代码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;//跳出循环
            }
        }
    }

}

测试代码

java复制代码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");
	}
	
    }
 
}

运行结果如下

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有