银行家算法 : java实现(基于课本)

银行家算法 : java实现(基于课本)

属性

需要在构造方法中传入的
  1. 整型Resources , 用于表名可用资源种类数量, 共有几种资源
  2. 整型Process, 用于表名进程数量, 共有几个进程
  3. 整型数组Available, 用于表名每类可用资源的数量
  4. 整形矩阵Max, 用于表名每个进程所需的总的资源量
  5. 整型矩阵Allocation, 用于表示每个进程目前已经拥有的每类资源资源的资源数量
其他属性
  1. 整形矩阵Need, 用于表示每个进程目前需要的每类资源资源的资源数量
  2. Available2, Allocation2, Need2, 分别时以上三个数据结构的备份, 用于安全性检测, 不破环原数据结构
  3. 整型数组work, 用于表示目前可用的资源数(在检测安全性时使用)
  4. 布尔数组finish, 安全性检测时每一个进程完成后, 对应的索引改为true

方法

public

  1. BankerAlgorithm() 构造方法
  2. Algorithm() 银行家算法
  3. UpdateResources() 更新数据的算法

private

  1. setNeed() 构造Need矩阵的方法
  2. reSetNeed() 刷新需求矩阵的方法
  3. reCopying() 复制备份的方法
  4. rebuild() 用于初始化work和finish的方法
  5. reFinish() 用于刷新work和finish数组的方法
  6. able() 用于判断work中的值够不够减的方法
  7. isSecurity() 用于判断请求是不是安全的方法
  8. findThePath() 如果安全,用于排列出一个安全组合的方法

大体执行流程

传入参数调用构造方法后, 使用银行家算法Algorithm(), 传入请求参数(那个进程申请什么资源多少)

Algorithm()调用setNeed()建立Need矩阵, 经过两部初始判断后调用isSecurity()方法判断请求是否安全,

isSecurity()建立work和finish, 通过判断后返回布尔值给Algorithm(), 如果安全就调用findThePath()找到安全组合, 并输出

测试类中可选择更新数据, 也可选择不更新数据UpdateResources()

需要注意

所有的属性貌似在对象创建之初先于构造方法创建,
也就是说如果属性数组的大小由其他数值属性(需要被构造方法赋值)来确定时,
因为在构造方法赋值前,所使用的初始数值为0, 所以就是说属性数组大小为零,
所以任何此类数组属性都可由动态数组代替(ArrayList/LinkedList).

代码

算法类

import java.util.ArrayList;

public class BankerAlgorithm {

    public int Resources;      //资源数量
    public int Process;        //进程数量
    public int[] Available;    //可用资源向量
    public int[][] Max;        //最大需求矩阵
    public int[][] Allocation; //分配矩阵

    public BankerAlgorithm(int Resources, int Process, int[] Available, int[][] Max, int[][] Allocation){
        //构造方法
        this.Process = Process;
        this.Resources = Resources;
        this.Allocation = Allocation;
        this.Max = Max;
        this.Available = Available;
    }

    /**
     * 所有的属性貌似在对象创建之初先于构造方法创建,
     * 也就是说如果属性数组的大小由其他数值属性(需要被构造方法赋值)来确定时,
     * 因为在构造方法赋值前,所使用的初始数值为0,所以就是说属性数组大小为零
     * 所以任何此类数组属性都可由动态数组代替(ArrayList/LinkedList)
    * */
    private final ArrayList<ArrayList<Integer>> Need = new ArrayList<>();

    private void setNeed(){
        for(int i=0;i<Process;i++){
            Need.add(i,new ArrayList<>());
            for(int j=0;j<Resources;j++){
                Need.get(i).add(j,(Max[i][j] - Allocation[i][j]));
            }
        }
    }

    private void reSetNeed(){
        Need.clear();
        setNeed();
    }

    //Available Allocation Need的备份
    private final ArrayList<Integer> Available2 = new ArrayList<>();
    private final ArrayList<ArrayList<Integer>> Allocation2 = new ArrayList<>();
    private final ArrayList<ArrayList<Integer>> Need2 = new ArrayList<>();

    private void reCopying(){        //用于复制备份
        Available2.clear();
        Allocation2.clear();
        Need2.clear();
        for(int i=0;i<Process;i++){
            Allocation2.add(i,new ArrayList<>());
            Need2.add(i,new ArrayList<>());
            for(int j=0;j<Resources;j++){
                Allocation2.get(i).add(j,Allocation[i][j]);
                Need2.get(i).add(j,Need.get(i).get(j));
            }
        }
        for(int i=0;i<Resources;i++){
            Available2.add(i,Available[i]);
        }
    }

    public void Algorithm(int i, int[] Request){    //进程i向系统提出资源请求
        reSetNeed();
        boolean f = true;           //要求量小于需求量
        for(int j=0;j<Resources;j++){
            if (Request[j] > Need.get(i).get(j)) {
                f = false;
                break;
            }
        }
        if(f){
            boolean f2 = true;          //要求量小于剩余量
            for(int j=0;j<Resources;j++){
                if (Request[j] > Available[j]) {
                    f2 = false;
                    break;
                }
            }
            if(f2){
                reCopying();
                for(int j=0;j<Resources;j++){
                    Available2.set(j,Available2.get(j)-Request[j]);
                    Allocation2.get(i).set(j,(Allocation2.get(i).get(j)+Request[j]));
                    Need2.get(i).set(j,(Need2.get(i).get(j)-Request[j]));
                }
                if(isSecurity()){
                    ArrayList<Integer> path = findThePath();
                    for(int p:path)
                        System.out.print("p"+p+" ");
                }else {
                    System.out.println("此请求不安全!");
                }
            }else
                System.out.println("请求不通过: 请求资源数量大于现有资源量!");
        }else
            System.out.println("请求不通过: 申请资源数量大于自身所需!");
    }

    //work和finish
    private final ArrayList<Integer> work = new ArrayList<>();
    private final ArrayList<Boolean> finish = new ArrayList<>();

    private void rebuild(){         //用于初始化work和finish
        for(int i=0;i<Resources;i++){
            work.add(Available2.get(i));
        }
        for(int i=0;i<Process;i++)
            finish.add(false);
    }

    private void reFinish(){            //用于刷新work和finish数组
        work.clear();
        for(int i=0;i<Resources;i++){
            work.add(Available2.get(i));
        }
        finish.clear();
        for(int i=0;i<Process;i++)
            finish.add(false);
    }

    private boolean able(int i){        //用于判断work中的值够不够减
        boolean f = true;
        for(int j=0;j<Resources;j++){
            if (work.get(j) < Need2.get(i).get(j)) {
                f = false;
                break;
            }
        }
        return f;
    }

    private boolean isSecurity(){       //用于判断是不是安全
        rebuild();
        boolean flag = false;
        for(int n=0;n<Process;n++) {
            if(!flag) {
                flag = true;
                for (int i = 0; i < Process; i++) {
                    if (able(i) && !finish.get(i)) {
                        for (int j = 0; j < Resources; j++) {
                            work.set(j,work.get(j)+Allocation2.get(i).get(j));
                            Allocation2.get(i).set(j,0);
                        }
                        finish.set(i,true);
                    }
                }
                for (int i = 0; i < Process; i++) {
                    if (!finish.get(i)) {
                        flag = false;
                        break;
                    }
                }
            }
        }
        return flag;
    }

    private ArrayList<Integer> findThePath(){   //用于排列出一个安全组合
        reCopying();
        rebuild();
        reFinish();
        ArrayList<Integer> Path = new ArrayList<>();
        boolean flag = false;
        for(int n=0;n<Process;n++) {
            if(!flag) {
                flag = true;
                for (int i = 0; i < Process; i++) {
                    if (able(i) && !finish.get(i)) {
                        for (int j = 0; j < Resources; j++) {
                            work.set(j,work.get(j)+Allocation2.get(i).get(j));
                            Allocation2.get(i).set(j,0);
                        }
                        finish.set(i,true);
                        Path.add(i);
                    }
                }
                for (int i = 0; i < Process; i++) {
                    if (!finish.get(i)) {
                        flag = false;
                        break;
                    }
                }
            }
        }
        return Path;
    }

    public void UpdateResources(int n, int[] Request){  //执行操作, 并更新数据
        if(isSecurity()) {
            for (int i = 0; i < Resources; i++) {
                Available[i] = Available[i] - Request[i];
                Allocation[n][i] = Allocation[n][i] + Request[i];
                Need.get(n).set(i, Need.get(n).get(i) - Request[i]);
            }
        }
    }

}

测试类(两个测试案例)

public class Test {

    public static void test1(){
        int Resources = 3;
        int Process = 5;
        int[] Available = new int[]{3,3,2};
        int[][] Max = new int[Process][Resources];
        int[][] Allocation = new int[Process][Resources];
        int[] max = new int[]{
                7,5,3,3,2,2,9,0,2,2,2,2,4,3,3
        };
        int[] allocation = new int[]{
                0,1,0,2,0,0,3,0,2,2,1,1,0,0,2
        };
        for(int i=0;i<Process;i++){
            for(int j=0;j<Resources;j++){
                Max[i][j] = max[i*Resources+j];
                Allocation[i][j] = allocation[i*Resources+j];
            }
        }
        BankerAlgorithm banker = new BankerAlgorithm(Resources,Process,Available,Max,Allocation);
        int[] request1 = new int[]{1,0,2};
        //P1发出请求Request(1,0,2),执行银行家算法
        banker.Algorithm(1,request1);
        banker.UpdateResources(1,request1);

        System.out.println();

        int[] request2 = new int[]{3,3,0};
        banker.Algorithm(4,request2);
        banker.UpdateResources(1,request1);
    }

    public static void test2(){
        int Resources = 3;
        int Process = 5;
        int[] Available = new int[]{2,1,0};
        int[][] Max = new int[Process][Resources];
        int[][] Allocation = new int[Process][Resources];
        int[] max = new int[]{
                7,5,3,3,2,2,9,0,2,2,2,2,4,3,3
        };
        int[] allocation = new int[]{
                0,3,0,3,0,2,3,0,2,2,1,1,0,0,2
        };
        for(int i=0;i<Process;i++){
            for(int j=0;j<Resources;j++){
                Max[i][j] = max[i*Resources+j];
                Allocation[i][j] = allocation[i*Resources+j];
            }
        }
        BankerAlgorithm banker = new BankerAlgorithm(Resources,Process,Available,Max,Allocation);
        int[] request0 = new int[]{0,2,0};
        banker.Algorithm(0,request0);
    }

    public static void main(String[] args) {
        test1();
        System.out.println();
        test2();
    }

}

热门文章

暂无图片
编程学习 ·

Java输出数组的内容

Java输出数组的内容_一万个小时-CSDN博客_java打印数组内容1. 输出内容最常见的方式// List<String>类型的列表List<String> list new ArrayList<String>();list.add("First");list.add("Second");list.add("Third");list.ad…
暂无图片
编程学习 ·

母螳螂的“魅惑之术”

在它们对大蝗虫发起进攻的时候&#xff0c;我认认真真地观察了一次&#xff0c;因为它们突然像触电一样浑身痉挛起来&#xff0c;警觉地面对限前这个大家伙&#xff0c;然后放下自己优雅的身段和祈祷的双手&#xff0c;摆出了一个可怕的姿势。我被眼前的一幕吓到了&#xff0c;…
暂无图片
编程学习 ·

疯狂填词 mad_libs 第9章9.9.2

#win7 python3.7.0 import os,reos.chdir(d:\documents\program_language) file1open(.\疯狂填词_d9z9d2_r.txt) file2open(.\疯狂填词_d9z9d2_w.txt,w) words[ADJECTIVE,NOUN,VERB,NOUN] str1file1.read()#方法1 for word in words :word_replaceinput(fEnter a {word} :)str1…
暂无图片
编程学习 ·

HBASE 高可用

为了保证HBASE是高可用的,所依赖的HDFS和zookeeper也要是高可用的. 通过参数hbase.rootdir指定了连接到Hadoop的地址,mycluster表示为Hadoop的集群. HBASE本身的高可用很简单,只要在一个健康的集群其他节点通过命令 hbase-daemon.sh start master启动一个Hmaster进程,这个Hmast…
暂无图片
编程学习 ·

js事件操作语法

一、事件的绑定语法 语法形式1 事件监听 标签对象.addEventListener(click,function(){}); 语法形式2 on语法绑定 标签对象.onclick function(){} on语法是通过 等于赋值绑定的事件处理函数 , 等于赋值本质上执行的是覆盖赋值,后赋值的数据会覆盖之前存储的数据,也就是on…
暂无图片
编程学习 ·

Photoshop插件--晕影动态--选区--脚本开发--PS插件

文章目录1.插件界面2.关键代码2.1 选区2.2 动态晕影3.作者寄语PS是一款栅格图像编辑软件&#xff0c;具有许多强大的功能&#xff0c;本文演示如何通过脚本实现晕影动态和选区相关功能&#xff0c;展示从互联网收集而来的一个小插件&#xff0c;供大家学习交流&#xff0c;请勿…
暂无图片
编程学习 ·

vs LNK1104 无法打开文件“xxx.obj”

写在前面&#xff1a; 向大家推荐两本新书&#xff0c;《深度学习计算机视觉实战》和《学习OpenCV4&#xff1a;基于Python的算法实战》。 《深度学习计算机视觉实战》讲了计算机视觉理论基础&#xff0c;讲了案例项目&#xff0c;讲了模型部署&#xff0c;这些项目学会之后可以…
暂无图片
编程学习 ·

工业元宇宙的定义与实施路线图

工业元宇宙的定义与实施路线图 李正海 1 工业元宇宙 给大家做一个关于工业元宇宙的定义。对于工业&#xff0c;从设计的角度来讲&#xff0c;现在的设计人员已经做到了普遍的三维设计&#xff0c;但是进入元宇宙时代&#xff0c;就不仅仅只是三维设计了&#xff0c;我们的目…
暂无图片
编程学习 ·

【leectode 2022.1.15】完成一半题目

有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目&#xff0c;整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题&#xff0c;请返回被选的 N 道题目至少包含多少种知识点类型。 示例 1&#xff1a…
暂无图片
编程学习 ·

js 面试题总结

一、js原型与原型链 1. prototype 每个函数都有一个prototype属性&#xff0c;被称为显示原型 2._ _proto_ _ 每个实例对象都会有_ _proto_ _属性,其被称为隐式原型 每一个实例对象的隐式原型_ _proto_ _属性指向自身构造函数的显式原型prototype 3. constructor 每个prot…
暂无图片
编程学习 ·

java练习代码

打印自定义行数的空心菱形练习代码如下 import java.util.Scanner; public class daYinLengXing{public static void main(String[] args) {System.out.println("请输入行数");Scanner myScanner new Scanner(System.in);int g myScanner.nextInt();int num g%2;//…
暂无图片
编程学习 ·

RocketMQ-什么是死信队列?怎么解决

目录 什么是死信队列 死信队列的特征 死信消息的处理 什么是死信队列 当一条消息初次消费失败&#xff0c;消息队列会自动进行消费重试&#xff1b;达到最大重试次数后&#xff0c;若消费依然失败&#xff0c;则表明消费者在正常情况下无法正确地消费该消息&#xff0c;此时…
暂无图片
编程学习 ·

项目 cg day04

第4章 lua、Canal实现广告缓存 学习目标 Lua介绍 Lua语法 输出、变量定义、数据类型、流程控制(if..)、循环操作、函数、表(数组)、模块OpenResty介绍(理解配置) 封装了Nginx&#xff0c;并且提供了Lua扩展&#xff0c;大大提升了Nginx对并发处理的能&#xff0c;10K-1000K Lu…
暂无图片
编程学习 ·

输出三角形

#include <stdio.h> int main() { int i,j; for(i0;i<5;i) { for(j0;j<i;j) { printf("*"); } printf("\n"); } }
暂无图片
编程学习 ·

stm32的BOOTLOADER学习1

序言 最近计划学习stm32的BOOTLOADER学习,把学习过程记录下来 因为现在网上STM32C8T6还是比较贵的,根据我的需求flash空间小一些也可以,所以我决定使用stm32c6t6.这个芯片的空间是32kb的。 #熟悉芯片内部的空间地址 1、flash ROM&#xff1a; 大小32KB&#xff0c;范围&#xf…
暂无图片
编程学习 ·

通过awk和shell来限制IP多次访问之学不会你打死我

学不会你打死我 今天我们用shell脚本&#xff0c;awk工具来分析日志来判断是否存在扫描器来进行破解网站密码——限制访问次数过多的IP地址&#xff0c;通过Iptables来进行限制。代码在末尾 首先我们要先查看日志的格式&#xff0c;分析出我们需要筛选的内容&#xff0c;日志…
暂无图片
编程学习 ·

Python - 如何像程序员一样思考

在为计算机编写程序之前&#xff0c;您必须学会如何像程序员一样思考。学习像程序员一样思考对任何学生都很有价值。以下步骤可帮助任何人学习编码并了解计算机科学的价值——即使他们不打算成为计算机科学家。 顾名思义&#xff0c;Python经常被想要学习编程的人用作第一语言…
暂无图片
编程学习 ·

蓝桥杯python-数字三角形

问题描述 虽然我前后用了三种做法&#xff0c;但是我发现只有“优化思路_1”可以通过蓝桥杯官网中的测评&#xff0c;但是如果用c/c的话&#xff0c;每个都通得过&#xff0c;足以可见python的效率之低&#xff08;但耐不住人家好用啊&#xff08;哭笑&#xff09;&#xff09…