How to avoid Nested synchronization and the resulting deadlock

Question

I need to lock two objects in a functionality and the current code looke like this;

Object obj1  = ...//get from somewhere
Object obj2 = ...//get from somewhere

synchronized(obj1){
  ...//blah
  synchronized(obj2){
     ...//blah
  }
}

As you can see this is a plain and straight recipe for deadlocks if another thread runs this piece of code with obj1 and two reversed.
Is there a way to avoid this situation using concurrency-utils locks?

I was contemplating maintaining a map of objects and their locks and verifying if they were available to take, but can't seem to come up with a clean way which will predict the lock order.

Answer 1

You need to consistently lock in the order of obj1 and then obj2. If you never violate this order, you won't have deadlocks.

Answer 2

Although you preserve locking order, if obj1 is switched with obj2 you'll run into deadlock.

You must look for another solution to avoid this cases: lock ordering + optional tie breaking lock

int fromHash = System.identityHashCode(obj1);
int toHash = System.identityHashCode(obj2);

if (fromHash < toHash) {
    synchronized (obj1) {
        synchronized (obj2) {
               ........
        }
    }
} else if (fromHash > toHash) {
    synchronized (obj2) {
        synchronized (obj1) {
            ........
        }
    }
} else {
    synchronized (TIE_LOCK) {
        synchronized (fromAcct) {
            synchronized (toAcct) {
               ...
            }
        }
    }

Answer 3

Depending on what you are doing you may be able to take what you want from the first locked object and use that information to process the second locked object. e.g.

instead of

synchronized(list1) {
  for(String s : list1) {
     synchronized(list2) {
       // do something with both lists.
     }
  }
}

do this

List<String> listCopy;
synchronized(list1) {
  listCopy = new ArrayList<String>(list1);
}

synchornized(list2) {
   // do something with liastCopy and list2
}

You can see you only have lock at a time so you won't get a deadlock.

Answer 4

Essentially what you have is the dining philospher's problem.

https://en.wikipedia.org/wiki/Dining_philosophers_problem

Ovidiu Lupas's answer is similar to Dijkstra's Resource Heirarchy solution, but there are 3 more solutions, explained on the wiki page

This is what the arbitrator solution looks like. If all of the objects which you're operating from inherit from the same type, you could use static class variables to implement the arbitrators on the class of objects.

import java.util.concurrent.locks.Lock;

public void init()
{
  Lock arbitrator = new Lock();
}

public void meth1()
{
  arbitrator.lock();
  synchronized (obj1) {
    synchronized (obj2) {
      arbitrator.unlock();
      // Do Stuff
    }
  }
}

public void meth2()
{
  arbitrator.lock();
  synchronized (obj2) {
    synchronized (obj1) {
      arbitrator.unlock();
      // Do Stuff
    }
  }
}

The Chandy/Misra solution requires a lot of message passing so I'm not going to implement it, but wikipedia has a pretty good explaination

Answer 5

You can solve it in other way I suppose.

class Obj implements Comparable<Obj> {
    // basically your original class + compare(Obj other) implementation
}

class ObjLock implements Lock, Comparable<ObjLock> {

    private final Lock lock;
    private final Obj obj; // your original object

    ObjLock(Obj obj) {
        this.obj = obj;
        this.lock = new ReentrantLock();
    }

    @Override
    public int compare(ObjLock other) {
         return this.obj.compare(other.obj); // ObjLock comparison based on Obj comparison
    }

    // + reimplement Lock methods with this.lock invocations

}

Then do

class ObjLocksGroup {

    private final List<ObjLock> objLocks;

    ObjLocksGroup(ObjLock... objLocks) {
        this.objLocks = stream(objLocks)
                .sorted() // due to ObjLock implements Comparable and sorting you are sure that order of ObjLock... will always be the same
                .collect(toList));
    }

    void lock() {
        this.objLocks.forEach(ObjLock::lock);
    }

    void unlock() {
        this.objLocks.forEach(ObjLock::unlock);
    }
}

And use it as you want:

ObjLocksGroup locks = new ObjLocksGroup(obj1, obj2) // the same as obj2, obj1, order does not matter anymore.
locks.lock();
locks.unlock();