java并发09-细说CAS

CAS 全称是 compare and swap，是一种用于在多线程环境下实现同步功能的机制。CAS 操作包含三个操作数 -- 内存地址V、旧的预期值A、要更新的值B，当且仅当内存地址V值等于旧的预期值A时才会将内存V的值修改为B，否则什么都不干。CAS是整个JUC体系最核心、最基础的理论。

在 Java 中，Java 并没有直接实现 CAS，CAS 相关的实现是通过 C++ 内联汇编的形式实现的。Java 代码需通过 JNI 才能调用。关于实现上的细节，后文将作分析。

一、CAS实现原理

1.1 示例

我们先来看以下代码：

public class Test {
    public int i = 0;

    public void increase() {
        ++i;
    }
    public static void main(String[] args) {
        final Test test = new Test();
        for(int i=0;i<10;i++){
            new Thread(){
                public void run() {
                    for(int j=0;j<10000;j++) {
                        test.increase();
                    }
                };
            }.start();
        }
        //后台默认两个线程：一个是main线程，一个是gc线程
        while(Thread.activeCount()>2) {
            Thread.yield();
        }
        System.out.println(test.i);
    }
}

很容易看出来，这个代码是线程不安全的。实际上运行结果也总是小于10000。

那该怎么办呢？解决的策略一般都是给这个increase方法加个锁，如下：

public synchronized void increase() {
        ++inc;
}

加了 synchronized 之后，就最多只能有一个线程能够进入这个 increment() 方法了。这样，就不会出现线程不安全了（可参考细说synchronized）。然而，一个简简单单的自增操作，就加了 synchronized 进行同步，好像有点大材小用的感觉，加了 synchronized 关键词之后，当有很多线程去竞争 increment 这个方法的时候，拿不到锁的方法是会被阻塞在方法外面的，最后再来唤醒他们，而阻塞/唤醒这些操作，是非常消耗时间的。

那有没有其他方法来代替 synchronized 对方法的加锁，并且保证 increment() 方法是线程安全呢？如果我采用下面这种方式，能否保证 increment 是线程安全的呢？步骤如下：

线程从内存中读取 i 的值，假如此时 i 的值为 0，我们把这个值称为 k 吧，即此时 k = 0。
令 j = k + 1。
用 k 的值与内存中i的值相比，如果相等，这意味着没有其他线程修改过 i 的值，我们就把 j（此时为1）的值写入内存；如果不相等（意味着i的值被其他线程修改过），我们就不把j的值写入内存，而是重新跳回步骤 1，继续这三个操作。

public static void increment() {
    do{
        int k = i;
        int j = k + 1;
    }while (!compareAndSwap(k, j))
}

这里可能有人会说，第三步的 compareAndSet 这个操作不仅要读取内存，还干了比较、写入内存等操作，这一步本身就是线程不安全的啊？

如果你能想到这个，说明你是真的有去思考、模拟这个过程，不过我想要告诉你的是，这个 compareAndSet 操作，他其实只对应操作系统的一条硬件操作指令，尽管看似有很多操作在里面，但操作系统能够保证他是原子执行的。我们可以用以下代码模拟这个过程。

public class Test {

    public int i = 0;

    public void increase() {
        int k;
        int j;
        do{
            k = i;
            j = k + 1;
        }while (!compareAndSet(k, j));
    }
    //通过加锁模拟操作系统的一条硬件操作指令
    public synchronized boolean compareAndSet(int k, int j){
        if (i == k){
            i = j;
            return true;
        }else {
            return false;
        }
    }
    public static void main(String[] args) {
        final Test test = new Test();
        for(int i=0;i<10;i++){
            new Thread(){
                public void run() {
                    for(int j=0;j<10000;j++) {
                        test.increase();
                    }
                };
            }.start();
        }
        //后台默认两个线程：一个是main线程，一个是gc线程
        while(Thread.activeCount()>2) {
            Thread.yield();
        }
        System.out.println(test.i);
    }
}

运行以上代码，得到i的最终运算结果总为100000，因此，我们可以看到CAS这种写法是线程安全的。

1.2 原理总结

CAS中有三个核心参数：

需要读写的内存地址V。
线程上次从内存中读取V的值存放在A中，每个线程私有。
拟写入内存的新值B

上面说的比较抽象，看下面的这幅图比较容易理解。

如上图中，主存中保存V值，线程中要使用V值要先从主存中读取V值到线程的工作内存A中，然后计算后变成B值，最后再把B值写回到内存V值中。多个线程共用V值都是如此操作。CAS的核心是在将B值写入到V之前要比较A值和V值是否相同，如果不相同证明此时V值已经被其他线程改变，重新将V值赋给A，并重新计算得到B，如果相同，则将B值赋给V。

二、Java中的CAS

JUC下的atomic类都是通过CAS来实现的，下面就以AtomicInteger为例来阐述CAS的实现。直接看方法compareAndSet，调用了unsafe类的compareAndSwapInt方法，其四个参数分别表示：AtomicInteger对象、AtomicInteger对象的地址（定位到V）、预期值（A）、修改值（B）。

   /**
     * Atomically sets the value to the given updated value
     * if the current value {@code ==} the expected value.
     * 如果当前值等于预期值，则以原子方式将该值设置为给定的更新值
     *
     * @param expect the expected value 预期的原值A
     * @param update the new value 修改值B
     * @return {@code true} if successful. False return indicates that
     * the actual value was not equal to the expected value.
     */
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

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

在看unsafe的compareAndSwapInt方法，这个方法是一个native方法。其四个参数分别表示：AtomicInteger对象、AtomicInteger对象的地址（定位到V）、预期值（A）、修改值（B）。

在unsafe.cpp找到方法CompareAndSwapInt，可以依次看到变量obj、offset、e和x，其中addr就是当前内存位置指针，最终再调用Atomic类的cmpxchg方法。

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.hpp，从变量命名上基本可以见名知义

static jint cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value);

CAS依赖不同的CPU会有不同的实现，在src/os_cpu目录下可以看到不同的实现，以atomic_linux_x86.inline.hpp为例，是这么实现的：

inline jint  Atomic::cmpxchg(jint exchange_value, volatile jint* dest, jint  compare_value) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

底层是通过指令cmpxchgl来实现，如果程序是多核环境下，还会先在cmpxchgl前生成lock指令前缀，反之如果是在单核环境下就不需要生成lock指令前缀。为什么多核要生成lock指令前缀？因为CAS是一个原子操作，原子操作隐射到计算机的实现，多核CPU的时候，如果这个操作给到了多个CPU，就破坏了原子性，所以多核环境肯定得先加一个lock指令，不管这个它是以总线锁还是以缓存锁来实现的，单核就不存在这样的问题了。

因此我们可以看到CAS并不是真的无锁。

三、CAS存在的问题

3.1 循环时间太长

一般CAS操作都是在不停的自旋，这个操作本身就有可能会失败的。如果线程太密集，就会一直不停的失败，则会给CPU带来非常大的开销。

3.2 ABA问题

因为CAS需要在操作值的时候，检查值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。这种问题就是常说的ABA问题

为了解决这个 ABA 的问题，我们可以引入版本控制。例如在变量前面追加上版本号，每次变量更新的时候把版本号加1，那么A→B→A就会变成1A→2B→3A。

从Java 1.5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

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

看了CAS的实现就知道这个只能针对一个共享变量，如果是多个共享变量就只能使用synchronized。除此之外，可以考虑使用AtomicReference来包装多个变量，通过这种方式来处理多个共享变量的情况。

四、Java8 对 CAS 的优化

由于采用这种 CAS 机制是没有对方法进行加锁的，所以，所有的线程都可以进入 increment() 这个方法，假如进入这个方法的线程太多，就会出现一个问题：每次有线程要执行第三个步骤的时候，i 的值老是被修改了，所以线程又到回到第一步继续重头再来。

而这就会导致一个问题：由于线程太密集了，太多人想要修改 i 的值了，进而大部分人都会修改不成功，白白着在那里循环消耗资源。

为了解决这个问题，Java8 引入了一个 cell[] 数组，它的工作机制是这样的：假如有 5 个线程要对 i 进行自增操作，由于 5 个线程的话，不是很多，起冲突的几率较小，那就让他们按照以往正常的那样，采用 CAS 来自增吧。

但是，如果有 100 个线程要对 i 进行自增操作的话，这个时候，冲突就会大大增加，系统就会把这些线程分配到不同的 cell 数组元素去，假如 cell[10] 有 10 个元素吧，且元素的初始化值为 0，那么系统就会把 100 个线程分成 10 组，每一组线程对 cell 数组其中的一个元素做自增操作，这样到最后，cell 数组 10 个元素的值都为 10，系统在把这 10 个元素的值进行汇总，进而得到 100，二这，就等价于 100 个线程对 i 进行了 100 次自增操作。

当然，我这里只是举个例子来说明 Java8 对 CAS 优化的大致原理，具体的大家有兴趣可以去看源码，或者去搜索对应的文章哦

参考资料

https://zhuanlan.zhihu.com/p/61924478

https://www.cnblogs.com/iou123lg/p/9314826.html