CAS（CompareAndSet）又叫比较并交换，是一种无锁算法（自旋 / 自旋锁 / 无锁）。CAS能保证数据的原子性，在jdk中，Atmoic变量就是CAS应用的典型例子，持外，CAS也应用在很多场景，因此理解CAS对于我们掌握jdk中并发相关的知识是很重要的一部分。

什么是CAS？

CAS（CompareAndSet）又叫比较并交换，是一种无锁算法（自旋 / 自旋锁 / 无锁）。
CAS包含三个值，内存值（V)，预期值（A），新值（B）。先比较内存地址的值和预期的值是否相等，如果相等，就将新值赋在内存地址上，否则，不做任何处理。具体步骤如下：

获得字段的期望值（oldValue），即从内存中读取值。
计算出需要替换的新值（newValue）。
当CAS进行内存地址的值与预期值比较时，如果相等，则证明内存地址的值没有被修改，可以替换成新值，然后继续往下运行；如果不相等，说明明内存地址的值已经被修改，放弃替换操作，然后重新自旋。

CAS原理剖析

以AtomicInteger原子整型类为例，看一下CAS底层实现机制。

public final int incrementAndGet() {
  for (;;) {
    int current = get();
    int next = current + 1;
    if (compareAndSet(current, next))
      return next;
  }
}
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

我们继续跟踪，发现已经到了unsafe类中，说明已经到了C++中的代码。

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

我们来看下c++中是怎么实现的：
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

继续跟踪到 jdk8u: atomic_linux_x86.inline.hpp

inline jint Atomic::cmpxchg (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  int mp = os::is_MP(); //is_MP = Multi Processor
  __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;
}

jdk8u: os.hpp is_MP()，判断是否多核

static inline bool is_MP() {
    // During bootstrap if _processor_count is not yet initialized
    // we claim to be MP as that is safest. If any platform has a
    // stub generator that might be triggered in this phase and for
    // which being declared MP when in fact not, is a problem - then
    // the bootstrap routine for the stub generator needs to check
    // the processor count directly and leave the bootstrap routine
    // in place until called after initialization has ocurred.
    return (_processor_count != 1) || AssumeMP;
  }

到这里我们可以发现系统底层的最终实现就是：lock cmpxchg 指令。 cmpxchg 可以理解为compare and exchange，lock指令在执行后面指令的时候锁定一个北桥信号（不采用锁总线的方式）。

CAS的问题

1、ABA问题

CAS操作是先比较A的预期值和内存地址中的值是否相同，如果相同就认为此时没有其他线程修改A值。但是，此时假如一个线程读取到A值，此时有另外一个线程将A值改成了B，然后又将B改回了A，这时比较A和预期值是相同的，就认为A值没有被改变过。为了解决ABA的问题，可以使用版本号，每次修改变量，都在这个变量的版本号上加1，这样，刚刚A->B->A，虽然A的值没变，但是它的版本号已经变了，再判断版本号就会发现此时的A已经被别人偷偷改过了。

解决方法：AtomicReference原子引用。

2、性能问题

如果自旋长时间不成功，会给CPU带来非常大的执行开销。

public final int getAndSet(int newValue) {
    for (;;) {
        int current = get();
        if (compareAndSet(current, newValue))
            return current;
    }
}

可以看到源码中的自旋就是当CAS成功时，才会return。因此CAS带来的性能问题也是需要考虑的。自旋也是CAS的特点，自旋算是一种非阻塞算法，相对于其他阻塞算法而已，非阻塞是不需要cpu切换时间片保存上下文的，节省了大量性能消耗。CAS相对于同步锁的优点：如果在并发量不是很高时CAS机制会提高效率，但是在竞争激烈并发量大的情况下效率是非常低，因为自旋时间过长，失败次数过多造成重试次数过多。

解决思路：参考LongAdd，实现热点分散，多段操作。

CAS的使用场景

CAS在JUC包中的原子类、AQS以及CurrentHashMap等重要并发容器类的实现上都有应用。在java.util.concurrent.atomic包的原子类如AtomicXXX 中，都使用了CAS保障对数字成员进行操作的原子性。

JUC并发编程与源码分析