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

15.1 锁得劣势

如果在基于锁的类中包含有细粒度的操作（例如同步容器类，在其他大多数方法中只包含了少量操作），那么当在锁上存在着激烈的竞争时，调度开销与工作开销的比值会非常高。

与锁相比，volatile变量是一种更轻量级的同步机制，因为在使用这些变量时不会发生上下文切换或线程调度等操作。

锁定还存在其他以下缺点。当一个线程正在等待锁时，它不能做任何其他事情。

15.2 硬件对并发的支持

现在几乎所有的现代处理器中都包含了某种形式的原子读-改-写指令，例如比较并交换(Compare-and-Swap)或者关联加载/条件储存(Load-Linked/Store-Conditional)。操作系统和JVM使用这些指令来实现锁和并发的数据结构。

15.2.1 比较并交换

CAS是一项乐观的技术，它希望能成功地执行更新操作，并且如果有另一个线程在最近一次检测后更新了该值，那么CAS能检测到这个错误。

当多个线程尝试使用CAS同时更新一个变量时，只有其中一个线程能更新变量的值，而其他线程都将失败。然而，失败的线程并不会被挂起(这与获取锁的情况不同：当获取锁失败时，线程将被挂起来)，而是被告知在这次竞争中失败。

CAS的典型使用模式是：首先从V中读取值A，并根据A计算新值B，然后再通过CAS以原子方式将V中的值由A变成B（只要在这期间没有任何其他线程将V的值修改为其他值）。

15.2.2 非阻塞的计算器

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

15.2.3 JVM对CAS的支持

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

15.3 原子变量类

原子变量比锁的粒度更细，量级更轻，并且对于多处理器系统上实现高性能的并发代码来说时非常关键的。

java中共有12个原子变量类，可分为4组：

• 标量类(Scalar)
  AtomicInteger、 AtomicLOng、 AtomicBoolean以及AtomicReference。这些类都支持CAS,但是它们不宜用作基于散列的容器中的键值。
• 更新器类
• 数组类
  原子数组类（只支持Integer、Long和Reference版本）中的元素可以实现原子更新。
• 复合变量。

15.3。1 原子变量是一种"更好的volatile"

原子变量相比volatile修饰的变量更有原子安全性。

性能比较：锁与原子变量

在中低难度的竞争下，原子变量能提供更高的可伸缩性，而在高清度的竞争下，锁能够更有效地避免竞争。

15.4.1 非阻塞的栈

栈是通过compareAndSet来修改的，因此将采用原子操作来更新top的引用，或者在发现存在其他线程干扰的情况下，修改操作将失败。

15.4.2 非阻塞的链表

15.4.2 原子的域更新器

原子的域更新类表示现有volatile域的一种基于反射的“视图”，从而能够在已有的volatile域上使用CAS。在更新器类中没有构造函数，要创建一个更新器对象，可以调用newUpdater工厂方法，并制定类和域的名字。

在ConcurrentLinkedQueue中使用原子的域更新器

private class Node<E> {
    private final E item;
    private volatile Node<E> next;
    public Node(E item) {
        this.item = item;
    }
}
private static AtomicReferencePieldUpdater<Node, Node> nextUpdater
    = AtomicReferenceFiledUpdater(Node.class, Node.class, "next");

几乎在所有情况下，普通原子变量的性能都很不错，只有在很少的情况下才需要使用原子的域更新器.（如果在执行原子更新的同时还需要维持现有类的串行化形式，那么原子的域更新器将非常有用。）

15.4.4 ABA问题

ABA问题是一种异常现象：如果在算法中的接地点可以被循环使用，那么在使用“比较并交换”指令时就可能出现这种问题（主要在没有垃圾回收机制的环境中）。

AtomicStampedReference（以及AtomicMarkableReference）支持在两个变量上执行原子的条件更新。

AtomicStampedReference将更新一个“对象-引用”二元组，通过在引用上加上“版本号”，从而避免ABA问题。
类似地，AtomicMarkableReference将更新一个“对象引用-布尔值”二元组，在某些算法中将通过这种二元组使节点保存在链表中同时又将其标记为“已删除的节点”。

小结

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