概述

CAS（Compare-and-Swap），即比较并替换，是一种实现并发算法时常用到的技术。

CAS需要有3个操作数：内存地址V，旧的预期值A，即将要更新的目标值B。CAS指令执行时，当且仅当内存地址V的值与预期值A相等时，将内存地址V的值修改为B，否则就什么都不做。整个比较并替换的操作是一个原子操作。

当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。

例子

假设要新建多个线程来对一个int变量进行自增操作。由于自增操作不具备原子性，所以为了保证并发下结果的正确，必须要采取一些措施来保证线程安全。其中一种方法是使用原子操作类AtomicInteger的getAndIncrement()方法来进行自增。

AtomicInteger#getAndIncrement

现在就来看看getAndIncrement()方法是怎么保证自增操作的原子性的。

1
2
3

public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);   //unsafe是一个Unsafe类型的变量
}

可以看到又调用了Unsafe类的getAndAddInt方法

Unsafe#getAndAddInt

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;
}

该方法的作用是：拿到内存位置的最新值v，使用CAS尝试修将内存位置的值修改为目标值v+delta，如果修改失败，则获取该内存位置的新值v，然后继续尝试，直至修改成功。

从而可以得知，AtomicInteger是利用CAS算法来保证自增操作的原子性。

Unsafe#compareAndSwapInt

/**
 * Atomically update Java variable to <tt>x</tt> if it is currently
 * holding <tt>expected</tt>.
 * @return <tt>true</tt> if successful
 */
public final native boolean compareAndSwapInt(Object o, long offset,
                                              int expected,
                                              int x);

可以看到compareAndSwapInt是一个本地方法，这个本地方法在openjdk中依次调用的c++代码为：unsafe.cpp，atomic.cpp和atomic_windows_x86.inline.hpp，最终调用的代码如下：

#define LOCK_IF_MP(mp) __asm cmp mp, 0  \  
                       __asm je L0      \  
                       __asm _emit 0xF0 \  
                       __asm L0:  
  
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)  
    cmpxchg dword ptr [edx], ecx  
  }  
}

这是一段C++内嵌汇编的代码。

Atomic::cmpxchg方法部分解析：

os::is_MP()是一个内联函数，用来判断当前系统是否为多处理器。如果是则返回1，否则返回0。
LOCK_IF_MP(mp)会根据mp的值来决定是否为cmpxchg指令添加lock前缀。如果mp是1则添加，否则不添加。
cmpxchg是汇编指令，作用是比较并交换操作数

CAS的缺点

循环时间长时开销很大

如果CAS在比较时失败的话，会重新获取内存中的值，再一次比较，直到尝试成功。所以如果CAS长时间一直不成功的话，会给CPU带来很大的开销。

针对这个问题的一个思路是引入退出机制，如果尝试次数超过一定限度就停止尝试并退出。当然，最好是避免在高并发的情况下使用CAS。

只能保证原子性

CAS只能保证变量的原子性，而只有原子性是不能保证线程安全的。所以CAS需要和volatile关键字配合才能保证线程安全。

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

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作。但是对多个共享变量操作时，循环CAS就无法保证操作的原子性。这时就只能用其他方法，例如锁来保证原子性。

ABA问题

如果在内存中初次读取到的值是A，并且在准备赋值的时候检查到它的值仍为A，但是如果在这段时间它的值曾经被修改为B，后来再改回A，那么CAS就会误认为它从来没有改变过，从而允许这次赋值。这个漏洞称为CAS操作中的ABA问题。

ABA问题会导致什么后果？

举个现实的例子。假如一位客户银行余额为1w，他提取了5k，因为某种意外，有两个线程（线程1和线程2）执行这个提取操作，线程1成功提取，余额为5k；这时候有人给这位客户汇款5k，所以有一个线程3执行了这个汇款过程，客户余额为1w；这时才执行到线程2，线程2发现余额还是1w，没有问题，所以又提取了5k。所以客户提取了5k，但实际上两个线程提取了1w，这就出现了问题。

怎么解决ABA问题？

引入版本号。内存中的值每修改一次，版本号加1。在进行CAS操作时，不仅比较内存中的值，也要比较版本号，只有两者都一致时，才会替换内存中的值。例如AtomicStampedReference类便是使用版本号来解决ABA问题的。

概述

例子