Simulating deadlock using multi-dimensional array

Question

I am attempting to code a deadlock detection algorithm. I must use a 7x7 array filled with w's, x's, and n's. w = waiting for resource, x = exclusively holding a resource, and n = no need for the resource. The rows represent jobs or processes and the columns represent resources. I will give a test case array:

    String [][] grid = {{"w","n","x","x","x","n","n"},
                        {"x","w","n","n","n","x","n"},   
                        {"n","x","w","n","n","n","n"},   
                        {"n","n","n","n","n","n","x"},   
                        {"n","n","n","n","n","n","n"},   
                        {"n","n","w","n","n","n","w"},   
                        {"w","w","w","w","w","w","w"}};

As you can see the deadlock is among Row 0, 1 and 2. R0 is waiting forC0 (resource 1), but R1 is holding it. R1 is waiting for C1 (resource 2) but R2 is holding it. R2 is waiting for C2 (resource 3), but R0 is holding it. Visually, it is a cycle.

My algorithm searches the rows for w's and the columns for x's and places them in a single dimensional array. That part works. The array should read w x w x w x...until the end. To check if we have completed a cycle I keep track of the index of the rows where w's and x's are found and place them into another single dimensional array. So in this example, the first array would read w x w x w x... and the the second array would read 0 1 1 2 2 0... Once the single dimensional arrays reach a size of 4 (determined by count variable) I would check the first index (array[0]) and the last index (array[count-1]). If array[0] is 'w' and array[count-1] is 'x' and if the row indexes are equal then a deadlock is detected.

My algorithm works on paper, but somehow my math is wrong with my second array (WHI) The indexes print out correctly the first time ( 0 1 1 2 2 0...) but if I print out WHI[0] (which should always be 0) it gives me 1 2 5 5 6 6 6 6 ...

    public void printSingleArrays()
{
    String [] WH = new String[14];
    int [] WHI = new int[14];
    int count = 0;

    for (int a = 0; a < WH.length && a < WHI.length; a += 2)
        for (int i = 0; i < array.length ; i++)
            for (int j = 0; j < array[i].length ; j++)
            {
                if (array[i][j].equals("w"))
                {
                    WH[a] = array[i][j];
                    WHI[a] = i;

                    count++;

                    System.out.print(WH[a] + " ");
                    System.out.println(WHI[a] + " ");

                    for (int k = 0; k < array.length; k++)
                    {
                        if (array[k][j].equals("x"))
                        {
                            WH[a+1] = array[k][j];
                            WHI[a+1] = k;

                            System.out.print(WH[a+1] + " ");
                            System.out.print(WHI[a+1] + " ");

                            count++;

                            if (count >= 4)
                            {
                                System.out.print("Count is: " + count); // used for debugging
                                System.out.print(", First letter is: " + WH[0]);
                                System.out.println(", Index is: " + WHI[0]);
                            }
                            else
                                System.out.println();
                        }
                    }
                }
            }
    for (int m = 0; m < WH.length; m++)
    {
        System.out.print(WH[m] + " ");
    }
    System.out.println();
    for (int n = 0; n < WH.length; n++)
    {
        System.out.print(WHI[n] + " ");
    }
}

Obviously, constructors and a client class are needed. I would just like to know how my array WHI changes when I print out WHI[0]?? Let me know if you need more resources or instruction the the problem!

Answer 1

Here is example of solving problem using graph.

• First construct graph by iterating through grid
• First iterating through all rows(j) for each column(i), it will find acquirer node who has "x" and waiting nodes who has "w".
• Then add acquirer node into list of acquires of each waiting nodes.
• Now we have graph ready, just find cycle by iterating over graph by dfs and see if node has been visited, if any of node was visited previously then it's a cycle, it means it is a deadlock.
• Now in this case, graph can be disconnected graph means all node may not reach one or more node. In that case we may need to keep track of which nodes have been visited while detecting cycle and look for cycle for the node which was not visited.

Here is the code:

package example;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DeadlockDetection {
    static String [][] grid = {{"w","n","x","x","x","n","n"},
        {"x","w","n","n","n","x","n"},
        {"n","x","w","n","n","n","n"},
        {"n","n","n","n","n","n","x"},
        {"n","n","n","n","n","n","n"},
        {"n","n","w","n","n","n","w"},
        {"w","w","w","w","w","w","w"}};

    public static void main(String[] args) {
        System.out.println(isDeadlock());
    }


    public static class Node{
        int id;
        List<Node> acquirerNodes = new ArrayList<Node>();
        public Node(int id){
            this.id=id;
        }
    }

    public static boolean isDeadlock(){
        List<Node> nodes = new ArrayList<Node>();
        //Construct Graph
        for(int i=0; i< grid.length; i++){
            nodes.add(new Node(i));
        }
        for(int i=0; i<grid.length; i++){
            List<Node> waitingNodes = new ArrayList<Node>();
            Node acquirer = null;
            for(int j=0; j<grid.length; j++){
                if(grid[j][i].equals("w") ){
                    waitingNodes.add(nodes.get(i));
                } else if(grid[j][i].equals("x") ){
                    acquirer = nodes.get(i);
                }
                if(acquirer != null)
                    for(Node n: waitingNodes)
                        n.acquirerNodes.add(acquirer);
            }
        }
        //In case of non-strongly disconnected graph, we may need to traverse through all nodes.
        HashSet<Node> nodesFoundInGraph = new HashSet<Node>();
        for(int i=0; i< grid.length; i++){
            if(!nodesFoundInGraph.contains(nodes.get(i))){
                HashSet<Node> visited = new HashSet<Node>();
                if(isCycle(nodes.get(i), visited))
                    return true;
                nodesFoundInGraph.addAll(visited);
            }
        }
        return false;
    }

    public static boolean isCycle(Node node, Set<Node> visited){
        if(visited.contains(node)){
            return true;
        }
        visited.add(node);
        for(Node n: node.acquirerNodes){
            if(isCycle(n, visited)){
                return true;
            }
        }
        return false;
    }
}