CAS

1. 简介

compare and swap的缩写，中文翻译成比较并交换,实现并发算法时常用到的一种技术。它包含三个操作数--内存位置、预期原值及更新值。
执行CAS操作的时候，将内存位置的值与预期原值比较:
如果相匹配，那么处理器会自动将该位置值更新为新值
如果不匹配，处理器不做任何操作，多个线程同时执行CAS操作只有一个会成功。

2. 处理流程

CAS有3个操作数，位置内存值，旧的预期值A，要修改的更新值B。
当且仅当旧的预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做或重来当它重来重试的这种行为成为----自旋!!

3. 原理

CAS是JDK提供的非阻塞原子性操作，它通过硬件保证了比较-更新的原子性。CAS是一条CPU的原子指令(cmpxchg指令)，不会造成所谓的数据不一致问题，Unsafe提供的CAS方法(如compareAndSwapXXX)底层实现即为CPU指令cmpxchg。
执行cmpxchg指令的时候，会判断当前系统是否为多核系统，如果是就给总线加锁，只有一个线程会对总线加锁成功，加锁成功之后会执行cas操作，也就是说CAS的原子性实际上是CPU实现独占的,比起用synchronized重量级锁，这里的排他时间要短很多，所以在多线程情况下性能会比较好。

3.1 底层源码

AtomicInteger类中有Unsafe类，VALUE属性：
比如AtomicInteger调用compareAndSet(), 底层实际调用compareAndSetXX():

public final boolean compareAndSet(int expectedValue, int newValue) {
    return U.compareAndSetInt(this, VALUE, expectedValue, newValue);
}

底层调用本地方法compareAndSetInt()：

// 其中o表示当前AtomicInteger对象，offset为当前AtomicInteger对象的地址，
// expected为期望值，x需要修改的新值
public final native boolean compareAndSetInt(Object o, long offset,
                                                 int expected,
                                                 int x);

AtomicInteger类主要利用CAS(compare and swap)+volatile和native方法来保证原子操作，从而避免synchronized的高开销, 执行效率大为提升。
另外在getAndIncrement()底层也是调用的compareAndSetInt()：
其中compareAndSetInt()是调用unsafe.cpp中的UNSAFE_ENTRY()方法：

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
  oop p = JNIHandles::resolve(obj);
  if (p == NULL) {
    // 获取value在内存中的地址
    volatile jint* addr = (volatile jint*)index_oop_from_field_offset_long(p, offset);
    // 调用函数atomic_cmpxchg来进行交换，如果交换成功，就返回true, 反之返回false
    return RawAccess<>::atomic_cmpxchg(addr, e, x) == e;
  } else {
    assert_field_offset_sane(p, offset);
    return HeapAccess<>::atomic_cmpxchg_at(p, (ptrdiff_t)offset, e, x) == e;
  }
} UNSAFE_END

RawAccess<>::atomic_cmpxchg是原子比较并交换操作的模板方法，其具体实现与不同的硬件平台和数据类型有关。打开src/hotspot/os_cpu/linux_x86/atomic_linux_x86.hpp：

inline T Atomic::PlatformCmpxchg<4>::operator()(T volatile* dest,
                                                T compare_value,
                                                T exchange_value,
                                                atomic_memory_order /* order */) const {
    STATIC_ASSERT(4 == sizeof(T));
    __asm__ volatile ("lock cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest)
                    : "cc", "memory");
    return exchange_value;
}

执行汇编原子操作，比较并交换内存中的数值操作。CAS是靠硬件实现的从而在硬件层面提升效率，最底层还是交给硬件来保证原子性和可见性，实现方式是基于硬件平台的汇编指令，在intel的CPU中(X86机器上)，使用的是汇编指令cmpxchgl指令

3.2 Unsafe类

是CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地(native)方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。Unsafe类存在于sun.misc包中，其内部方法操作可以像C的指针一样直接操作内存，因为java中CAS操作的执行依赖于Unsafe类的方法。
Unsafe类中的所有方法都是native修饰的，也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应的任务。

3.3 VALUE

VALUE变量表示该变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的。同时变量value用volatile修饰，保证了多线程之间的内存可见性。

3.4 源码执行过程

假设线程A和线程B两个线程同时执行getAndAddInt()操作:

1. AtomicInteger里面的value原始值为3，即主内存中AtomicInteger的value为3，根据JMM模型，线程A和线程B各自持有一份值为3的value的副本分别到各自的工作内存。
2. 线程A通过getIntVolatile(var1, var2)拿到value值3，这时线程A被挂起。
3. 线程B也通过getIntVolatile(var1, var2)方法获取到value值3，此时刚好线程B没有被挂起并执行compareAndSwapInt()方法比较内存值也为3，成功修改内存值为4，线程B打完收工，一切OK。
4. 这时线程A恢复，执行compareAndSwapInt方法比较，发现自己手里的值数字3和主内存的值数字4不一致，说明该值已经被其它线程抢先一步修改过了，那A线程本次修改失败，只能重新读取重新来一遍了。
5. 线程A重新获取value值，因为变量value被volatile修饰，所以其它线程对它的修改，线程A总是能够看到，线程A继续执行compareAndSwapInt进行比较替换，直到成功。

4. 自旋锁

CAS是实现自旋锁的基础，CAS利用CPU指令保证了操作的原子性，以达到锁的效果，自旋是指尝试获取锁的线程不会立即阻塞，而是采用循环的方式去尝试获取锁，当线程发现锁被占用时，会不断循环判断锁的状态，直到获取。这样的好处是减少线程上下文切换的消耗，缺点是循环会消耗CPU。
在原子类AtomicInteger中调用getAndIncrement()底层就有相同的实现：

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

4.1 SpinLock类

SpinLock通过CAS进行获取锁：

public static void main(String[] args) throws InterruptedException {
    SpinLock lock = new SpinLock();
    for (int i = 0; i < 100; i++) {
        int finalI = i;
        // 底层调用lock和unlock方法
        String result = lock.<String>execute(() -> {
            System.out.println("线程" + finalI + "执行");
            try {
                Thread.sleep(300);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            return "success";
        });
    }
}

运行效果：

4.2 自旋锁和互斥锁区别

特性	自旋锁（SpinLock）	互斥锁（Mutex）
等待方式	忙等待（持续循环检查锁状态）	挂起线程（放弃CPU，等待唤醒）
上下文切换	无（避免切换开销）	有（挂起和唤醒线程的开销）
CPU消耗	高（自旋时持续占用CPU）	低（线程挂起不占用CPU）
适用场景	短时间锁竞争（临界区执行时间极短）	长时间锁竞争（临界区执行时间较长）

5. CAS缺点

5.1 CPU消耗高

如果CAS失败，会一直进行尝试。如果CAS长时间一直不成功，可能会给CPU带来很大的开销。

5.2 ABA问题

ABA问题是并发编程中使用CAS（Compare-and-Swap，比较并交换）操作时可能出现的一种经典问题，其核心是由于共享变量的值在两次检查期间发生了“先改变再恢复原值”的变化，导致CAS操作误判为变量未被修改，从而引发潜在的逻辑错误。

5.3 使用AtomicStampedReference

public static void main(String[] args) throws InterruptedException {
    AtomicStampedReference<Integer> atomicReference = new AtomicStampedReference<>(100, 1);
    new Thread(() -> {
        int stamp = atomicReference.getStamp();
        System.out.println(atomicReference.getReference() + "\t 当前版本号：" + stamp);
        atomicReference.compareAndSet(100, 101, 1, atomicReference.getStamp() + 1);
        atomicReference.compareAndSet(101, 100, 2, atomicReference.getStamp() + 1);
        System.out.println(atomicReference.getReference() + "\t 当前版本号：" + atomicReference.getStamp());
    }, "t1").start();

    new Thread(() -> {
        int stamp = atomicReference.getStamp();
        System.out.println(atomicReference.getReference() + "\t 当前版本号：" + stamp);
        try {
            // 模拟t1线程发生ABA事件
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        boolean flag = atomicReference.compareAndSet(100, 101, 2, stamp + 1);
        System.out.println("更新标识：" + flag + "\t 当前版本号" + atomicReference.getStamp());
    }, "t2").start();
}

运行结果：