一、乐观锁和悲观锁

CAS是一种典型的乐观锁，甚至可以认为乐观锁就是基于CAS机制实现的。乐观锁思想基于一个乐观的猜测：当我修改这个变量时，大概率不会有其他人也来修改它。因此，我在尝试修改时，不会加锁。大概率下我会一次修改成功。但是如果我不幸没修改成功（被别人顶开了），那么我继续尝试，直到修改成功。乐观锁的好处是，它是一种无锁的设计，线程不会阻塞，省去了线程切换的开销。缺点是，高并发场景下，锁竞争激烈，导致循环尝试的次数可能很多，cpu占用率会升高。
相反，悲观锁是一种悲观思想，它总认为最坏的情况可能会出现，它认为数据很可能会被其他人所修改，所以悲观锁在持有数据的时候总会把资源 或者 数据 锁住，这样其他线程想要请求这个资源的时候就会阻塞，直到等到悲观锁把资源释放为止。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。

二、CAS原理解析

在并发修改一个变量时，我们的选择之一是使用 synchronized 关键字，但是在线程竞争压力大的情况下，synchronized 内部会膨胀为重量级锁，此时仅能有一个线程进入代码块执行，如果这把锁始终不能释放，其他线程会一直阻塞等待下去。此时，可以认为是悲观锁。
悲观锁会因线程一直阻塞导致系统上下文切换，系统的性能开销大。
我们从AtomicInteger开始

  1. // 提供自增易用的方法，返回增加1后的值
  2. public final int incrementAndGet() {
  3.         return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
  4. }
  6. // 额外提供的compareAndSet方法
  7. public final boolean compareAndSet(int expect, int update) {
  8.         return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
  9. }

我们看到了 AtomicInteger 内部方法都是基于 Unsafe 类实现的，Unsafe类是个跟底层硬件CPU指令通讯的工具类。在使用Unsafe的api时，传了这些参数：
（1）this，AtomicInteger 对象本身，用于获取内存地址，从而根据value属性的内存偏移量来获取value的内存地址。
（2）valueOffset，value 变量的内存偏移地址。
（3）expect，期望更新的值。
（4）update，要更新的最新值。
value属性是使用volatile关键字修饰的，为了保证其可见性。

2.1 CAS底层硬件指令

底层硬件通过将 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. }

2.2 ABA问题

因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。
ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A。
从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。