2019.2.2 *
更新CAS对应的x86汇编指令的解释，对底层实现又理解了一部分

全文简单概括

CAS（Compare And Swap）比较并替换，实现并发算法时常用到的一种技术。在Java中，主要在Atomic包，调用Unsafe类相关方法体现。

涉及三个值：内存中真正存的值（可能被其他线程改变）、逻辑上的原值、（当前线程）要写入的新值。通过循环检查内存中的值是不是原来的值，以此来判断是不是正有其他线程在改变它。判断成功立即写入新值，这一步是原子的。

存在ABA问题，即内存中虽然还是逻辑上原来的值，但是已经被变成B过了。

这个问题JDK1.5已经通过AtomicStampedReference类解决，将对象追加一个版本号stamp，这样每次改变过都是一个“全新的值”

正文

下文主要是链接文章的学习、修改与填充，加入了自己的看法，结合其他资料，拓展了其中不了解的点

Compare And Swap

比较并替换，实现并发算法时常用到的一种技术

涉及三个值：当前内存值V、逻辑上的旧值A、即将更新的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。

并发下的累加问题

public class Case{
    public volatile int n;
    public void add(){
        n++;
    }
}

通过 javac Case.java编译后javap -verbose Case

分析其中add()字节码指令：

  public void add();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=3, locals=1, args_size=1
         0: aload_0
         1: dup
         2: getfield   # *1* 拿到原始的n
         5: iconst_1
         6: iadd       # *2* n＋1
         7: putfield   # *3* 累加后的n写回
        10: return

字节码解释

开头字母大多指明了为哪种数据类型服务
a-reference，d-double，f-float，c-char，b-byte，s-short，l-lomg，i-int
aload_0: 从局部变量表根据索引拿一个值，0处始终是this。即拿到this
dup: 在操作数堆栈上创建顶部引用的额外副本，并将其添加到操作数堆栈的顶部
iconst_1: 将刚刚拿到的int型数据压入操作数栈，索引是1

JDK自带的原子操作

在java.util.concurrent.atomic包下有对基本数据包装类和数组等的原子操作

AtomicInteger.getAndAdd

如AtomicInteger通过CAS策略解决了并发下的累加问题。只摘取相关的部分，OpenJDK8：

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

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 o 指定类型
     * long offset 被加数的内存偏移值
     * int delta 加数
     */
    public final int getAndAddInt(Object o, long offset, int delta) {
        int v;
        do {
            //*保证缓存一致性同时从给定偏移量处的对象o
            v = getIntVolatile(o, offset);
        } while (!compareAndSwapInt(o, offset, v, v + delta));
        //*不断地重新获取内存中的值，直至成功CAS
        return v;
    }
    
}

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

1547195494009.png

意思是先想办法拿到内存地址，再通过Atomic::cmpxchg(x, addr, e)实现比较交换。e是原内存值，x为新值。

这个函数在WindowsX86下实现如下：*

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
    int mp = os::isMP(); #判断是否是多处理器
    _asm {
        mov edx, dest  #变量内存位置放edx
        mov ecx, exchange_value  #要更新的值放ecx
        mov eax, compare_value #原内存值放eax
        LOCK_IF_MP(mp) #决定是否Lock
        #这句是真正的CAS操作
        cmpxchg dword ptr [edx], ecx
        # dword ptr 将 [edx] 强制类型转换成双字
        # cmpxchg 将 eax 里 内存原值 与（转换后的）对象值 比较
        # 如果相等，就是没别的线程在改变这个对象，那么这个线程就可以改了，将ecx值更新到这个对象。
    }
}

如果是多处理器，LOCK_IF_MP(mp)为cmpxchg指令添加lock前缀。反之，就省略lock前缀。（单处理器会不需要lock前缀提供的内存屏障效果）

Lock前缀

intel手册对lock前缀的说明如下：

确保后续指令执行的原子性。
在Pentium及之前的处理器中，带有lock前缀的指令在执行期间会锁住总线，使得其它处理器暂时无法通过总线访问内存，很显然，这个开销很大。在新的处理器中，Intel使用缓存锁定来保证指令执行的原子性，缓存锁定将大大降低lock前缀指令的执行开销。
禁止该指令与前面和后面的读写指令重排序。
把写缓冲区的所有数据刷新到内存中。

上面的第2点和第3点所具有的内存屏障效果，保证了CAS同时具有volatile读和volatile写的内存语义。

用CAS处理并发存在的问题

参考：https://www.jianshu.com/p/42989f93105d

ABA问题*

因为CAS的关键是操作值的时候检查值有没有变化。如果一个值原来是A，变成了B，又变回了A，那么可以通过CAS检查，但实际却有线程在改变它。

解决方案

从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。主要是通过让对象多了stamp版本号，所以 ABA 变为了 1A-2B-3A

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;

    /** 首先检查当前引用是否等于预期引用，
     * 并且当前标志是否等于预期标志
     * 如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。
     */
    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);
    }
}

不断检查的开销大的问题

Unsafe中的do-while不断CAS检查可能长时间不成功。

谢谢观看，如果有用麻烦点个喜欢，对我是莫大的鼓励。

CAS从源码到底层实现