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()交替执行时会出现 本文只介绍第一种情况)
多线程操作
第一种情况: 只有 offer()
第二种情况: offer()和 poll()方法交替执行
同时执行 offer()(假设我们现在有 3 个线程)
不变性: 永远只有一个线程 CAS 成功 并且总会成功一个
循环次数分析:Thread1 成功 循环一次退出 Thread2 失败 再循环一次成功 Thread3 失败 再循环两次成功 如果有 n 个线程同时执行 offer() 执行次数 最大为 n 次 最少为 1 次
方法 5 中三目表达式解析: p=condition?result1:result2 我先说一下这里的意义 满足 result1 的场景为 : 获取尾节点 tail 的快照已经过时了(其他线程更新了新的尾节点 tail) 直接跳转到当前获得的最新尾节点的地方 满足 result2 的场景为: 多线程同时操作 offer() 执行 1 方法 CAS 成功后 未更新尾节点(未执行 3 方法: 两种原因 1 是未满足前置条件 if 判断 2 是 CAS 更新失败) 直接找 next 节点
方法 2 与方法 5 是整个 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 之前
图 2
对于 Thread2 进入 2 方法 p!=t 满足 执行 casTail(t, newNode) 更新尾节点的快照 如下图
图 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 核心总结
tail 和 head 都是 延迟更新的 但是 tail 更新在 head 更新后面 因为方法 4 中 需要依赖 head 节点 去找每一个存活的节点
前面的叙述中 可以看到 offer() 方法内 核心操作 就是 p=condition?result1:result2
偶数次 offer() 操作更新一次 tail 单线程的环境下
与 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()插入的节点 直接去尾节点 直接跨过去
能抵达每一个相对于当前快照来说最新的 next 节点
高并发时 tail 和 p 相互配合 尽力去离当前尾节点 最近的地方
ConcurrentLinkedQueue 缺点
CAS 操作 虽然总会成功 但是竞争效率如果很低 不如用同步锁 采用 CAS 编写并发代码 都是大佬级别 难度高 不接地气(嘿嘿)
循环可能会带来额外的资源开销