并发队列中迭代器弱一致性原理探究

一、前言

并发队列里面的 Iterators 是弱一致性的,next 返回的是队列某一个时间点或者创建迭代器时候的状态的反映。当创建迭代器后,其他线程删除了该元素时候并不会抛出 java.util.ConcurrentModificationException 异常,能够保持创建迭代器后的元素一定被正确的 next 出来。

二、 ConcurrentLinkedQueue 类图结构

image.png以 ConcurrentLinkedQueue 为例说下是如何实现的,如图内部的 Itr 类实现了接口 Iterator 的功能。 nextNode 变量用来存放 next()函数要返回的节点,nextItem 则用于保存 next() 函数要返回的节点的值,lasetRet 则记录最后一次 next() 时候的节点元素,用于 remove 操作。

三、测试代码

3.1 实验一

本实验是测试获取迭代器后调用 next 前删除元素看看会有什么结果 首先列下测试代码: image.png主线程 debug 断点查看图: image.png如图主线程获取了队列元素 zlx 节点的迭代器,在调用 next 的时候 debug 阻塞主。 下面激活 SleepInterrupt 线程,执行 remove 操作: image.pngremove 后调度到主线程执行 image.png 可知目前队列里面已经没有 zlx 元素了,下面看看迭代结果: zlx gh zzz 可知还是迭代出来了已经删除的元素,并且没抛出异常。

3.2 试验 2

本实验测试获取迭代器前调用 next 后删除迭代器后面的元素看看有什么结果 首先列下测试代码: image.png主线程 debug 断点图 image.png 如图主线程获取了队列元素 zlx 节点的迭代器,在调用 next 的时候 debug 阻塞主。 下面激活 SleepInterrupt 线程,执行 remove 操作: image.pngremove 后调度到主线程执行 image.png 可知现在队列里面没有了 gh 元素,下面看看迭代结果 zlx zzz

3.3 试验 3

本实验测试获取迭代器前调用 next 后删除迭代器后面的元素看看有什么结果 首先列下测试代码: image.png下面看看迭代结果 image.png

四、源码分析

首先调用队列的 iterator() 方法时候会实例化一个迭代器,所以每次调用该方法都是一个新的实例,构造函数内部调用了 advance 方法,目的是确定第一个元素的 iterator.

Itr() {    advance();//(1)}// 获取队列中下一个可用节点。调用 next()时候返回节点值,或者返回 nullprivate E advance() {    //lastRet 记录调用最后一次调用 next 时候的节点
    lastRet = nextNode;(2)    //x 存放节点值
    E x = nextItem;(3)    // 获取 next 节点
    Node<E> pred, p;    // 如果为 nul 则调用阻塞队列的 first 方法获取
    if (nextNode == null) {        p = first();//(4)
        pred = null;
    } else {        // 不为 nul 则获取下一个节点 (5)
        pred = nextNode;
        p = succ(nextNode);
    }    for (;;) {        //p=null 则直接返回,重置节点 null(6)
        if (p == null) {
            nextNode = null;
            nextItem = null;            return x;
        }        // 否者记录当前节点并返回值
        E item = p.item;        if (item != null) {//(7)
            nextNode = p;
            nextItem = item;            return x;
        } else {            // 跳过 null 值节点 (8)
            Node<E> next = succ(p);            if (pred != null && next != null)
                pred.casNext(p, next);
            p = next;
        }
    }
}
// 判断是否有原始 public boolean hasNext() {    return nextNode != null;}// 有则删除 public E next() {    if (nextNode == null) throw new NoSuchElementException();    return advance();
}// 删除元素 public void remove() {    Node<E> l = lastRet;    if (l == null) throw new IllegalStateException();    // rely on a future traversal to relink.
    l.item = null;
    lastRet = null;
}

下面看图说话: 假设初始队列里面有三个元素 image.png 那么调用队列的 iterator 时候执行(1)(4)(7)后队列状态图: image.png 调用 hasNext()时候知道 nextNode != null 所以返回 true. 然后调用 next() 方法执行(2)(5)(7)后, 返回 zlx, 队列状态图 image.png 也就说第一次调用队列的 iterator 方法会在构造函数调用 advance 方法一次,这时候已经把队列第一个可用的节点指针赋值给 nextNode,节点值赋值给 nextItem;这样当调用 hasNext 时候先看 nextNode 是否 null,null 说明队列为空则返回 false 说明队列里面没有元素, 否者会调用 next 方法,该方法会再次调用 advance 方法,由于调用 hasNext 确定了 nextNode 不为 null 所以会调用(5)来获取下次调用 next 要返回的值,也就是当前 nextNode 的后继节点。如果后继节点为 null 则返回 nextNode 对应的值 nextItem,否者设置下一次调用 next 时候需要的 nextNode 和 nextItem。 下面考虑下实验一的情况,首先线程 1 调用调用 hasNext() 后情况为: image.png 假如线程 1 调用 next 前另外线程把队列里面的 zlx 删除了,现在队列状态: image.png 现在在调用 next 方法(2)(5)(7)后的状态为: image.png 所以返回 x=zlx; 试验 2 的结果很明显,这里不再说了,下面看看试验 3 最后还有一个 remove 方法,他仅仅是把最后一次 next 时候记录的节点内容重置为 null,并且记录节点为 null, 下面图解说下: 第一次调用 hasNext 后 image.png 然后调用 remove 方法因为 lastRet=null 所以抛出了异常,其实应该先调用 next 方法在调用 remove 方法。 image.png这样是 OK 的先调用 next 方法设置 lastRet,然后在调用 remove 删除。 然后看 remove 里面并没有看到有对队列里面的头尾节点进行操作,也就说并没有在队列中移除该元素的操作,乍一看这有问题,但是没问题:下面看删除 zlx 后队列状态 image.png 也就是 remove 仅仅把节点内容变为 null,所以 head 还是指向这个元素(注意本节讲的都是不带哨兵节点的队列,正常情况下队列一开始有个 null 的哨兵节点,如果本节考虑的话,那么上面的图应该有两个 null 节点,一个是哨兵,一个是 zlx 节点变成的) 而 poll 时候如果节点内容为 null 则会继续查看后继节点,所以这里 remove 简单的把节点内容变为 null 即可。

四、总结

并发队列里面的迭代器通过使用 nextItem 保留创建迭代器时候的节点的值,保证了在调用 hasNext 和 next 方法之间其他线程删除该元素后还可以正常返回删除节点的内容,并不抛出异常,之所以说是弱一致性是因为调用 next 时候该元素已经不在队列里面了,但是迭代返回还可以返回。另外 remove 操作并没有立刻把删除的原始从队列中干掉,而是在出队时候从队列里面解除,让它变为自引用节点,等待被垃圾回收。