Java并发之CAS原理剖析

CAS(Compare and Swap)，即比较并交换，是实现并发算法常用的一种技术。

CAS的思想很简单：三个参数，一个当前内存值V、旧的预期值A、即将更新的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。

问题

一个n++的问题。

public class Case {

    public volatile int n;

    public void add() {
        n++;
    }
}

n++其实是被拆分成了几个指令：

执行getfield拿到原始n；
执行iadd进行加1操作；
执行putfield写把累加后的值写回n；

通过volatile修饰的变量可以保证线程之间的可见性，但并不能保证这3个指令的原子执行，在多线程并发执行下，无法做到线程安全，得到正确的结果。

如何解决

在add方法加上synchronized修饰解决。

public class Case {

    public volatile int n;

    public synchronized void add() {
        n++;
    }
}

但是synchronized属于重量级锁，很多时候会引起性能问题，像synchronized这种独占锁属于悲观锁，它是在假设一定会发生冲突的，那么加锁恰到好处，除此之外，还有乐观锁，乐观锁的含义就是假设没有发生冲突，那么我正好可以进行某项操作，如果要是发生冲突呢，那我就重试直到成功，乐观锁最常见的就是CAS。

再来看一段代码：

public int a = 1;
public boolean compareAndSwapInt(int b) {
    if (a == 1) {
        a = b;
        return true;
    }
    return false;
}

以上代码在并发下执行，结果是无法符合预期的，无法确认a的最终值。

同样可以在compareAndSwapInt方法加锁同步，变成一个原子操作，同一时刻只有一个线程能够修改变量a。

除了低性能的加锁方案，我们可以使用JDK自带的CAS方案，在CAS中，比较和替换是一组原子操作，不会被外部打断，且在性能上更占优势。

下面以AutomicInteger的实现为例，分析一下CAS是如何实现的。

public class AtomicInteger extends Number implements java.io.Serializable {
    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    public final int get() {return value;}
}

Unsafe，是CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地(native)方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。
变量valueOffset，表示该变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的。
变量value用volatile修饰，保证了多线程之间的内存可见性。

看看AutomicInteger如何实现并发下的累加操作：

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

假设线程A和线程B同时执行getAndAdd操作：

AutomicInteger里面的value原始值为3，即主内存中AutomicInteger的value为3，根据Java内存模型，线程A和线程B各自持有一份value的副本，值为3。
线程A通过getIntVolatile(var1, var2)拿到value值3，这时线程A被挂起。
线程B也通过getIntVolatile(var1, var2)方法获取到value值3，运气好，线程B没有被挂起，并执行compareAndSwapInt方法比较内存值也为3，成功修改内存值为2。
这时线程A恢复，执行compareAndSwapInt方法比较，发现自己手里的值(3)和内存的值(2)不一致，说明该值已经被其它线程提前修改过了，那只能重新来一遍了。
重新获取value值，因为变量value被volatile修饰，所以其它线程对它的修改，线程A总是能够看到，线程A继续执行compareAndSwapInt进行比较替换，直到成功。

整个过程中，利用CAS保证了对于value的修改的并发安全，继续深入看看Unsafe类中的compareAndSwapInt方法实现。

1	public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

Unsafe类中的compareAndSwapInt，是一个本地方法，该方法的实现位于unsafe.cpp中。

compareAndSwapInt(var1, var2, var5, var5 + var4)其实换成compareAndSwapInt(obj, offset, expect, update)比较清楚，意思就是如果obj内的value和expect相等，就证明没有其他线程改变过这个变量，那么就更新它为update，如果这一步的CAS没有成功，那就采用自旋的方式继续进行CAS操作。

CAS的问题

ABA问题

CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。这就是CAS的ABA问题。常见的解决思路是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A-B-A就会变成1A-2B-3A。目前在JDK的automic包里提供了一个类AutomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

循环时间长开销大

如果CAS不成功，则会原地自旋，如果长时间自旋会给CPU带来非常大的执行开销。

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

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。从Java 1.5开始JDK提供了AutomicReference类来保证引用对象之间的原子性，你可以把多个变量放到一个对象里来进行CAS操作。

总结

synchronized属于重量级锁，悲观锁，可以修饰代码块，修饰方法，修饰静态方法。
CAS是非阻塞的，轻量级锁，乐观锁。
悲观锁机制存在的问题：

在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题。
一个线程持有锁会导致其他所有需要此锁的线程挂起。
如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置，引起性能风险。

CAS在竞争激烈的时候会长时间自旋，引起性能问题。

问题

如何解决

CAS的问题

ABA问题

循环时间长开销大

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

总结

参考资料