J.U.C并发框架之CAS

本篇将入门J.U.C并发框架CAS，会对一部分源码进行解析。

CAS

维基百科对CAS的定义：比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

CAS源码追踪

为了理解这个操作，不妨从一个原子变量开始解析，进入AtomicInteger类查看源码，这个类提供了很多方法，比如compareAndSet()：

1
2
3

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

又比如getAndSet()：

1
2
3

public final int getAndSet(int newValue) {
  return unsafe.getAndSetInt(this, valueOffset, newValue);
}

继续追踪getAndSetInt()，有：

public final int getAndSetInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var4));
    return var5;
}

可见，该原子类很多方法最终都和compareAndSwapInt()的实现有关，在sun.misc包的Unsafe类下这是一个native方法：

1	public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

在HotSpot源码中继续追踪，打开目录hotspot-327ea6f9647c/src/share/vm/prims下的unsafe.cpp文件，查找compareAndSwapInt方法的实现：

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

cmpxchg是一个CPU指令，这里将其视其为一个原子操作即可。

当然CAS包含一系列方法，比如CompareAndSwapLong()等，实现原理基本相同。

CAS操作流程

compareAndSwapInt的参数形式是这样的：compareAndSwapInt(Object var1, long var2, int var4, int var5)，参数简要说明如下：

var1：进行CAS操作的对象；
var2：对象内部当前值的内存地址偏移量；
var4：期望值；
var5：更新到的值；

在AtomicInteger中复合操作的方法基本上都依靠CAS实现，而compareAndSet更是直接对native方法compareAndSwapInt进行封装。为了说明CAS操作的流程，这里用getAndIncrement()举例。

首先列出Java源码：

1
2
3

public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}

追踪getAndAddInt()：

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    return var5;
}

getIntVolatile是一个native方法，读取值的同时也要保证内存可见性。

CAS操作流程大体如下：

调用方法，传入当前对象(this)、所持有的值的内存地址偏移量以及增加值“1”这三个变量；
读取所持有的值，读取时保证内存可见；
以第二步为循环体进行do-while循环，当持有的值和预期值(var5)不相同，则循环一直执行；
满足循环终止条件后，方法返回第二步读取到的值；

ABA问题

维基百科解释得很清楚：

ABA问题是无锁结构实现中常见的一种问题，可基本表述为：

进程P1读取了一个数值A

P1被挂起(时间片耗尽、中断等)，进程P2开始执行

P2修改数值A为数值B，然后又修改回A

P1被唤醒，比较后发现数值A没有变化，程序继续执行。

通常解决的方法是每次修改value的时候添加个时间戳，可以借助AtomicStampedReference这个原子引用类来完成，但是这个类比较“鸡肋”，因为通常ABA不是一个必须解决的问题，而且当遇到ABA问题使用传统互斥同步的方法更高效(见《深入理解Java虚拟机》 P396)。

小结

每个刚接触并发的新人，一开始都会被介绍一个多线程增加共享的counter值的程序，在线程不安全下运行该程序，得到的结果总是和预期值差一点点。一方面告诉我们写程序要考虑并发的安全，同时其实也表明，大多数情况下，多个线程彼此之间不总是处于引发线程不安全的竞争关系中，不然最后的结果也不会只是离预期“差一点点”(是否差一点点还是要根据具体案例)。如果程序员对不发生竞争这件事保持乐观，那么可能更倾向于使用乐观锁。在本篇中CAS实现了乐观锁(当然CAS也可以实现悲观锁)，这是通过底层CPU指令赋予compareAndSwapInt方法以原子性做到的。

参考

JAVA CAS原理深度分析：这一篇中关于CPU锁的介绍很通俗易懂。

Java Programming Tutorial
Java Native Interface (JNI)：这是一篇JNI入门，对以后本文相关内容的扩展解析有裨益。

Intel’s ‘cmpxchg’ instruction：一篇简介CPU指令cmpxchg的PDF。

J.U.C并发框架：Doug Lea的文章，描述了J.U.C并发框架的根源、设计、实现、用法及性能。