原子变量与非阻塞同步机制

在java.util.concurrent 包中的许多类, 比如Semaphore 和ConcurrentLinkedQueue, 都提供了比使用Synchronized 更好的性能和可伸缩性. 本部分将介绍这种性能提升的利器：原子变量和非阻塞的同步机制.

Java锁与非阻塞算法的性能比较与分析+原子变量类的应用

近年来很多关于并发算法的研究都聚焦在非阻塞算法 (nonblocking algorithms),这种算法使用底层的原子机器指令取代锁 ,比如比较并交换 (compare-and-swap),从而保证数据在并发访问下的一致性 .非阻塞算法广泛应用于操作系统和 JVM中的线程和进程调度、垃圾回收以及实现锁和其他的并发数据结构。与基于锁的方案相比 ,非阻塞算法的设计和实现都要复 杂得多 ,但是他们在可伸缩性和活跃度上占有很大的优势。因为非阻塞算法可以让多个线程在竞争相同资源时不会发生阻塞 ,所以它能在更精化的层面上调整粒度 ,并且极大的减少调度的开销。

并且，在非阻塞算法中埔村砸死锁或其他活跃性问题。在基于锁的算法中 ,如果一个线程在持有锁的时候休眠 ,或者停滞不前 ,那么其他线程都无法执行下去 ,而非阻塞算法不会受到单个线程失败的影响 .在 Java 5.0中 ,使用原子变量 (atomic variable classes),比如 AtomicInteger和 AtomicReference,能够高效地构建非阻塞算法 .

即使你不使用原子变量开发阻塞算法 ,它也可以当做更优的 volatile变量来使用 .原子变量提供了与 volatile类型变量相同的内存语义 ,同时还支持原子更新 --使它们能更加理想地用于计数器、序列发生器和统计数据收集等 ,另外也比基于锁的方案具有更加出色的可伸缩性 .

15.1锁的劣势

通过使用一致的加锁协议来协调对共享状态的访问 ,确保无论哪个线程持有守护变量的锁 ,他们都能独占地访问这些变量 ,并且对变量的任何修改对其他随后获得同一锁的线程都是可见的 .

现代 JVM能够对非竞争锁的获取和释放进行优化 ,让它们非常高效 ,但是如果有多个线程同时请求锁 JVM就需要向操作系统寻求帮助。但如果出现了这种情况 ,一些线程将会挂起 ,并在稍后恢复运行。当线程恢复执行时，必须等待其它线程执行完他们的时间片以后才能被调度执行。 在线程的挂起和恢复等过程中存在着很大的开销 , 并通常存在较长时间的中断。 （ JVM并不一定会挂起线程）。

如果基于锁的类中包含细粒度的操作 (比如同步容器类 ,大多数方法只包含很少的操作 ),那么在锁上存在激烈的的锁竞争时 ,调度开销与工作开销的比值会非常高。

与锁相比， volatile 变量 与锁相比是更轻量的同步机制 ,因为它们不会引起上下文的切换和线程调度等操作。然而 ,volatile变量与锁相比有一些局限性 :尽管他们提供了相似的可见性保证 ,但是它们不能用于构建原子化的复合操作。这意味着当一个变量依赖其他变量时 ,或者当变量的新值依赖于旧值时 ,是不能用 volatile变量的 .这些都限制了 volatile变量的使用 ,因此它们不能用于实现可靠的通用工具 ,比如计数器 .

加锁还有其他的缺点 .当一个线程正在等待锁时 ,它不能做任何其他事情。如果一个线程在持有锁的情况下发生了延 迟 (原因包括页错误、调度延 迟、或者类似情况 ),那么其他所有需要该锁的线程都不能执行下去。如果阻塞的线程是优先级很高的线程 ,持有锁的线程优先级较低 ,那么会造成严重问题 --性能风险 ,被称为 优先级反转 (priority inversion)。即使更高的优先级占先 ,它仍然需要等待锁被释放 ,这导致它的优先级会降至与优先级较低的线程相同的水平。如果持有锁的线程发生了永久性的阻塞 (因为无限循环、死锁、活锁和其它活跃度失败 ),所有等待该锁的线程永 远都不能执行下去。

即使忽略些的风险 ,加锁对于细分的操作而言 ,仍是一种 高开销 的机制 ,比如递增计数器 .在管理线程之间的竞争时，应该有一种力度更细的技术，类似于 volatile变量的机制 ,但同时还要支持原子更新操作。幸运的是 ,现代处理器为我们提供了这样的机制。

15.2硬件对并发的支持

独占锁是一种悲观技术 ——它假设最坏（如果你不锁门，那么捣蛋鬼就会闯入并搞得一团遭）的情况，并且只有在确保其他线程不会造成干扰（通过获取正确的锁）的情况下才能执行下去。

对于细粒度的操作，还有一种更高效的方法，也是一种乐观的方法，通过这种方法可以在不发生干扰的情况下完成更新操作。这种方法需要借助冲突检测机制来判断在更新过程中是否存在来自其他的线程干扰，如果存在这个操作将失败，并且可以选择重试或者不重试。

在针对多处理器操作而设计的处理器中提供了一些特殊指令，用于管理对共享数据的并发访问。现在，几乎所有的现代处理器都包含了某种形式的原子读 -改 -写指令，如比较并交换（ Compare-and-Swap ）或者关联加载 /条件存储（
Load-Linked/Store-Conditional ）。操作系统和 JVM使用这些指令来实现锁和并发的数据结构，但在 Java 5.0之前，在 Java类中还不能直接使用这些指令。

2.1 比较并交换 CAS

在大多数处理器架构中采用的方法是实现一种比较并交换指令。 CAS包含 3个操作数 ——需要读写的内存位置 V、进行比较的值 A和拟写入的新值 B。当且仅当 V的值等于 A时， CAS才会通过原子的方式用新值 B来更新 V的值，否则不会执行任何操作。无论位置 V的值是否等于 A ，都将返回 V原有的值。 CAS的含义是： “我认为 V的值应该是 A ，如果是，那么将 V的值更新成 B，否则不修改并告诉 V的值实际是多少 ”。 CAS是一项乐观技术，它希望能成功地执行操作，并且如果有另一个线程在最近一次检查后更新了该变量，那么 CAS能检测到这个错误。程序清单 15-1说明了 CAS的语义。

程序清单 15-1 模拟CAS操作
@ThreadSafepublic
class SimulatedCAS {
    @GuardedBy("this")
    private int value;

    public synchronized int get() {
        return value;
    }

    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = value;
        if (oldValue == expectedValue)
            value = newValue;
        return oldValue;
    }

    public synchronized boolean compareAndSet(int expectedValue, int newValue) {
        return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}

当多个线程尝试使用 CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其他线程都将失败。然而，失败的线程并不会被挂起（注意，这与锁不同），而是被告知在这次竞争中失败，并可再次尝试。由于一个线程在竞争 CAS时失败不会阻塞，因此它可以决定是否重新尝试，或者执行一些恢复操作，或者不执行任何操作。这种灵活性大大减少了与锁相关的活跃性风险。

CAS的典型使用模式是：首先从 V中读取 A ，并根据 A计算新值 B ，然后再通过 CAS以原子方式将 V中的值由 A变成 B （只要在这期间没有任何线程将 V的值修改为其他值）。由于 CAS能检测到来自其他线程的干扰，因此即使不使用锁也能实现原子的读 —改 —写操作序列。

2.2 非阻塞的计数器

程序清单 15-2 基于 CAS实现了一个线程安全的计数器。自增操作遵循了经典形式 —取得旧值 ,根据它计算出新值 (加 1),并使用 CAS设定新值。如果 CAS失败 ,立即重试操作 .尽管在竞争十分激烈的情况下 ,更希望等待或者回退 ,以避免重试造成的活锁 ,但是 ,通常反复重试都是合理的策略。但在一些竞争很激烈的情况下，更好的方式时在重试之前首先等待一段时间或者回退，从而避免造成或锁问题。

程序清单 15-2 基于CAS实现的非阻塞计数器
@ThreadSafepublic
public class CasCounter {
    private SimulatedCAS value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }
}

初看起来，虽然 Java语言的锁定语法比较简洁，基于 CAS的计数器看起来也比基于锁的计数器性能差一些 : 它具有更多的操作和更复 杂的控制流 ,表面看来还依赖于复 杂的 CAS的操作。但是 ,实际上基于 CAS的计数器 ,性能上 远远胜过了基于锁的计数器 ,而在没有竞争时甚至更高。原因有二：

i。 JVM和 OS管理锁的工作却并不简单 .加锁需要遍历 JVM中整个复 杂的代码路径 ,并可能引起系统级的加锁、线程挂起以及上下文切换。在最优的情况下 ,加锁需要至少一个 CAS,所以使用锁时没有用到 CAS ，但实际上也不能节省任何执行开销。

ii。另一方面 ,程序内部执行 CAS不会调用到 JVM的代码、系统调用或者调度活动。在应用级看起来越长的代码路径 ,在考 虑到 JVM和 OS的时候 ,事实上会变成更短的代码。

一个很管用的经验法则是，在大多数处理器上，在无竞争的锁获取和释放上的开销，大约是 CAS开销的两倍。

CAS最大的缺点 :它强迫调用者处理竞争问题 (通过重试、回退 ,或者放弃 );然而在锁中可以通过阻塞自动处理竞争问题， CAS最大的缺陷在于难以正确地构建外围算法。

2.3 JVM 对 CAS 的支持

在 Java 5.0中引入了底层的支持，在 int、 long和对象的引用等类型上都公开了 CAS操作，并且 JVM把它们编译为底层硬件提供的最有效方法。在支持 CAS的平台上，运行时把它们编译为相应的（多条） 机器指令 。在最坏的情况下，如果不支持 CAS指令，那么 JVM将使用 自旋锁 。

在原子变量类（如
java.util.conncurrent.atomic 中的AtomicXxx ）中使用了这些底层的JVM 支持为数字类型和引用类型提供一种高效的CAS 操作，而且在java.util.concurrent 中大多数类在实现时则直接或间接的使用这些原子变量类。

15.3原子变量类

原子变量比锁的粒度更细，量级更轻，并且对于在多处理器系统上实现高性能的并发代码来说是非常关键的。原子变量将发生竞争的范围缩小到单个变量上，这是获得粒度最细的情况。更新原子变量的快速 (非竞争 )路径 ,并不会比获取锁的快速路径差 ,并且通常会更快 ;而慢速路径肯定比锁的慢速路径快 ,因为它不会引起线程的挂起和重新调度。在使用基于原子变量而非锁的算法中，线程在执行时更不易出现延 迟，并且如果遇到竞争，也更容易恢复过来。

原子变量类相当于一个泛化的 volatile变量，能够支持原子的和有条件的读 -改 -写操作。以 AtomicInteger为例，该原子类表示一个 int类型的值，并提供 get和 set方法，这些 volatile类型的 int变量在读取和写入上有着相同的语义。它还提供了一原子的 compareAndSet方法，以及原子的添加、递增和递减等方法。 AtomicInteger在发生竞争的情况下能提供更高的可伸缩性，因为它直接利用了硬件对并发的支持。

共有12 个原子变量类，可分为四组：标量类（Scalar ）、更新器类、数组类及复合变量类。最常用的原子变量就是标量类：AtomicInteger 、AtomicLong 和AtomicBoolean 以及AtomicReference 。所有这些类都支持CAS ，此外AtomicInteger 和AtomicLong 还支持算术运算。

原子数组类中的元素可以实现原子更新。原子数组类为数组的元素提供了 volatile类型的访问语义，这是普通数组所不具备的特性。 volatile类型的数组仅在数组引用上具有 volatile语义，而在其元素上没有。

尽管原子的标量类扩展了 Number类，但并没有扩展一些基本的包装类，这是因为：基本类型的包装类是不可修改的，而原子变量类是可修改的。在原子变量类中同样没有重新定义 hashCode或 equals方法，每个实例都是不同的。与其他可变对象相同，他们也不宜用做基于散列的容器中的键值对。

3.1 性能比较：锁与原子变量

为了说明锁和原子变量之间的可伸缩性差异，我们构造了一个测试基准，其中将比较伪随机数生成器（ PRNG ）的几种不同的实现，在 PRNG中，在生成一个随机数时需要用到一个数字，所以在 PRNG中必须记录前一个数值并将其作为状态的一部分。

在程序清单 15-4和 15-5中给出了线程安全的 PRNG的两种实现，一种使用 ReentrantLock ，另一种使用 AtomicInteger。测试程序反复调用他们，在每次迭代中将随机生成一个数字，并执行一些仅在线程本地数据上执行的 “繁忙 ”迭代。这是一种典型的操作模式，以及在一些共享状态以及线程本地状态上的操作。

程序清单 15-4  基于ReentrantLock实现的随机数生成器
@ThreadSafe
public class ReentrantLockPseudoRandom {

    private final Lock lock = new ReentrantLock();

    private int seed;

    public ReentrantLockPseudoRandom(int seed) {
        this.seed = seed;
    }

    public int nextInt(int m) {
        lock.lock();
        try {
            int s = seed;
            seed = calculateNext(s);
            int remainder = s % n;
            return remainder > 0 ? remainder : remainder + n;
        } finally {
            lock.unlock();
        }
    }
}

程序清单 15-5  基于AtomicInteger实现的随机数生成器
@ThreadSafe
public class AtomicPseudoRandom {
    private AtomicInteger seed;

    public AtomicPseudoRandom(int seed) {
        this.seed = new AtomicInteger(seed);
    }

    public int nextInt(int m) {
       while (true) {
           int s = seed;
           int nextSeed = calculateNext(s);
           if (seed.compareAndSet(s, nextSeed)) {
               int remainder = s % n;
               return remainder > 0 ? remainder : remainder + n;
           }
       }
    }
}

图 15-1和图 15-2给出了在媒体迭代中工作量较低以及适中情况下的吞吐量。如果线程本地的计算较少，那么在锁和原子变量上的竞争将非常激烈。如果线程本地的计算量较多，那么在锁和原子变量上的竞争就会降低，因为在线程中访问锁和原子变量的频率将降低。

从图中可以看出，在高度竞争的情况下，锁的性能将超过原子变量的性能。原因是，使用原子变量时， CAS算法在遇到竞争时将立即重试，通常这是一种正确的方法，但是在竞争激烈的环境下却导致了更多的竞争。

而在竞争适中的情况下，原子变量的性能将 远超过锁的性能，这是因为锁在发生竞争时会挂起线程，从而降低了 CPU的使用率和共享内存总线上的同步通信量。

注意，我们应该意识到，图 15-1中的竞争级别过高而有些不切实际：任何一个真实程序都不会出了竞争锁或原子变量，其他设么工作都不做。

Java锁与非阻塞算法的性能比较与分析+原子变量类的应用 Java锁与非阻塞算法的性能比较与分析+原子变量类的应用

锁与原子变量在不同竞争程度上的性能差异很好的说明了各自的优势和劣势。在中低程度的竞争下，原子变量能提供更高的可伸缩性，而在高强度的竞争下，锁能更有效的避免竞争。

在图 15-1和图 15-2中都包含了第三掉曲线，他是一个使用 ThreadLocal来保存 PRNG状态的 PseudoRandom。这种实现方法改变类的行为，即每个线程都只能看到自己私有的，而不是共享的伪随机数字序列，这说明了能够避免使用共享状态，开销将会更小。

15.4非阻塞算法

基于锁的算法会带来一些活跃度的风险 . 如果线程在持有锁的时候因为阻塞 I/O,页面错误 ,或其他原因发生延 迟 ,很可能所有线程都不能继续执行下去。如果在某种算法中，一个线程的失败或挂起不应该影响其他线程的失败或挂起 ,这样的算法被称为非阻塞 (nonblocking)算法。如果在算法的每一步骤中都有一些线程能够继续执行 ,那么这样的算法称为无锁 (lock-free)算法。

如果在算法中仅将 CAS用于协调线程之间的操作，并且能构建正确的话 ,那么它既是非阻塞的 ,又是无锁的。

在非阻塞算法中，通常不会出现死锁和优先级反转问题 (但可能会出现饥饿和活锁 ,因为他们允许重进入 )。在许多常见的数据结构中都可以使用非阻塞算法，包括栈、队列、优先级队列以及散列表等，而要设计一些新的这种数据结构，最好还是由专家们来完成。

15.5 ABA问题

ABA问题是一种异常现象：如果在算法中的节点可以被循环使用，那么使用 “比较并交换 ”指令就可能会出现这种问题。在某些算法中，如果 V的值首先由 A变成 B ，再由 B变成 A ，那么仍然被认为是发生了变化，并需要重新执行算法中的某些步骤。

如果在算法中采用自己的方式来管理节点对象的内存，那么可能出现 ABA问题。一种相对简单的解决方案是：不是更新某个引用的值，而是更新两个值，包括一个引用和一个版本号。即使这个值由 A变为 B ，然后又变为 A ，版本号也将是不同的。

AtomicStampedReference （以及AtomicMarkableReference ）支持在两个变量上执行原子的条件更新。AtomicStampedReference 将更新一个“ 对象- 引用” 二元组，通过在引用上加上“ 版本号” ，从而避免ABA 问题。类似的，AtomicMarkableReference 将更新一个“ 对象引用- 布尔值” 二元组，，在某些算法中将通过它将节点保存在链表中同时又将其标记为“ 已删除的节点” 。

小结

非阻塞算法通过底层的并发原语来保证线程的安全性，如CAS比较交换而不是使用锁。这些底层原语通过原子变量类向外公开，这些类也用做一种“更好的volatile变量”，从而为整数和对象引用提供原子的更新操作。

非阻塞算法在设计和实现中很困难,但是通常情况下能够提供更好的可伸缩性,并能更好地预防活跃度失败。从JVM的一个版本到下一个版本间并发性的提升很大程度上来源于非阻塞算法的使用,包括在JVM内部以及平台类库.

</article>