一、 媒介

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

二、 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时候首先

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

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

这时候会执行（3）所以p=q,然后在轮回后指针位置为：

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

如果线程2cas时候线程3也在执行，那么线程3会失败，轮回一次后，线程3的节点状态为：

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

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

q==null所以执行（1）。

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