转载

<<Java并发编程实践>>有感 ConcurrentLinkedQueue解读

ConcurrentLinkedQueue(上集)

算法实现 CAS

CAS的优点

当一个线程执行任务失败不影响其他线程的进行最大限度的利用CPU资源能提高程序的伸缩性伸缩性:不修改任何代码升级硬件就能带来性能上的提高升级硬件带来的性能提高明显就是伸缩性良好
CAS的缺点

代码复杂影响阅读性刚开始看 ConcurrentLinkedQueue 的时候没有正确的思路,理解起来会比较费劲我推荐直接用多线程同时执行的方式去理解这样会比较好

重要概念

不变性
- 所有item不为null的节点都能从head头节点开始通过succ()方法访问到
- head!=null 只要队列有值保证真实的head永不为null head哪怕会自引用迟早也会解除这种假状态
可变性
- heatd.item 可能为null也可能不为null 因为cas活锁操作每一行代码执行都不影响其他线程的访问相同的代码块
- tail尾节点的更新是滞后于head的个人理解在offer中尾节点掉队后通过head节点 (不变性1的保证) 成功访问最后一个p.next=null的节点
快照
- snapshot是我自己的理解因为对于多线程操作来说当前引用对象如offer()中 t=tail中的t; p=t中的p; q=p.next中的q都是一个快照他获得一个对象的快照版本然后在后续的操作中使(t!=(t=tail))这样操作有意义

重要方法

offer()
poll()

源码

public boolean offer(E e) {
        checkNotNull(e); //NullPointException检查   
        final Node<E> newNode = new Node<E>(e); //包装成一个Node对象

        for (Node<E> t = tail, p = t;;) {//获取当前尾节点 t=tail,p是真正的尾节点 p.next==null 
            Node<E> q = p.next;
            if (q == null) {
                // p is last node 
                if (p.casNext(null, newNode)) {//方法1 CAS更新 自己想3个线程同时进行这个操作
                    // Successful CAS is the linearization point
                    // for e to become an element of this queue,
                    // and for newNode to become "live".
                    if (p != t) // hop two nodes at a time //方法2 延迟更新尾节点 下面说为什么
                        casTail(t, newNode);  //方法3 成不成功无所谓 下面说
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)// 方法4 学习offer方法时 可以暂时放弃这一步
                // We have fallen off list.  If tail is unchanged, it
                // will also be off-list, in which case we need to
                // jump to head, from which all live nodes are always
                // reachable.  Else the new tail is a better bet.
                p = (t != (t = tail)) ? t : head;
            else  //去找到真正的尾节点 此处和方法2 应是相互辉映的存在
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q; //方法5
        }
    }

解读offer()方法

自顶向下思考CAS中可能出现的情况 CAS是活锁所谓活锁即是每一行代码运行时允许其他线程访问相同的代码块成功与失败并存衍生了更多的条件判断本人觉得CAS方法都应该从这个方法去理解再自己画画时序图 (注意:理解 offer()时,先把方法4排除 ，因为4方法出现自引用的情况只有 offer() 和 poll() 交替执行时会出现本文只介绍第一种情况)

多线程操作
1. 第一种情况: 只有 offer()
2. 第二种情况: offer() 和 poll() 方法交替执行
同时执行 offer() (假设我们现在有3个线程)
```
offer()
offer()
offer() 
```

只有 offer() 操作时

假设:

Thread 1执行完1方法成功还未执行2方法 Thread2和Thread3进入5方法 ,也就是说Thread2和Thread3执行5方法发生在Thread1执行2方法之前 Thread2 and Thread3 invoke method5() before Thread1 invoke method2()

此时 Thread2.p =q,Thread3.p=q, 因为p==t成立时序图如下,然后Thread1执行方法2 p==t 不执行tail尾节点的更新操作由此可知尾节点是延迟更新一切为了更高效～～～
```
图1
```

Thread 2 与 Thread3 此时再次执行 1 方法见图1 他们此时的q.next==null 我们规定Thread2 CAS成功 Thread3失败了成功后的时序图如下我们假设 Thread3 invoke method5() after Thread2 invoke method2() Thread2执行方法2 在 Thread3执行方法5之前

<<Java并发编程实践>>有感 ConcurrentLinkedQueue解读

图2

对于Thread2 进入2方法 p!=t 满足执行 casTail(t, newNode) 更新尾节点的快照如下图

<<Java并发编程实践>>有感 ConcurrentLinkedQueue解读

图3

Thread2 工作完成退出循环

对于Thread3 因为执行1方法失败进入5方法此时Thread3的tail快照t3

p = (p != t && t != (t = tail)) ? t : q;

按图3来翻译

p=(p!=t3&&t3!=(t3=t2))?t2:q;

p=t2;//直接去当前能获取到的尾节点！！！

到这里 offer() 方法解决完成

ConcurrentLinkedQueue核心总结

offer()
offer()

与Michael-Scott 队列比较

Michael-Scott队列每次操作都需要判断是否需要推动尾节点采取CAS的操作优点也是缺点
Doug Lead老神仙的CAS 我这个菜鸟猜测能不用CAS 就尽量不用因为CAS存在竞争提供以最少次数的更新达到最终正确的效果
我们把 offer() 中的整个行为想象为跳台阶 result1的形式就像是武侠小说中的越阶战斗！！！result2的形式就是一步一个脚印每次平稳地去下一个台阶
我们想象一下 offer() 最优的情况 10个线程同时 offer()
每一个执行1方法成功的线程都没有(执行2方法或则执行3方法失败) 没关系尾节点的更新终会成功

每一个失败的线程都是去当前节点的next节点 p.next进行插入操作在第9个线程(相当于我们上文中的线程2)

当第10个线程操作时虽然它很可怜一直排到最后但是尾节点更新一下就越过了9阶!!!(不太恰当的地方请大佬们指点)
ConcurrrntLinkedQueue 优点
```
offer()
```
ConcurrentLinkedQueue 缺点
1. CAS操作虽然总会成功但是竞争效率如果很低不如用同步锁采用CAS编写并发代码都是大佬级别难度高不接地气(嘿嘿)
2. 循环可能会带来额外的资源开销