四十九、CAS原理

1、CAS 简介

CAS 的英文全称是 Compare-And-Swap，中文叫做“比较并交换”，它是一种思想、一种算法。

在多线程的情况下，各个代码的执行顺序是不能确定的，所以为了保证并发安全，可以使用互斥锁。而 CAS 的特点是避免使用互斥锁，当多个线程同时使用 CAS 更新同一个变量时，只有其中一个线程能够操作成功，而其他线程都会更新失败。不过和同步互斥锁不同的是，更新失败的线程并不会被阻塞，而是被告知这次由于竞争而导致的操作失败，但还可以再次尝试，从而就实现了无锁的线程安全。

2、CAS 的思路

在大多数处理器的指令中，都会实现 CAS 相关的指令，这一条指令就可以完成“比较并交换”的操作，也正是由于这是一条（而不是多条）CPU 指令，所以 CAS 相关的指令是具备原子性的，这个组合操作在执行期间不会被打断，这样就能保证并发安全。由于这个原子性是由 CPU 保证的，所以无需程序员来操心。

CAS 有三个操作数：内存值 V、预期值 A、要修改的值 B。CAS 最核心的思路就是，仅当预期值 A 和当前的内存值 V 相同时，才将内存值修改为 B。

对此展开描述一下：CAS 会提前假定当前内存值 V 应该等于值 A，而值 A 往往是之前读取到当时的内存值 V。在执行 CAS 时，如果发现当前的内存值 V 恰好是值 A 的话，那 CAS 就会把内存值 V 改成值 B，而值 B 往往是在拿到值 A 后，在值 A 的基础上经过计算而得到的。如果执行 CAS 时发现此时内存值 V 不等于值 A，则说明在刚才计算 B 的期间内，内存值已经被其他线程修改过了，那么本次 CAS 就不应该再修改了，可以避免多人同时修改导致出错。这就是 CAS 的主要思路和流程。

3、CAS 的语义

CAS 的等价语义的代码，如下所示：

/**
 * 描述：     模拟CAS操作，等价代码
 */
public class SimulatedCAS {
    private int value;
    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = value;
        if (oldValue == expectedValue) {
            value = newValue;
        }
        return oldValue;
    }
}

在这段代码中有一个 compareAndSwap 方法，在这个方法里有两个入参，第 1 个入参期望值 expectedValue，第 2 个入参是 newValue，它就是计算好的新值，我们希望把这个新的值去更新到变量上去。

compareAndSwap 方法是被 synchronized 修饰的，用同步方法为 CAS 的等价代码保证了原子性。

4、CAS的应用场景

4.1 并发容器

（1）案例一：ConcurrentHashMap
截取部分 putVal 方法的代码，如下所示：

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;
        }
    //以下部分省略
    ...
}

在第 10 行，有一个醒目的方法是 “casTabAt”，这个方法名就带有 “CAS”，可以猜测它一定是和 CAS 密不可分了，下面给出 casTabAt 方法的代码实现：

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

该方法里面只有一行代码，即调用变量 U 的 compareAndSwapObject 的方法，那么，这个变量 U 是什么类型的呢？U 的定义是：

private static final sun.misc.Unsafe U

可以看出，U 是 Unsafe 类型的，Unsafe 类包含 compareAndSwapInt、compareAndSwapLong、compareAndSwapObject 等和 CAS 密切相关的 native 层的方法，其底层正是利用 CPU 对 CAS 指令的支持实现的。

上面介绍的 casTabAt 方法，不仅被用在了 ConcurrentHashMap 的 putVal 方法中，还被用在了 merge、compute、computeIfAbsent、transfer 等重要的方法中，所以 ConcurrentHashMap 对于 CAS 的应用是比较广泛的。

（2）案例二：ConcurrentLinkedQueue
非阻塞并发队列 ConcurrentLinkedQueue 的 offer 方法里也有 CAS 的身影，offer 方法的代码如下所示：

public boolean offer(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);

    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {
            if (p.casNext(null, newNode)) {
                if (p != t) 
                    casTail(t, newNode); 
                return true;
            }
        }
        else if (p == q)
            p = (t != (t = tail)) ? t : head;
        else
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

可以看出，在 offer 方法中，有一个 for 循环，这是一个死循环，在第 8 行有一个与 CAS 相关的方法，是 casNext 方法，用于更新节点。那么如果执行 p 的 casNext 方法失败的话，casNext 会返回 false，那么显然代码会继续在 for 循环中进行下一次的尝试。所以在这里也可以看出 ConcurrentLinkedQueue 的 offer 方法使用到了 CAS。

4.2 数据库

在数据库中，也存在对乐观锁和 CAS 思想的应用。在更新数据时，可以利用 version 字段在数据库中实现乐观锁和 CAS 操作，而在获取和修改数据时都不需要加悲观锁。

具体思路如下：当获取完数据，并计算完毕，准备更新数据时，会检查现在的版本号与之前获取数据时的版本号是否一致，如果一致就说明在计算期间数据没有被更新过，可以直接更新本次数据；如果版本号不一致，则说明计算期间已经有其他线程修改过这个数据了，那就可以选择重新获取数据，重新计算，然后再次尝试更新数据。

假设取出数据的时候 version 版本为 1，相应的 SQL 语句如下所示：
UPDATE student
SET name = ‘小王’,version = 2
WHERE id = 10 AND version = 1;

这样一来就可以用 CAS 的思想去实现本次的更新操作，它会先去比较 version 是不是最开始获取到的 1，如果和初始值相同才去进行 name 字段的修改，同时也要把 version 的值加一。

4.3 原子类

在原子类中，例如 AtomicInteger的 getAndAdd 方法也使用了 CAS，该方法代码如下所示：

//AtomicInteger的 getAndAdd 方法
public final int getAndAdd(int delta) {    
    return unsafe.getAndAddInt(this, valueOffset, delta);
}

//Unsafe 的 getAndAddInt 方法
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    return var5;
}

compareAndSwapInt 方法的作用就是，判断如果现在原子类里 value 的值和之前获取到的 var5 相等的话，那么就把计算出来的 var5 + var4 给更新上去，所以说这行代码就实现了 CAS 的过程。

一旦 CAS 操作成功，就会退出这个 while 循环。如果操作失败就意味着在获取到 var5 之后，并且在 CAS 操作之前，value 的数值已经发生变化了，证明有其他线程修改过这个变量。

这样一来，就会再次执行循环体里面的代码，重新获取 var5 的值，也就是获取最新的原子变量的数值，并且再次利用 CAS 去尝试更新，直到更新成功为止，所以这是一个死循环。

Unsafe 的 getAndAddInt 方法是通过循环 + CAS 的方式来实现的，在此过程中，它会通过 compareAndSwapInt 方法来尝试更新 value 的值，如果更新失败就重新获取，然后再次尝试更新，直到更新成功。

5、CAS 有什么缺点？

CAS 是有很多优点的，比如可以避免加互斥锁，可以提高程序的运行效率，但是同样 CAS 也有非常明显的缺点。在使用 CAS 的时候应该同时考虑到它的优缺点，合理地进行技术选型。

5.1 ABA 问题

决定 CAS 是否进行 swap 的判断标准是“当前的值和预期的值是否一致”，如果一致，就认为在此期间这个数值没有发生过变动，这在大多数情况下是没有问题的。

但是在有的业务场景下，想确切知道从上一次看到这个值以来到现在，这个值是否发生过变化。例如，这个值假设从 A 变成了 B，再由 B 变回了 A，此时不仅认为它发生了变化，并且会认为它变化了两次。

在这种场景下，使用 CAS，就看不到这两次的变化，因为仅判断“当前的值和预期的值是否一致”就是不够的了，CAS 并不能检测出在此期间值是不是被修改过，它只能检查出现在的值和最初的值是不是一样，这样就会发生 ABA 问题。

那么如何解决这个问题呢？添加一个版本号就可以解决。

在变量值自身之外，再添加一个版本号，那么这个值的变化路径就从 A→B→A 变成了 1A→2B→3A，这样一来，就可以通过对比版本号来判断值是否变化过，这比直接去对比两个值是否一致要更靠谱，所以通过这样的思路就可以解决 ABA 的问题了。

在 atomic 包中提供了 AtomicStampedReference 这个类，它是专门用来解决 ABA 问题的，解决思路正是利用版本号，AtomicStampedReference 会维护一种类似 <Object,int> 的数据结构，其中的 int 就是用于计数的，也就是版本号，它可以对这个对象和 int 版本号同时进行原子更新，从而也就解决了 ABA 问题。

5.2 自旋时间过长

由于单次 CAS 不一定能执行成功，所以 CAS 往往是配合着循环来实现的，有的时候甚至是死循环，不停地进行重试，直到线程竞争不激烈的时候，才能修改成功。

可是如果应用场景本身就是高并发的场景，就有可能导致 CAS 一直都操作不成功，这样的话，循环时间就会越来越长。而且在此期间，CPU 资源也是一直在被消耗的，这会对性能产生很大的影响。所以这就要求要根据实际情况来选择是否使用 CAS，在高并发的场景下，通常 CAS 的效率是不高的。

5.3 范围不能灵活控制

通常去执行 CAS 的时候，是针对某一个，不能针对多个共享变量同时进行 CAS 操作，因为这多个变量之间是独立的，简单的把原子操作组合到一起，并不具备原子性。因此如果想对多个对象同时进行 CAS 操作并想保证线程安全的话，是比较困难的。

有一个解决方案，那就是利用一个新的类，来整合刚才这一组共享变量，这个新的类中的多个成员变量就是刚才的那多个共享变量，然后再利用 atomic 包中的 AtomicReference 来把这个新对象整体进行 CAS 操作，这样就可以保证线程安全。

相比之下，如果使用其他的线程安全技术，那么调整线程安全的范围就可能变得非常容易，比如用 synchronized 关键字时，如果想把更多的代码加锁，那么只需要把更多的代码放到同步代码块里面就可以了。