1、什么是 CAS

CAS 是指比较并交换 compare and swap 或 compare and set 或 compare and exchange。CAS 操作利用了处理器提供的 cmpxchg 指令实现的。自旋 CAS 实现的基本思路就是循环进行 CAS 操作直到成功为止。

2、CAS 工作流程

CAS 指令需要有三个操作数，分别是内存位置（Java 中可以简单地理解为变量的内存地址，用 V 表示）、旧的预期值（用 A 表示）和准备设置的新值（B 表示）。CAS 指令执行时，当且仅当 V 符合 A 时，处理器才会用 B 更新 V 的值，否则它就不执行更新。但是，不管是否更新了 V 的值，都会返回 V 的旧值，上述处理过程是一个原子操作，执行期间不会被其他线程中断。

cas(V, A, B)，V-变量，A-期望值, B-修改值

流程如图所示：

CAS流程图.png

3、CAS 实现原子操作的三大问题

3.1、ABA 问题

其他线程修改数次最后值和原值相同，即其他线程将变量值 A 修改为 B，但是又被改回了 A。等到本线程使用期望值 A 与当前值进行比较时，发现变量 A 没有变，于是 CAS 就将 A 值进行了交换操作，但是实际该值已经被其他线程改变过，这与乐观锁的设计思想不符合。

ABA 问题的解决思路是，每次变量更新的时候把变量的版本号加 1，那么 A-B-A 就会变成 A1-B2-A3，只要变量被某一线程修改过，改变对应的版本号就会发生递增变化，从而解决了 ABA 问题，基础类型简单值不需要版本号。在 JDK 的 java.util.concurrent.atomic 包中提供了 AtomicStampedReference 来解决 ABA 问题，该类的 compareAndSet 是该类的核心方法，实现如下：

  1.     /**
  2.      * Atomically sets the value of both the reference and stamp
  3.      * to the given update values if the
  4.      * current reference is {@code ==} to the expected reference
  5.      * and the current stamp is equal to the expected stamp.
  6.      *
  7.      * @param expectedReference 预期引用
  8.      * @param newReference 更新后的引用
  9.      * @param expectedStamp 预期标志
  10.      * @param newStamp 更新后的标志
  11.      * @return {@code true} if successful
  12.      */
  13.     public boolean compareAndSet(V   expectedReference,
  14.                                  V   newReference,
  15.                                  int expectedStamp,
  16.                                  int newStamp) {
  17.         Pair<V> current = pair;
  18.         return
  19.             expectedReference == current.reference &&
  20.             expectedStamp == current.stamp &&
  21.             ((newReference == current.reference &&
  22.               newStamp == current.stamp) ||
  23.              casPair(current, Pair.of(newReference, newStamp)));
  24.     }

该类检查了当前引用与当前标志是否与预期相同，如果全部相等，才会以原子方式将该引用和该标志的值设为新的更新值，这样 CAS 操作中的比较就不依赖于变量的值了。

3.2、循环时间长开销大

自旋 CAS 如果长时间不成功，会给 CPU 带来非常大的执行开销。如果 JVM 能支持处理器提供的 pause 指令，那么效率会有一定的提升。

pause 指令有两个作用

  1. 可以延迟流水线执行指令（de-pipeline），使 CPU 不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器延迟时间是零
  2. 可以避免在退出循环的时候因内存顺序冲突（Memory Order Violation）而引起 CPU 流水线被清空（CPU Pipeline Flush)，从而提高 CPU 的执行效率

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

当对一个共享变量执行操作时，我们可以使用循环 CAS 的方式来保证原子操作，但是对多个共享变量操作时，循环 CAS 就无法保证操作的原子性。

如何保证多个共享变量的原子操作

  1. 使用锁
  2. 把多个共享变量合并成一个共享变量来操作
    比如，两个共享变量 i=2, j=a，合并一下 ij=2a，然后用 CAS 来操作 ij。从 JDK1.5 开始，JDK 提供了AtomicReference 类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行 CAS 操作。

4、Unsafe

4.1、测试代码

  1. import sun.misc.Unsafe;
  3. import java.lang.reflect.Field;
  5. public class TestUnsafe {
  7.     int i = 0;
  8.     private static TestUnsafe t = new TestUnsafe();
  10.     public static void main(String[] args) throws Exception {
  11.         // Unsafe unsafe = Unsafe.getUnsafe();
  13.         Field unsafeField = Unsafe.class.getDeclaredFields()[0];
  14.         unsafeField.setAccessible(true);
  15.         Unsafe unsafe = (Unsafe) unsafeField.get(null);
  17.         Field f = TestUnsafe.class.getDeclaredField("i");
  18.         long offset = unsafe.objectFieldOffset(f);
  19.         System.out.println(offset);
  21.         boolean success = unsafe.compareAndSwapInt(t, offset, 0, 1);
  22.         System.out.println(success);
  23.         System.out.println(t.i);
  24.         // unsafe.compareAndSwapInt()
  25.     }
  26. }

Java 程序序中 CAS 的操作是用 sun.misc.Unsafe 类里的 compareAndSwapInt() 和 compareAndSwapLong() 等几个方法包装提供的，虚拟机在内部对这些方法做了特殊处理，即时编译出来的结果就是一条平台相关的处理器 CAS 指令，没有方法的调用过程，或者可以认为是无条件内联进去了。这里的 JDK 版本是 jdk8u。

4.2、AtomicInteger 的代码片段

  1.  /**
  2.  * Atomically increments by one the current value.
  3.  *
  4.  * @return the updated value
  5.  */
  6. public final int incrementAndGet() {
  7.     return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
  8. }

4.3、sun.misc.Unsafe 代码片段

  1.  public final int getAndAddInt(Object var1, long var2, int var4) {
  2.     int var5;
  3.     do {
  4.         var5 = this.getIntVolatile(var1, var2);
  5.     } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
  7.     return var5;
  8. }
  10. public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

4.4、unsafe.cpp

  1. UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  2.   UnsafeWrapper("Unsafe_CompareAndSwapInt");
  3.   oop p = JNIHandles::resolve(obj);
  4.   jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  5.   // cmpxchg = compare and exchange
  6.   return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
  7. UNSAFE_END

4.5、atomic_linux_x86.inline.hpp

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

4.6、os.hpp

is_MP：是否是多个处理器（Multi Processor）

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

atomic_linux_x86.inline.hpp

  1. #define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "