欢迎访问昆山宝鼎软件有限公司网站! 设为首页 | 网站地图 | XML | RSS订阅 | 宝鼎邮箱 | 宝鼎售后问题提交 | 后台管理


新闻资讯

MENU

软件开发知识

并刊行列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 道理探究

点击: 次  来源:宝鼎软件 时间:2017-07-28

原文出处: 本日你不格斗来日诰日你就落伍

一、 媒介

常用的并刊行列有阻塞行列和非阻塞行列,前者利用锁实现,后者则利用CAS非阻塞算法实现,利用非阻塞行列一般机能较量好,下面就看看常用的非阻塞ConcurrentLinkedQueue是如何利用CAS实现的。

二、 ConcurrentLinkedQueue类图布局

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

如图ConcurrentLinkedQueue中有两个volatile范例的Node节点别离用来存在列表的首尾节点,个中head节点存放链表第一个item为null的节点,tail则并不是总指向最后一个节点。Node节点内部则维护一个变量item用来存放节点的值,next用来存放下一个节点,从而链接为一个单向无界列表。

public ConcurrentLinkedQueue() {
    head = tail = new Node<E>(null);
}

如上代码初始化时候会构建一个item为NULL的空节点作为链表的首尾节点。

三、offer操纵

offer操纵是在链表末端添加一个元素,下面看看实现道理。

public boolean offer(E e) {
    //e为null则抛出空指针异常
    checkNotNull(e);

   //结构Node节点结构函数内部挪用unsafe.putObject,后头统一讲
    final Node<E> newNode = new Node<E>(e);


    //从尾节点插入
    for (Node<E> t = tail, p = t;;) {

        Node<E> q = p.next;

        //假如q=null说明p是尾节点则插入
        if (q == null) {

            //cas插入(1)
            if (p.casNext(null, newNode)) {
                //cas乐成说明新增节点已经被放入链表,软件开发,然后配置当前尾节点(包括head,1,3,5.。。个节点为尾节点)
                if (p != t) // hop two nodes at a time
                    casTail(t, newNode);  // Failure is OK.
                return true;
            }
            // Lost CAS race to another thread; re-read next
        }
        else if (p == q)//(2)
            //多线程操纵时候,由于poll时候会把老的head变为自引用,然后head的next变为新head,所以这里需要
            //从头找新的head,因为新的head后头的节点才是激活的节点
            p = (t != (t = tail)) ? t : head;
        else
            // 寻找尾节点(3)
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

从结构函数知道一开始有个item为null的哨兵节点,而且head和tail都是指向这个节点,软件开发,然后当一个线程挪用offer时候首先

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

如图首先查找尾节点,q==null,p就是尾节点,所以执行p.casNext通过cas配置p的next为新增节点,这时候p==t所以不从头配置尾节点为当前新节点。由于多线程可以挪用offer要领,所以大概两个线程同时执行到了(1)举办cas,那么只有一个会乐成(如果线程1乐成了),乐成后的链表为:

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

失败的线程会轮回一次这时候指针为:

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

这时候会执行(3)所以p=q,然后在轮回后指针位置为:

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

所以没有其他线程滋扰的环境下会执行(1)执行cas把新增节点插入到尾部,没有滋扰的环境下线程2 cas会乐成,然后去更新尾节点tail,由于p!=t所以更新。这时候链表和指针为:

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

如果线程2cas时候线程3也在执行,那么线程3会失败,劳务派遣管理系统,轮回一次后,线程3的节点状态为:

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

这时候p!=t ;而且t的原始值为told,t的新值为tnew ,所以told!=tnew,所以 p=tnew=tail;

然后在轮回一下后节点状态:

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究

q==null所以执行(1)。

此刻就差p==q这个分支还没有走,这个要在执行poll操纵后才会呈现这个环境。poll后会存在下面的状态

并刊队列-无界非阻塞行 图纸加密 列 ConcurrentLinkedQueue 原理探究