11

import java.util.Scanner;

public class DeadlockAvoidanceSystem {
   private int[][] max; // 最大需求矩阵
   private int[][] allocation; // 已分配矩阵
   private int[][] need; // 还需要资源矩阵
   private int[] available; // 可用资源向量
   private int[] work; // 存放系统可提供资源量
   private boolean[] finish; // 标记系统是否有足够的资源分配给各个进程
   private int[] safeSequence; // 存放安全序列
   private int numOfProcesses; // 进程的数量
   private int numOfResources; // 资源的数量

   public void initialize() {
       Scanner scanner = new Scanner(System.in);

       // 输入进程和资源的数量
       System.out.print("请输入进程的数量：");
       numOfProcesses = scanner.nextInt();
       System.out.print("请输入资源的数量：");
       numOfResources = scanner.nextInt();
       System.out.println("-------------------------------------------------");

       // 初始化矩阵和向量
       max = new int[numOfProcesses][numOfResources];
       allocation = new int[numOfProcesses][numOfResources];
       need = new int[numOfProcesses][numOfResources];
       available = new int[numOfResources];
       work = new int[numOfResources];
       finish = new boolean[numOfProcesses];
       safeSequence = new int[numOfProcesses];

       // 输入各进程的最大需求矩阵
       System.out.println("请输入各进程的最大需求矩阵的值[Max]：");
       for (int i = 0; i < numOfProcesses; i++) {
           System.out.println("进程 " + i + " 的最大需求量：");
           for (int j = 0; j < numOfResources; j++) {
               max[i][j] = scanner.nextInt();
           }
       }System.out.println("-------------------------------------------------");

       // 输入各进程已经分配的资源量，并计算还需要的资源量
       System.out.println("请输入各进程已经分配的资源量[Allocation]：");
       for (int i = 0; i < numOfProcesses; i++) {
           System.out.println("进程 " + i + " 的已分配资源量：");
           for (int j = 0; j < numOfResources; j++) {
               allocation[i][j] = scanner.nextInt();
           }
       }   System.out.println("-------------------------------------------------");

       // 输入系统可用的资源量
       System.out.println("请输入系统可用的资源量[Available]：");
       System.out.println("请输入资源的可用数量：");
       for (int i = 0; i < numOfResources; i++) {
           available[i] = scanner.nextInt();
       }    System.out.println("-------------------------------------------------");

       // 计算还需要的资源量
       calculateNeed();
   }

   public void calculateNeed() {
       for (int i = 0; i < numOfProcesses; i++) {
           for (int j = 0; j < numOfResources; j++) {
               need[i][j] = max[i][j] - allocation[i][j];
           }
       }
   }

   public boolean isSafe() {
       // 初始化工作向量和标记向量
       for (int i = 0; i < numOfResources; i++) {
           work[i] = available[i];
       }
       for (int i = 0; i < numOfProcesses; i++) {
           finish[i] = false;
       }

       // 安全性算法
       int count = 0;
       while (count < numOfProcesses) {
           boolean found = false;
           for (int i = 0; i < numOfProcesses; i++) {
               if (!finish[i] && isNeedLessOrEqualWork(i)) {
                   for (int j = 0; j < numOfResources; j++) {
                       work[j] += allocation[i][j];
                   }
                   finish[i] = true;
                   safeSequence[count] = i;
                   count++;
                   found = true;
               }
           }
           if (!found) {
               break;
           }
       }

       // 判断是否安全
       return count == numOfProcesses;
   }

   private boolean isNeedLessOrEqualWork(int process) {
       for (int i = 0; i < numOfResources; i++) {
           if (need[process][i] > work[i]) {
               return false;
           }
       }
       return true;
   }

   public boolean requestResources(int process) {
       Scanner scanner = new Scanner(System.in);

       // 输入进程请求的资源量
       System.out.println("请输入该进程的请求资源量：");
       int[] request = new int[numOfResources];
       for (int i = 0; i < numOfResources; i++) {
           request[i] = scanner.nextInt();
       }

       // 检查请求是否合法
       if (!isRequestValid(process, request)) {
           System.out.println("请求的资源量超过进程的需求量，请重新输入。");
           return false;
       }

       // 检查请求是否安全
       if (isRequestSafe(process, request)) {
           // 分配资源
           allocateResources(process, request);
           return true;
       } else {
           System.out.println("当前系统状态不安全，无法进行资源分配。");
           return false;
       }
   }

   private boolean isRequestValid(int process, int[] request) {
       for (int i = 0; i < numOfResources; i++) {
           if (request[i] > need[process][i]) {
               return false;
           }
           if (request[i] > available[i]) {
               return false;
           }
       }
       return true;
   }

   private boolean isRequestSafe(int process, int[] request) {
       int[] tempAvailable = new int[numOfResources];
       int[][] tempAllocation = new int[numOfProcesses][numOfResources];
       int[][] tempNeed = new int[numOfProcesses][numOfResources];

       // 备份当前资源状态
       for (int i = 0; i < numOfResources; i++) {
           tempAvailable[i] = available[i];
       }
       for (int i = 0; i < numOfProcesses; i++) {
           for (int j = 0; j < numOfResources; j++) {
               tempAllocation[i][j] = allocation[i][j];
               tempNeed[i][j] = need[i][j];
           }
       }

       // 模拟分配资源
       for (int i = 0; i < numOfResources; i++) {
           tempAvailable[i] -= request[i];
           tempAllocation[process][i] += request[i];
           tempNeed[process][i] -= request[i];
       }

       // 模拟安全性算法
       int[] tempWork = new int[numOfResources];
       boolean[] tempFinish = new boolean[numOfProcesses];
       for (int i = 0; i < numOfResources; i++) {
           tempWork[i] = tempAvailable[i];
       }
       for (int i = 0; i < numOfProcesses; i++) {
           tempFinish[i] = false;
       }

       int count = 0;
       while (count < numOfProcesses) {
           boolean found = false;
           for (int i = 0; i < numOfProcesses; i++) {
               if (!tempFinish[i] && isNeedLessOrEqualWork(i, tempNeed, tempWork)) {
                   for (int j = 0; j < numOfResources; j++) {
                       tempWork[j] += tempAllocation[i][j];
                   }
                   tempFinish[i] = true;
                   count++;
                   found = true;
               }
           }
           if (!found) {
               break;
           }
       }

       // 判断是否安全
       return count == numOfProcesses;
   }

   private boolean isNeedLessOrEqualWork(int process, int[][] tempNeed, int[] tempWork) {
       for (int i = 0; i < numOfResources; i++) {
           if (tempNeed[process][i] > tempWork[i]) {
               return false;
           }
       }
       return true;
   }

   private void allocateResources(int process, int[] request) {
       for (int i = 0; i < numOfResources; i++) {
           available[i] -= request[i];
           allocation[process][i] += request[i];
           need[process][i] -= request[i];
       }
   }

   public void displaySafeSequence() {
       System.out.println("安全序列为：");
       for (int i = 0; i < numOfProcesses; i++) {
           System.out.print("P" + safeSequence[i]);
           if (i < numOfProcesses - 1) {
               System.out.print(" -> ");
           }
       }
       System.out.println();
   }

   public void displayMatrices() {
       System.out.println("Max 需求矩阵：");
       displayMatrix(max);

       System.out.println("Allocation 已分配矩阵：");
       displayMatrix(allocation);

       System.out.println("Need 还需要资源矩阵：");
       displayMatrix(need);

       System.out.println("Available 可用资源量：");
       displayVector(available);
       System.out.println("-------------------------------------------------");
   }

   private void displayMatrix(int[][] matrix) {
       for (int i = 0; i < matrix.length; i++) {
           for (int j = 0; j < matrix[i].length; j++) {
               System.out.print(matrix[i][j] + " ");
           }
           System.out.println();
       }
   }

   private void displayVector(int[] vector) {
       for (int i = 0; i < vector.length; i++) {
           System.out.print(vector[i] + " ");
       }
       System.out.println();
   }

   public static void main(String[] args) {
       DeadlockAvoidanceSystem system = new DeadlockAvoidanceSystem();
       system.initialize();

       System.out.println("当前系统的资源分配状态：");
       system.displayMatrices();

       if (system.isSafe()) {
           System.out.println("当前系统状态安全。");
           system.displaySafeSequence();
       } else {
           System.out.println("当前系统状态不安全，原因如下：");
           System.out.println("无法找到安全序列，存在进程无法获得足够的资源。");
       }

       Scanner scanner = new Scanner(System.in);
       System.out.print("请输入要申请资源的进程：");
       int process = scanner.nextInt()-1;

       if (system.requestResources(process)) {
           System.out.println("资源分配成功。");
           System.out.println("当前系统的资源分配状态：");
           system.displayMatrices();

           if (system.isSafe()) {
               System.out.println("当前系统状态安全。");
               system.displaySafeSequence();
           } else {
               System.out.println("当前系统状态不安全，原因如下：");
               System.out.println("无法找到安全序列，存在进程无法获得足够的资源。");
           }
       } else {
           System.out.println("资源分配失败。");
       }
   }
}