CAS算法

CAS（Compare And Swap）比较并交换，它是一种算法，体现的是乐观锁的思想，总是认为自己可以成功完成操作，在多个线程同时使用CAS操作一个变量时，只有一个会胜出并成功更新，其余均会失败，失败的线程不会被挂起，仅被告知失败，并且允许再次尝试。

三个重要参数：

V：当前内存中的值
A：旧的预期值
B：要更新的值

当且仅当 V == A 时，通过原子操作将 V 修改为 B，并返回 true，否则什么都不做，返回 false。

CAS算法必须和 volatile 一起使用，并且要在多核CPU下才可以实现。

使用CAS算法的类有JUC包下的AtomicInteger类，其getAndSet()就是调用Unsafe类的getAndAddInt()

AtomicInteger类的部分源码如下：

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); }
    }
    
    //线程都会直接读取value并且不缓存它，保证value在多线程之间的内存可见性
    private volatile int value;
    public final int get() {return value;}
    
    public final int getAndAdd(int delta) {    
        return unsafe.getAndAddInt(this, valueOffset, delta);
    }
}

Unsafe类的部分源码如下：

public final class Unsafe {
    
    private Unsafe() {}

    private static final Unsafe theUnsafe = new Unsafe();
    
    // 拿到调用它的那个Class的ClassLoader判断是否是SystemDomainLoader,如果不是则抛安全异常
    // 就是判断是否可以信任调用者并返回他实例
    @CallerSensitive
    public static Unsafe getUnsafe() {
        Class<?> caller = Reflection.getCallerClass();
        if (!VM.isSystemDomainLoader(caller.getClassLoader()))
            throw new SecurityException("Unsafe");
        return theUnsafe;
    }
    
    
   /**
     * Object obeject 指定要获取哪个对象中的属性
     * long valueOffset 指定该属性在内存中的偏移值
     * int i 加数
     * 知道 obeject 和 valueOffset 才能确定共享变量
     * 源码中的变量为var1 var2，不能闻其名知其义，所以我改了名字，方便阅读
     */
    public final int getAndAddInt(Object obeject, long valueOffset, int i) {
        int A;
        do {    
            // 获取当前内存中的值,即旧的预期值
            A = this.getIntVolatile(obeject,valueOffset);
            
            // 这里的obeject, valueOffset传递给底层去确定 V（当前内存中的值）
        } while (!compareAndSwapInt(obeject, valueOffset, A, A + i));
        
        return A;
    }
    
}

ABA问题

CAS算法的实现有一个前提：需要取出内存中某时刻的数据，然后在下一时刻进行比较和交换，在这个时间差内可能数据已经发生了改变，就会产生ABA问题。

ABA问题指第一个线程从内存的V位置取出A，这时第二个线程也从内存的V位置取出A，并将V位置的数据修改为B，接着又将V位置的数据修改为A，然后第一个线程操作成功。对于第一个线程来说，CAS操作是成功的，但是该过程中V位置的数据发生了变化，第一个线程感知不到，在某些应用场景下可能出现过程数据不一致的问题。

解决办法：

每次对共享变量进行修改操作时都会带上一个版本号，在预期的版本号和数据的版本号一致时就可以执行修改操作，并对版本号执行加1操作，否则执行失败。因为每次操作都会让版本号进行加1，所以不会出现ABA问题，版本号只能增加不能减少。

从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。

AtomicStampedReference类的部分源码如下：

public class AtomicStampedReference<V> {

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

    private volatile Pair<V> pair;

    /** 
     *  首先检查当前引用是否等于预期引用，
     *  并且当前标志是否等于预期标志
     *  如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。
     *  
     *  expectedReference：表示预期值
     *  newReference：表示要更新的值
     *  expectedStamp：表示预期的时间戳
     *  newStamp：表示要更新的时间戳
     */
    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)));
    }
    
    private boolean casPair(Pair<V> cmp, Pair<V> val) {
        return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
    }
}

CAS缺点

循环时间太长，消耗CPU资源；
只能保证一个共享变量原子操作；
会出现ABA问题；

CAS算法和ABA问题

CAS算法和ABA问题

CAS算法

ABA问题

CAS缺点