Java中CAS学习记录

CAS在网上已经有数不清的文章，这里只是自己在学习过程中的一个记录，方便以后查阅。

一. 概述

Java中CAS全称Compare and Swap，也就是比较交换。在Java同步工具中，经常可以看到CAS的身影。在Doug Lea大神提供的J.U.C并发包中，可以说CAS是实现整个J.U.C包的基石。

在CAS方法中，有三个操作数，当前的内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相等时，将内存值V修改为B，否则什么都不做。

因为CAS会在进行修改的时候对当前内存值进行检测，所以当有其他线程修改了变量值的时候，这个时候当前线程的修改就会失败，以此来保证了“读-修改-写”操作的原子性。

三. CAS使用

先来看下面的代码：

package io.github.brightloong.lab.concurrent.cas;

import java.util.concurrent.TimeUnit;

/**
 * NoUseCAS class
 *
 * @author BrightLoong
 * @date 2018/6/10
 */
public class NoUseCAS {

    private volatile int value = 0;

    public void add() {
        value++;
    }

    public int getValue() {
        return value;
    }

    public static void main(String[] args) {
        NoUseCAS noUseCAS = new NoUseCAS();
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        TimeUnit.MILLISECONDS.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    noUseCAS.add();
                }
            }).start();
        }
        try {
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("最后结果：" + noUseCAS.getValue());
    }
}

输出结果每次都可能不一样，而不是每次都输出10。通过volatile虽然保证了变量线程之间的可见性，但是并不能保证“++”操作的原子性，因为“++”操作是先获取到值，然后再执行“+”操作，找到NoUseCAS.class文件，执行javap -c NoUseCAS.class 得到字节码，找到“add()”方法的字节码如下：

public void add();
    Code:
       0: aload_0
       1: dup
       2: getfield      #2                  // Field value:I
       5: iconst_1
       6: iadd
       7: putfield      #2                  // Field value:I
      10: return

可以看到getfield获取当前的值，iadd执行加操作，putfield赋值，如果这个时候线程A在执行完getfield后，拿到值为2，同时有另一个线程B将值修改为3，这个时候线程A继续执行操作的话最后会返回结果3，这就和期望的值不一样了。

如何解决

可以使用AtomicInteger来解决上面的问题，它提供了getAndIncrement()方法来替代“++”操作，并且保证了该操作的原子性，

代码片段：

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;

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

    //使用volatile修饰保证线程间的可见性。
    private volatile int value;
    
    //原子++操作，并调用unsafe.getAndAddInt
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

}

Unsafe.java中相关代码片段如下：

//使用了compareAndSwapInt()
public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }
//调用本地方法（native）
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

下面具体分析本地方法

三. CAS原理

在openjdk9中找到unsafe.cpp，其路径为：jdk9u/hotspot/src/share/vm/prims/unsafe.cpp

//定义compareAndSetInt为Unsafe_CompareAndSetInt
{CC "compareAndSetInt",   CC "(" OBJ "J""I""I"")Z",  FN_PTR(Unsafe_CompareAndSetInt)},

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
  oop p = JNIHandles::resolve(obj);
  //获取内存地址
  jint* addr = (jint *)index_oop_from_field_offset_long(p, offset);

  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
} UNSAFE_END

Atomic::cmpxchg在atomic.hpp中，文件路径为：jdk9u/hotspot/src/share/vm/runtime/atomic.hpp

inline unsigned Atomic::cmpxchg(unsigned int exchange_value,
                         volatile unsigned int* dest, unsigned int compare_value,
                         cmpxchg_memory_order order) {
  assert(sizeof(unsigned int) == sizeof(jint), "more work to do");
  return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest,
                                       (jint)compare_value, order);
}

使用的是内联函数（inline）,会根据当前处理器的类型调用对应的内联函数，以下是windows_x86的实现。文件路径为：jdk9u/hotspot/src/os_cpu/windows_x86/vm/atomic_windows_x86.hpp

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value, cmpxchg_memory_order order) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

• LOCK_IF_MP(MP):判断前系统是否为多核处理器如果是则为cmpxchg指令添加lock前缀。

• cmpxchg：使用cmpxchg指令

  intel手册对lock前缀的说明如下(参考：https://www.jianshu.com/p/fb6e91b013cc)：

• 确保后续指令执行的原子性。

  在Pentium及之前的处理器中，带有lock前缀的指令在执行期间会锁住总线，使得其它处理器暂时无法通过总线访问内存，很显然，这个开销很大。在新的处理器中，Intel使用缓存锁定来保证指令执行的原子性，缓存锁定将大大降低lock前缀指令的执行开销。

• 禁止该指令与前面和后面的读写指令重排序。

• 把写缓冲区的所有数据刷新到内存中。

CAS的ABA问题

CAS存在ABA的问题，如下图所示，线程A最开始获取的值A，到赋值前检查的时候依然是A，然后进行了赋值；但是线程A并不知道这期间有线程B将值更改为B，然后又有线程C将值改回A。

我们可以使用版本号来解决以上的问题，也就是上面的修改就会变成1A-1B-2A,就可以发现最开始是1A，但是比较的时候是2A，代表这期间被改动过。可以使用AtomicStampedReference解决ABA的问题，它就是使用版本号来标记变量来保证CAS的正确性。