cas

what is cas?

cas是compare and swap的缩写，比较并交换的意思。让cpu比较共享内存中某个值是否和预期的值相同，相同则更新为新值，整个过程是cpu中完成的。
java是在sun.misc.Unsafe中实现cas操作的。我们知道java的跨平台性限制了java不能和操作系统耦合，也导致java无法直接访问操作系统底层api，sun.misc.Unsafe.java中并没有直接实现cas的操作，而是通过jni本地调用c++来操作cpu指令来实现。

过程分析

Unsafe部分代码：

    /**
     * 原子自增方法
     * val1为对象
     * var2为属性相对对象首地址偏移量
     * var4为增量
     */
   public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        //自旋，直到compareAndSwapInt返回true
        do {
            //获取新值
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
        return var5;
    }

    public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
    /**
     * cas int
     * val1为对象引用
     * var2为值相对对象内存地址偏移量
     * var4为期望值
     * var5为更新值
     */
    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

    public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

compareAndSwapInt

是java本地接口调用c++语言再调用cpu指令来实现cas
1.Unsafe.java-将对象引用、值在对象中的偏移量、期望的值和欲更新的新值传递给Unsafe.cpp。
2.Unsafe.cpp-接受从Unsafe.java传递过来的对象引用、偏移量、期望的值和欲更新的新值，根据对象引用和偏移量计算出值的地址，然后将值的地址、期望的值、欲更新的新值传递给CPU,Unsafe.cpp;更新成功则返回true给Unsafe.java，没有更新则返回false。
3.CPU-接受从Unsafe.cpp传递过来的地址、期望的值和欲更新的新值，执行指令cmpxchg，比较地址中的值是否和期望的值一样，一样则将值更新为新的值，不一样则不做任何操作,将操作结果返回给Unsafe.cpp。

getAndAddInt

是java方法，如果一次更新失败，会循环处理，也称自旋重新用最新值调用cas直到成功为止。

cpu怎么保证cas的原子性

这个不是很了解，大部分处理器都实现了CAS的原子性，对于多核处理器在运行到CAS指令的时候会标记一个lock，当处理器运行到lock这个标记时，其他处理器就处于等待状态，单核处理器按步骤进行不会影响。另外一种保证原子性的处理器是通过保证在同一时间内当前处理器访问的共享内存地址不被其他处理器访问，新的方式提高了效率。

cas缺点

ABA问题

描述：当一个线程在对共享变量进行操作时，读取到的值为A，如果在这段期间曾经被改成B，然后又改回A，那CAS操作就会误认为它从来没有被修改过。
危害：略
解决方法：java并发包中提供了一个带有标记的原子引用类AtomicStampedReference，它可以通过控制变量值的版本来保证CAS的正确性，相当于给主内存的‘“变量的值”加了个版本标记。

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)));
    }
//将变量值包装成Pair<V>对象，
private boolean casPair(Pair<V> cmp, Pair<V> val) {
        return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
    }

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

从AtomicStampedReference源码可以大致看出思路，将真实变量的值加上版本标记封装成Pair，用以比对，相当于每次操作都搭上了版本标记。

自旋时间长开销大

如果CAS操作失败，就需要循环进行CAS操作(循环同时将期望值更新为最新的)，如果长时间都不成功的话，那么会造成CPU极大的开销。
解决方法：限制自旋次数，防止进入死循环。

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

CAS的原子操作只能针对一个共享变量。
解决方法：如果需要对多个共享变量进行操作，可以使用加锁方式(悲观锁)保证原子性，或者可以把多个共享变量合并成一个共享变量进行CAS操作。

cas应用

原子类利用cas的原子性进行原子操作封装；
利用cas的原子性和乐观锁思想高效解决线程并发安全性问题，例如ConcurrentHashMap、ReentrantLock等；

附：

Unsafe中基本都是调用native方法，这个native方法又是如何实现的，那么就需要去JVM里面找对应的实现(hotspot目录，发现 \src\share\vm\prims\unsafe.cpp，这个就是对应jvm相关的c++实现类了)