11.4　非阻塞方式

线程之间的同步机制的核心是监视器对象上的锁。不同线程之间通过竞争锁的所有权来获得执行某些特定代码的机会。锁机制的目的是保证多线程程序运行时的正确性，但是会对性能造成很大的影响。锁机制在运行时的代价很高，涉及CPU和内存方面的很多处理。对于一个声明为synchronized的方法，有多个线程竞争对应监视器对象上的锁来获取执行该方法的机会。如果其中某一个线程成功获取了对象上的锁，则其他尝试获取锁的线程会处于等待状态。基于锁机制的实现方式在很大程度上限制了多线程程序的吞吐量和性能，而且会带来死锁和优先级倒置等问题。

死锁问题指的是两个线程分别持有另外一个线程所需要获取的锁，同时又希望获取另外一个线程已经持有的锁。每个线程都由于等待对方释放锁而处于等待状态，因此无法释放自己持有的锁来让对方运行。这样造成的结果是两个线程都无法运行。优先级倒置问题指的是线程的优先级由于锁机制而无法成功应用。有可能因为低优先级的线程持有锁的时间过长，导致高优先级的线程长时间处于等待状态。

锁机制对于多线程程序性能的影响主要来自于其所带来的线程阻塞问题。如果能够不阻塞线程，又能保证多线程程序的正确性，那无疑是更好的一种机制。在程序中，对共享变量的使用一般遵循一定的模式，即由读取、修改和写入三步组成。在读取步骤中读取共享变量的当前值，在修改步骤中根据变量的当前值进行某些修改操作，最后在写入步骤中把修改之后的结果作为共享变量的新值写入。比如代码清单11-1中的getNext方法对共享变量value的使用就遵循这样的模式。先读取value的当前值，把该值加上1之后作为新值，最后把新值写入value中。类似的使用方式还有很多。在这三步执行过程中，随时可能发生线程切换，造成不同线程看到变量value的不同值，从而产生错误。锁机制的做法是把这三步变成一个原子操作，从而解决了这个问题。如果读取、修改和写入这三步合起来在CPU上形成一个原子操作，那么CPU在执行这三步时不会发生线程切换，也就不会造成数据不一致的问题。

目前CPU基本都提供了相关的指令来实现读取、修改和写入这三步的原子操作。比较常见的指令名称是“比较和替换（compare and swap, CAS）”。这个指令会先比较某个内存地址的当前值是不是指定的旧值。如果是，就用指定的新值来替换它；否则就什么也不做。指令的返回结果是内存地址的当前值。CAS指令的这种执行方式的含义在于：如果这个内存地址的当前值还是上次访问时的旧值，就说明从上次访问到这次访问的时间间隔内，没有其他线程对该内存地址进行过修改，可以安全地进行修改操作；否则说明有其他线程进行了修改，当前线程所持有的值已经不再有效，需要使用内存地址的当前值重新进行计算，并在适当的时机再次使用CAS指令进行更新。通过CAS指令可以实现不依赖锁机制的非阻塞算法。一般的做法是把对CAS指令的调用放在一个无限循环中。如果当前循环没能完成修改操作，就不断进行尝试，总会在某个时机上，CAS指令成功完成修改。

Java平台利用了CPU提供的CAS指令来实现非阻塞操作。相关的API在java.util.concurrent.atomic包中。需要注意的是，不是所有的CPU都支持CAS或类似功能的指令。在某些平台上，java.util.concurrent.atomic包的实现仍然是通过内部的锁机制来实现的。java.util.concurrent.atomic包中提供的Java类分成三类，每一类Java类提供不同的功能。

第一类是支持以原子操作来进行更新的数据类型的Java类，包括AtomicBoolean、AtomicInteger、AtomicLong和AtomicReference类，分别用于对布尔类型、整数、长整数和对象引用进行更新。在内存模型相关的语义上，这4个类的对象类似于volatile变量。这4个类所包含的方法不尽相同，但是都与值的获取和设置相关。其中最重要的方法是compareAndSet，用来实现CAS指令的语义。调用compareAndSet方法时需要提供两个参数，第一个是所期望的对象的旧值，第二个是希望设置成的对象的新值。如果对象的当前值与所期望的旧值相同，则把当前值设置为新值。从compareAndSet方法的返回值可以判断设置是否成功。在内存模型语义上，compareAndSet方法相当于读取volatile变量的当前值后再写入新值，不过是作为一个原子操作而完成的。与compareAndSet方法功能相同的是weakCompareAndSet方法。与compareAndSet方法相比，weakCompareAndSet方法的性能要好一些，但是所提供的语义比较弱。使用weakCompareAndSet方法只能保证对当前变量的修改对于其他线程是可见的，但不能保证在调用weakCompareAndSet方法之前对其他变量的修改也是对于其他线程可见的。这点与volatile关键词的语义是不同的。所以weakCompareAndSet方法只适合于用来对值不依赖于其他变量的变量进行修改，如计数器。这4个类中的get和set方法分别用来直接获取和设置变量的值，相当于读取和写入volatile变量的值。这4个类中最后一个相同的方法是lazySet。这个方法与set方法类似，但是允许编译器把对lazySet方法的调用与后面的指令进行重排，因此对值的设置操作有可能被推迟。代码清单11-9给出了一个使用AtomicInteger类实现的线程安全的标识符生成器的示例。AtomicInteger类提供了getAndIncrement方法，相当于代码清单11-1中的value++，不过这个方法是线程安全和非阻塞的。

代码清单11-9　使用AtomicInteger类实现的生成唯一标识符的Java类

public class AtomicIdGenerator{

private final AtomicInteger counter=new AtomicInteger（0）；

public int getNext（）{

return counter.getAndIncrement（）；

}

}

代码清单11-10给出了getAndIncrement方法的内部实现方式，这也是compare-AndSet方法的一般使用模式。由于compareAndSet方法不一定能够成功完成，因此需要把对compareAndSet方法的调用包装在一个无限循环中，不断进行调用，直到compareAndSet方法调用成功为止。

代码清单11-10　AtomicInteger类的getAndIncrement的内部实现

public final int getAndIncrement（）{

for（；）{

int current=get（）；

int next=current+1；

if（compareAndSet（current, next））

return current；

}

}

第二类是提供对数组类型的变量进行处理的Java类。把数组对象的引用变量声明为volatile只能保证对这个引用变量本身的修改对其他线程是可见的，但是不涉及数组中所包含的元素。AtomicIntegerArray、AtomicLongArray和AtomicReferenceArray类把volatile的语义扩展到了数组元素的访问中。这三个类的使用方式类似于对应的操作单个变量的类，只不过在方法调用中多了一个参数来指定要操作的数组元素的序号。

最后一类Java类通过反射的方式对任何对象中包含的volatile变量使用compareAndSet方法进行修改。AtomicIntegerFieldUpdater、AtomicLongFieldUpdater和AtomicReferenceFieldUpdater类分别用来对声明为volatile的int型、long型和对象引用类型的变量进行修改。这三个类提供了一种方式把compareAndSet方法的功能扩展到在任何Java类中声明为volatile的域上。这三个类在使用上虽然灵活，但是在原子操作上所提供的语义较弱，因为除了这三个类的对象之外，还可能有其他对象以其他方式对声明为volatile的域进行修改。代码清单11-11给出了AtomicReferenceFieldUpdater类的使用示例。在对TreeNode类中的volatile域parent进行更新时，通过一个固定的AtomicReferenceFieldUpdater类的对象的compareAndSet方法来完成。AtomicReferenceFieldUpdater类提供了一个静态工厂方法newUpdater，这个静态工厂方法根据包含volatile域的Java类的类型、域本身的类型和域的名称这3个参数来创建用来更新域的值的AtomicReferenceFieldUpdater类的对象。AtomicReferenceFieldUpdater类的对象中包含的方法与对应的AtomicReference类是相同的。如果程序中的Java类需要用到compareAndSet方法提供的语义，那么可以利用这三个类。

代码清单11-11　更新volatile对象引用AtomicReferenceFieldUpdater类的使用示例

public class TreeNode{

private volatile TreeNode parent；

private static final AtomicReferenceFieldUpdater＜TreeNode, TreeNode＞parentUpdater=AtomicReferenceFieldUpdater.newUpdater（TreeNode.class, TreeNode.class，"parent"）；

public boolean compareAndSetParent（TreeNode expect, TreeNode update）{

return parentUpdater.compareAndSet（this, expect, update）；

}

}

从整体的角度来说，java.util.concurrent.atomic包中的Java类属于比较底层的实现，一般作为java.util.concurrent包中很多非阻塞的数据结构的实现基础。实际上使用比较多的主要是AtomicBoolean、AtomicInteger、AtomicLong和AtomicReference这4个类。在实现线程安全的计数器时，AtomicInteger和AtomicLong类是最佳的选择。