CAS算法

CAS 是什么

• CAS 的全称 Compare-And-Swap，它是一条 CPU 并发语句。
• 它的功能是判断内存某一个位置的值是否为预期，如果是则更改这个值，这个过程就是原子的。
• CAS 并发原体现在 JAVA 语言中就是 sun.misc.Unsafe 类中的各个方法。调用 UnSafe 类中的 CAS 方法，JVM 会帮我们实现出 CAS 汇编指令。这是一种完全依赖硬件的功能，通过它实现了原子操作。由于 CAS 是一种系统源语，源语属于操作系统用语范畴，是由若干条指令组成，用于完成某一个功能的过程，并且原语的执行必须是连续的，在执行的过程中不允许被中断，也就是说 CAS 是一条原子指令，不会造成所谓的数据不一致的问题。

CAS实现例子，以AtomicInteger为例

// AtomicInteger初始化过程
AtomicInteger atomicInteger = new AtomicInteger(666);

public AtomicInteger(int initialValue) {
        value = initialValue;
}

private volatile int value;

// AtomicInteger执行getAndIncrement();
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1); 
       //this:当前对象,valueOffset:value的内存地址
    }

    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5; //期望值
        do {
            var5 = this.getIntVolatile(var1, var2); 
//获取主内存中的value值(因为value为volatile，所以变化是实时可见的)
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
// compareAndSwapInt里会重新再取一次主内存的值，跟var5我们传入的期望值相比较，
// 如果此时期望值跟我们主内存的值相等时(也就是值没有被修改过)才会退出循环，否则重新获取

        return var5;
    }

CAS 的缺点？

• 循环时间长开销很大
  如果 CAS 失败，会一直尝试，如果 CAS 长时间一直不成功，可能会给 CPU 带来很大的开销（比如线程数很多，每次比较都是失败，就会一直循环），所以希望是线程数比较小的场景。
• 只能保证一个共享变量的原子操作
  对于多个共享变量操作时，循环 CAS 就无法保证操作的原子性。
• 引出 ABA 问题

ABA 问题(原子类 AtomicInteger 的 ABA 问题谈一谈？原子更新引用知道吗？)

• 出现原因:
  CAS 判断的条件是 expect期望值跟当前值相等时，就交换
  假如两个线程同时获取一个值，一个线程T1将A值改为B值然后再改回A值，另一个线程T2执行的比较慢，
  再取的时候T1线程已经执行完了，查询到的还是A值，满足CAS 所以会交换，但其实已经发生了两次交换
• 实例代码[ABAProblem.class]( AtomicReference为原子变量引用）

        User user = new User().setName("hcq").setAge(24);
        AtomicReference<User> atomicReference = new AtomicReference<>();
        //首先开一个线程来把这个值修改两次
        threadPool.submit(() -> {
            boolean firstCAS = atomicReference.compareAndSet(null, user);
            System.out.println(Thread.currentThread().getName() + "，第一次修改" + firstCAS + "，变量数据" + atomicReference.get());
            boolean secondCAS = atomicReference.compareAndSet(user, null);
            System.out.println(Thread.currentThread().getName() +"，第二次修改" + secondCAS + "，变量数据" + atomicReference.get());

        });
        //休眠2秒，保证前面的执行完成
        Thread.sleep(2000);
        boolean threeCAS = atomicReference.compareAndSet(null, user);
        System.out.println(Thread.currentThread().getName() +"，第三次修改" + threeCAS + "，变量数据" + atomicReference.get());

• 执行结果

pool-1-thread-1，第一次修改true，变量数据User(name=hcq, age=24)
pool-1-thread-1，第二次修改true，变量数据null
main，第三次修改true，变量数据User(name=hcq, age=24)

由输出结果可见，thread-1已经将atomicReference改了两次，但是对main线程来说，他最后的值还是null，对于他来说是没有任何改变的。

• ABA问题解决方案[ABASolution.class]（原子时间戳变量）

AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(1, 1);
//这个类的CAS方法是带时间戳判定的。
 public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }