CAS & ABA问题

CAS

CAS是一种乐观锁，自旋锁，是通过比较内存值与预期值是否匹配，如果匹配，就更新值，如果不匹配，则不做任何操作，继续自旋重试。多个线程同时执行一个CAS，只有一个会成功。

在JUC包中，CAS应用的场景非常多，举个例子，比如ConcurrentHashMap，它的初始化是在put方法里面，如下图所示：

在我们put的时候会调用initTable，继续跟踪代码，如下图所示：

其中 U是 private static final sun.misc.Unsafe U; ,用到 Unsafe类的方法有很多，如图：

案例一

我们就用 AtomicInteger 做个演示，

static void demo1() {
    // 初始值为 1024
    AtomicInteger atomicInteger = new AtomicInteger(1024);
    // 因为预期值和初始值一致，所以返回 true
    System.out.println(atomicInteger.compareAndSet(1024, 2049));
    // 此时的 atomicInteger 值为 2049
    System.out.println(atomicInteger);
    // 再次比较和交换，因为现在的值为2049， 所以返回结果为 false 
    System.out.println(atomicInteger.compareAndSet(1024, 4399));
    // 此时的 atomicInteger 值依然为 2049
    System.out.println(atomicInteger);
  }

案例二（虽然CAS高效的实现了原子性操作,但是也会带来一些问题）

CAS会带来ABA问题，什么是ABA呢？举个例子解释一下：

ABA 是指在 CAS 操作时，其他线程将变量值 A 改为了 B，但是又被改回了 A，等到本线程使用期望值 A 与当前变量进行比较时， 发现变量 A 没有变，于是 CAS 就将 A 值进行了交换操作，但是实际上该值已经被其他线程改变过。

业务场景的话， 可以用银行取钱的场景来说明，
小明在提款机，提取了50元，因为提款机问题，有两个线程，同时把余额从100变为50
线程1（提款机）：获取当前值100，期望更新为50，
线程2（提款机）：获取当前值100，期望更新为50，
线程1 成功执行，线程2 某种原因block了，这时，某人给小明汇款50
线程3（默认）：获取当前值50，期望更新为100，
这时候线程3成功执行，余额变为100，
线程2从Block中恢复，获取到的也是100，compare之后，继续更新余额为50！！！
此时可以看到，实际余额应该为100（100-50+50），但是实际上变为了50（100-50+50-50）这就是ABA问题带来的成功提交。

  static void demo2() {
    // 初始值100块钱 
    AtomicInteger atomicInteger = new AtomicInteger(100);
    // 线程1 、线程2 提取 50；线程2 某种原因 Block 了
    atomicInteger.compareAndSet(100, 50);
    // 某人给小明汇款50
    atomicInteger.compareAndSet(50, 100);
    // 线程2从 Block 中恢复，获取到的也是 100
    atomicInteger.compareAndSet(100, 50);
    // 线程2 compare之后，继续更新余额为50
    System.out.println(atomicInteger);
  }

解决的话通过增加版本号，每次更新的时候版本号都+1，即A->B->A就变成了1A->2B->3A，
代码示例如下：

static void demo3() {
    // 第一个参数 initialRef 为49，第二个参数 initialStamp ，解释为版本号或者戳的概念
    AtomicStampedReference<Integer> stampedReference =
        new AtomicStampedReference<>(49, 1);
    // 插入者
    new Thread(() -> {
      try {
        Thread.sleep(500);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
      //  预期的值，更新值，预期的版本号，新的版本号
      stampedReference.compareAndSet(49, 100,
          stampedReference.getStamp(), stampedReference.getStamp() + 1);
      System.out.println(
          "插入一个线程进行修改，修改结果：" + stampedReference.getReference() +
              " 版本号" + stampedReference.getStamp());
      // 再次修改： 预期的值，更新值，预期的版本号，新的版本号
      stampedReference.compareAndSet(100, 49,
          stampedReference.getStamp(), stampedReference.getStamp() + 1);
      System.out.println(
          "插入一个线程进行修改，修改结果：" + stampedReference.getReference() +
              " 版本号" + stampedReference.getStamp());
    }).start();

    // 执行者
    new Thread(() -> {
      int stamp = stampedReference.getStamp();
      // 插入者睡眠了500ms，所以这里获取到的版本号为 1 
      System.out.println("期望版本号是" + stamp);
      try {
        // 模拟延时，让上面线程先执行，放大问题
        Thread.sleep(2000);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
      // 上面睡眠2000ms后，上面插入者已经执行完毕，值为49，版本号也更新到了3，这个时候去修改，初始值都是49，没问题，当前版本号为1，实际版本号已经到达了3 ，所以更新失败
      System.out.println("修改结果：" +
          stampedReference.compareAndSet(49, 59, stamp, stamp + 1));
      System.out.println("实际版本号是" + stampedReference.getStamp());
    }).start();
  }