为什么ExecutorService在执行HashMap操作时会出现死锁？

Question

当运行以下类时，ExecutionService经常会死锁。

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

}

那么为什么会发生这种情况呢？或者更好的问题是——我该如何编写一个测试来确保自定义抽象映射的实现是线程安全的？（某些实现具有多个映射，另一些委托给缓存实现等）一些背景：这在Windows上的Java 1.6.0_04和1.6.0_07下发生。我知道问题来自sun.misc.Unsafe.park()：我可以在我的Core2 Duo 2.4Ghz笔记本电脑上重现这个问题，但在调试模式下不会出现；我可以在我的Core2 Quad工作电脑上进行调试，但我已经通过RDP挂起了它，所以直到明天才能获得堆栈跟踪。大多数下面的答案都是关于HashMap的非线程安全性，但我在HashMap中找不到锁定的线程——所有的线程都在ExecutionService代码（和Unsafe.park()）中。我将在明天仔细检查线程。所有这些都是因为自定义的抽象Map实现不是线程安全的，所以我开始确保所有实现都是线程安全的。实质上，我想确保我对ConcurrentHashMap等的理解与我所期望的完全相同，但发现ExecutionService奇怪地缺乏……

- Stephen

---

明天我要做的事情：

1. 仔细检查HashMap [resize]代码中停止的线程。
2. 升级到最新的虚拟机。

- Stephen

在调整大小时，您不会停止任何线程-它们将调整大小并退出。检查是否有线程卡在迭代Callable中。 - Robert Munteanu

Answer 1

您正在使用一个众所周知的非线程安全类，并抱怨死锁问题。我看不出这里有什么问题。

此外，ExecutionService 怎么样了？

strangely lacking

使用HashMap等容器可能会导致数据过期的常见误解是错误的，参见一个漂亮的竞态条件，了解如何通过这种方式破坏JVM。

理解为什么会出现这种情况是一个非常棘手的过程，需要了解JVM和类库内部的知识。

至于ConcurrentHashMap，只需阅读javadoc即可澄清您的问题。如果无法解决问题，请参考《Java并发编程实践》。

---

更新：

我成功重现了你的情况，但这不是死锁。其中一个actions永远不会执行完毕。堆栈跟踪如下：

"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)

看起来情况和我链接的那个案例非常相似 - HashMap 被重新调整大小，由于调整大小的内部机制，导致迭代器被困在一个无限循环中。

当这种情况发生时，invokeAll 永远不会返回，程序会挂起。但这既不是死锁，也不是活锁，而是一种 竞态条件。

- Robert Munteanu

---

我理解了（我想 - 我会阅读关于竞态条件的内容）。问题在于我在HashMap代码中找不到任何已锁定的线程。这一切都是在ExecutionService排队功能中发现的，例如Unsafe.park()所述。 - Stephen

我在我的Core 2上使用6u14时没有发生死锁，所以我无法对此进行任何评论。您可以尝试使用ConcurrentHashMap来查看死锁是否仍然存在。但我在这里看不到死锁的原因。 - Robert Munteanu

@Stephen - 我成功地复现了它，并添加了解释。 - Robert Munteanu

不，问题并不在于ExecutorService或者队列。问题在于HashMap不是线程安全的，因此当多个线程同时修改其内部状态时，基本上是未定义的。在你的测试中，似乎迭代器陷入了无限循环。这就是问题所在。 - dmeister

Answer 2

死锁是什么意思？

这段代码至少存在两个问题。多个线程同时使用HashMap可能会陷入无限循环。在遍历entry set时，底层数据结构可能被改变（即使每个操作都同步，hasNext/next也不是原子操作）。

另外，请注意1.6.0版本直到最新的Synhronized Security Release（SSR）更新为止，最新版本为1.6.0_13和1.6.0_14。

- Tom Hawtin - tackline

---

你能提供一个链接，详细介绍SSR版本中包含的内容吗？ - pjp

@pjp，它们现在被称为特殊CPU（临时更新补丁，因为它们目前与Oracle季度CPU不同步）。以下是最新公告的链接，在撰写本文时的风险矩阵：http://www.oracle.com/technetwork/topics/security/javacpujune2011-313339.html#AppendixJAVA 通常不会提供更多详细信息。 - Tom Hawtin - tackline

Answer 3

我认为你的地图正在被并发修改。如果在迭代操作进行时调用put()，在某些情况下（特别是如果发生了调整大小），你可能会陷入无限循环。这是一个相当知名的行为（请参见此处）。

死锁和无限循环将表现出非常不同的情况。如果你有一个真正的死锁，线程转储将清楚地显示交错的线程。另一方面，一旦你进入了一个无限循环，你的CPU将飙升高，并且每次你进行转储时堆栈跟踪都会有所不同。

这与执行器无关，而与不安全的HashMap并发使用有关，它从未被设计成以这种方式使用。事实上，使用少量线程的数组就可以很容易地重现这个问题。

解决这个问题的最佳方法是切换到ConcurrentHashMap。如果你切换到同步的HashMap或Hashtable，你不会陷入无限循环，但在迭代过程中仍可能遇到ConcurrentModificationExceptions。

- sjlee

Answer 4

关于让测试生效的问题 - 不是：

 executor.invokeAll(actions);

使用

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

还要注意，为了使测试实际起作用（并报告错误），您需要执行类似以下操作：

 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... 

- Stephen