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

一、前言

并发队列里面的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.png remove后调度到主线程执行 image.png 可知目前队列里面已经没有zlx元素了,下面看看迭代结果: zlx gh zzz 可知还是迭代出来了已经删除的元素,并且没抛出异常。

3.2 试验2

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

3.3 试验3

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

四、源码分析

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


Itr() {
    advance();//(1)
}

//获取队列中下一个可用节点。调用next()时候返回节点值,或者返回null
private 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操作并没有立刻把删除的原始从队列中干掉,而是在出队时候从队列里面解除,让它变为自引用节点,等待被垃圾回收。  

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 并发队列中迭代器弱一致性原理探究


FavoriteLoading添加本文到我的收藏
  • Trackback 关闭
  • 评论 (0)
  1. 暂无评论

您必须 登陆 后才能发表评论

return top