Java并行化资源池队列 2 —— 无锁化的无界队列

Java™ 5.0 第一次让使用 Java 语言开发非阻塞算法成为可能，java.util.concurrent 包充分地利用了这个功能。非阻塞算法属于并发算法，它们可以安全地派生它们的线程，不通过锁定派生，而是通过低级的原子性的硬件原生形式 —— 例如比较和交换。非阻塞算法的设计与实现极为困难，但是它们能够提供更好的吞吐率，对生存问题（例如死锁和优先级反转）也能提供更好的防御。

在不只一个线程访问一个互斥的变量时，所有线程都必须使用同步，否则就可能会发生一些非常糟糕的事情。Java 语言中主要的同步手段就是 synchronized 关键字（也称为内置锁），它强制实行互斥，确保执行synchronized 块的线程的动作，能够被后来执行受相同锁保护的 synchronized 块的其他线程看到。在使用得当的时候，内置锁可以让程序做到线程安全，但是在使用锁定保护短的代码路径，而且线程频繁地争用锁的时候，锁定可能成为相当繁重的操作。

原子变量提供了原子性的读-写-修改操作，可以在不使用锁的情况下安全地更新共享变量。原子变量的内存语义与volatile 变量类似，但是因为它们也可以被原子性地修改，所以可以把它们用作不使用锁的并发算法的基础。基于这些原子化操作构建起来的并发控制算法称为无锁化非阻塞算法，所谓无锁化其实并不是不加锁，只是所加的锁粒度极小（指令级别或微指令级别），因此从程序本身的宏观角度来看，就好象不使用锁进行并发控制一样，正因为如此无锁化操作，需要在CPU指令级别提供基础支持，当前较新的CPU芯片都提供了原子化的CMPXHG指令，来实现原子化操作的支持。在Java平台上所提供的原子化操作API，如果宿主系统提供原子化指令，那么Java的原子化操作就会使用原子化指令实现原子化操作，反之Java的原子化操作会采用细粒度自旋锁来实现，当然所有这些对于使用者都是透明化的。如果深入 JVM 和操作系统，会发现非阻塞算法无处不在。如垃圾收集器使用非阻塞算法加快并发和平行的垃圾搜集；调度器使用非阻塞算法有效地调度线程和进程等。非阻塞算法要比基于锁的算法复杂得多。开发非阻塞算法是相当专业的训练，而且要证明算法的正确也极为困难。但是在 Java 版本之间并发性能上的众多改进来自对非阻塞算法的采用，而且随着并发性能变得越来越重要，可以预见在 Java 平台的未来发行版中，会使用更多的非阻塞算法。

采用非阻塞思想来实现无锁化并行队列，其最难理解的核心思想部分是“通过让较快的线程帮助较慢的线程来防止方法调用陷入饥饿”，其次是要一直意识到非阻塞算法并不是不使用锁，而是使用粒度极小的原子锁。因此与前面的算法实现一样，首先要构建队列节点元素，但节点的next域采用原子化引用AtomicReference来直向下一个元素节点，因此队列本身是一个包含哨兵头结点和尾节点，以及由AtomicReference串接起来的队列，同时每个元素节点还包含各自的节点值，这里每个节点值采用Java泛型化类型表示。队列节点定义代码如下：

然后定义队列的主体实现，其中主要包括：入队和出对操作。

很容易看出这种实现的队列是无锁的。每个方法调用首先找出一个未完成的入队操作，然后尝试完成它。最坏的情形下，所有的线程都试图移动队列的tail域，且其中之一必须成功。仅当另一个线程的方法调用在改变引用中获得成功时，一个线程才可能在入队或出队一个节点时失败，因此总会有某个方法调用成功。这种无锁化的实现从本质上改进了队列的性能，无锁算法的性能比最有效的阻塞算法还要高。