java - 在迭代中避免不必要的 ConcurrentModificationException

Question

我有大量的东西，一个重复迭代它们的线程，以及一个偶尔删除或添加单个东西的单独线程。事物在同步链表中:

private List<Thing> things = Collections.synchronizedList(new LinkedList<Thing>());

我的第一个线程遍历它们:

while (true) {
    for (Thing thing : things) {
        thing.costlyOperation();
    }
    // ...
}

当我的第二个线程添加或删除内容时，上面的迭代器会因 ConcurrentModificationException 而爆炸。但是，在我的上述案例中似乎允许删除和添加。约束是 (A) coSTLyOperation 方法不能在列表中不存在 Thing 时调用，并且 (B) 应该立即调用(在当前或下一次迭代中)事物存在，并且 (C) 通过第二个线程的添加和删除必须快速完成，而不是等待。

在进入迭代循环之前，我可能会在 things 上同步，但这会阻塞另一个线程太久。或者，我可以修改 Thing 以包含一个 isDead 标志，然后执行一个不错的快速 iterator.remove() 循环来摆脱死东西在上面的循环之前，我会再次检查标志。但是我想在这个 for 循环附近解决这个问题，并且污染最小。我还考虑过创建列表的副本(一种“故障安全迭代”形式)，但这似乎违反了约束 A。

我需要编写自己的集合和迭代器吗？从头开始？即使在这种情况下，我是否忽略了 CME 实际上是一个有用的异常(exception)？有没有我可以使用的数据结构、策略或模式来代替默认迭代器来解决这个问题？

Answer 1

如果在使用迭代器时修改了迭代器的底层结构，您可以获得 CME——无论并发性如何。事实上，只在一个线程上就很容易得到一个:

List<String> strings = new ArrayList<String>();
Iterator<String> stringsIter = strings.iterator();
strings.add("hello"); // modify the collection
stringsIter.next();   // CME thrown!

确切的语义取决于集合，但通常，CME 会在您创建迭代器后修改集合时出现。 (这是假设迭代器不明确允许并发访问，当然，java.util.concurrent 中的某些集合允许并发访问)。

天真的解决方案是同步整个 while (true) 循环，但当然你不想这样做，因为那样你就锁定了一堆昂贵的操作。

相反，您可能应该复制集合(在锁下)，然后对副本进行操作。为了确保事物仍在 things 中，您可以在循环中仔细检查它:

List<Thing> thingsCopy;
synchronized (things) {
    thingsCopy = new ArrayList<Thing>(things);
}
for (Thing thing : thingsCopy) {
    synchronized (things) {
        if (things.contains(thing)) {
            thing.costlyOperation();
        }
    }
}

(您还可以使用上述允许在迭代时进行修改的 java.util.concurrent 集合之一，例如 CopyOnWriteArrayList 。)

当然，现在您仍然拥有围绕coSTLyOperation 的同步块(synchronized block)。您可以将 contains 检查单独移动到同步块(synchronized block)中:

boolean stillInThings;
synchronized (things) {
    stillInThings = things.contains(thing);
}

... 但这只会降低快感，并不会消除它。这对您来说是否足够好取决于您的应用程序的语义。一般来说，如果您希望代价高昂的操作仅在事物在事物中时发生，您需要对其进行某种锁定。

如果是这种情况，您可能需要考虑使用 ReadWriteLock而不是 synchronized block 。这有点危险(因为如果您不小心总是在 finally block 中释放锁，这种语言会让您犯更多错误)，但可能是值得的。基本模式是使 thingsCopy 和双重检查在读者锁下工作，而对列表的修改在写者锁下发生。