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.

Answer 3

In terms of making the test work - instead of:

 executor.invokeAll(actions);

use

 executor.invokeAll(actions, 2, TimeUnit.SECONDS);

also note that to make the test actually work (and report errors), you'll need to do something like:

 List<Future> results = executor.invokeAll(actions, 2, TimeUnit.SECONDS);
 executor.shutdown();
 for (Future result : results) {
     result.get(); // This will report the exceptions encountered when executing the action ... the ConcurrentModificationException I wanted in this case (or CancellationException in the case of a time out)
 }
 //If we get here, the test is successful...

Answer 4

I believe your map is being concurrently modified. If put() is called while your iterating action is in progress, under certain conditions (especially if the resizing happens) you may end up in an infinite loop. This is a fairly well-known behavior (see here).

The deadlock and an infinite loop will exhibit themselves very differently. If you have a true deadlock, the thread dump will clearly show the interlocking threads. On the other hand, once you got into an infinite loop, your CPU will spike high and stack traces will vary every time you take the dump.

This has nothing to do with the Executor and everything to do with unsafe concurrent use of HashMap which was never designed to be used that way. In fact it is pretty easy to reproduce this problem with an array of handful of threads.

The best solution to this is to switch to ConcurrentHashMap. If you switch to a synchronized HashMap or Hashtable, you will not get into an infinite loop, but you may still get ConcurrentModificationExceptions during iteration.