银行家算法实现代码-蒲公英云

银行家算法代码

简介：本文为大家奉献银行家算法的java代码实现，拿去吧，我的算法思路就是深度优先遍历（DFS），对深度优先遍历不熟悉的，可以看看我的这篇博客。

理解DFS参考文章：排列数字（Java每日一题）

银行家算法：银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

/*银行家算法  Banker Algorithm*/
/*算法思路：dfs（深度优先遍历）*/
import java.util.*;
public class Main{
    static class Process{
     // 每个进程的情况
        public Resources max;
        public Resources allocation;
        public Resources need;
        public Process() {
            // TODO Auto-generated constructor stub
        }
        public Process(Resources max, Resources allocation, Resources need)
        {
            this.max = max;
            this.allocation = allocation;
            this.need = need;
        }
    }
    static class Resources  // 这里以三个资源为例子
    {
        int A, B, C;
        public Resources(int A, int B, int C) {
            this.A = A;
            this.B = B;
            this.C = C;
            //System.out.println("RE" + this.A + " " + this.B + " " + this.C);
        }
        void showAll()  // 查看当前的资源的占比情况 调试用的
        {
            System.out.println("A:" + A + " " + "B:" + B + " " + "C:" + C);
        }
    }
    static List<Process> pset = new ArrayList<Process>();   // 存放每个进程的情况
    static List<Integer> v = new ArrayList<Integer>();  // 存放最后的安全序列的
    static int N = 110;   // 资源的最大个数的限制
    static boolean [] st = new boolean[N];   // dfs的辅助数组
    static int n;
    static Resources available;    // 把可用的资源定义为全局数组 方便修改
    static int cnt = 0;   // 存放最后的结果数
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("输入进程数：");
        n = in.nextInt();  // 进程的数量
        int a, b, c;
        int i = 0;
        int t = n;
        while(t -- > 0)
        {
            System.out.println("输入进程P" + i + "的Max:");
            System.out.print("A:");
            a = in.nextInt();
            System.out.print("B:");
            b = in.nextInt();
            System.out.print("C:");
            c = in.nextInt();
            i ++;
            Resources max = new Resources(a, b, c);
            System.out.println("输入Allocation:");
            System.out.print("A:");
            a = in.nextInt();
            System.out.print("B:");
            b = in.nextInt();
            System.out.print("C:");
            c = in.nextInt();            
            Resources allocation = new Resources(a, b, c);
            pset.add(new Process(max, allocation, Sub(max, allocation)));
        }
        System.out.println("输入Available:");
        System.out.print("A:");
        a = in.nextInt();
        System.out.print("B:");
        b = in.nextInt();
        System.out.print("C:");
        c = in.nextInt();
        available = new Resources(a, b, c);
        if (n == 0) return;        
        dfs(0);
        if (cnt == 0) System.out.println("没有安全序列");
        System.out.println("安全序列的数量：" + cnt);
    }
    static Resources Sub(Resources r1, Resources r2)  // 计算两个资源集合相减的结果
    {
        Resources r = new Resources(r1.A - r2.A, r1.B - r2.B, r1.C - r2.C);
//        System.out.println("Sub");
//        r.showAll();
        return r;
    }
    static Resources Add(Resources r1, Resources r2)  // 两个资源集合相加
    {
        Resources r = new Resources(r1.A + r2.A, r1.B + r2.B, r1.C + r2.C);
//        System.out.println("Add:");
//        r.showAll();
        return r;
    }
    static boolean CP(Resources r1, Resources r2) // 对两个资源集合进行比较 r1 <= r2返回true
    {
        boolean flag = false;
        if (r1.A <= r2.A && r1.B <= r2.B && r1.C <= r2.C) flag = true;
//        if (flag == false)
//        {
//            System.out.println("r1 ");
//            r1.showAll();
//            System.out.println("r2 ");
//            r2.showAll();
//        }
        return flag;
    }
    // 深度优先遍历的模板
    static void dfs(int u)
    {
        if (u == n)
        {
            cnt ++;   
            for (Integer it : v)   // 打印结果
            {
                System.out.print("P" + it + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; ++ i)
        {
            Resources t1 = pset.get(i).need;
            Resources t2 = pset.get(i).allocation;
            if (!st[i] && CP(t1, available)) // 如果当前的这个进程的need小于available而且没有被访问过
            {
                st[i] = true;
                available = Add(t2, available);
                v.add(i);
                dfs(u + 1);
                available = Sub(available, t2);
                st[i] = false;
                v.remove(v.size() - 1);
            }
        }
    }
}

运行结果：

输入进程数：5
输入进程P0的Max:
A:7
B:5
C:3
输入Allocation:
A:0
B:1
C:0
输入进程P1的Max:
A:3
B:2
C:2
输入Allocation:
A:2
B:0
C:0
输入进程P2的Max:
A:9
B:0
C:2
输入Allocation:
A:3
B:0
C:2
输入进程P3的Max:
A:2
B:2
C:2
输入Allocation:
A:2
B:1
C:1
输入进程P4的Max:
A:4
B:3
C:3
输入Allocation:
A:0
B:0
C:2
输入Available:
A:3
B:3
C:2
P1 P3 P0 P2 P4 
P1 P3 P0 P4 P2 
P1 P3 P2 P0 P4 
P1 P3 P2 P4 P0 
P1 P3 P4 P0 P2 
P1 P3 P4 P2 P0 
P1 P4 P3 P0 P2 
P1 P4 P3 P2 P0 
P3 P1 P0 P2 P4 
P3 P1 P0 P4 P2 
P3 P1 P2 P0 P4 
P3 P1 P2 P4 P0 
P3 P1 P4 P0 P2 
P3 P1 P4 P2 P0 
P3 P4 P1 P0 P2 
P3 P4 P1 P2 P0 
安全序列的数量：16