Java 并发 - 原子变量

在 java.util.concurrent 包的许多类中(例如 Semaphore 和 ConcurrentLinkedQueue),都提供了比基于 synchronized 机制更高的性能和可伸缩性。这些优化的根源是:「原子变量」和「非阻塞的同步机制」。

synchronized 机制是基于互斥锁的,锁会阻塞进程,继而带来一系列可能导致的问题。近年来,并发算法领域的多数研究都侧重于非阻塞算法,这种算法用原子机器指令(例如后面会说的 CAS 指令)代替锁来保证数据在并发访问中的一致性。因此,原子变量是非阻塞算法的基石。

并发访问要关注两个问题:「互斥性」和「可见性」。原子变量除了能满足以上「互斥性」的要求,还能满足「可见性」。在没有原子变量之前,如果不需要「互斥性」只需要「可见性」,我们可以使用 volatile(如果使用了 synchronized,可见性自动满足);在有了原子变量之后,我们可以用它来代替 volatile,同时还能获得额外的原子操作。

锁的劣势

当多个线程争用锁时,JVM 会借助操作系统的功能挂起线程,等待之后再被恢复(如果用了自旋锁就不一定会被挂起),这里的主要开销就来自于线程的挂起和恢复。除此之外,锁还有可能会带来类似死锁、活跃性等问题。

与锁相比,volatile 变量的使用不会发生上下文切换和线程调度,因此它是轻量级的。它提供了「可见性」,但不能用于构造原子的复合操作,继而也就不能实现计数器或互斥体等工具(i++ 这种自增操作在没有原子变量之前,只能通过加锁来保证数据一致性)。

我们希望既可以有类似 volatile 的机制,操作是轻量级的,又可以支持原子操作,这就要借助现代处理器中的一些机制。

硬件层面的并发支持

在现代的多核处理器中,有一些特殊的机器指令,例如 Test-and-Set, Fetch-and-Increment, Swap, Compare-and-Swap 等,这些指令都是原子的复合操作,它们组合起来足以实现各种 mutex,而 mutex 又可以构造更复杂的并发对象。因此,操作系统和 JVM 可以使用这些指令来实现锁和并发的数据结构。

CAS(Compare-and-Swap)

CAS 操作在修改目标变量 V 的时候,它先测试 V 的当前值和我们的预期值是否相同,如果相同就设置 V 为新的值。

它的最经典的使用模式就是:

  1. 从变量 V 中读取值 A
  2. 根据值 A 计算得到新的值 B
  3. 通过 CAS 操作,比较变量 V 当前的值是否还是 A:如果是,就将 V 设置为 B;如果不是,操作失败,一般不做任何额外操作,只是再次从第一步开始重新尝试。

以下是使用该模式实现的线程安全的计数器,它是非阻塞的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class CasCounter {
private AtomicLong value = new AtomicLong(0L);
public long getValue() {
return value.get();
}
public long increment() {
long current;
do {
current = value.get();
}
while (!value.compareAndSet(current, current + 1));
return current + 1;
}
public static void main(String[] args) {
CasCounter counter = new CasCounter();
for (int i = 0; i < 10000; i++) {
new Thread(counter::increment).start();
}
System.out.println("Counts: " + counter.getValue());
}
}

在竞争不高时,基于 CAS 的计时器在性能上远远超过基于锁的计数器。它的主要缺点在于,使用 CAS 操作我们需要自己处理竞争问题(例如以上代码中 compareAndSet 方法返回 false 的情况下,我们要再次循环尝试),而使用锁的情况下,这种竞争问题是底层自动处理的。

CAS 操作是在 Java 5.0 之后引入的底层支持,它们在 int, long 和对象引用等类型上都公开了 CAS 操作。即使在最坏情况下,平台不支持 CAS 操作,也会用采用自旋锁来减轻线程调度的开销。在 java.util.concurrent 中的大多数类都直接或间接地引用了这些原子变量类。

原子变量类

原子变量操作将竞争范围缩小到单个变量上,并且不需要上下文切换和线程调度,因此它比锁的粒度更细,量级更轻。我们也可以把原子变量视作为更好的 volatile,它同时满足「可见性」要求和原子操作。

上面我们已经给出了一个原子变量 AtomicLong 的使用示例,CasCounter 实现比较简单,因为只有一个状态,单个原子变量实际已经封装了其所有需要的操作。但如果我们的类有两个状态,我们可以把这两个状态封装为一个 Immutable 的对象,然后用 AtomicReference 来对该对象实现 CAS 操作,实际上就是把这个类约化为单个状态的情况。

部分代码如下:

1
2
3
4
5
6
7
8
9
10
11
public class CasNumberRange {
private static class IntPair {
final int lower;
final int upper;
...
}
private final AtomicReference<IntPair> values
= new AtomicReference<>(new IntPair(0, 0));
...
}

锁和原子变量的性能比较

比较结论是:在高度竞争的情况下,锁的性能超过原子变量的性能;但在更真实的竞争情况下则反过来。原因是,高度竞争情况下,CAS 操作失败之后会立即重试,这会导致更多的竞争,而锁会挂起线程,降低 CPU 的使用率和共享内存总线上的通信量。

这一点在 Redis 中也是同样的,Redis 可以通过 WATCH 来实现 CAS 操作,继而实现事务,但是在系统负载很重,主键争用非常厉害的时候,用 WATCH/MULTI/EXEC 组成的乐观锁性能会严重下降,这种情况用悲观锁效率更高。

非阻塞算法

什么是非阻塞算法?这个是相对于基于锁的算法来说的,在基于锁的并行算法中,由于锁的存在,可能会发生各种活跃性故障,如果线程在持有锁的情况下出现异常,可能导致其他等待该锁的线程都无法继续执行下去。

如果某种算法的每个步骤都不存在阻塞,也不会被其他线程的挂起或失败影响,那么这种算法就是非阻塞算法,或者称无锁(Lock-Free)算法。

前面的 CasCounter 就是非阻塞算法,许多常见的数据结构也可以使用非阻塞算法(栈、队列、优先队列、散列表)。

非阻塞的栈较为容易实现,因为它只有一个状态,就是栈顶,通过 CAS 操作就可以实现。

而 ConcurrentLinkedQueue 则较难实现,因为它不止一个状态,我们要考虑多个状态之间的一致性。不过总的来说,构建非阻塞算法的技巧在于:将执行原子修改的范围缩小到单个变量上。前面的 CasNumberRange 就展现了这种技巧。

这里就不继续深入这些非阻塞容器的实现了,这些类的实现应当由专家们来完成。

ABA 问题

ABA 问题存在于 CAS 操作中,如果我们的主线程第一次获取了变量 V 的值 A,然后变量 V 先被其他线程改为值 B,又被改为值 A,那么当我们主线程执行 CAS 操作的时候,发现变量 V 的值还是 A,并没有发生变化,那这个判断正确么?

至少在某些情况下这是错误的,因此,我们可以额外维护一个原子变量 version(版本号),每次修改都会让版本号递增,我们可以通过配合版本号来判断值是否发生变化。在 ElasticSearch 中,就是借助 version 来实现 CAS 操作,也就是实现一个乐观锁。

总结

原子变量可以当做一种「更好的 volatile 变量」来使用,也可以用来构造非阻塞算法,借助的就是它通过底层实现的原子操作(例如 CAS)。

然而非阻塞算法的设计和实现都非常困难,尤其是涉及多个状态的时候,不过它通常都能提供更高的伸缩性,JVM 中并发性能的提升都主要来自于对非阻塞算法的使用。


参考: