深入理解java并发CAS机制

在并发的情况下，Java主要靠synchronized和lock来保证同步，已解决多线程下的线程不安全问题，锁虽然功能强大，但也并非完美的。

CAS原理(悲观锁乐观锁)

也许大家已经听说过，锁分两种，一个叫悲观锁，一种称之为乐观锁。Synchronized就是悲观锁的一种，也称之为独占锁，加了synchronized关键字的代码基本上就只能以单线程的形式去执行了，它会导致其他需要该资源的线程挂起，直到前面的线程执行完毕释放所资源。
乐观锁是一种更高效的机制，它的原理就是每次不加锁去执行某项操作，如果发生冲突则失败并重试，直到成功为止，其实本质上不算锁，所以很多地方也称之为自旋，乐观锁用到的主要机制就是CAS。
CAS，Compare and Swap即比较并替换，设计并发算法时常用到的一种技术，Doug lea大神在java同步器中大量使用了CAS技术，鬼斧神工的实现了多线程执行的安全性。

CAS实例分析

CAS的思想很简单：三个参数，一个当前内存值V、旧的预期值A、即将更新的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。
java.util.concurrent.atomic包下的原子操作类都是基于CAS实现的,下面以AtomicInteger的实现为例，分析一下CAS是如何实现的

public class AtomicInteger extends Number implements java.io.Serializable {

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

    private volatile int value;

1.变量unsafe，是CAS的核心类，通过Unsafe类直接访问底层系统，基于Unsafe类可以直接操作特定内存的数据。
2.变量valueOffset，表示该变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的。
3.变量value用volatile修饰，保证了多线程之间的内存可见性。

AtomicInteger的累加操作：

public final int getAndAdd(int delta) { 
    return unsafe.getAndAddInt(this, valueOffset, delta);
}
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;
}

假设现在线程A和线程B同时执行getAndAdd操作：

1.AtomicInteger里面的value原始值为3，即主内存中AtomicInteger的value为3，根据Java内存模型，线程A和线程B各自持有一份value的副本，值为3。
2.线程A通过getIntVolatile(var1, var2)方法获取到value值3，线程切换，线程A挂起。
3.线程B通过getIntVolatile(var1, var2)方法获取到value值3，并利用compareAndSwapInt方法比较内存值也为3，比较成功，修改内存值为2，线程切换，线程B挂起。
4.线程A恢复，利用compareAndSwapInt方法比较，发现手里的值3和内存值2不一致，此时value正在被另外一个线程修改，线程A不能修改value值。
5.线程的compareAndSwapInt无法实现，循环判断，重新获取value值，因为value是volatile变量，所以线程对它的修改，线程A总是能够看到。线程A继续利用compareAndSwapInt进行比较并替换，直到compareAndSwapInt修改成功返回true。

整个过程中，利用CAS保证了对于value的修改的线程安全性。

Unsafe类

JNI: Java Native Interface为JAVA本地调用，允许java调用其他语言。

CAS通过Unsafe类调用JNI的代码实现的,而compareAndSwapInt就是借助C来调用CPU底层指令实现的。下面是sun.misc.Unsafe类的compareAndSwapInt()方法的源代码：

public final native boolean compareAndSwapInt(Object o, 
                                              long offset,
                                              int expected,
                                              int x);

可以看到这是个native(本地方法)调用，该方法的实现位于unsafe.cpp中。

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  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(x, addr, e)，
这个方法在Linux的x86的源代码的片段：

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

在intel x86处理器的源代码的片段：

// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line
// so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  // 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
  }
}

源代码中，程序会根据当前处理器的类型来决定是否为cmpxchg指令添加lock前缀。如果是多处理器，就为cmpxchg指令加上lock前缀（lock cmpxchg）。反之，就省略lock前缀（单处理器自身会维护单处理器内的顺序一致性，不需要lock前缀提供的内存屏障效果）。

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

1.确保对内存的读-改-写操作原子执行。
2.禁止该指令与之前和之后的读和写指令重排序。
3.把写缓冲区中的所有数据刷新到内存中。

多核处理器：在Pentium及之前的处理器中，带有lock前缀的指令在执行期间会锁住总线，使得其它处理器暂时无法通过总线访问内存，很显然，这个开销很大。在新的处理器中，Intel使用缓存锁定来保证指令执行的原子性，缓存锁定将大大降低lock前缀指令的执行开销。
单核处理器：单核处理器这个指令在执行过程中，为什么不用加lock呢？因为在单处理器系统（UniProcessor）中，能够在单条指令中完成的操作都可以认为是" 原子操作"，因为中断只能发生于指令之间。

优缺点

优点：

1.CAS摒弃了锁，在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题，CAS极大地提高了性能。
2.一个线程持有锁会导致其它所有需要此锁的线程挂起，使用CAS线程不存在阻塞的情况。

缺点：

ABA问题。因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A,从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。

循环时间长开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。

只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。

深入理解java并发CAS机制

CAS原理(悲观锁乐观锁)

CAS实例分析

Unsafe类

优缺点

推荐阅读更多精彩内容