package os.chapter3._3_6_1;

import java.util.Arrays;

public class BankerAlgorithm {
    private final int[][] max; // 最大需求矩阵
    private final int[][] allocation; // 已分配矩阵
    private final int[][] need; // 剩余需求矩阵
    private final int[] available; // 可用资源向量
    private final int processNum; // 进程数量
    private final int resourceNum; // 资源数量

    public BankerAlgorithm(int[][] max, int[][] allocation, int[] available) {
        this.max = max;
        this.allocation = allocation;
        this.need = new int[max.length][max[0].length];
        this.available = available;
        this.processNum = max.length;
        this.resourceNum = max[0].length;
        initNeed();
    }

    public void initNeed(){
        for (int i = 0; i < processNum; i++) {
            for (int j = 0; j < resourceNum; j++) {
                this.need[i][j] = max[i][j] - allocation[i][j];
            }
        }
    }

    // 银行家算法
    public void bankerAlgorithm(int[] request,int p) {
        System.out.println("==========================================");

        System.out.println("检查初始时的安全性");
        //初始时刻的安全性
        int[] safeSequence = safetyCheck();

        if (safeSequence==null){
            System.out.println("初始时系统不安全");
        }else{
            // 输出安全序列
            System.out.println("Safe Sequence:");
            for (int i : safeSequence) {
                System.out.print("P" + i + " ");
            }
            System.out.println();
        }

        System.out.println("==========================================");

        System.out.println("检查是否满足条件1");
        for(int j=0;j<resourceNum;j++){
            if(request[j]>need[p][j]){
                System.out.println("P"+p+"所需要的资源已超过它所宣布的最大值");
                return;
            }
        }

        System.out.println("检查是否满足条件2");
        for(int j=0;j<resourceNum;j++){
            if(request[j]>available[j]){
                System.out.println("尚无足够资源，P"+p+"必须等待");
                return;
            }
        }

        System.out.println("==========================================");

        //试探分配
        System.out.println("开始试探分配");
        System.out.println("P"+p+":"+Arrays.toString(request));
        for(int j=0;j<resourceNum;j++){
            available[j]=available[j]-request[j];
            allocation[p][j]=allocation[p][j]+request[j];
            need[p][j]=need[p][j]-request[j];
        }

        System.out.println("开始安全检查");
        int[] s = safetyCheck();
        if (s!=null) {
            System.out.println("可以分配"+"P"+p+":"+Arrays.toString(request));
        } else {
            System.out.println("不能分配"+"P"+p+":"+Arrays.toString(request));
        }
        System.out.println("==========================================");

    }


    // 安全性检查算法
    public int[] safetyCheck() {
        int[] work; // 工作向量
        work = Arrays.copyOf(available, available.length);

        boolean[] finish = new boolean[processNum]; // 进程是否完成执行的标志
        int[] safeSequence = new int[processNum]; // 安全序列
        int count = 0; // 记录已完成的进程数量

        // 初始化完成标志数组
        for (int i = 0; i < processNum; i++) {
            finish[i] = false;
        }

        // 寻找可执行的进程直到全部进程执行完毕或者找不到可执行的进程
        while (count < processNum) {
            boolean found = false;

            // 遍历所有进程，查找满足资源需求的进程
            for (int i = 0; i < processNum; i++) {
                if (!finish[i] && checkResources(i,work)) {
                    for (int j = 0; j < resourceNum; j++) {
                        work[j] += allocation[i][j];
                    }

                    finish[i] = true;
                    safeSequence[count] = i;
                    count++;
                    found = true;
                }
            }

            // 如果没有找到满足资源需求的进程，则认为系统不安全
            if (!found) {
                return null;
            }
        }

        return safeSequence;

    }



    // 检查进程的资源需求是否小于等于可用资源
    private boolean checkResources(int process,int[] work) {
        for (int i = 0; i < resourceNum; i++) {
            if (need[process][i] > work[i]) {
                return false;
            }
        }
        return true;
    }

    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};

        BankerAlgorithm banker = new BankerAlgorithm(max, allocation, available);


        int[] request1={1,0,2};
        banker.bankerAlgorithm(request1,1);

        int[] request4={3,3,0};
        banker.bankerAlgorithm(request4,4);

        int[] request0={0,2,0};
        banker.bankerAlgorithm(request0,0);


    }
}

==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
==========================================
开始试探分配
P1:[1, 0, 2]
开始安全检查
可以分配P1:[1, 0, 2]
==========================================
==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
尚无足够资源，P4必须等待
==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
==========================================
开始试探分配
P0:[0, 2, 0]
开始安全检查
不能分配P0:[0, 2, 0]
==========================================

Process finished with exit code 0