jeudi 16 juin 2016

Bankers Algorithm & backtracking to find all possible safe solutions to avoid deadlock in a simulated system

I parse this input file:

Resources = 5;
Processes = 7;
RArray = 7,6,5,8,9;  //resource array
AArray0 = 1,1,0,0,1; //Allocation arrays
AArray1 = 2,0,0,2,1;
AArray2 = 0,2,1,1,2;
AArray3 = 0,1,1,1,2;
AArray4 = 1,1,2,0,1;
AArray5 = 1,1,0,2,1;
AArray6 = 1,0,1,1,1;
PArray0 = 3,1,2,1,1; //Process arrays requesting resources
PArray1 = 1,0,0,1,0;
PArray2 = 3,2,3,4,2;
PArray3 = 6,4,4,5,6;
PArray4 = 2,0,0,2,1;
PArray5 = 6,4,5,5,8;
PArray6 = 4,1,1,1,2;

After parsing, I am trying to find all the solutions for the system to select a process to execute based on the initial available resources 1 0 0 1 0 (Due to pre-allocation; see inputs above). Only Process1 can execute initially.

I call bankers() to begin executing this process, which frees memory, then recursevly call bankersHelper for every subsequent possible Process selection. However, it is not behaving the way I thought it was supposed to work.

I am lost on how to implement this correctly for the threads to diverge when it it should fork after the program figures out it can execute both Process0 & Process6 after running Process4. So thus far the sequence should be:

                             P1
                             |
                             |
                             P4
                             |
                        P0--------P6

And bankersHelper() should continue looking for possible Processes to select.

However, the program cuts off midway through P0 for an unknown reason, then continues to P6 and finishes linearly.

I recursively call bankersHelper() for each Process that returns canRun = true based on the current available system resources.

Here is the method bankers()

public static void bankers(int[][] request) {
    boolean canRun;
    int[][] updatedRequest = request;
    boolean[] canExec = new boolean[n];
    boolean[] hasExec = new boolean[n];
    int toRun = 0;
    //based off available, find processes to run
        for (int i = 0;i < n; i++) {
            canRun = true;
            for (int j=0;j<m;j++) {
                if (request[i][j] > available[j]) {
                    canRun = false;
                }
            }
            if (canRun) {
                toRun ++;
                System.out.println("Can Execute Process " + i);
                canExec[i] = true;
            }
        }
        System.out.print("Resources available : n");
        for (int i=0;i<m;i++) {
            System.out.print(available[i] + " ");
        }
        System.out.println("n" + "Processes toRun: " + toRun);
        System.out.print("canExec Process ");
        for (int k=0;k<n;k++) {
            if (canExec[k]) {
                System.out.print(" ["+k+"] > " + canExec[k]);
            }
        }
        System.out.println();
        for (int i = 0;i < toRun;i++) {
            bankersHelper(canExec, available, hasExec);
        }
}

and helper method bankersHelper

private static void bankersHelper(boolean[] canExec, int[] available, boolean[] hasExec) {
    System.out.println("n" + "BEGIN bankersHelper() ---------");
    int toRun = 0;
    boolean[] updatedHasExec = hasExec;
    int[] updatedAvailable = available;
    int[] release = new int[m];
    boolean[] updatedCanExec = canExec;
    System.out.print("nAvailable Resources: ");
    for (int k=0;k<m;k++) {
        System.out.print(updatedAvailable[k]+" ");
    }
    System.out.println();

    for (int i = 0;i < request.length;i++) {
        if(updatedCanExec[i] && !updatedHasExec[i]) {
            //
            System.out.println("nProcess P" +i+" has been selected");
            System.out.print("P"+i+" acquires resources: ");
            for (int j = 0;j < m;j++) {
                System.out.print(request[i][j]+" ");
                updatedAvailable[j] -= request[i][j];
            }
            System.out.println("nProcess P" +i+" Executes");
            //
            updatedHasExec[i] = true;
            System.out.print("Process P" +i+" releases resources: ");
            for (int k=0;k<m;k++) {
                release[k] = request[i][k] + allocation[i][k];
                System.out.print(release[k]+" ");
                updatedAvailable[k] += release[k];
            }
            System.out.print("nAvailable Resources: ");
            for (int k=0;k<m;k++) {
                System.out.print(updatedAvailable[k]+" ");
            }
            System.out.println("n" + ">>");
        }
    }
    System.out.println(">>>>");
    for (int i = 0;i < n;i++)
        System.out.println("P"+i+" hasRun? " + updatedHasExec[i]);
    for (int i = 0;i < n;i++) {
        if (!updatedHasExec[i]) {
            boolean canRun = true;
            for (int j=0;j<m;j++) {
                if (request[i][j] > updatedAvailable[j]) {
                    canRun = false;
                }
            }
            if (canRun) {
                System.out.println("Can Execute Process " + i);
                updatedCanExec[i] = true;
                toRun++;

            }
        }
    }
    for (int i = 0;i < toRun;i++)
        bankersHelper(updatedCanExec, updatedAvailable, updatedHasExec);
}

I have been pouring over my code for hours now not getting anywhere, as I cannot figure out what I have done wrong. Any help and tips would be greatly appreciated. This is driving me INSANE!

Thank you Stackers

Here is a screenshot of Process0 cutting off unexpectdly. P0 output should look exactly like P6 below it: console

Aucun commentaire:

Enregistrer un commentaire