1 CAS是什么

CAS是Compare-And-Swap的缩写，即对比和替换，它在保证数据原子性的前提下尽可能的减少了锁的使用，很多编程语言或者系统实现上都大量的使用了CAS。

因为没有线程阻塞唤醒带来的性能消耗问题。这也是为什么CAS比synchronized性能高的原因！

1.1 JAVA中CAS的实现

JAVA中的CAS主要使用的是Unsafe类。Unsafe的CAS操作主要是基于硬件平台的汇编指令，目前的处理器基本都支持CAS，只不过不同的厂家的实现不一样罢了。

sun.misc.Unsafe类虽然提供了一系列直接操作内存对象的方法，但只是在jdk内部使用，JAVA官方不建议开发者直接调用Unsafe类；所以我们一般直接使用到的，都是java.util.concurrent.atomic包下的Atomic*类，比如AtomicBoolean、AtomicInteger等，其compareAndSet方法，也都是调用的Unsafe的CAS方法。

public final class Unsafe {
	...
	public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
	public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
	public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);
	...
}

value 表示需要操作的对象
valueOffset 表示对象(value)的地址的偏移量（通过Unsafe.objectFieldOffset(Field valueField)获取）
expect 表示更新时value的期待值
update 表示将要更新的值

具体过程为每次在执行CAS操作时，线程会根据valueOffset去内存中获取当前值去跟expect的值做对比如果一致则修改并返回true，如果不一致说明有别的线程也在修改此对象的值，则返回false。

Unsafe类中compareAndSwapInt的具体实现所对应的cpp代码为：

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

1.2 CAS和自旋的配合

很多文章都信誓旦旦的说CAS底层使用自旋，从而达到高效的无锁并发。这是将Atomic的CAS实现和Unsafe的CAS实现混淆的结果，JAVA的CAS追本溯源都在Unsafe的CAS方法中，它顾名思义，只有比较和替换，没有自旋。

但不可否认，当CAS和自旋搭配使用的时候，确实效果更佳，尤其是在并发做加减的时候，所以Unsafe类提供了一个将CAS和自旋搭配使用的自增方法。

public final int getAndSetInt(Object var1, long var2, int var4) {
    int var5;
    do {
        //getIntVolatile方法获取对象var1中offset=var2偏移地址对应的整型field的值,支持volatile load语义。
        //说人话就是取出var1内存中偏移量为var2位置对应的整型field的值
        var5 = this.getIntVolatile(var1, var2);
        //自旋操作，不停比较该值，如果CAS成功，则退出，否则一直循环。
    } while(!this.compareAndSwapInt(var1, var2, var5, var4));

    return var5;
}

相同原理的还有getAndSetLong/getAndSetObject/getAndAddLong/getAndAddInt等方法。

1.3 Java 8对CAS机制的优化——LongAdder

当并发操作一个AtomicInteger而不是使用synchronize时，我们确实可以享受到CAS无锁并发带来的高性能，但CAS就完美无缺么？肯定不是的，比如说大量的线程同时并发修改一个AtomicInteger，可能有很多线程会不停的自旋，进入一个无限重复的循环中。

这些线程不停地获取值，然后发起CAS操作，但是发现这个值被别人改过了，于是再次进入下一个循环，获取值，发起CAS操作又失败了，再次进入下一个循环。

在大量线程高并发更新AtomicInteger的时候，这种问题可能会比较明显，导致大量线程空循环，自旋转，性能和效率都不是特别好。

于是，Java 8推出了一个新的类，LongAdder，他尝试使用分段CAS以及自动分段迁移的方式来大幅度提升多线程高并发执行CAS操作的性能！

在LongAdder的底层实现中，首先有一个base值，刚开始多线程来不停的累加数值，都是对base进行累加的，比如刚开始累加成了base = 5。

接着如果发现并发更新的线程数量过多，就会开始施行分段CAS的机制，也就是内部会搞一个Cell数组，每个数组是一个数值分段。这时，让大量的线程分别去对不同Cell内部的value值进行CAS累加操作，这样就把CAS计算压力分散到了不同的Cell分段数值中。

如此操作可以大幅度的降低多线程并发更新同一个数值时出现的无限循环的问题，大幅度提升了多线程并发更新数值的性能和效率！

更重要的是他内部实现了自动分段迁移的机制，也就是如果某个Cell的value执行CAS失败了，那么就会自动去找另外一个Cell分段内的value值进行CAS操作。这样也解决了线程空旋转、自旋不停等待执行CAS操作的问题，让一个线程过来执行CAS时可以尽快的完成这个操作。

最后，如果你要从LongAdder中获取当前累加的总值，就会把base值和所有Cell分段数值加起来返回给你。

LongAdder顾名思义，只是一个自增器，只能用来做增长操作

2 CAS的ABA问题

CAS还存在一个更加严重的问题——ABA问题：

线程1准备用CAS修改变量值A，在此之前，其它线程将变量的值由A替换为B，又由B替换为A，然后线程1执行CAS时发现变量的值仍然为A，所以CAS成功。但实际上这时的现场已经和最初不同了。

有没有解决方案呢？有的，JAVA中ABA中解决方案有两种，我们依次介绍

2.1 AtomicStampedReference类

解决ABA最简单的方案就是给值加一个修改版本号，每次值变化，都会修改它版本号，CAS操作时都对比此版本号。

AtomicStampedReference就是这种思路在JAVA中的产物，它主要维护包含一个对象引用以及一个可以自动更新的整数”stamp”的pair对象来解决ABA问题。

其关键代码如下（省略无用代码）：

//关键代码
public class AtomicStampedReference<V> {
    private static class Pair<T> {
        final T reference;  //维护对象引用
        final int stamp;  //用于标志版本
        private Pair(T reference, int stamp) {
            this.reference = reference;
            this.stamp = stamp;
        }
        static <T> Pair<T> of(T reference, int stamp) {
            return new Pair<T>(reference, stamp);
        }
    }
    private volatile Pair<V> pair;
    ....
    /**
      * expectedReference ：更新之前的原始值
      * newReference : 将要更新的新值
      * expectedStamp : 期待更新的标志版本
      * newStamp : 将要更新的标志版本
      */
    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair; //获取当前pair
        return
            expectedReference == current.reference && //原始值等于当前pair的值引用，说明值未变化
            expectedStamp == current.stamp && // 原始标记版本等于当前pair的标记版本，说明标记未变化
            ((newReference == current.reference &&
              newStamp == current.stamp) || // 将要更新的值和标记都没有变化
             casPair(current, Pair.of(newReference, newStamp))); // cas 更新pair
    }
}

不需要过分在意源码，我们只要知道怎么用就好，demo如下：

public static void main(String[] args) {
        AtomicStampedReference<String> reference = new AtomicStampedReference<String>("aaa",1);
        reference.compareAndSet("aaa","bbb",reference.getStamp(),reference.getStamp()+1);
    }

2.2 AtomicMarkableReference类

AtomicMarkableReference可以理解为AtomicStampedReference的简化版，就是不关心修改过几次，仅仅关心是否修改过。因此变量mark是boolean类型，仅记录值是否有过修改。

关键代码如下

// Pair对象维护对象的引用和对象标记
private static class Pair<T> {
    final T reference;
    final boolean mark;// 通过标记的状态区分对象是否有更改

    private Pair(T reference, boolean mark) {
        this.reference = reference;
        this.mark = mark;
    }

    static <T> Pair<T> of(T reference, boolean mark) {
        return new Pair<T>(reference, mark);
    }
}
/**
 * @param expectedReference 期待的原始对象
 * @param newReference      将要更新的对象
 * @param expectedMark      期待原始对象的标记
 * @param newMark           将要更新对象的标记
 */
public boolean compareAndSet(V expectedReference,
                             V newReference,
                             boolean expectedMark,
                             boolean newMark) {
    Pair<V> current = pair;
    return
            expectedReference == current.reference && // 如果期待的原始对象与Pair的reference一样则返回true
                    expectedMark == current.mark && // 如果期待的原始对象的标记与Pair的mark一样则返回true
                    ((newReference == current.reference &&
                            newMark == current.mark) || // 如果要更新的对象和对象标记与Pair的refernce和mark一样的话直接返回true，否则执行CAS操作
                            casPair(current, Pair.of(newReference, newMark)));
}

不需要过分在意源码，我们只要知道怎么用就好，demo如下：

public class AtomicMarkableReferenceDemo {

    private static final Integer INIT_NUM = 10;

    private static final Integer TEM_NUM = 20;

    private static final Integer UPDATE_NUM = 100;

    private static final Boolean INITIAL_MARK = Boolean.FALSE;

    private static AtomicMarkableReference atomicMarkableReference = new AtomicMarkableReference(INIT_NUM, INITIAL_MARK);

    public static void main(String[] args) {
        new Thread(() -> {
            System.out.println(Thread.currentThread().getName() + " ： 初始值为：" + INIT_NUM + " , 标记为： " + INITIAL_MARK);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if (atomicMarkableReference.compareAndSet(INIT_NUM, UPDATE_NUM, atomicMarkableReference.isMarked(), Boolean.TRUE)) {
                System.out.println(Thread.currentThread().getName() + " ： 修改后的值为：" + atomicMarkableReference.getReference() + " , 标记为： " + atomicMarkableReference.isMarked());
            }else{
                System.out.println(Thread.currentThread().getName() +  " CAS返回false");
            }
        }, "线程A").start();

        new Thread(() -> {
            Thread.yield();
            System.out.println(Thread.currentThread().getName() + " ： 初始值为：" + atomicMarkableReference.getReference() + " , 标记为： " + INITIAL_MARK);
            atomicMarkableReference.compareAndSet(atomicMarkableReference.getReference(), TEM_NUM, atomicMarkableReference.isMarked(), Boolean.TRUE);
            System.out.println(Thread.currentThread().getName() + " ： 修改后的值为：" + atomicMarkableReference.getReference() + " , 标记为： " + atomicMarkableReference.isMarked());
        }, "线程B").start();
    }
}

输出结果

线程A ： 初始值为：10 , 标记为： false
线程B ： 初始值为：10 , 标记为： false
线程B ： 修改后的值为：20 , 标记为： true
线程A CAS返回false

由于线程B修改了对象，标记由false改为true，所以当上下文切换为线程A的时候，如果标记不一致，线程A执行CAS方法就会返回false。