Loading…

Create a lock class to prevent deadlock

 

There are several common options to prevent deadlock. One of the most popular is to explicitly declare what lock is required. This way, we will be able to check whether the created lock is a deadlock and if so, we can stop working.

 

Let’s take a look and sort out the way we can detect a deadlock. Suppose we request the following sequence of locks:

 

А = {1, 2, 3, 4}

В = {1, 3, 5}

С = {7, 5, 9, 2}

 

This will result in a deadlock appearance due to the fact that:

 

А blocks 2 and is waiting for 3

В blocks 3 and is waiting for 5

С blocks 5 and is waiting for 2

 

You can imagine this scenario as a graph, where 2 is connected to 3, and 3 is connected to 5, and 5 is connected to 2. Deadlock is described by a loop. An edge (w, v) exists in the graph if the process announces that it requests lock v immediately after lock w. In the previous example, the following edges will exist in the following graph:

 

(1, 2), (2, 3), (3, 4), (1, 3), (3, 5), (7, 5), (5, 9), (9, 2).

 

The owner of the link does not matter.

 

This class will require the declare method, which uses threads and processes to declare the sequence in which resources will be requested. The declare method will check the sequence of the declaration by adding each continuous pair of elements (v, w) to the graph. Subsequently, it will check it for cycles. If a cycle occurs, it will remove the added edge from the graph and exit.

 

We have to discuss only one nuance. How do we detect a loop? We can detect a loop by a depth-first search through each related element (i.e., through each graph component). There are complex components that allow you to select all the connected graph components, but our task is not so difficult.

 

We know that if a looped link arises, then we should check one of the links. Thus, if a depth-first search touches these links, we will definitely find a looped link.

 

The pseudocode for this loop detection is something like this:

 

boolean checkForCycle(locks[] locks) {

touchedNodes = hash table(lock -> boolean)

// initialize touchedNodes by setting each lock in locks as false

for each (lock x in process.locks) {

if (touchedNodes[x] == false) {

if (hasCycle(x, touchedNodes)) {

return true;

}

}

}

return false;

}

 

boolean hasCycle(node x, touchedNodes) {

touchedNodes[r] = true;

if (x.state == VISITING) {

return true;

} else if (x.state == FRESH) {

//…(see the full code below)

}

}

 

In this code block, we can eecute several depth-first searches, but we need to initialize touchedNodes only once. We do iterations until all the values in touchedNotes are false.

 

The following code below is more detailed. For clarity, we suppose that all the locks and processes (owners) are consistently arranged.

 

public class LockFactory {

private static LockFactory instance;

private int numberOfLocks = 5; /* by default*/

private LockNode[] locks;

 

/ * Display the process (of the owner) in order,

* in which the owner demanded a lock * /

 

 

private Hashtable<Integer, LinkedList<LockNode>> lockOrder;

 

private LockFactory(int count) { … }

public static LockFactory getInstance() { return instance; }

 

public static synchronized LockFactory initialize(int count) {

if (instance == null)

instance = new LockFactory(count); 

return instance;

}

 

public boolean hasCycle(Hashtable<Integer, Boolean> touchedNodes, int[] resourcesInOrder) {

/* verify for the looped link existence */

for (int resource : resourcesInOrder) {

if (touchedNodes.get(resource) == false) {

LockNode n = locks[resource];

if (n.hasCycle(touchedNodes)) {

return true;

}

}

}

return false;

}

 

/ * To prevent deadlock, force processes

* announce that they want to block. We check

* that the requested sequence will not cause deadlock

* (looped link in a directed graph) * /

 

public boolean declare(int ownerId, int[] resourcesInOrder) {

Hashtable<Integer, Boolean> touchedNodes = new Hashtable<Integer, Boolean>();

/* adding nodes to the graph */

int index = 1;

touchedNodes.put(resourcesInOrder[0], false);

for (index = 1; index < resourcesInOrder.length; index++) {

LockNode prev = locks[resourcesInOrder[index – 1]];

LockNode curr = locks[resourcesInOrder[index]];

prev.joinTo(curr);

touchedNodes.put(resourcesInOrder[index], false);

}

/ * if looped link is received, remove this list of resources

* and return false * /

if (hasCycle(touchedNodes, resourcesInOrder)) {

for (int j = 1; j < resourcesInOrder.length; j++) {

LockNode p = locks[resourcesInOrder[j – 1]];

LockNode c = locks[resourcesInOrder[j]];

p.remove(c);

}

return false;

}

/* The looped link is not found. We keep the order that was announced,

* since we can verify that the process really causes

* lock in the desired order * /

 

LinkedList<LockNode> list = new LinkedList<LockNode>();

for (int i = 0; i < resourcesInOrder.length; i++) {

LockNode resource = locks[resourcesInOrder[i]];

list.add(resource);

}

lockOrder.put(ownerId, list);

 

return true;

}

/ * Receive the lock, check first that the process

* really requests locking in the declared order * /

 

public Lock getLock(int ownerld, int resourceID) {

LinkedList<LockNode> list = lockOrder.get(ownerId);

if (list == null) return null;

 

LockNode head = list.getFirst();

if (head.getId() == resourceID) {

list.removeFirst();

return head.getLock();

}

return null;

}

}

public class LockNode {

public enum VisitState { FRESH, VISITING, VISITED );

 

private ArrayList<LockNode> children;

private int lockId;

private Lock lock;

private int maxLocks;

 

public LockNode(int id, int max) { … }

 

/* Connect “this” to “node”, verify not to create 

*a looped link (loop) */

public void joinTo(LockNode node) { children.add(node); }

public void remove(LockNode node) { children.remove(node); }

 

/* Check for the existence of loop with the help of depthfirst search */ 

public boolean hasCycle(Hashtable<Integer, Boolean> touchedNodes) {

VisitState[] visited = new VisitState[maxLocks];

for (int i = 0; i < maxLocks; i++) {

visited[i] = VisitState.FRESH;

}

return hasCycle(visited, touchedNodes);

}

 

private boolean hasCycle(VisitState[] visited,

Hashtable<Integer, Boolean> touchedNodes) {

if (touchedNodes.containsKey(lockId)) {

touchedNodes.put(lockId, true);

}

if (visited[lockId) == VisitState.VISITING) {

/ * We loop back to this node, therefore

* we know that there is a loop (looped link) * /

 

return true;

} else if (visited[lockId] == VisitState.FRESH) {

visited[lockId] = VisitState.VISITING;

for (LockNode n : children) {

if (n.hasCycle(visited, touchedNodes)) {

return true;

}

}

visited[lockId] = VisitState.VISITED;

}

return false;

}

 

public Lock getLock() {

if (lock == null) lock = new ReentrantLock();

return lock;

}

 

public int getId() { return lockId; }}

 


Leave a Comment