Jonas Bonér bio photo

Jonas Bonér

Present.
Entrepreneur.
Hacker.
Public Speaker.
Powder Skier.
Perpetual Learner.
Jazz Fanatic.
Wannabee Musician.

Twitter LinkedIn Github

Use Total Ordering of Objects to Avoid Deadlocks

Writing multi-threaded applications in Java can as you know be quite tricky, and if not done correctly, one can easily end up with deadlock situations. For example, take a look at this little code snippet. This piece of Java code implements a Node, which has three methods (that is of our interest): 
Object get()
void set(Object o)
void swap(Node n)

Here's the implementation: 

public class Node {
    private Object value;
    public synchronized Object get() {
        return value;
    }
    public synchronized void set(Object value) {
        this.value = value;
    }
    public synchronized void swap(Node n) {
        Object tmp = get();
        set(n.get());
        n.set(tmp);
    }
   ... // remaining methods omitted

}
This class might look okay, but it actually suffers from potential deadlock. For example what happens if, one thread T1 invokes n1.swap(n2) while an other one T2 concurrently invokes n2.swap(n1) ? Thread T1 acquires the lock for node n1, and thread T2 acquires the lock for node n2. Thread T1 now invokes n2.get() (in the swap(..) method). This invocation now has to wait since node n2 is locked by thread T2, this while the reverse holds for thread T2 (e.g. it needs to wait for node n1 which is locked by thread T1). Which means that we have a deadlock.

This program is however easily fixed by using the technique of totally ordering all objects in the system. 

public class Node {
    private Object value;
    public synchronized Object get() {
        return value;
    }
    public synchronized void set(Object value) {
        this.value = value;
    }
    private synchronized void doSwap(Node n) {
        Object tmp = get();
        set(n.get());
        n.set(tmp);
    }
    public void swap(Node n) {
        if (this ==  n) {
            return;
        } else if (System.identityHashCode(this) < System.identityHashCode(n)) {
            doSwap(n);
       } else {
           n.doSwap(this);
       }
    }
   ... // remaining methods omitted

}

In this program, all locks will be acquired in increasing order, guaranteed to be the same for all threads, and thereby avoiding deadlock situations.