从源码分析非线程安全集合类的不安全迭代器

作者: 猴子007 | 来源:发表于2017-01-27 19:04 被阅读194次

非线程安全集合类（这里的集合指容器Collection，非Set）的迭代器结合了及时失败机制，但仍然是不安全的。这种不安全表现在许多方面：

并发修改“通常”导致及时失败
单线程修改也可能导致及时失败的“误报”
迭代器会“丢失”某些并发修改行为，让及时失败失效

如果不了解其不安全之处就随意使用，就像给程序埋下了地雷，随时可能引爆，却不可预知。
ArrayList是一个常用的非线程安全集合，下面以基于ArrayList讲解几种代表情况。

及时失败

及时失败也叫快速失败，fast-fail。
“及时失败”的迭代器并不是一种完备的处理机制，而只是“善意地”捕获并发错误，因此只能作为并发问题的预警指示器。它们采用的实现方式是，将计数器的变化与容器关联起来：如果在迭代期间计数器被修改，那么hasNext或next将抛出ConcurrentModificationException。然而，这种检查是在没有同步的情况下进行的，因此可能会看到失效的计数器，而迭代器可能并没有意识到已经发生了修改。这是一种设计上的权衡，从而降低并发修改操作的检测代码对程序性能带来的影响。

然而，及时失败机制十分简洁（简单&清晰），同时对集合的性能影响十分小，所以大部分非线程安全的集合类仍然使用这种机制来进行“善意”的提醒。

几种非线程安全的代表情况

并发修改“通常”导致及时失败

“通常”是因为及时失败的“善意”性质，它很多时候会给我们提醒，但有时候也不会给出提醒，有时候甚至给出某种意义上的错误提醒。这一小节针对正常的情况，这是我们考察一个机制是否值得“采纳并完善”的根本属性。

构造下列程序：

…
private Collection users = new ArrayList(); // 所以应使用CopyOnWriteArrayList
…
users.add(new User("张三",28));
users.add(new User("李四",25));
users.add(new User("王五",31));
…
public void run() {
    Iterator itrUsers = users.iterator();
    while(itrUsers.hasNext()){
        System.out.println("aaaa");
        User user = (User)itrUsers.next();
        if(“张三”.equals(user.getName())){ // 在迭代过程中修改集合
            itrUsers.remove();
        } else { // 正常输出
            System.out.println(user);
        }
    }
}
…

忽略细节，假设有多个线程在同时执行run方法，操作users集合。这时，“通常”会导致及时失败。这里的异常可能从next或remove方法中抛出(当然这里是从next，因为next先执行)：

private class Itr implements Iterator<E> {
…
    public boolean hasNext() {
        return cursor != size;
    }
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    public void remove() { // 迭代器的remove方法
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet); // 集合的remove方法
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
…
}

实际检查并抛出异常的是checkForComodification方法：

private class Itr implements Iterator<E> {
…
int expectedModCount = modCount;
    …
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    …
}

modCount是当前集合的版本号，每次修改（增删改）集合都会加 1；expectedModCount是当前迭代器的版本号，在迭代器实例化时初始化为modCount，只有remove方法正常执行（不抛出异常）才可以修改这个值，与modCount保持同步。

因此，如果在线程A正常迭代的过程中，线程B修改了users集合，modCount就会发生变化，这时，线程B的expectedModCount能够与modCount保持同步，线程A的expectedModCount却发现自己与modCount不再同步，从而抛出ConcurrentModificationException异常。

扯远些：
对于线程安全的集合类而言，我们不希望任何失败。但对于非线程安全的类，有人认为“应该在假设线程安全的情况下使用”，所以及时失败机制完全没有必要；有人认为“集合类的状态太多（所有非线程安全域的状态数量的乘积），并发使用时应该给出错误提醒，否则很难排查并发问题”，所以及时失败机制很有必要。这个问题见仁见智，个人支持后者观点。

所以，这种及时失败的检查是不完备的。

单线程修改也可能导致及时失败的“误报”

多线程并发修改集合时，抛出ConcurrentModificationException异常作为及时失败的提醒，往往是我们期望的结果。然而，如果在单线程遍历迭代器的过程中修改了集合，也会抛出ConcurrentModificationException异常，看起来发生了及时失败。这不是我们期望的结果，是一种及时失败的误报。

我们改用集合的remove方法移除user“张三”：

…
public void run() {
    …
        if(“张三”.equals(user.getName())){ // 在迭代过程中修改集合
            users.remove(user); // itrUsers.remove();
        } else { // 正常输出
            System.out.println(user);
        }
    …
}
…

假设只有一个线程执行run方法，在”张三”被删除之后，下一次执行next方法时，仍旧会抛出ConcurrentModificationException异常，也就是导致了及时失败。

这时因为集合的remove方法并没有维护集合修改的状态（如对modCount&expectedModCount组合的修改和检查）：

public class ArrayList<E> extends AbstractList<E>
…
    public boolean remove(Object o) { // 集合的remove方法
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
…
}

这也让我们更容易理解及时失败的本质——依托于对集合修改状态的维护。这里的主要原因看起来是“集合的remove方法破坏了正常维护的集合修改状态”，但对于使用者而言，集合在单线程环境下却抛出了ConcurrentModificationException异常，这是由于及时失败机制没有区分单线程与多线程的情况，统一给出同样的提醒（抛出ConcurrentModificationException异常），因而是及时失败的误报。

迭代器会“丢失”某些并发修改行为，让及时失败失效

除了误报，及时失败之仅限于“善意”（有提醒就是“善意”的，没有也不是“恶意”的）还体现在其可能“丢失”某些并发修改行为。在这里，“丢失”意味着不提醒——某些线程并发修改了当前集合，但没有抛出ConcurrentModificationException异常，及时失败机制失效了。

主动避过及时失败的检查

利用hasNext方法提前结束线程，可以主动避过及时失败的检查，从而导致修改行为的丢失：

private class Itr implements Iterator<E> {
…
    public boolean hasNext() {
        return cursor != size; // 思考：如果删除了集合的倒数第二个元素，会发生什么？
    }
…
}

还是单线程的场景下，假设我们删除了集合的倒数第二个元素。这时next方法导致cursor=oldSize-1，同时remove方法导致newSize=oldSize-1（oldSize是集合修改之前的size值，newSize集合修改之后的）；所以hasNext方法会返回false，让用户误以为集合迭代已经结束（实际上还有最后一个元素），从而循环终止（在我们的程序里用hasNext判断是否结束），无法抛出ConcurrentModificationException异常，及时失败失效了。

推广到多线程的情景是一样的，因为size是共享的。

及时失败的实现是非线程安全的

很容易忽略的一点是，上述集合修改状态的维护本身就是在没有同步的情况下进行的，因此可能看到更多（远比上述要多）失效的集合修改状态，使迭代器意识不到集合发生了修改，这是一种竞态条件（Race Condition）。

假设线程A进入迭代器的remove方法，线程B进入迭代器的next方法，现在线程A执行集合的remove方法：

private class Itr implements Iterator<E> {
…
    public void remove() {
        …
            ArrayList.this.remove(lastRet);
        …
    }
…
}

首先，假设没有其他线程并发修改，则两个线程都可以通过checkForComodification()的检查；然后线程A快速的执行集合的remove方法；待线程A执行完集合的remove方法，由于线程B之前已经通过了检查，现在就无法意识到“users集合在线程A中已经发生了变化”。另外，因为几乎完全不存在同步措施，modCount的修改也存在竞态条件，其他状态也无法保证是否有效。

总结

上面看到了非线程安全集合类的迭代器是不安全的，但在单线程的环境下，这些集合类在性能、维护难度等方面仍然具有不可替代的优势。那么该如何在兼具一定程度线程安全的前提下，更好的发挥內建集合类的优势呢？总结起来无非两点：

使用非线程安全的集合时（实际上对于某些“线程安全”的集合类，其迭代器也是线程不安全的），迭代过程中需要用户自觉维护，不修改该集合。
应尽可能明确线程安全的需求等级，做好一致性、活跃性、性能等方面的平衡，再针对性的使用相应的集合类。

参考：

传智播客_张孝祥_Java多线程与并发库高级应用视频教程/19_传智播客_张孝祥_java5同步集合类的应用.avi

本文链接：源码|从源码分析非线程安全集合类的不安全迭代器
作者：猴子007
出处：https://monkeysayhi.github.io
本文基于知识共享署名-相同方式共享 4.0 国际许可协议发布，欢迎转载，演绎或用于商业目的，但是必须保留本文的署名及链接。

从源码分析非线程安全集合类的不安全迭代器

及时失败

几种非线程安全的代表情况

并发修改“通常”导致及时失败

单线程修改也可能导致及时失败的“误报”

迭代器会“丢失”某些并发修改行为，让及时失败失效

主动避过及时失败的检查

及时失败的实现是非线程安全的

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

并发编程

Java学习笔记