Java中的CAS操作和实现原理

1.什么是CAS?

CAS:Compare and Swap, 翻译成比较并交换。

看到这个定义，可以说是没有任何意义的一句话，但是确实最能概括CAS操作过程的一句话。

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。 如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值 。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该 位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前 值。）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。”

以下这段JAVA代码，基本上反映了CAS操作的过程。但是请注意，真实的CAS操作是由CPU完成的，CPU会确保这个操作的原子性，CAS远非JAVA代码能实现的功能（下面我们会看到CAS的汇编代码）。

	/**
	* 假设这段代码是原子性的，那么CAS其实就是这样一个过程
	*/
	public boolean compareAndSwap(int v,int a,int b) {
		if (v == a) {
			v = b;
			return true;
		}else {
			return false;
		}
	}

通常将 CAS 用于同步的方式是从地址 V 读取值 A，执行多步计算来获得新 值 B，然后使用 CAS 将 V 的值从 A 改为 B。如果 V 处的值尚未同时更改，则 CAS 操作成功。

这段话的意思是，CAS操作可以防止内存*享变量出现脏读脏写问题，多核的CPU在多线程的情况下经常出现的问题，通常我们采用锁来避免这个问题，但是CAS操作避免了多线程的竞争锁，上下文切换和进程调度。

类似于 CAS 的指令允许算法执行读-修改-写操作，而无需害怕其他线程同时 修改变量，因为如果其他线程修改变量，那么 CAS 会检测它（并失败），算法 可以对该操作重新计算。

2.JAVA中的CAS操作实现原理

CAS通过调用JNI的代码实现的。JNI:Java Native Interface为JAVA本地调用，允许java调用其他语言。

以Unsafe类的compareAndSwapInt()方法为例来说，compareAndSwapInt就是借助C语言和汇编代码来实现的。
下面从分析比较常用的CPU（intel x86）来解释CAS的实现原理。
下面是JDK中sun.misc.Unsafe类的compareAndSwapInt()方法的源代码：

// native方法，是没有其Java代码实现的，而是需要依靠JDK和JVM的实现
public final native boolean compareAndSwapInt(Object o, long offset,
                                              int expected,
                                              int x);

可以看到这是个本地方法。这个本地方法在openjdk中依次调用的c++代码为：unsafe.cpp，atomic.cpp和atomicwindowsx86.inline.hpp。这个本地方法的最终实现在openjdk的如下位置：openjdk-7-fcs-src-b147-27jun2011\openjdk\hotspot\src\oscpu\windowsx86\vm\ atomicwindowsx86.inline.hpp（对应于windows操作系统，X86指令集）。下面是对应于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 // 如果是多核处理器就会在这行指令前加Lock标记
  }
}

os::is_MP() 会返回当前JVM运行所在机器是否为多核CPU，当然返回1代表true，0代表false

然后是一段内嵌汇编，C/C++支持内嵌汇编，大家知道这个特性就好，我来通俗易懂的解释一下这段汇编的大体意思。

  __asm {
    mov edx, dest             # 取Atomic::cmpxchg方法的参数dest内存地址存入寄存器edx
    mov ecx, exchange_value   # 取Atomic::cmpxchg方法的参数exchange_value内存地址存入寄存器ecx
    mov eax, compare_value    # 取Atomic::cmpxchg方法的参数compare_value内存地存入寄存器eax
    LOCK_IF_MP(mp)            # 如果是多核处理器，就在下一行汇编代码前加上lock前缀
    cmpxchg dword ptr [edx], ecx # 比较ecx和eax的中内存地址的中存的变量值，如果相等就写入edx内存地址中，否则不
  }

x86汇编指令cmpxchg本身保证了原子性，其实就是cpu的CAS操作的实现，那么问题来了，为什么保证了原子性还需要在多核处理器中加上lock前缀呢？

答案是：多核处理器中不能保证可见性，lock前缀可以保证这行汇编中所有值的可见性，这个问题的原因是多核CPU中缓存导致的（x86中罪魁祸首是store buffer的存在）。
这样通过lock前缀保障多核处理器的可见性，然后通过cmpxchg指令完成CPU上原子性的CAS操作，完美解决问题！
多说一句，这只是x86中的实现方式，对于其他平台，还是有不同的方式实现，这点希望读者一定要搞清楚。
这段汇编代码看不懂也没关系，但其大意是使用CPU的锁机制，确保了整个CAS操作的原子性。关于CPU中的锁机制和CPU的原子操作 ——CPU中的原子操作。

3.concurrent包中CAS的应用

由于java的CAS同时具有 volatile 读和volatile写的内存语义，因此Java线程之间的通信现在有了下面四种方式：
1、A线程写volatile变量，随后B线程读这个volatile变量。
2、A线程写volatile变量，随后B线程用CAS更新这个volatile变量。
3、A线程用CAS更新一个volatile变量，随后B线程用CAS更新这个volatile变量。
4、A线程用CAS更新一个volatile变量，随后B线程读这个volatile变量。

注：volatile 关键字保证了变量的可见性，根据JAVA内存模型，每一个线程都有自己的栈内存，不同线程的栈内存里的变量有可能因为栈内的操作而不同，而 CPU又是直接操作栈中的数据并保存在自己的缓存中，所以多核CPU就出现了很大的问题，而volatile修饰的变量，保证了CPU各个核心不会从栈内存中和 缓存中读数据，而是直接从堆内存中读数据，而且写操作会直接写回堆内存中，从而保证了多线程间共享变量的可见性和局部顺序性（但不保证原子性），关于volatile——Java并发编程：volatile关键字解析

Java的CAS操作可以实现现代CPU上硬件级别的原子指令（不是依靠JVM或者操作系统的锁机制），而同时volatile关键字又保证了线程间共享变量的可见性和指令的顺序性，因此凭借这两种手段，就可以实现不依靠操作系统实现的锁机制来保证并发时共享变量的一致性。

如果我们仔细分析concurrent包的源代码实现，会发现一个通用化的实现模式：
首先，声明共享变量为volatile；
然后，使用CAS的原子条件更新来实现线程之间的同步；
同时，配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。