在 java.util.concurrent 包的许多类中，例如 Semaphore 和 ConcurrentLinkedQueue，都提供了比 synchronized 机制更高的性能和可伸缩性。本章将介绍这种性能提升的主要来源：原子变量和非阻塞的同步机制。
15.1 锁的劣势
现代的许多 JVM 都对非竞争锁获取和释放等操作进行了极大的优化，但如果有多个线程同时请求锁，那么 JVM 就需要借助操作系统的功能。如果出现了这种情况，那么一些线程将被挂起并且在稍后恢复运行。当线程恢复执行时，必须等待其他线程执行完它们的时间片以后，才能被调度执行。在挂起和恢复线程等过程中存在着很大的开销，并且通常存在着较长时间的中断。如果在基于锁的类中包含有细粒度的操作（在被锁保护的代码块中只包含少量操作），那么当在锁上存在着激烈的竞争时，调度开销与工作开销的比值会非常高。
与锁相比，volatile 变量是一种更轻量级的同步机制，因为在使用这些变量时不会发生上下文切换或线程调度等操作。然而，volatile 变量同样存在一些局限，比如不能支持 读-改-写 的原子操作。
锁还存在其他一些缺点。当一个线程正在等待锁时，它不能做任何其他事情。如果一个线程在持有锁的情况下被延迟执行（例如发生了缺页错误、调度延迟、或者其他类似情况），那么所有需要这个锁的线程都无法执行下去。如果被阻塞的线程优先级比较高，而持有锁的线程优先级比较低，那么这将是一个严重的问题——也被称为 优先级反转（Priority Inversion）。
15.2 硬件对并发的支持
独占锁是一项悲观锁技术——它假设最坏的情况，并且只有在确保其他线程不会造成干扰的情况下才能执行下去。
对于细粒度的操作，还有另一个种更高效的方法，也是一种乐观的方法，通过这种方法可以在不发生干扰的情况下完成更新操作。这种方法需要借助冲突检查机制来判断在更新过程中是否存在来自其他线程的干扰，如果存在，这个操作将失败，并且可以重试（也可以不重试）。
15.2.1 比较并交换
在大多数处理器架构中采用的方法是实现一个比较并交换（CAS）指令。CAS 包含了 3 个操作数——需要读写的内存位置 V、进行比较的值 A 和 拟写入的新值 B。当且仅当 V 的值等于 A 时，CAS 才会通过原子方式用新值 B 来更新 V 的值，否则不会执行任何操作。无论位置 V 的值是否等于 A，都将返回 V 原有的值。CAS 是一项乐观的技术，它希望能成功地执行更新操作，并且如果有另一个线程在最近一次检查后更新了该变量，那么 CAS 能检测到这个错误。程序清单 15-1 说明了 CAS 语义。
// 程序清单 15-1
public class SimulatedCAS {
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 同时更新同一个变量时，只有其中一个线程能更新变量的值，而其他线程都将失败。然而，失败的线程并不会被挂起（这与获取锁的情况不同：当获取锁失败时，线程将被挂起），而是被告知在这次竞争中失败，并可以再次尝试。
15.2.2 非阻塞的计数器
程序清单 15-2 中的 CasCounter 使用 CAS 实现了一个线程安全的计数器：
// 程序清单 15-2
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;
}
}
递增操作采用了标准形式——读取旧值，根据它计算出新值（加 1），并使用 CAS 来设置这个新值。如果 CAS 失败，那么该操作将立即重试。CasCounter 不会阻塞，但如果其他线程同时更新计数器，那么会多次执行重试操作。
初看起来，基于 CAS 的计数器似乎比基于锁的计数器在性能上更差一些，因为它需要执行更多的操作和更复杂的控制流，并且还依赖看似复杂的 CAS 操作。但实际上，当竞争程度不高时，基于 CAS 的计数器在性能上远远超过了基于锁的计数器，而在没有竞争时甚至更高。如果要快速获取无竞争的锁，那么至少需要一次 CAS 操作再加上与其他所相关的操作，因此基于锁的计数器即使在最好的情况下也会比基于 CAS 的计数器在一般情况下能执行更多的操作。
一个很管用的经验法则时：在大多数处理器上，在无竞争的锁获取和释放的 “快速代码路径” 上的开销，大约是 CAS 开销的两倍。
15.2.3 JVM 对 CAS 的支持
在 Java 5.0 之前，如果不便携明确地代码，那么就无法执行 CAS。在 Java 5.0 中引入了底层的支持，在 int、long 和对象的引用等类型上都公开了 CAS 操作。在原子变量类（例如 java.util.concurrent.atomic 中的 AtomicXxx）中使用了这些底层的 JVM 支持为数字类型和引用类型提供了一种高效的 CAS 操作，而在 java.util.concurrent 中的大多数类在实现时则直接或间接地使用了这些原子变量类。
15.3 原子变量类
共有 12 个原子变量类，可分为 4 组：标量类（Scalar）、更新器类、数组类以及复合变量类。最常用的原子变量类就是标量类：AtomicInteger、AtomicLong、AtomicBoolean 以及 AtomicReference。
15.3.1 原子变量是一种 “更好的 volatile”
略
15.4 非阻塞算法
如果在某种算法中，一个线程的失败或挂起不会导致其他线程也失败或挂起，那么这种算法就被称为非阻塞算法。如果在算法的每个步骤中都存在某个线程能够执行下去，那么这种算法也被称为无锁（Lock-Free）算法。如果在算法中仅将 CAS 用于协调线程之间的操作，并且能正确地实现，那么它既是一种物阻塞算法，又是一种无锁算法。到目前为止，我们已经看到了一个非阻塞算法：CasCounter。在许多常见的数据结构中都可以使用非阻塞算法，包括栈、队列、优先队列以及散列表等。
15.4.1 非阻塞的栈
// 程序清单 15-6
// 使用 Treiber 算法构造的非阻塞栈
public class ConcurrentStack<E> {
AtomicReference<Node<E>> top = new AtomicReference<>();
public void push(E item) {
Node<E> newHead = new Node<>(item);
Node<E> oldHead;
do {
oldHead = top.get();
newHead.next = oldHead;
} while (!top.compareAndSet(oldHead, newHead));
}
public E pop() {
Node<E> oldHead;
Node<E> newHead;
do {
oldHead = top.get();
if (oldHead == null) {
return null;
}
newHead = oldHead.next;
} while (!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}
private static class Node <E> {
public final E item;
public Node<E> next;
public Node(E item) {
this.item = item;
}
}
}
在 CasCounter 和 ConcurrentStack 中说明了非阻塞算法的所有特性：某项工作的完成具有不确定性，必须重新执行。
15.4.2 非阻塞的链表
到目前为止，我们已经看到了两个非阻塞算法，计数器和栈，它们很好地说明了 CAS 的基本使用模式：在更新某个值时存在不确定性，以及在更新失败时重新尝试。
链接队列比栈更为复杂，因为它必须支持对头节点和尾节点的快速访问。因此，它需要单独维护头指针和尾指针。有两个指针指向位于尾部的节点：当前最后一个元素的 next 指针，以及尾节点。当成功地插入一个新元素时，这两个指针都需要采用原子操作来更新。初看起来，这个操作无法通过原子变量来实现。在更新这两个指针时需要不同的 CAS 操作，并且如果第一个 CAS 成功，但第二个 CAS 失败，那么队列将处于不一致的状态。而且，即使这两个 CAS 都成功了，那么在执行这两个 CAS 之间，仍可能由另一个线程会访问这个队列。因此，在为链接队列构建非阻塞算法时，需要考虑到这两种情况。
我们需要使用一些技巧。第一个技巧是，即使在一个包含多个步骤的更新操作中，也要确保数据结构总是处于一致的状态。这样，当线程 B 到达时，如果发现线程 A 正在执行更新，那么线程 B 就可以知道有一个操作已部分完成，并且不能立即开始执行自己的更新操作。然后 B 可以等待（通过反复检查队列的状态）并直到 A 完成更新，从而使两个线程不会相互干扰。
// 程序清单 15-7
// Michael-Scott 非阻塞算法中的插入算法
public class LinkedQueue<E> {
private static class Node <E> {
final E item;
final AtomicReference<Node<E>> next;
public Node(E item, Node<E> next) {
this.item = item;
this.next = new AtomicReference<>(next);
}
}
private final Node<E> dummy = new Node<>(null, null);
private final AtomicReference<Node<E>> head = new AtomicReference<>(dummy);
private final AtomicReference<Node<E>> tail = new AtomicReference<>(dummy);
public boolean put(E item) {
Node<E> newNode = new Node<>(item, null);
while (true) {
Node<E> curTail = tail.get();
Node<E> tailNext = curTail.next.get();
if (curTail == tail.get()) {
if (tailNext != null) {
// 队列处于中间状态，推进尾节点
tail.compareAndSet(curTail, tailNext);
} else {
// 处于稳定状态，尝试插入新节点
if (curTail.next.compareAndSet(null, newNode)) {
// 插入操作成功，尝试推进尾节点
tail.compareAndSet(curTail, newNode);
return true;
}
}
}
}
}
}
在 ConcurrentLinkedQueue 中使用的正是上面的算法。在许多队列算法中，空队列通常都包含一个 “哨兵（Sentinel）节点” 或者 “哑（Dummy）结点”，并且头节点和尾节点在初始化时都指向该哨兵节点。
当插入一个新的元素时，需要更新两个指针。首先更新当前最后一个元素的 next 指针，将新节点链接到列表队尾（处于中间状态），然后更新尾节点，将其指向这个新元素（最终的稳定状态）。
实现这两个技巧时的关键点在于：当队列处于稳定状态时，尾节点的 next 域将为空，如果队列处于中间状态，那么 tail.next 将为非空。因此，任何线程都能够通过检查 tail.next 来获取队列当前的状态。而且，当队列处于中间状态时，可以通过将尾节点向前移动一个节点，从而结束其他线程正在执行的插入元素操作，并使得队列恢复为稳定状态。
15.4.3 原子的域更新器
略
15.4.4 ABA 问题
在 CAS 操作中将判断 “V 的值是否仍然为 A？”，并且如果是的话就继续执行更新操作。在大多数情况下，包括本章给出的示例，这种判断是完全足够的。然而，有时候还需要直到 “自从上次看到 V 的值为 A 以来，这个是是否发生了变化？”在某些算法中，如果 V 的值首先由 A 变成 B，再由 B 变成 A，那么仍然被认为是发生了变化，并需要重新执行算法中的某些步骤。
有一个相对简单的解决方案：不是更新某个引用的值，而是更新两个值，包括一个引用和一个版本号。即使这个值由 A 变为 B，然后又变为 A，版本号也将是不同的。AtomicStampedReference(以及 AtomicMarkableReference) 支持在两个变量上执行原子的条件更新。AtomicStampedReference 将更新一个 “对象 - 引用” 二元组，通过在引用上加上 “版本号”，从而避免 ABA 问题。
网友评论