无锁定且无等待算法
如果每个线程在其他线程任意延迟（或甚至失败）时都将持续进行操作，就可以说该算法是 无等待的。与此形成对比的是， 无锁定算法要求仅 某个线程总是执行操作。（无等待的另一种定义是保证每个线程在其有限的步骤中正确计算自己的操作，而不管其他线程的操作、计时、交叉或速度。这一限制可以是系统中线程数的函数；例如，如果有 10 个线程，每个线程都执行一次 CasCounter.increment() 操作，最坏的情况下，每个线程将必须重试最多九次，才能完成增加。）
再过去的 15 年里，人们已经对无等待且无锁定算法（也称为 无阻塞算法）进行了大量研究，许多人通用数据结构已经发现了无阻塞算法。无阻塞算法被广泛用于操作系统和 JVM 级别，进行诸如线程和进程调度等任务。虽然它们的实现比较复杂，但相对于基于锁定的备选算法，它们有许多优点：可以避免优先级倒置和死锁等危险，竞争比较便宜，协调发生在更细的粒度级别，允许更高程度的并行机制等等。
原子变量类
在 JDK 5.0 之前，如果不使用本机代码，就不能用 Java 语言编写无等待、无锁定的算法。在 java.util.concurrent.atomic 包中添加原子变量类之后，这种情况才发生了改变。所有原子变量类都公开比较并设置原语（与比较并交换类似），这些原语都是使用平台上可用的最快本机结构（比较并交换、加载链接/条件存储，最坏的情况下是旋转锁）来实现的。 java.util.concurrent.atomic 包中提供了原子变量的 9 种风格（ AtomicInteger； AtomicLong； AtomicReference； AtomicBoolean；原子整型；长型；引用；及原子标记引用和戳记引用类的数组形式，其原子地更新一对值）。
原子变量类可以认为是 volatile 变量的泛化，它扩展了可变变量的概念，来支持原子条件的比较并设置更新。读取和写入原子变量与读取和写入对可变变量的访问具有相同的存取语义。
虽然原子变量类表面看起来与清单 1 中的 SynchronizedCounter 例子一样，但相似仅是表面的。在表面之下，原子变量的操作会变为平台提供的用于并发访问的硬件原语，比如比较并交换。
更细粒度意味着更轻量级
调整具有竞争的并发应用程序的可伸缩性的通用技术是降低使用的锁定对象的粒度，希望更多的锁定请求从竞争变为不竞争。从锁定转换为原子变量可以获得相同的结果，通过切换为更细粒度的协调机制，竞争的操作就更少，从而提高了吞吐量。
 |
ABA 问题
因为在更改 V 之前，CAS 主要询问“V 的值是否仍为 A”，所以在第一次读取 V 以及对 V 执行 CAS 操作之前，如果将值从 A 改为 B，然后再改回 A，会使基于 CAS 的算法混乱。在这种情况下，CAS 操作会成功，但是在一些情况下，结果可能不是您所预期的。（注意， 清单 1 和 清单 2 中的计数器和互斥例子不存在这个问题，但不是所有算法都这样。）这类问题称为 ABA 问题，通常通过将标记或版本编号与要进行 CAS 操作的每个值相关联，并原子地更新值和标记，来处理这类问题。 AtomicStampedReference 类支持这种方法。 |
|
java.util.concurrent 中的原子变量
无论是直接的还是间接的，几乎 java.util.concurrent 包中的所有类都使用原子变量，而不使用同步。类似ConcurrentLinkedQueue 的类也使用原子变量直接实现无等待算法，而类似 ConcurrentHashMap 的类使用 ReentrantLock 在需要时进行锁定。然后， ReentrantLock 使用原子变量来维护等待锁定的线程队列。
如果没有 JDK 5.0 中的 JVM 改进，将无法构造这些类，这些改进暴露了（向类库，而不是用户类）接口来访问硬件级的同步原语。然后，java.util.concurrent 中的原子变量类和其他类向用户类公开这些功能。
使用原子变量获得更高的吞吐量
上月，我介绍了 ReentrantLock 如何相对于同步提供可伸缩性优势，以及构造通过伪随机数生成器模拟旋转骰子的简单、高竞争示例基准。我向您显示了通过同步、 ReentrantLock 和公平 ReentrantLock 来进行协调的实现，并显示了结果。本月，我将向该基准添加其他实现，使用 AtomicLong 更新 PRNG 状态的实现。
清单 5 显示了使用同步的 PRNG 实现和使用 CAS 备选实现。注意，要在循环中执行 CAS，因为它可能会失败一次或多次才能获得成功，使用 CAS 的代码总是这样。
清单 5. 使用同步和原子变量实现线程安全 PRNG
public class PseudoRandomUsingSynch implements PseudoRandom {
private int seed;
public PseudoRandomUsingSynch(int s) { seed = s; }
public synchronized int nextInt(int n) {
int s = seed;
seed = Util.calculateNext(seed);
return s % n;
}
}
public class PseudoRandomUsingAtomic implements PseudoRandom {
private final AtomicInteger seed;
public PseudoRandomUsingAtomic(int s) {
seed = new AtomicInteger(s);
}
public int nextInt(int n) {
for (;;) {
int s = seed.get();
int nexts = Util.calculateNext(s);
if (seed.compareAndSet(s, nexts))
return s % n;
}
}
}
|
下面图 1 和图 2 中的图与上月那些图相似，只是为基于原子的方法多添加了一行。这些图显示了在 8-way Ultrasparc3 和单处理器 Pentium 4 上使用不同数量线程的随机发生的吞吐量（以每秒转数为单位）。测试中的线程数不是真实的；这些线程所表现的竞争比通常多得多，所以它们以比实际程序中低得多的线程数显示了 ReentrantLock 与原子变量之间的平衡。您将看到，虽然 ReentrantLock 拥有比同步更多的优点，但相对于 ReentrantLock，原子变量提供了其他改进。（因为在每个工作单元中完成的工作很少，所以下图可能无法完全地说明与 ReentrantLock 相比，原子变量具有哪些可伸缩性优点。）
图 1. 8-way Ultrasparc3 中同步、ReentrantLock、公平 Lock 和 AtomicLong 的基准吞吐量
图 2. 单处理器 Pentium 4 中的同步、ReentrantLock、公平 Lock 和 AtomicLong 的基准吞吐量
大多数用户都不太可能使用原子变量自己开发无阻塞算法 — 他们更可能使用 java.util.concurrent 中提供的版本，如 ConcurrentLinkedQueue。但是万一您想知道对比以前 JDK 中的相类似的功能，这些类的性能是如何改进的，可以使用通过原子变量类公开的细粒度、硬件级别的并发原语。
开发人员可以直接将原子变量用作共享计数器、序号生成器和其他独立共享变量的高性能替代，否则必须通过同步保护这些变量。
结束语
JDK 5.0 是开发高性能并发类的巨大进步。通过内部公开新的低级协调原语，和提供一组公共原子变量类，现在用 Java 语言开发无等待、无锁定算法首次变为可行。然后， java.util.concurrent 中的类基于这些低级原子变量工具构建，为它们提供比以前执行相似功能的类更显著的可伸缩性优点。虽然您可能永远不会直接使用原子变量，还是应该为它们的存在而欢呼。