Why does ExecutorService deadlock when performing HashMap operations?

Question

When running the following class the ExecutionService will often deadlock.

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;


public class ExecutorTest {
public static void main(final String[] args) throws InterruptedException {
    final ExecutorService executor = Executors.newFixedThreadPool(10);

    final HashMap<Object, Object> map = new HashMap<Object, Object>();
    final Collection<Callable<Object>> actions = new ArrayList<Callable<Object>>();
    int i = 0;
    while (i++ < 1000) {
        final Object o = new Object();
        actions.add(new Callable<Object>() {
            public Object call() throws Exception {
                map.put(o, o);
                return null;
            }
        });
        actions.add(new Callable<Object>() {
            public Object call() throws Exception {
                map.put(new Object(), o);
                return null;
            }
        });
        actions.add(new Callable<Object>() {
            public Object call() throws Exception {
                for (Iterator iterator = map.entrySet().iterator(); iterator.hasNext();) {
                    iterator.next();
                }
                return null;
            }
        });
    }
    executor.invokeAll(actions);
    System.exit(0);
}

}

So why does this happen? Or better yet - how can I write a test to ensure that implementations of an custom abstract map are thread safe? (Some implementations have multiple maps, another delegates to a cache implementation etc)

Some background: this occurs under Java 1.6.0_04 and 1.6.0_07 on Windows. I know that the problem comes from sun.misc.Unsafe.park():

• I can reproduce the problem on my Core2 Duo 2.4Ghz laptop but not while running in debug
• I can debug on my Core2 Quad at work, but I've hung it over RDP, so won't be able to get a stack trace until tomorrow

Most answers below are about the non-thread safety of HashMap, but I could find no locked threads in HashMap - it was all in the ExecutionService code (and Unsafe.park()). I shall closely examine the threads tomorrow.

All this because a custom abstract Map implementation was not thread-safe so I set about ensuring that all implementations would be thread-safe. In essence, I'm wanting to ensure that my understanding of ConcurrentHashMap etc are exactly what I expect, but have found the ExecutionService to be strangely lacking...

Answer 1

You're using an well-known not-thread-safe class and complaining about deadlock. I fail to see what the issue is here.

Also, how is the ExecutionService

strangely lacking

?

It's a common misconception that by using e.g. a HashMap you will at most get some stale data. See a beautiful race condition about how you can blow up your JVM by doing just that.

Understanding why this happens is a very tricky process and requires knowledge of the internals of both the JVM and the class libraries.

As for the ConcurrentHashMap, just read the javadoc - it should clarify your questions. If not, take a look at Java Concurrency in Practice.

---

Update:

I managed to reproduce your situation, but it's not a deadlock. One of the actions never completes execution. The stack trace is:

"pool-1-thread-3" prio=10 tid=0x08110000 nid=0x22f8 runnable [0x805b0000]
java.lang.Thread.State: RUNNABLE
at ExecutorTest$3.call(ExecutorTest.java:36)
at java.util.concurrent.FutureTask$Sync.innerRun(FutureTask.java:303)
at java.util.concurrent.FutureTask.run(FutureTask.java:138)
at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
 at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
at java.lang.Thread.run(Thread.java:619)

It looks like the exact case I linked to - the HashMap gets resized and due to the internal mechanics of resizing the iterator gets stuck in an infinite loop.

When this happens, invokeAll never returns and the program hangs. But it's neither a deadlock, nor a livelock, but a race condition.

Answer 2

What do you understand by deadlock?

There are at least two problems with the code. The HashMap is used from multiple threads simultaneously and so can get into an infinite loop. You are iterating the the entry set whilst potentially changing the underlying data structure (even if each individual operation was synchronized hasNext/next would not be atomic).

Also note that the versions of 1.6.0 up to date with the latest Synhronized Security Release (SSR) are 1.6.0_13 and 1.6.0_14.