CAS and Lock-Free in Java

在Java中的原子类中频繁的使用CAS策略来保证数据更新的安全性，它是一种Lock-Free机制，这篇文章将会讲解CAS原理，以及它在Java中的应用。

Lock-Free

如果一个方法是 Lock-Free 的, 它保证线程无限次调用这个方法都能够在有限步内完成.

相比于传统的基于 Mutex 锁机制, Lock-Free 有下面的优势:

• Lock-Free 的速度更快
• 线程之间不会相互影响, 没有死锁
• 不受异步信号影响, 可重入
• 不会发生线程优先级反转

在通常使用 Mutex 互斥锁的场景, 有的线程抢占了锁, 其他线程则会被阻塞, 当获得锁的进程挂掉之后, 整个程序就 block 住了. 但在 Lock-Free 的程序中, 单个线程挂掉, 也不会影响其他线程, 因为线程之间不会相互影响.

但是, Lock-Free 也有不少缺陷:

• 只能利用有限的原子操作, 例如 CAS (操作的位数有限), 编码实现复杂
• 竞争会加剧, 优先级不好控制
• 测试时需要考虑各种软硬件环境, 很难做到尽善尽美

再引入一个 Wait-Free 概念:

假如一个方法是 Wait-Free 的, 那么它保证了每一次调用都可以在有限的步骤内结束.

一般来说: 阻塞 > Lock-Free > Wait-Free

CAS原语

CAS (compare and swap) 是 CPU 硬件同步原语(primitive), CAS(V, A, B) 操作可以用下面的代码来示意:

1
2
3
4
5
6
7
8

template <class T>
bool CAS(T* addr, T expect_val, T val) {
    if (*addr == expect_val) {
        *addr = val;
        return true;
    }
    return false;
}

从 80486 开始, 所有的 Intel 处理器上, 通过一条汇编指令 CMPXCHG 即可实现 CAS 操作. CAS 的价值在于它是一个原子操作, 不会被 CPU中断或者其他方式打断, 因为在硬件层实现, 所以开销极小.

CAS 并不是一项新技术, 它的使用可以追溯到 70 年代, 早在 80 年代就有很多经典书籍中提到使用 CAS 来实现并行编程, 如 USC 大牛 Kai HWang 的 “Computer Architecture and Parallel Processing”.

GCC 4.1+ 开始支持 CAS 的原子操作:

1
2

bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval)
type __sync_val_compare_and_swap (type *ptr, type oldval, type newval)

通常将 CAS 用于同步的方式是从地址 V 读取值 A, 执行多步计算来获得新值 B, 然后使用 CAS 将 V 的值从 A 改为 B, 如果 V 处的值尚未同时更改, 则 CAS 操作成功.

CAS中的ABA问题

ABA 问题描述:

• 切换到线程 T1, 获取内存 V 的值 A
• 切换到线程 T2, 获取内存 V 的值 A, 修改成 B, 然后再修改成 A
• 切换到线程 T1, 获取内存 V 的值还是 A, 继续执行

coolshell 上有篇文章给出了一个生动的例子(From 维基百科):

你拿着一个装满钱的手提箱在飞机场，此时过来了一个火辣性感的美女，然后她很暖昧地挑逗着你，并趁你不注意的时候，把用一个一模一样的手提箱和你那装满钱的箱子调了个包，然后就离开了，你看到你的手提箱还在那，于是就提着手提箱去赶飞机去了.

更具有参考意义的是Hazard Pointer Wiki上提到的一个 Lock-Free 堆栈的例子:

• 当前栈元素 [A, B, C], 栈顶 head 指向 A
• 线程 T1 执行 pop() 准备 CAS(&head, B, A)
• 线程 T2 抢占, pop A, pop B, 然后 push A
• 线程 T1 恢复, CAS(&head, B, A) 成功, 则此时 head 指向一个被 pop 的元素 B

CAS机制还存在其他问题：

• 循环时间长开销大:

  自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。

• 只能保证一个共享变量的原子操作:

  当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。

CAS在Java中的应用

• 在Java中所有原子类都采用了CAS机制，并且在jdk1.5之后提供了AtomicStampedReference来解决上述提到的ABA问题；
• AQS，非阻塞数据结构和原子变量类（java.util.concurrent.atomic包中的类），这些concurrent包中的基础类都是使用CAS机制来实现的，而concurrent包中的高层类又是依赖于这些基础类来实现的。从整体来看，concurrent包的实现示意图如下：