Conmpare And Swap（比较并且交换)，乐观锁的一种实现方式

1.5引入CAS即Java原子类
java.util.concurrent.atomic
jdk所提供的原子类可以大致分为四种类型：

• 原子更新基本数据类型，AtomicLong，AtomicInteger，AtomicBoolean
• 原子更新数组类型，AtomicLongArray，AtomicIntegerArray
• 原子更新对象引用，AtomicReference
• 原子更新字段（基于反射），AtomicIntegerFieldUpdater

以AtomicInteger的compareAndSet为例
/CAS操作有三个操作数：内存值，预期值，更新值/

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
//valueOffset是value在内存中的偏移量
private static final long valueOffset;
private volatile int value;

Unsafe是Java中一个底层类，包含了很多基础的操作，比如数组操作、对象操作、内存操作、CAS操作、线程(park)操作、栅栏（Fence）操作，JUC包、一些三方框架都使用Unsafe类来保证并发安全。

Unsafe里的native方法参考

特点：1.循环（自旋）开销大；2.只能保证一个变量的原子性操作
3.ABA问题
指在CAS操作时，其他线程将变量值A改为了B，但是又被改回了A，等到本线程使用期望值A与当前变量进行比较时，发现变量A没有变，于是CAS就将A值进行了交换操作，但是实际上该值已经被其他线程改变过，这与乐观锁的设计思想不符合。

一般的解决思路：添加版本号，每次变量更新的时候把变量的版本号加1，那么A-B-A就会变成A1-B2-A3，只要变量被某一线程修改过，改变量对应的版本号就会发生递增变化，从而解决了ABA问题。

JDK的解决方法：在java.util.concurrent.atomic包中提供了AtomicStampedReference和AtomicMarkableReference

public class AtomicStampedReference<V> {
    //省略源码其余部分
    /* 构造函数
     * @param initialRef the initial reference 初始引用
     * @param initialStamp the initial stamp 相当于初始版本号
     */
    public AtomicStampedReference(V initialRef, int initialStamp) {
        pair = Pair.of(initialRef, initialStamp);
    }
    /*核心*/
    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            //当reference和stamp都相等时，才允许CAS操作
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }
}

AtomicMarkableReference是AtomicStampedReference的简化版，不关心修改过几次，仅仅关心是否修改过。因此变量mark是boolean类型，仅记录值是否有过修改。

    public AtomicMarkableReference(V initialRef, boolean initialMark) { pair = Pair.of(initialRef, initialMark);}

    public boolean compareAndSet(V       expectedReference,
                                 V       newReference,
                                 boolean expectedMark,
                                 boolean newMark) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedMark == current.mark &&
            ((newReference == current.reference &&
              newMark == current.mark) ||
             casPair(current, Pair.of(newReference, newMark)));
    }