CAS

CAS——compare and swap,比较并交换。是一种乐观锁的实现方式。更新操作时，在每次更新之前，都先比较一下被更新的目标T，值是不是等于读取到的旧值O，如果相等，则认为在读取到并运算出新值期间没有被其他线程访问，将值更新为新值N，如果T ≠ O，则期间被修改，重新进行【读取 –> 运算 –> 比较】的过程，直到能成功的更新。

乐观锁：乐观的认为不会有其他线程对此资源进行并发访问的，不锁定资源的方式来更新资源。典型的实现CAS。

悲观锁：悲观的认为一定会有其他线程对此资源进行并发访问，一定要锁定资源，自己访问的时候其他线程不允许访问。典型的如synchronized。

java中就有典型的CAS实现，比如AtomicInteger类的源码。

我们可以看看 java.util.concurrent.atomic.AtomicInteger#incrementAndGet 方法：

public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

可以发现，自增方法的实现是调用了Unsafe类中的实现。
那我们再看sun.misc.Unsafe相关代码：

/**
 * Atomically adds the given value to the current value of a field
 * or array element within the given object <code>o</code>
 * at the given <code>offset</code>.
 *
 * @param o object/array to update the field/element in
 * @param offset field/element offset
 * @param delta the value to add
 * @return the previous value
 * @since 1.8
 */
public final int getAndAddInt(Object o, long offset, int delta) {
  int v;
  do {
    v = getIntVolatile(o, offset);
  } while (!compareAndSwapInt(o, offset, v, v + delta));
  return v;
}  


/**
 * Atomically update Java variable to <tt>x</tt> if it is currently
 * holding <tt>expected</tt>.
 * @return <tt>true</tt> if successful
 */
public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);

实际的逻辑实现，最终是调用到了一个native方法——compareAndSwapInt()，此方法由JVM使用C++实现。

按照一般认知，比较并交换，包含多个步骤（取值，比较，交换），而这多个步骤放在一起做，不是原子的，那么它是如何保证它的原子性的？

看方法的描述：Atomically update Java variable to x if it is currently holding expected. —— 如果变量的值是预期的，则原子的更新为x。

可以看到，整个比较并交换过程，是由JVM底层保证的原子性。

那么JVM底层又是如何保证原子性的呢？

在jvm源码中，找到对应方法的实现逻辑，对应源码在 jdk8u : 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调用，cmpxchg的含义就为 compare and exchange。

再进一步跟源码，在 jdk8u: atomic_linux_x86.inline.hpp的93行， atomic_linux_x86.inline.hpp这个文件，对应的就是atomic这个类，在linux_x86架构上实现。

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

os::is_MP()，返回当前系统是否是多核。

cmpxchg本身也是一条CPU指令，但也不是原子的。

__asm__表示后面的是一条汇编指令。LOCK_IF_MP是一个宏，表示如果是多核cup，后面的指令需要lock一下，加上lock以后，其他核的cpu就无法打断后面的指令，也就是原子的了。所以多核cpu会有指令：lock cmpxchg

这个lock指令，是cpu级别的锁，但不是总线锁，而是在执行lock后的指令前，锁定一个北桥信号。（关于这一段描述，是摘抄自网上其他内容的说法，涉及到计算机原理和cpu指令相关的知识）

总结：JVM的AtomicInteger 的CAS实现，实际上是汇编代码调用cpu的cmpxchg指令，且该条cpu指令并非原子，由汇编代码判断是否对核cpu，多核则该指令进行加锁保证其原子性。

原文地址：http://www.cnblogs.com/kingdy/p/cas.html