grubbel - Use Total Ordering of Objects to Avoid Deadlocks

Use Total Ordering of Objects to Avoid Deadlocks

[ jonas ] 10:18, Wednesday, 27 July 2005

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) and 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.

TrackBack

I don't see, where there could be a deadlock. If you call n1.swap(n2), it invokes n1.get() and n2.swap(n1) invokes n2.get(). Both getters are locked.
When n1.get() returns n1.swap(n2) calls n2.get(), which is locked. But T2 doesn't need any n1 method at this time and finishes n2.get(), so n1.swap(n2) can invoke it. For T2, the n1.get() method is unlocked, so T2 calls n1.get().
So every thread is forced to wait sometime. Correct me if I'm wrong, but I don't see any deadlock.

And your solution calls in both cases n1.doSwap(n2). In this case, it results the same way as n1.swap(n2) and n2.swap(n1) in the first listing do.
But this is, as I think, only because you swap data. If you calculate something or so, your solution could provide wrong results, because it invokes two times the same method on the same object.

--Newlukai, July 28, 2005 09:18 AM