CAS原理剖析

CAS 被认为是一种乐观锁，有乐观锁，相对应的是悲观锁。
在上述示例中，我们使用了 synchronized，如果在线程竞争压力大的情况下，synchronized 内部会升级为重量级锁，此时仅能有一个线程进入代码块执行，如果这把锁始终不能释放，其他线程会一直阻塞等待下去。此时，可以认为是悲观锁。
悲观锁会因线程一直阻塞导致系统上下文切换，系统的性能开销大。
那么，我们可以用乐观锁来解决，所谓的乐观锁，其实就是一种思想。
乐观锁，会以一种更加乐观的态度对待事情，认为自己可以操作成功。当多个线程操作同一个共享资源时，仅能有一个线程同一时间获得锁成功，在乐观锁中，其他线程发现自己无法成功获得锁，并不会像悲观锁那样阻塞线程，而是直接返回，可以去选择再次重试获得锁，也可以直接退出。
CAS 正是乐观锁的核心算法实现。
在示例代码的方案中都提到了 AtomicInteger、LongAdder、Lock锁底层，此外，当然还包括 java.util.concurrent.atomic 并发包下的所有原子类都是基于 CAS 来实现的。
以 AtomicInteger 原子整型类为例，一起来分析下 CAS 底层实现机制。

  1. atomicData.incrementAndGet()

源码如下所示：

  1. // 提供自增易用的方法，返回增加1后的值
  2. public final int incrementAndGet() {
  3.         return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
  4. }
  5. // 额外提供的compareAndSet方法
  6. public final boolean compareAndSet(int expect, int update) {
  7.         return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
  8. }
  9. // Unsafe 类的提供的方法
  10. public final int getAndAddInt (Object o,long offset, int delta){
  11.         int v;
  12.         do {
  13.                 v = getIntVolatile(o, offset);
  14.         } while (!weakCompareAndSetInt(o, offset, v, v + delta));
  15.         return v;
  16. }

我们看到了 AtomicInteger 内部方法都是基于 Unsafe 类实现的，Unsafe 类是个跟底层硬件CPU指令通讯的复制工具类。
由这段代码看到：

  1. unsafe.compareAndSwapInt(this, valueOffset, expect, update)

所谓的 CAS，其实是个简称，全称是 Compare And Swap，对比之后交换数据。上面的方法，有几个重要的参数：
（1）this，Unsafe 对象本身，需要通过这个类来获取 value 的内存偏移地址。
（2）valueOffset，value 变量的内存偏移地址。
（3）expect，期望更新的值。
（4）update，要更新的最新值。
如果原子变量中的 value 值等于 expect，则使用 update 值更新该值并返回 true，否则返回 false。
再看如何获得 valueOffset的：

  1. // Unsafe实例
  2. private static final Unsafe unsafe = Unsafe.getUnsafe();
  3. private static final long valueOffset;
  4. static {
  5.         try {
  6.               // 获得value在AtomicInteger中的偏移量
  7.                 valueOffset = unsafe.objectFieldOffset
  8.                         (AtomicInteger.class.getDeclaredField("value"));
  9.         } catch (Exception ex) { throw new Error(ex); }
  10. }
  11. // 实际变量的值
  12. private volatile int value;

这里看到了 value 实际的变量，是由 volatile 关键字修饰的，为了保证在多线程下的内存可见性。
为何能通过 Unsafe.getUnsafe() 方法能获得 Unsafe 类的实例？其实因为 AtomicInteger 类也在 rt.jar 包下面的，所以 AtomicInteger 类就是通过 Bootstrap 根类加载器进行加载的。
源码如下所示：

  1. @CallerSensitive
  2. public static Unsafe getUnsafe() {
  3.         Class var0 = Reflection.getCallerClass();
  4.         // Bootstrap 类加载器是C++的，正常返回null，否则就抛异常。
  5.         if (!VM.isSystemDomainLoader(var0.getClassLoader())) {
  6.                 throw new SecurityException("Unsafe");
  7.         } else {
  8.                 return theUnsafe;
  9.         }
  10. }

类加载器委托关系：

CAS原理解析 - 图1

4CPU如何实现原子操作

CPU 处理器速度远远大于在主内存中的，为了解决速度差异，在他们之间架设了多级缓存，如 L1、L2、L3 级别的缓存，这些缓存离CPU越近就越快，将频繁操作的数据缓存到这里，加快访问速度 ，如下图所示：

CAS原理解析 - 图2

现在都是多核 CPU 处理器，每个 CPU 处理器内维护了一块字节的内存，每个内核内部维护着一块字节的缓存，当多线程并发读写时，就会出现缓存数据不一致的情况。
此时，处理器提供：

  • 总线锁定

当一个处理器要操作共享变量时，在 BUS 总线上发出一个 Lock 信号，其他处理就无法操作这个共享变量了。
缺点很明显，总线锁定在阻塞其它处理器获取该共享变量的操作请求时，也可能会导致大量阻塞，从而增加系统的性能开销。

  • 缓存锁定

后来的处理器都提供了缓存锁定机制，也就说当某个处理器对缓存中的共享变量进行了操作，其他处理器会有个嗅探机制，将其他处理器的该共享变量的缓存失效，待其他线程读取时会重新从主内存中读取最新的数据，基于 MESI 缓存一致性协议来实现的。
现代的处理器基本都支持和使用的缓存锁定机制。
注意：
有如下两种情况处理器不会使用缓存锁定：
（1）当操作的数据跨多个缓存行，或没被缓存在处理器内部，则处理器会使用总线锁定。
（2）有些处理器不支持缓存锁定，比如：Intel 486 和 Pentium 处理器也会调用总线锁定。

5解密CAS底层指令
其实，掌握以上内容，对于 CAS 机制的理解相对来说算是比较清楚了。
当然，如果感兴趣，也可以继续深入学习用到了哪些硬件 CPU 指令。
底层硬件通过将 CAS 里的多个操作在硬件层面语义实现上，通过一条处理器指令保证了原子性操作。这些指令如下所示：
（1）测试并设置（Tetst-and-Set）
（2）获取并增加（Fetch-and-Increment）
（3）交换（Swap）
（4）比较并交换（Compare-and-Swap）
（5）加载链接/条件存储（Load-Linked/Store-Conditional）
前面三条大部分处理器已经实现，后面的两条是现代处理器当中新增加的。而且根据不同的体系结构，指令存在着明显差异。
在IA64，x86 指令集中有 cmpxchg 指令完成 CAS 功能，在 sparc-TSO 也有 casa 指令实现，而在 ARM 和 PowerPC 架构下，则需要使用一对 ldrex/strex 指令来完成 LL/SC 的功能。在精简指令集的体系架构中，则通常是靠一对儿指令，如：load and reserve 和 store conditional 实现的，在大多数处理器上 CAS 都是个非常轻量级的操作，这也是其优势所在。
sun.misc.Unsafe 中 CAS 的核心方法：

  1. public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
  2. public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
  3. public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

这三个方法可以对应去查看 openjdk 的 hotspot 源码：
源码位置：hotspot/src/share/vm/prims/unsafe.cpp

  1. #define FN_PTR(f) CAST_FROM_FN_PTR(void*, &f)
  2. {CC"compareAndSwapObject", CC"("OBJ"J"OBJ""OBJ")Z",  FN_PTR(Unsafe_CompareAndSwapObject)},
  3. {CC"compareAndSwapInt",  CC"("OBJ"J""I""I"")Z",      FN_PTR(Unsafe_CompareAndSwapInt)},
  4. {CC"compareAndSwapLong", CC"("OBJ"J""J""J"")Z",      FN_PTR(Unsafe_CompareAndSwapLong)},

上述三个方法，最终在 hotspot 源码实现中都会调用统一的 cmpxchg 函数，可以在 hotspot 源码中找到核心代码。
源码地址：hotspot/src/share/vm/runtime/Atomic.cpp
cmpxchg 函数源码：

  1. jbyte Atomic::cmpxchg(jbyte exchange_value, volatile jbyte*dest, jbyte compare_value) {
  2.          assert (sizeof(jbyte) == 1,"assumption.");
  3.          uintptr_t dest_addr = (uintptr_t) dest;
  4.          uintptr_t offset = dest_addr % sizeof(jint);
  5.          volatile jint*dest_int = ( volatile jint*)(dest_addr - offset);
  6.          // 对象当前值
  7.          jint cur = *dest_int;
  8.          // 当前值cur的地址
  9.          jbyte * cur_as_bytes = (jbyte *) ( & cur);
  10.          // new_val地址
  11.          jint new_val = cur;
  12.          jbyte * new_val_as_bytes = (jbyte *) ( & new_val);
  13.           // new_val存exchange_value，后面修改则直接从new_val中取值
  14.          new_val_as_bytes[offset] = exchange_value;
  15.          // 比较当前值与期望值，如果相同则更新，不同则直接返回
  16.          while (cur_as_bytes[offset] == compare_value) {
  17.           // 调用汇编指令cmpxchg执行CAS操作，期望值为cur，更新值为new_val
  18.              jint res = cmpxchg(new_val, dest_int, cur);
  19.              if (res == cur) break;
  20.              cur = res;
  21.              new_val = cur;
  22.              new_val_as_bytes[offset] = exchange_value;
  23.          }
  24.          // 返回当前值
  25.          return cur_as_bytes[offset];
  26. }

源码中具体变量添加了注释，因为都是 C++ 代码，所以作为了解即可 ~

  1. jint res = cmpxchg(new_val, dest_int, cur);

这里就是调用了汇编指令 cmpxchg 了，其中也是包含了三个参数，跟CAS上的参数能对应上。