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

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 2

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);
                }
            }