Java并发编程-CAS

　　，学习了并发编程中的volatile，最后取了网上流传很广的一张图来结尾，从图中可以看出除了volatile变量的读写，还有一个叫做CAS的东西，所以这篇文章再来学习CAS。

1、  并发编程三要素-原子性、可见性、有序性

　　在讨论CAS前，我想先讨论一下并发编程的三要素，这个应该可以帮助理解CAS的作用等。其实上一篇提到的Java内存模型就是围绕着在并发过程中如何处理原子性、可见性和有序性这3个特征来建立的，所以我理解Java编程实现如果满足了这3个特性，就是线程安全的，可以支持并发访问。

原子性：指的是一个操作不能再继续拆分，要么一次操作完成，要么就是不执行。在Java中，为了保证原子性，提供了两个高级的字节码指令（monitorenter和monitorexit），这个就是关键字synchronized，可以看。我理解其实还有一种操作也是可以满足原子性的，就是CAS。

可见性：指的是一个变量在被一个线程更改后，其他的线程能立即看到最新的值。

有序性：指的是程序的执行按照代码的先后顺序执行。对于可见性和有序性，Java提供了关键字volatile，volatile禁止指令重排，保证了有序性，同时volatile可以保证变量的读写及时从缓存中刷新到主存，也就保证了可见性，可以看。除此以外，synchronized是可见性和有序性另外一种实现，同步方法和同步代码块保证一个变量在同一时间只能有一个线程访问，这就是一种先后顺序，而对于可见性保证，只能有一个线程操作变量，那么其他线程只能在前一个线程操作完成后才可以看到变量最新的值。

我们可以发现synchronized一次性满足了3个特性，那么我们是不是可以大胆的认为CAS+volatile组合在一起也可以满足3个特性。         

2、  CAS介绍

　　CAS全称compare-and-swap，是计算机科学中一种实现多线程原子操作的指令，它比较内存中当前存在的值和外部给定的期望值，只有两者相等时，才将这个内存值修改为新的给定值。CAS操作包含三个操作数，需要读写的内存位置（V）、拟比较的预期原值（A）和拟写入的新值（B），如果V的值和A的值匹配，则将V的值更新为B，否则不做任何操作。多线程尝试使用CAS更新同一变量时，只有一个线程可以操作成功，其他的线程都会失败，失败的线程不会被挂起，只是在此次竞争中被告知失败，下次可以继续尝试CAS操作的。

3、  CAS背后实现

　　JUC下的atomic类都是通过CAS来实现的，下面就以AtomicInteger为例来阐述CAS的实现。直接看方法compareAndSet，调用了unsafe类的compareAndSwapInt方法：

public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

　　其中四个参数分别表示对象、对象的地址（定位到V）、预期值（A）、修改值（B）。

　　再看unsafe类的方法，这是一个native方法，所以只能继续放看openJDK的代码。

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

　　在unsafe.cpp找到方法CompareAndSwapInt，可以依次看到变量obj、offset、e和x，其中addr就是当前内存位置指针，最终再调用Atomic类的cmpxchg方法。

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.hpp，从变量命名上基本可以见名知义。

static jint     cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value);

　　和volatile类型，CAS也是依赖不同的CPU会有不同的实现，在src/os_cpu目录下可以看到不同的实现，以atomic_linux_x86.inline.hpp为例，是这么实现的：

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

　　底层是通过指令cmpxchgl来实现，如果程序是多核环境下，还会先在cmpxchgl前生成lock指令前缀，反之如果是在单核环境下就不需要生成lock指令前缀。为什么多核要生成lock指令前缀？因为CAS是一个原子操作，原子操作隐射到计算机的实现，多核CPU的时候，如果这个操作给到了多个CPU，就破坏了原子性，所以多核环境肯定得先加一个lock指令，不管这个它是以总线锁还是以缓存锁来实现的，单核就不存在这样的问题了。

4、  CAS存在的问题

4.1  ABA问题

　　因为CAS需要在操作值的时候，检查值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加1，那么A→B→A就会变成1A→2B→3A。

　　关于ABA问题的举例，参考链接里面有篇文章其实说的很清楚了，不过我认为他这个例子好像描述的有点问题，应该是线程1希望A替换为B，执行操作CAS（A,B），此时线程2做了个操作，将A→B变成了A→C，A的版本已经发生了变化，再执行线程1时会认为A还是那个A，链表变成B→C，如果有B.next=null，C这个节点就丢失了。

　　从Java 1.5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

4.2  循环时间长开销大

　　一般CAS操作都是在不停的自旋，这个操作本身就有可能会失败的，如果一直不停的失败，则会给CPU带来非常大的开销。

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

　　看了CAS的实现就知道这个只能针对一个共享变量，如果是多个共享变量就只能使用synchronized。除此之外，可以考虑使用AtomicReference来包装多个变量，通过这种方式来处理多个共享变量的情况。

参考资料：