在自己动手构建无锁的并发容器(栈和队列)中我们基于CAS算法构建了自己的无锁队列,其底层实现是不带哨兵结点的双向链表。双向链表为当前结点保留了指向前驱结点的引用,这种特性有时很有用,比如AQS中线程被唤醒后会通过prev指针找到前驱结点,通过判断其是否是头结点来决定是否要获取锁。然而大部分情况下我们只需要队列提供基本的入队和出队功能,基于双向链表来实现无疑把问题复杂化了。同时由于入队和出队过程增加了不必要的指针操作,一定程度上也影响了其性能。从上一篇最后对不同队列的性能测试中可以看出,基于双向链表实现的无锁队列在并发环境下的表现并不令人满意,不仅与同样使用CAS的ConcurrentLinkedQueue差距较大,连基于独占锁实现的LinkedBlockingQueue都比不过,这就有点尴尬了。从构建更加高效的队列的角度而言,双向链表并不是最优选择,尽管其在特殊情况下很有用,更好的方案是使用单向链表。下面就探讨下如何基于CAS算法和单向链表实现无锁的并发队列。完整的代码见github:beautiful-concurrent
2 队列内部结构 2.1 结点的定义在进行正式编码前,我们来思考下基于单向链表实现的队列需要哪些结构。首先必须思考的是该链表是否带哨兵结点。哨兵结点可以帮我们排除某些边界情况,有利于编程模型的统一。尽管在基于双向链表实现队列时并没有使用哨兵,但这里还是选择带哨兵结点的方式,哨兵结点和链表中的正常结点用同样的数据结构表示,如下图所示：
//链表结点 private static class Node<E> { //UNSAFE对象,用来进行CAS操作 private static final sun.misc.Unsafe UNSAFE; //next指针域在Node对象中的偏移量 private static final long nextOffset; static { try { //类加载时执行,反射方式创建UNSAFE对象,我们要通过该对象以CAS的方式更新 //Node对象中的next指针 Class<?> unsafeClass = Unsafe.class; Field f = unsafeClass.getDeclaredField("theUnsafe"); f.setAccessible(true); UNSAFE = (Unsafe) f.get(null); // UNSAFE = sun.misc.Unsafe.getUnsafe(); Class<?> k = LockFreeSingleLinkedQueue.Node.class; nextOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("next")); } catch (Exception e) { throw new Error(e); } } //CAS方式更新next指针,expect:cmp update:val private boolean casNext(Node<E> cmp, Node<E> val) { return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); } //实际存储的元素 public E item; //指向下一个结点的指针 public volatile Node<E> next; public Node(E item) { this.item = item; } @Override public String toString() { return "Node{" + "item=" + item + '}'; } }结点的定义内容看似很多,其内部主要成员就两个,泛型元素item,这是存储于结点中真正有用的信息,其次是指向下一个结点的指针next。其他的内容主要是为了保证能原子的更新next指针。为什么结点中用来指向下一个结点的next指针需要被原子的更新？
2.2 为什么结点内部的next指针需要原子的更新在基于双向链表实现队列时,Node结点中定义的next指针并不需要被原子的更新,这是由其特殊的结构和特殊的插入方式决定的。回想其入队过程:
1.新结点的prev指针指向原尾结点
2.CAS方式更新尾指针指向新结点
3.原尾结点的next指针指向新结点
1主要用来确定结点在队列中的顺序,2则用来判断当前线程的插入是否成功,一旦2执行成功,新结点就算成功插入了。我们可以思考下以新结点的prev指针来确定队列的顺序有什么好处:每个结点在加入队列前都要通过1来维护在队列中的顺序,将其prev指针指向原尾结点。因为prev指针是每个结点都有的,故并发情况即使多个结点的prev指针都指向同一个尾结点也不会有覆盖的问题,它们不会相互影响。也就是说,在2真正执行前,所有成功执行1的结点都是平等的,都享有2的CAS竞争成功加入队列的权利。如下图所示：
尽管图中是线程2CAS竞争成功从而将其结点入队,但如果是线程1或者线程3CAS竞争成功情况也是类似的。那单链表构成的队列又是怎样一种情况呢?单链表的入队流程相对简洁,只有两步:
1.原尾结点的next指针指向新结点
2.CAS更新尾指针指向新结点
1用来确定新结点在队列中的顺序,和双向链表中通过自身的prev指针来实现不同,单向链表中是通过修改原尾结点的next指针使其指向自己来达到目的的。这在并发环境下就会导致结果覆盖的问题,后一个执行1的线程将覆盖掉前一个线程执行1的结果。这意味着新结点要成功加入队列,不仅需要其所在线程成功竞争CAS,还要保证没有其他线程将其执行1的结果覆盖,而这在并发环境下是难以保证的,如下图: