JAVA-银行家算法

简介: JAVA-银行家算法

银行家算法是一个避免死锁的著名算法,是由艾兹格.迪杰斯特拉设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

一、背景介绍

在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。

安全序列:指一个进程序列{p1,......,pn}是安全的,即对于每一个进程pi(1<= i<=n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程pj(j<i)当前占有资源量之和。


安全状态一定是没有死锁发生的。


不安全状态:不存在一个安全序列,不安全状态一定导致死锁。

二、相关数据结构

银行家算法中的数据结构
  • 设系统中有m种不同资源, n个进程
  • Available向量: 系统中尚未分配的每种资源的总量
  • Available[j]: 尚未分配的资源j的数量
  • Max矩阵: 各个进程对每种资源的最大需求量(进程事先声明)
  • Max[i, j](Claim[i,j]): 进程i 对资源j 的最大需求量
  • Allocation矩阵: 当前资源分配状况
  • Allocation[i, j]: 进程i获得的资源j的数量
  • Need矩阵: 每个进程还需要的资源的数量
  • Need[i, j]: 进程i尚需的资源j的数量
各数据结构之间的关系
  • Resource[j] = Available[j] + (Allocation[1, j] + Allocation[2, j] + … + Allocation[n, j])
  • Max[i, j] <= Resource[j]
  • Allocation[i, j] <= Max[i, j]
  • Allocation[i, j] + Need[i, j] =Max[i, j]
安全性算法

1. 设Work和Finish 分别是长度为m 和n 的向量,按如下方式进行初始化:

    Work = Available

           Finish [i] = false ( i =1,2, …, n)

2. 查找这样的i使其满足:(a) Finish [i] = false  (b) Need i <=Work

3. 如果没有这样的 i 存在,那么就转到第4步.

4. Work = Work + Allocation i Finish[i] = True 返回到第2步.

5. 如果对所有的i,Finish [i] == True ,那么系统处于安全状态

例题讲解1

R1,R2,R3的数量分别为(9,3,6); Available(1,1,2)

问:1.该时刻是否为安全状态

      2.进程A请求资源Request(1,0,1),能够分配吗?为什么?

解题步骤如下:(注:!!!圆圈序号表示做题方法,答案中不必出现。)

1.画出如下表格

①首先将available中的数字填在首行work中

②available(1,1,2)分别和A、B、C、D中的need相比较,倘若小于,则从上往下依次选择。例如B(1,0,2)小于则将B填入第一行,其后need、Allocation依次填入


③接着计算work+allocation的值与R1R2R3(9,3,6)相比较,小于则为true


④将上一行中的work+allocation的值填入下一行work中,接着重复②之后的操作。


⑤直到填完最后一个进程,finish都为true则此时产生了一个安全序列。


2.①将requestA和needA和Available相比较,若小于二者则可继续判断,否则不够分配。


RequestA(1,0,1)<=Need(2,2,2)

RequestA(1,0,1)<=Available(1,1,2)


②修改A的allocation和need,allocation+requestA , need-requestA 并将值填入其中。

假定满足进程A的要求,为它分配所申请的资源,并且修改AllocaitonA 和 NeedA,得到:


此时:Available=(0,1,1):不能分配给任何进程;因此不能分配此次请求。


③此时available-requsetA得到(0,1,1)此时,更新A的状态,重复第一问判断是否存在安全状态。通过比较我们发现available(0,1,1)小于任何一个进程的Need故无法进行分配

例题讲解2

设系统在T0时刻系统状态如下:剩余资源向量为: A=(2, 3, 3)


问:① T0时刻是否为安全状态?若是,请给出安全序列。

      ② 在T0时刻若进程P2请求资源(0,3,4),是否能实施资源分配?为什么?

      ③ 在②的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配?为什么?


解析:与题1不同的是,题2并未给出一个系统的表,因此需要在草稿本上列出表格的大概状态。最大资源需求(Max)已分配资源数量(allocation)剩余资源向量(available)


need = max - allocation,其余步骤参考题1 即可


答案:1. 是,安全序列:p4, p5, p1, p2, p3


           2.因为 R(0,3,4)> A (2,3,3,)所以不能分配。


           3.因为R(2,0,1)<=N4(2, 0,1)且 < A(2,3,3)假设可以满足,则N4=(0, 0, 0), A= (0,3,2),在此基础上,是安全的,因此可以实施分配。安全序列为:p4,p5,p1,p2,p3

三、参考示例代码

import java.util.Arrays;
 
class BankersAlgorithm {
    private int[][] max;   // 最大需求矩阵
    private int[][] allocation;   // 已分配资源矩阵
    private int[][] need;   // 剩余需求矩阵
    private int[] available;   // 可用资源向量
    private int[][] request;   // 请求资源矩阵
 
    public BankersAlgorithm(int[][] max, int[][] allocation, int[] available) {
        this.max = max;
        this.allocation = allocation;
        this.available = available;
 
        int numOfProcesses = max.length;
        int numOfResources = available.length;
 
        this.need = new int[numOfProcesses][numOfResources];
        this.request = new int[numOfProcesses][numOfResources];
 
        // 计算剩余需求矩阵
        for (int i = 0; i < numOfProcesses; i++) {
            for (int j = 0; j < numOfResources; j++) {
                need[i][j] = max[i][j] - allocation[i][j];
            }
        }
    }
 
    public void requestResources(int pid, int[] request) {
        System.out.println("进程 " + pid + " 请求资源: " + Arrays.toString(request));
        boolean safe = checkSafety(pid, request);
 
        if (safe) {
            System.out.println("请求通过,为进程 " + pid + " 分配资源 " + Arrays.toString(request));
            allocateResources(pid, request);
        } else {
            System.out.println("请求被拒绝,进程 " + pid + " 等待...");
        }
    }
 
    private boolean checkSafety(int pid, int[] request) {
        int numOfProcesses = max.length;
        int numOfResources = available.length;
 
        int[] work = Arrays.copyOf(available, numOfResources);
        boolean[] finish = new boolean[numOfProcesses];
 
        // 设置该进程的请求资源情况
        for (int i = 0; i < numOfResources; i++) {
            allocation[pid][i] += request[i];
            need[pid][i] -= request[i];
            work[i] -= request[i];
        }
 
        int count = 0;   // 用于统计已分配资源的进程数
        boolean hasFinished = true;   // 标识是否存在符合条件的进程
 
        while (count < numOfProcesses && hasFinished) {
            hasFinished = false;
 
            for (int i = 0; i < numOfProcesses; i++) {
                if (!finish[i] && checkNeedLessOrEqual(work, need[i])) {
                    // 分配资源给进程
                    for (int j = 0; j < numOfResources; j++) {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = true;
                    count++;
                    hasFinished = true;
                }
            }
        }
 
        // 恢复该进程的请求资源情况
        for (int i = 0; i < numOfResources; i++) {
            allocation[pid][i] -= request[i];
            need[pid][i] += request[i];
            work[i] += request[i];
        }
 
        return count == numOfProcesses;
    }
 
    private boolean checkNeedLessOrEqual(int[] work, int[] need) {
        for (int i = 0; i < work.length; i++) {
            if (work[i] < need[i]) {
                return false;
            }
        }
        return true;
    }
 
    private void allocateResources(int pid, int[] request) {
        int numOfResources = available.length;
 
        for (int i = 0; i < numOfResources; i++) {
            available[i] -= request[i];
            allocation[pid][i] += request[i];
            need[pid][i] -= request[i];
        }
    }
}
 
public class TestBanker {
    public static void main(String[] args) {
        int[][] max = {
                {7, 5, 3},
                {3, 2, 2},
                {9, 0, 2},
                {2, 2, 2},
                {4, 3, 3}
        };
 
        int[][] allocation = {
                {0, 1, 0},
                {2, 0, 0},
                {3, 0, 2},
                {2, 1, 1},
                {0, 0, 2}
        };
 
        int[] available = {3, 3, 2};
 
        // 继续编写您想要的代码逻辑
    }
}
相关文章
|
11天前
|
缓存 算法 安全
Java中的数据结构与算法优化策略
Java中的数据结构与算法优化策略
|
9天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
19 1
|
11天前
|
缓存 算法 NoSQL
Java中的分布式缓存与一致性哈希算法
Java中的分布式缓存与一致性哈希算法
|
7天前
|
存储 算法 Java
分布式自增ID算法---雪花算法(SnowFlake)Java实现
分布式自增ID算法---雪花算法(SnowFlake)Java实现
|
9天前
|
算法 Java 程序员
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
12 0
|
10天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
11 0
|
10天前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
10 0
|
12天前
|
监控 算法 搜索推荐
有效利用Java中的内置算法优化应用性能
有效利用Java中的内置算法优化应用性能
|
12天前
|
存储 算法 搜索推荐
使用Java实现高效的数据结构与算法
使用Java实现高效的数据结构与算法
|
12天前
|
存储 算法 搜索推荐
Java中的数据结构与算法实现
Java中的数据结构与算法实现