无锁编程CAS[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

前言

CAS（Compare And Swap，比较并交换），要说CAS是无锁编程，多多少少有些“标题党”的感觉。因为CAS根据其设计思想，可以划分为乐观锁。不同于synchronized关键字，synchronized实现的是悲观锁。我第一次听说乐观锁和悲观锁的时候有点震惊：一把锁我还得知道它乐不乐观？乐不乐观？一把锁难道还有情绪？
实际上乐观锁和悲观锁是基于线程并发竞争的角度来说的，悲观锁就是假设每次操作都悲观的认为会发生线程竞争，不加锁就会导致程序结果错误；乐观锁就假设每次操作都乐观的认为不会发生线程竞争，所以不需要上锁，因此CAS被称为无锁编程，实际上是一种乐观锁的体现。

Atomic

先看两个常见的例子

public class AtomicDemo {

    private static int count = 0;

    public static void main(String[] args) throws InterruptedException {
        Thread thread1 = new Thread(() -> {
            for (int i = 0; i < 100000; i++) {
                count++;
            }
        });

        Thread thread2 = new Thread(() -> {
            for (int i = 0; i < 100000; i++) {
                count++;
            }
        });

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();

        System.out.println(count);
    }
}

两个线程累加同一个共享变量，线程不安全，输出的count小于等于200000。相信大家已经非常清楚为什么线程不安全了，所以想要解决这个问题也很简单，加锁就行。
但是这里如果要用无锁编程CAS来解决的话该怎么解决呢？
只需要简单的修改下代码

public class AtomicDemo {

    // AtomicInteger变量
    private static AtomicInteger count = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        Thread thread1 = new Thread(() -> {
            for (int i = 0; i < 100000; i++) {
                count.getAndIncrement();  // 等价于线程安全的count++操作
            }
        });

        Thread thread2 = new Thread(() -> {
            for (int i = 0; i < 100000; i++) {
                count.getAndIncrement();   // 等价于线程安全的count++操作
            }
        });

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();

        System.out.println(count.get());
    }
}

输出结果

无论运行多少遍，结果都是200000。也就是说在没有加锁的情况下，写出了线程安全的count++操作。相比大家已经看到了，实现的关键就是AtomicInteger#getAndIncrement()方法。所以我们直接看下getAndIncrement()的源码。
代码位置：java.util.concurrent.atomic.AtomicInteger

/**
 * Atomically increments by one the current value.
 * 以原子方式将当前值增加一
 */
public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}

由于该方法调用了unsafe.getAndAddInt(...)方法，继续往下追踪
代码位置：sun.misc.Unsafe

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

可以该实现主要调用了this.compareAndSwapInt(...)方法，该方法就是便是CAS（Compare And Swap，比较并交换）。既然是比较和交换，那我们应该明确两点：比较什么、交换什么？
CAS操作涉及到三个变量（V、E、N），V表示要更新的变量（工作内存中该变量的值）、E表示期望值（主内存中该变量的值）、N表示新值。
CAS实现原理
首先判断变量当前值（V）是否等于期望值（E），不等于则说明在当前线程修改这个变量，同步回主内存之前，有别的线程已经修改过这个变量并且同步回了主内存。所以当前线程不能把值同步回主内存，而是重新从主内存中读取该值，重复这整个操作，直到当前值（V）等于期望值（E），才将新值同步回主内存。再次看看CAS实现的源码

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
    	// var5就是期望值
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

// JVM保证该方法获取的就是变量的最新值
public native int getIntVolatile(Object var1, long var2);

// JVM保证该方法的CAS操作是原子操作
// var1是变量所处类的实例
// var2是变量的偏移量，和var1一起可以获取变量的值
// var4是期望值
// var5是新值
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

整个过程描述得更通俗一点就是：
1、线程A从主内存中读入变量count作为值V；
2、线程A读取count的最新值，作为期望值E
3、线程A把值（V）和期望（E）比较是否相等，相等就把新值（N）写回主内存，不相等就回到操作1
第三步是原子操作，比较V和E就是为了保证变量count没有被其他线程修改过。

以上就是CAS无锁编程的实现原理。

CAS缺陷

CAS并不是像降龙十八掌那样横扫一切的存在，它也有自己的缺陷。具体体现在以下三点：

自旋的实现方式让所有线程都处于高频运行，争抢CPU的状态，如果操作长时间不成功，会带来很大的CPU消耗
仅针对单个变量的操作，不能用于多个变量来实现原子操作
会存在ABA问题

ABA问题是指主内存中该变量的值从A变成B，再变成A的这种情况。
回头看上文描述的三个步骤。假设第一步线程A从主内存中读入的count=100，此时线程B把变量count改成了101，线程C又把变量count的值改成了100。此时线程A执行第二个步骤，读取count最新值count为100，作为期望值。虽然数值上没什么问题，但是此100已经非彼100了，这就是ABA问题，对线程A来说，无法感知数据的变化。如果业务上完全不在意ABA的影响，才可以用CAS。