import java.util.Scanner;

public class DeadlockAvoidanceSystem {
? ?private int[][] max; // 最大需求矩陣
? ?private int[][] allocation; // 已分配矩陣
? ?private int[][] need; // 還需要資源矩陣
? ?private int[] available; // 可用資源向量
? ?private int[] work; // 存放系統(tǒng)可提供資源量
? ?private boolean[] finish; // 標(biāo)記系統(tǒng)是否有足夠的資源分配給各個進(jìn)程
? ?private int[] safeSequence; // 存放安全序列
? ?private int numOfProcesses; // 進(jìn)程的數(shù)量
? ?private int numOfResources; // 資源的數(shù)量

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

? ? ? ?// 輸入進(jìn)程和資源的數(shù)量
? ? ? ?System.out.print("請輸入進(jìn)程的數(shù)量：");
? ? ? ?numOfProcesses = scanner.nextInt();
? ? ? ?System.out.print("請輸入資源的數(shù)量：");
? ? ? ?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];

? ? ? ?// 輸入各進(jìn)程的最大需求矩陣
? ? ? ?System.out.println("請輸入各進(jìn)程的最大需求矩陣的值[Max]：");
? ? ? ?for (int i = 0; i < numOfProcesses; i++) {
? ? ? ? ? ?System.out.println("進(jìn)程 " + i + " 的最大需求量：");
? ? ? ? ? ?for (int j = 0; j < numOfResources; j++) {
? ? ? ? ? ? ? ?max[i][j] = scanner.nextInt();
? ? ? ? ? ?}
? ? ? ?}System.out.println("-------------------------------------------------");

? ? ? ?// 輸入各進(jìn)程已經(jīng)分配的資源量，并計算還需要的資源量
? ? ? ?System.out.println("請輸入各進(jìn)程已經(jīng)分配的資源量[Allocation]：");
? ? ? ?for (int i = 0; i < numOfProcesses; i++) {
? ? ? ? ? ?System.out.println("進(jìn)程 " + i + " 的已分配資源量：");
? ? ? ? ? ?for (int j = 0; j < numOfResources; j++) {
? ? ? ? ? ? ? ?allocation[i][j] = scanner.nextInt();
? ? ? ? ? ?}
? ? ? ?} ? System.out.println("-------------------------------------------------");

? ? ? ?// 輸入系統(tǒng)可用的資源量
? ? ? ?System.out.println("請輸入系統(tǒng)可用的資源量[Available]：");
? ? ? ?System.out.println("請輸入資源的可用數(shù)量：");
? ? ? ?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() {
? ? ? ?// 初始化工作向量和標(biāo)記向量
? ? ? ?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);

? ? ? ?// 輸入進(jìn)程請求的資源量
? ? ? ?System.out.println("請輸入該進(jìn)程的請求資源量：");
? ? ? ?int[] request = new int[numOfResources];
? ? ? ?for (int i = 0; i < numOfResources; i++) {
? ? ? ? ? ?request[i] = scanner.nextInt();
? ? ? ?}

? ? ? ?// 檢查請求是否合法
? ? ? ?if (!isRequestValid(process, request)) {
? ? ? ? ? ?System.out.println("請求的資源量超過進(jìn)程的需求量，請重新輸入。");
? ? ? ? ? ?return false;
? ? ? ?}

? ? ? ?// 檢查請求是否安全
? ? ? ?if (isRequestSafe(process, request)) {
? ? ? ? ? ?// 分配資源
? ? ? ? ? ?allocateResources(process, request);
? ? ? ? ? ?return true;
? ? ? ?} else {
? ? ? ? ? ?System.out.println("當(dāng)前系統(tǒng)狀態(tài)不安全，無法進(jìn)行資源分配。");
? ? ? ? ? ?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];

? ? ? ?// 備份當(dāng)前資源狀態(tài)
? ? ? ?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("當(dāng)前系統(tǒng)的資源分配狀態(tài)：");
? ? ? ?system.displayMatrices();

? ? ? ?if (system.isSafe()) {
? ? ? ? ? ?System.out.println("當(dāng)前系統(tǒng)狀態(tài)安全。");
? ? ? ? ? ?system.displaySafeSequence();
? ? ? ?} else {
? ? ? ? ? ?System.out.println("當(dāng)前系統(tǒng)狀態(tài)不安全，原因如下：");
? ? ? ? ? ?System.out.println("無法找到安全序列，存在進(jìn)程無法獲得足夠的資源。");
? ? ? ?}

? ? ? ?Scanner scanner = new Scanner(System.in);
? ? ? ?System.out.print("請輸入要申請資源的進(jìn)程：");
? ? ? ?int process = scanner.nextInt()-1;

? ? ? ?if (system.requestResources(process)) {
? ? ? ? ? ?System.out.println("資源分配成功。");
? ? ? ? ? ?System.out.println("當(dāng)前系統(tǒng)的資源分配狀態(tài)：");
? ? ? ? ? ?system.displayMatrices();

? ? ? ? ? ?if (system.isSafe()) {
? ? ? ? ? ? ? ?System.out.println("當(dāng)前系統(tǒng)狀態(tài)安全。");
? ? ? ? ? ? ? ?system.displaySafeSequence();
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?System.out.println("當(dāng)前系統(tǒng)狀態(tài)不安全，原因如下：");
? ? ? ? ? ? ? ?System.out.println("無法找到安全序列，存在進(jìn)程無法獲得足夠的資源。");
? ? ? ? ? ?}
? ? ? ?} else {
? ? ? ? ? ?System.out.println("資源分配失敗。");
? ? ? ?}
? ?}
}