Problem with synchronized collections of Java when doing equals() in the reverse order from multiple threads

Question

Example scenario:

• Create two SynchronizedSets (s1 and s2)
• Pass them to two threads (T1 and T2)
• Start the threads

T1's run() : while (forever) s1.equals(s2)

T2's run() : while (forever) s2.equals(s1)

What happens? - SynchronizedSet's equals acquires lock on itself

• It computes the length of the param that's passed in and also what it contains to determine whether that is equal [Note: this is a guess based on the logs I analyzed]

• If the passed in param is also a SynchronizedSet, calls to size() and containAll() implies lock of that has to be acquired as well.

• In the above example, lock acquiring orders for T1 and T2 are as follows:

  T1: s1 -> s2 T2: s2 -> s1

Ofc, it leads to a deadlock.

This problem is not specific to Synchronized Collections alone. It can happen even with Hashtable or Vector.

I believe this is a Java API limitation (design). How to overcome this? How do I ensure this does not happen in my application? Is there some design principle I should follow without getting into this situation?

Answer 1

You can lock both sets in the same order in each thread:

            synchronized(s1) {
                synchronized(s2) {
                    s1.equals(s2);
                }
            }

and

            synchronized(s1) {
                synchronized(s2) {
                    s2.equals(s1);
                }
            }

Answer 2

I may suggest to use a synchronized(){] block.

something like this:

while(forever){
    synchronized(s1){
     s1.equals(s2);
    }
}

and

while(forever){
   synchronized(s1){
 s2.equals(s1);
   }
}

Answer 3

I believe this is a Java API limitation (design).

I believe that you are wrong. A fundamental requirement of every PL level locking scheme that I've ever used is that threads must lock resources in the same order or risk deadlock. This applies to databases as well.

In fact, the only way I think you could avoid this would be to either:

• require the application to acquire all locks that it needed in a single atomic operation, or
• do all locking using a single global lock.

Both of these approaches is impractical and unscalable.

How to overcome this?

Code your application so that locks are acquired by all threads in the same order. @Maurice's and @Nettogrof's answers give examples of how to do this, though it may be more difficult if you have lots of sets to worry about.

Answer 4

Stephen C's is good stuff. Further information: If you don't know which way around the sets are, you can use a "global" lock whenever both sets are going to be compared:

 private static final Object lock = new Object(); // May be context-local.

 [...]

     synchronized (lock) {
         synchronized (s1) {
             synchronized (s2) {
                 return s1.equals(s2);
             }
          }
     }

If the sets are likely to be contended, you can most of the time order by identity hash code and fall back to the global lock:

    int h1 = System.identityHashCode(s1);
    int h2 = System.identityHashCode(s2);
    return
         h1<h2 ? lockFirstEquals(h1, h2) :
         h2<h1 ? lockFirstEquals(h2, h1) :
         globalLockEquals(h1, h2);

Sometimes, you can use an alternative algorithm. IIRC, StringBuffer can deadlock with append (although the combination of operations on the objects doesn't make a great deal of sense). It could be implemented as:

public StringBuffer append(StringBuffer other) {
    if (other == null) {
        return append("null");
    }
    int thisHash  = System.identityHashCode(this);
    int otherHash = System.identityHashCode(other);
    if (thisHash < otherHash) {
        synchronized (this) {
            synchronized (other) {
                appendImpl(other);
            }
        }
    } else if (otherHash < thisHash) {
        synchronized (other) {
            synchronized (this) {
                appendImpl(other);
            }
        }
    } else {
        append(other.toString()); // Or append((Object)other);
    }
    return this;
}

The best solution would probably to change your threading strategy so you don't need any locking here.

Answer 5

You could order the sets by their identiyHashCode() before doing the equals() call. This way the order of the lock acquisition will always be the same.