Java CAS详解

发表于 更新于 分类于
介绍CAS实现原理

CAS介绍

CAS(Compare and swap)是并发编程中经常用到的一项技术。大体上讲，CAS算法会先使用期望值比较变量的实际值，如果相同，就使用目标值替换变量的值。如果不相同，就会重新读取期望值再次进行对比和替换。

CAS主要是为了解决共享资源被加锁后，线程从阻塞状态切换回运行态比较耗时的问题，CAS是在不阻塞线程的情况下达到资源互斥的目的。但是如果共享资源竞争比较激烈就不适合使用CAS了，CAS会导致很多线程一直在重试访问共享资源，造成CPU资源的浪费。另外，如果共享资源的操作比较耗时，也就不适合使用CAS，这种场景使用阻塞的资源锁会更合适。

CAS源码分析

以AtomicInteger.getAndIncrement为例进行源码分析，下面代码来自openJdk8源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class AtomicInteger extends Number implements java.io.Serializable {
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            //获取value变量地址
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }
    ......
    private volatile int value; //volatile类型的变量
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }
    ......
}

AtomicInteger.getAndIncrement通过Unsafe.getAndAddInt方法实现：

1
2
3
4
5
6
7
8
9
10
11
/** Unsafe.java **/
    //native方法，通过jni来调用
    public final native boolean compareAndSwapInt(Object o, long offset,int expected, int x);

    public final int getAndAddInt(Object o, long offset, int delta) {
        int v;
        do {
            v = getIntVolatile(o, offset);
        } while (!compareAndSwapInt(o, offset, v, v + delta));
        return v;
    }

getAndAddInt函数中，首先获取到期望值v，v + delta是目标值。然后进入compareAndSwapInt函数，compareAndSwapInt会首先对比实际值与期望值是否相同，如果相同就替换并返回true，while循环退出。如果不相同，compareAndSwapInt就返回false，继续执行while循环读取期望值，然后再次进行对比替换的步骤。

compareAndSwapInt是native函数，源码在hotspot的unsafe.cpp文件中，在现在的系统中对比替换操作都是通过硬件机制来实现。

1
2
3
4
5
6
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

Atomic::cmpxchg通过内嵌汇编语言来实现，在不同的硬件上有不同的实现。下面代码是windows x86平台的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
/** [hotspot]\src\os_cpu\windows_x86\vm\atomic_windows_x86.inline.hpp **/
inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest   //变量地址放入数据寄存器
    mov ecx, exchange_value  //目标值放入计数寄存器
    mov eax, compare_value  //期望值放入累加器寄存器
    LOCK_IF_MP(mp)   //根据当前cpu是否是多核进行加锁
    cmpxchg dword ptr [edx], ecx
  }
}

代码中cmpxchg汇编指令的含义是对比累加器(al/ax/eax/rax)和[edx]中的值（[edx]表示变量地址，本质上就是一个指针），如果值相同就把ecx寄存器的值放入[edx]中，否则就会把[edx]指向的变量值加载到累加器中。

备注：AtomicInteger和Unsafe代码来之openJdk8：https://hg.openjdk.org/jdk8/jdk8/jdk。unsafe.cpp代码在openjdk8 hotspot源码中：https://hg.openjdk.org/jdk8/jdk8/hotspot

ABA问题

CAS会有ABA的问题，AtomicInteger对于getAndIncrement这种只进行加运算的操作不会存在ABA问题。但如果还有减运算就会存在ABA问题。java也提供了AtomicStampedReference类来解决ABA问题。

参考文章

Compare and Swap
CMPXCHG — Compare and Exchange
从汇编底层全面解析 CAS 的来龙去脉
LongAdder解析
AQS详解（面试）
并发编程的灵魂：CAS机制详解
SynchronousQueue实现原理