required first commit

2 files changed, 185 insertions, 0 deletions

diff --git a/Main.java b/Main.java
new file mode 100644
index 0000000..9cdd760
--- /dev/null
+++ b/Main.java
@@ -0,0 +1,183 @@
+import java.util.Scanner;
+
+public class Main {
+
+    public static void main(String[] args) {
+
+
+
+
+
+
+
+        int n ; //number of rows in the array / processes on the system
+        int m ; //the number of columns in array / different types of resources. Resource A, B, C, and D add up to 4
+
+        Scanner scanner = new Scanner(System.in);
+        System.out.print("Enter the number of processes present on the system: ");
+        n = scanner.nextInt();
+        System.out.print("Enter the number of different types of resources there are: ");
+        m = scanner.nextInt();
+
+        int[] total = new int[m]; //total resources present on the system
+        System.out.print("Enter the total amount of each resource present on the system (Order matters - type the number and press enter for each resource type): ");
+        for(int k = 0; k < m; k++){
+            total[k] = scanner.nextInt();
+        }
+
+        int[][] allocation = new int[n][m]; //resources currently allocated to the process
+        System.out.println("Enter the resources currently allocated to each process. Preserve the resource type order you entered previously: ");
+        for(int k1 = 0; k1 < n; k1++){ //for each process
+            System.out.println("Enter the resources allocated to process " + k1 + ":");
+            for(int k2 = 0; k2 < m; k2++){
+                allocation[k1][k2] = scanner.nextInt();
+            }
+        }
+
+        int[][] max = new int[n][m]; //maximum resources the process needs to complete execution
+        System.out.println("Enter the maximum resources each process needs. Preserve the resource type order you entered previously: ");
+        for(int k1 = 0; k1 < n; k1++){ //for each process
+            System.out.println("Enter the maximum resources needed by process " + k1 + ":");
+            for(int k2 = 0; k2 < m; k2++){
+                max[k1][k2] = scanner.nextInt();
+            }
+        }
+
+        System.out.println("Calculating available resources...");
+        int[] available = new int[m]; //total resources available after allocation
+        int[] totalAlloc = new int[m]; //all allocated resources added up - needed to calculate available
+        for(int k1 = 0; k1 < m; k1++){ //for each COLUMN
+            totalAlloc[k1] = 0; //initialize to zero first
+            for(int k2 = 0; k2 < n; k2++){
+                totalAlloc[k1] += allocation[k2][k1];
+            }
+            available[k1] = total[k1] - totalAlloc[k1]; //subtract the total allocated of a resource type from the total
+        }
+
+
+        //Calculating need matrix
+        System.out.println("Calculating need matrix...");
+        int[][] need = new int[n][m]; //resources that a process still needs in order to successfully execute
+        for(int i = 0; i < n; i++){
+            for(int j = 0; j < m; j++){
+                need[i][j] = max[i][j] - allocation[i][j];
+            }
+        }
+
+        System.out.println("Determining if the system is currently in a safe state...");
+        if(runSafetyAlgorithm(need, available, allocation, n, m)){
+            System.out.println("The system is in a safe state!");
+        }
+        else{
+            System.out.println("The system is in an UNSAFE state!");
+        }
+
+        //handling requests
+        boolean x = true;
+        boolean granted;
+        int input;
+        while(x){
+            System.out.println("Enter the process number of your request: ");
+            int reqNum = scanner.nextInt();
+            System.out.println("Enter the resources this process would like to request (preserve the order as previously): ");
+            for(int j = 0; j < m; j++){
+                input = scanner.nextInt();
+                allocation[reqNum][j] += input;
+                available[j] -= input;
+
+
+            }
+            //Re-Calculating need matrix
+            System.out.println("Calculating need matrix...");
+            for(int i = 0; i < n; i++){
+                for(int j = 0; j < m; j++){
+                    need[i][j] = max[i][j] - allocation[i][j];
+                }
+            }
+            if(runSafetyAlgorithm(need, available, allocation, n, m)){
+                System.out.println("The system is in a safe state, so the request has been granted!");
+
+            }
+            else{
+                System.out.println("This request would leave the system in an unsafe state. The bank denies the request.");
+            }
+            System.out.println("Would you like to enter another request from this new state? (y/n): ");
+            String input2 = scanner.next();
+            if(input2.equals("y")){
+                //do nothing, go to beginning of while loop
+            }
+            else{
+                System.out.println("Exiting...");
+                x = false; //end the while loop and exit program
+            }
+        }
+
+
+
+    }
+
+    public static boolean runSafetyAlgorithm(int[][] need, int[] available, int [][] allocation, int n, int m){
+
+        //BEGINNING OF SAFETY ALGORITHM
+        //set work[][] = available[][] or unnecessary ?
+        boolean[] finish = new boolean[n]; //keeping track of whether a process has finished executing
+        //all processes have not finished at first - set all to false (using i instead of j here because we are dealing with columns)
+        for(int i = 0; i < n; i++){
+            finish[i] = false;
+        }
+
+        //while(!isFinished(finish)){ //while there is still a process that is not finished...
+        //I chose to repeat for the # of processes instead, because it is possible that a process will never finish (unsafe state in this case)
+        for(int i = 0; i < n; i++){
+
+            for(int i2 = 0; i2 < n; i2++){ //iterate through all processes (using i instead of j here because we are dealing with columns)
+                //if a process has not finished yet and its needs are less than what is available
+                if((finish[i2] == false) && (needLessThanAvailable(need[i2], available, m))){
+
+                    for(int j = 0; j < m; j++){
+                        available[j] += allocation[i2][j];
+                    }
+                    finish[i2] = true;
+                }
+            }
+
+
+        }
+
+        //determine if the system is in a safe state or not
+        boolean SafeState;
+        if(isFinished(finish)){
+            SafeState = true;
+        }
+        else{
+            SafeState = false;
+        }
+        return SafeState;
+
+        //END OF SAFETY ALGORITHM
+    }
+
+    //return true if all processes have finished executing
+    public static boolean isFinished(boolean[] finish){
+        for (boolean b : finish) {
+            if (b == false) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    //return true if the resource needs of a process are less than what is available
+    public static boolean needLessThanAvailable(int[] need, int [] available, int m){
+        for(int j = 0; j < m; j++){
+            if(need[j] > available[j]){
+                return false;
+            }
+        }
+        return true;
+    }
+
+
+
+
+}
diff --git a/readme.md b/readme.md
new file mode 100644
index 0000000..207ebf3
--- /dev/null
+++ b/readme.md
@@ -0,0 +1,2 @@
+This is an algorithm used to determine if an operating system is in a "safe state" i.e no deadlocks possible.
+A deadlock can occur in a system if each process is waiting on a resource from another process to complete, and no process can relinquish resources until it is completed.