在正式执行入队操作前要将当前队列的状态“记录”下来‘:获取当前队列的尾结点tailed和尾结点的下一个结点tailedNext(可能为null)。这是CAS算法的通用流程,毕竟CAS更新成功的前提是没有其他线程对状态进行过修改。然而,这里还有第二层含义,可以让线程发现当前队列是否正处于一种结点入队的中间状态,即一个线程已经修改尾结点的next指针指向新结点,但尚未来得及更新tail指针。当前线程如果发现队列正处于这样一种中间状态,则可以替其他线程执行CAS更新尾指针的操作。但在这么做之前,还必须保证队列此时没有处于出队操作导致的中间状态:队列为空,但tail指针并没有指向哨兵。故首先需要通过
if (sentinel.next == null && tailed != sentinel)进行判断,并在必要的情况下对队列状态进行修复。之后,通过
if (tailed == tail.get())判断是否已经有其他线程已经完成了入队操作,是的话则要重新执行for循环。否则队列此时必然处于以下两种情况之一：
1.所记录的尾结点的下一个结点(tailedNext)存在
说明此时已经有线程正在执行入队操作,但刚执行完第一步,还未来得及修改tail指针,那我们就帮它完成剩下的工作,当然这一步失败也没关系,可能是它自己完成了或者还有其他雷锋抢先我们一步。
2 所记录的尾结点的下一个结点(tailedNext)不存在
此时首先CAS更新尾结点的next指针指向新结点,CAS竞争失败说明有其他线程快我们一步,重新执行for循环;否则CAS方式更新tail指针,当然这一步同样可能失败,不过没关系,我为人人,人人为我,肯定有其他线程帮我们做了这工作。
4. 性能测试为了放大测试结果的差异,这次我们开启200个线程,每个线程混合进行10000次入队和出队操作,将上述流程重复进行100次统计出执行的平均时间(毫秒),完整的测试代码见github:beautiful-concurrent。测试结果如下图所示
从测试结果可知,基于单向链表实现的无锁队列LockFreeSingleLinkedQueue取得了第二名的好成绩。尽管与JDK中的ConcurrentLinkedQueue依旧有很大差距,但已经比基于锁实现线程安全的LinkedBlockingQueue出色不少了。当然也比基于双向链表实现的无锁队列表现的更为出色。
5. 总结CAS算法将多线程间同步的范围缩小到了单个变量,最大限度的提升了程序执行的并行度,某种程度上可以说这种并行化带来的可伸缩性是CAS算法最大的优势。然而也要看到,当对某个数据结构的修改涉及到多个变量时,CAS算法却无法同时对多个变量进行同步,这可能导致线程对数据结构的修改处于某个中间状态,而这个中间状态可能导致其他线程无法继续执行。这时候,可以基于CAS算法实现线程间的协作。当线程发现数据结构处于某个中间状态(意味着其他线程正在对其进行修改,但可能未修改完成便失去了CPU执行权),可以对这种中间状态进行修复(替其他线程执行其未完成的操作),比起白白自旋消耗cpu,这种相互协作显然能更好的提升性能,前面入队方法的实现就是这种基于CAS协作的典型例子,当然这也依赖于CAS操作本身的特性:原子性以及只有符合预期才能执行成功。理解了这一点,我们才能更好的使用CAS算法构建出高效的无锁的数据结构。