1 CAS(Compare And Swap) 概念和原理

CAS是Compare And Swap的缩写，中文含义是比较和交换。CAS定义了三个值：

V : 待更新的变量Var
E : 预期的旧值Expected Value
N : 新值New

执行过程的伪代码如下：

if(V==E){
  V=N;
}

也就是说只有在变量V的值等于期望的旧值时，才更新V为新值N。不然什么都不做。以此证明其他线程没有更改V的值。根据上面的伪代码来看，是不是会出现if通过了，但是在V=N的时候其他线程改了V呢？其实不会的，CAS的底层实现是依赖CPU的原子指令(cmpxchgl和lock)来实现的，也就是说比较和赋值操作是一个CPU级别的原子操作！那么在多线程操作同一个变量时，只会有一个线程操作成功，其他的都会失败，但是并不会阻塞其他线程，其他线程可以利用循环进行重试或者放弃修改。这是实现乐观锁的基础。

2 Java中的CAS

Java中提供了Unsafe类来提供CAS操作，目前有如下三个方法。

public final native boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);
public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);
public final native boolean compareAndSwapLong(Object o, long offset,long expected,long x);

参数和返回值解释：

参数o : 字段变量所属的对象。
参数offset : 变量相对于o在内存中的偏移位置。这个值是和class相关的，和具体对象无关。
参数expected : 期望的旧值。
参数x : 新值。当前面两个参数定位到的变量的值等于expected代表的旧值是，才更新。
返回值boolean : 更新成功返回true, 否则就是false。

这三个方法不会阻塞线程，然后调用方可以根据返回值决定是否重试或者放弃修改。

3 Java中依赖Unsafe的CAS实现的一些原子操作类

一个示例CASExample.java。

Java中依赖Unsafe的CAS实现的一些原子操作类位于java.util.concurrent.atomic包下。

4 CAS的三大问题

4.1 ABA问题

ABA指的是V的值原来是A，变成了B，后来又更新为了A。这时JDK1.5引入了一个AtomicStampedReference
来解决ABA的问题。原理是增加一个Pair<T>类型来持有引用和一个附加的标记stamp充当版本号。

private static class Pair<T> {
    final T reference;
    final int stamp;
    private Pair(T reference, int stamp) {
        this.reference = reference;
        this.stamp = stamp;
    }
    static <T> Pair<T> of(T reference, int stamp) {
        return new Pair<T>(reference, stamp);
    }
}

在执行cas时，同时检查这两个字段: 调用时newStamp为expectedStamp+1作为版本号,由于是每次都+1，所以每次更改Pair的reference都会增加stamp，就可以避免ABA的问题了。

public boolean compareAndSet(V   expectedReference,
                              V   newReference,
                              int expectedStamp,
                              int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
          casPair(current, Pair.of(newReference, newStamp)));
}