Deadlock in acquiring multiple locks

Question

I have a following code snippet (The code is in Java, but I have tried to reduce as much clutter as possible):

class State {

   public synchronized read() {
   }

   public synchronized write(ResourceManager rm) {
       rm.request();
   }

   public synchronized returnResource() {
   }
}

State st1 = new State();
State st2 = new State();
State st3 = new State();



class ResourceManager {
   public syncronized request() {
       st2 = findIdleState();
       return st2.returnResource();
   }
}


ResourceManager globalRM = new ResourceManager();


Thread1() 
{
    st1.write(globalRM);
}


Thread2() 
{
    st2.write(globalRM);

}

Thread3()
{
    st1.read();

}

This code snippet has the possibility of entering a deadlock with the following sequence of calls:

Thread1: st1.write()
Thread1: st1.write() invokes globalRM.request()
Thread2: st2.write()
Thread1: globalRM.request() tries to invoke st2.returnResource(), but gets blocked because Thread2 is holding a lock on st2.
Thread2: st2.write() tries to invoke globalRM.request(), but gets blocked because globalRM's lock is with Thread1

Thread3: st2.read(), gets blocked.

How do I solve such a deadlock? I thought about it for a while to see there is some sort of ordered locks approach I can use to acquire the locks, but I cannot think of such a solution. The problem is that, the resource manager is global, while states are specific to each job (each job has an ID which is sequential which can be used for ordering if there is some way to use order for lock acquisition).

Answer 1

There are some options to avoid this scenario, each has its advantages and drawbacks:

1.) Use a single lock object for all instances. This approach is simple to implement, but limits you to one thread to aquire the lock. This can be reasonable if the synchronized blocks are short and scalability is not a big issue (e.g. desktop application aka non-server). The main selling point of this is the simplicity in implementation.

2.) Use ordered locking - this means whenever you have to aquire two or more locks, ensure that the order in which they are aquired is the same. Thats much easier said then done and can require heavy changes to the code base.

3.) Get rid of the locks completely. With the java.util.concurrent(.atomic) classes you can implement multithreaded data structures without blocking (usually using compareAndSet-flavor methods). This certainly requires changes to the code base and requires some rethinking of the structures. Usually reqiures a rewrite of critical portions of the code base.

4.) Many problems just disappear when you consequently use immutable types and objects. Combines well with the atomic (3.) approach to implement mutable super-structures (often implemented as copy-on-change).

To give any recommendation one would need to know a lot more details about what is protected by your locks.

--- EDIT ---

I needed a lock-free Set implementation, this code sample illustrates it strengths and weaknesses. I did implement iterator() as a snapshot, implementing it to throw ConcurrentModificationException and support remove() would be a little more complicated and I had no need for it. Some of the referenced utility classes I did not post (I think its completely obvious what the missing referenced pieces do).

I hope its at least a little useful as a starting point how to work with AtomicReferences.

/**
 * Helper class that implements a set-like data structure
 * with atomic add/remove capability.
 * 
 * Iteration occurs always on a current snapshot, thus
 * the iterator will not support remove, but also never
 * throw ConcurrentModificationException.
 * 
 * Iteration and reading the set is cheap, altering the set
 * is expensive.
 */
public final class AtomicArraySet<T> extends AbstractSet<T> {

    protected final AtomicReference<Object[]> reference =
        new AtomicReference<Object[]>(Primitives.EMPTY_OBJECT_ARRAY);

    public AtomicArraySet() {
    }

    /**
     * Checks if the set contains the element.
     */
    @Override
    public boolean contains(final Object object) {
        final Object[] array = reference.get();
        for (final Object element : array) {
            if (element.equals(object))
                return true;
        }
        return false;
    }

    /**
     * Adds an element to the set. Returns true if the element was added.
     * 
     * If element is NULL or already in the set, no change is made to the
     * set and false is returned.
     */
    @Override
    public boolean add(final T element) {
        if (element == null)
            return false;
        while (true) {
            final Object[] expect = reference.get();
            final int length = expect.length;
            // determine if element is already in set
            for (int i=length-1; i>=0; --i) {
                if (expect[i].equals(element))
                    return false;
            }
            final Object[] update = new Object[length + 1];
            System.arraycopy(expect, 0, update, 0, length);
            update[length] = element;
            if (reference.compareAndSet(expect, update))
                return true;
        }
    }

    /**
     * Adds all the given elements to the set.
     * Semantically this is the same a calling add() repeatedly,
     * but the whole operation is made atomic.
     */
    @Override
    public boolean addAll(final Collection<? extends T> collection) {
        if (collection == null || collection.isEmpty())
            return false;
        while (true) {
            boolean modified = false;
            final Object[] expect = reference.get();
            int length = expect.length;
            Object[] temp = new Object[collection.size() + length];
            System.arraycopy(expect, 0, temp, 0, length);
ELoop:      for (final Object element : collection) {
                if (element == null)
                    continue;
                for (int i=0; i<length; ++i) {
                    if (element.equals(temp[i])) {
                        modified |= temp[i] != element;
                        temp[i] = element;
                        continue ELoop;
                    }
                }
                temp[length++] = element;
                modified = true;
            }
            // check if content did not change
            if (!modified)
                return false;
            final Object[] update;
            if (temp.length == length) {
                update = temp;
            } else {
                update = new Object[length];
                System.arraycopy(temp, 0, update, 0, length);
            }
            if (reference.compareAndSet(expect, update))
                return true;
        }
    }


    /**
     * Removes an element from the set.  Returns true if the element was removed.
     * 
     * If element is NULL not in the set, no change is made to the set and
     * false is returned.
     */
    @Override
    public boolean remove(final Object element) {
        if (element == null)
            return false;
        while (true) {
            final Object[] expect = reference.get();
            final int length = expect.length;
            int i = length;
            while (--i >= 0) {
                if (expect[i].equals(element))
                    break;
            }
            if (i < 0)
                return false;
            final Object[] update;
            if (length == 1) {
                update = Primitives.EMPTY_OBJECT_ARRAY;
            } else {
                update = new Object[length - 1];
                System.arraycopy(expect, 0, update, 0, i);
                System.arraycopy(expect, i+1, update, i, length - i - 1);
            }
            if (reference.compareAndSet(expect, update))
                return true;
        }
    }

    /**
     * Removes all entries from the set.
     */
    @Override
    public void clear() {
        reference.set(Primitives.EMPTY_OBJECT_ARRAY);
    }

    /**
     * Gets an estimation how many elements are in the set.
     * (its an estimation as it only returns the current size
     * and that may change at any time).
     */
    @Override
    public int size() {
        return reference.get().length;
    }

    @Override
    public boolean isEmpty() {
        return reference.get().length <= 0;
    }

    @SuppressWarnings("unchecked")
    @Override
    public Iterator<T> iterator() {
        final Object[] array = reference.get();
        return (Iterator<T>) ArrayIterator.get(array);
    }

    @Override
    public Object[] toArray() {
        final Object[] array = reference.get();
        return Primitives.cloneArray(array);
    }

    @SuppressWarnings("unchecked")
    @Override
    public <U extends Object> U[] toArray(final U[] array) {
        final Object[] content = reference.get();
        final int length = content.length;
        if (array.length < length) {
            // Make a new array of a's runtime type, but my contents:
            return (U[]) Arrays.copyOf(content, length, array.getClass());
        }    
        System.arraycopy(content, 0, array, 0, length);
        if (array.length > length)
            array[length] = null;
        return array;
    }

}

Answer 2

The answer to any deadlock is to acquire the same locks in the same order. You'll just have to figure out a way to do that.