Version: Next

CAS

什么是CAS

CAS: Compare and Swap——比较并交换

old value：共享资源的原状态值
new value：线程争夺到共享资源后想要设置的新状态值
- 例如：有一个资源，状态为 0，有两个线程争夺它，他们都读到了 0，则 都 以 oldValue = 0、newValue = 1来争夺这个资源
- 假设 线程一 率先获得了时间片，则它将自己的 oldValue = 0 与资源目前的真实状态值 0 进行 比较 compare 发现一致，则将 newValue = 1 通过 交换 swap 设置到 资源状态值 上
- 此时 线程二 发现自己的 oldValue 为 0，而资源状态值为 1，则放弃争夺，进入自旋，不断重试 CAS
compare 和 swap 两个操作必须合并为一个原子操作，否则可能出现多个线程同时抢到资源的情况，这个原语是 CPU 级别的，比操作系统的更底层

CAS(V, E, N) 包含3个参数，V表示要更新的变量，E表示期望的值，N表示要更新为的新值

当且仅当V的值达到期望值E时，才更新V的值为N
如果V的值没达到预期E值，就什么也不做，一直监听V的值，自旋等待

CAS的特性：乐观锁

CAS采用了乐观锁的思想，总是认为自己可以成功完成任务

在多个线程同时使用CAS操作一个变量时，只有一个会胜出并且成功更新，其余均会失败
失败的线程不会被挂起，仅被告知失败，并且允许再次尝试（一直监听V值的更新情况，是否达到E）
基于这样的原理，CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰，并进行恰当处理

CAS自旋锁

Unsafe类中的getAndSwapInt方法
this.compareAndSwapInt在达到期望值时返回true，因此当期望值未达到时，一直循环，自旋等待

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do { // 无限循环
      var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
  
    return var5;
}

传统CAS：观察CAS在JUC原子类中的使用

JUC原子类AtomicInteger，实例方法compareAndSet(int expect,int update)
底层调用Unsafe类的CAS方法
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
CAS是CPU的并发原语，是CPU的指令

如果期望的值达到了，就更新值为指定值；否则不更新值

@Test
public void testCAS() {
    AtomicInteger atomicInteger = new AtomicInteger(1);
    atomicInteger.compareAndSet(1, 2020);
  
    System.out.println(atomicInteger);
}  

2020

Unsafe类

Unsafe类
Java无法直接操作计算机内存
Java可以调用C++操作内存，通过native修饰的方法
Unsafe类相当于Java的一个后面，可以通过它操作内存

AtomicInteger源码中的静态代码块

static {
    try {
      valueOffset = unsafe.objectFieldOffset
        (AtomicInteger.class.getDeclaredField("value"));
    } catch (Exception ex) { throw new Error(ex); }
}

可以看到获取了一个valueOffset，这是通过unsafe调用C++获得内存地址的偏移地址

AtomicInteger中存储的整型值

private volatile int value;

可以看到使用了volatile禁止指令重排，确保可见性

AtomicInteger中的加一方法

public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}

Unsafe类中的getAndAddInt(Object var1, long var2, int var 4)方法

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
      var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
  
    return var5;
}

var1为对象；var2为偏移地址；var4为要增加的值；var5为当前地址位置上的int值

其中又调用了this.compareAndSwapInt(var1, var2, var5, var5 + var4)，意思为从对象var1偏移地址var2的位置上取出var5，第三个参数var5表示期待值为var5，如果期待被满足，就将值更改为var5 + var4

而在getAndIncrement()方法中，var4参数的值为1，即遇到期待值，就加1

内存操作，效率很高

ABA问题

对CAS算法的实现有一个重要的前提：需要取出内存中某时刻的数据，然后在下一个时刻进行比较、替换，在这个时间差内可能数据已经发生了变化，导致产生ABA问题

ABA问题指

第1个线程从内存的V位置取出A
这时第2个线程也从内存中取出A，并将V位置的数据需改为B，接着又将V位置的数据改为A
这时第1个线程在进行CAS操作时会发现内存位置V中的值仍为A，于是第1个线程的操作成功
尽管从第1个线程的角度出发，CAS操作是成功的，但其实在操作过程中V位置上的数据发生了变化，只是第1个线程没有感知到罢了，这在高并发情况下可能造成数据不一致问题

CAS：采用原子引用解决ABA问题

部分乐观锁是通过版本号(Version)来解决ABA问题的，还可以利用时间戳(Stamp)
乐观锁每次在执行数据的修改操作时都会带上一个版本号
在预期的版本号和数据的版本号一致时，就可以执行修改数据操作，并对版本号加1，否则执行失败
因为每次操作后，版本哈都随之增加，所以不会产生ABA问题，因为版本号只会增加，不会减少

AtomicStampedReference类的构造方法

带初始引用和时间戳

public AtomicStampedReference(V initialRef, int initialStamp) {
    pair = Pair.of(initialRef, initialStamp);
}

使用带版本号的CAS

注意

使用的值要在-128~127之间，否则会触发包装类重新去堆内存new一个值，导致前后两个值指的不是同一个地址，预期值无法被达到

public static void main(String[] args) {
    AtomicStampedReference<Integer> atomicInteger =
      new AtomicStampedReference<>(50, 0);
  
    new Thread(() -> {
      int stamp = atomicInteger.getStamp();  // 获取当前的戳
      System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
  
      try {
        TimeUnit.SECONDS.sleep(2);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
  
      atomicInteger.compareAndSet(50, //期望值
                                  1, // 新值
                                  atomicInteger.getStamp(), // 期望的stamp值
                                  atomicInteger.getStamp() + 1); // 新Stamp值
  
      System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
  
      // 按照ABA问题的原理，把值再改回去
      atomicInteger.compareAndSet(1, //期望值
                                  50, // 新值
                                  atomicInteger.getStamp(), // 期望的stamp值
                                  atomicInteger.getStamp() + 1); // 新Stamp值
  
    }, "Thread A").start();
  
    new Thread(() -> {
      int stamp = atomicInteger.getStamp();  // 获取当前的戳
      System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
  
      try {
        TimeUnit.SECONDS.sleep(4);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
  
      boolean result = atomicInteger.compareAndSet(50,
                                                   60,
                                                   stamp,  // 准备刷新值完成对值的修改，先看看时间戳有没有被别人动过
                                                   ++stamp);
  
      if (result) {
        System.out.println("操作成功");
      } else {
        System.out.println("操作失败，在" + Thread.currentThread().getName() + "操作期间，原值已经被别人动了手脚");
      }
  
      System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
    }, "Thread B").start();
}

Thread A -> Stamp:0 | Value:50
Thread B -> Stamp:0 | Value:50
Thread A -> Stamp:1 | Value:1
操作失败，在Thread B操作期间，原值已经被别人动了手脚
Thread B -> Stamp:2 | Value:50

那我就要用超过-127~128的值咋办呢？
定义一个Integer类型的变量，不要直接写值触发自动装箱拆箱

public class CasDemo {
      static Integer i = 2000;  // 定义一个Integer变量
  
      public static void main(String[] args) {
          AtomicStampedReference<Integer> atomicInteger =
                  new AtomicStampedReference<>(i, 0);
  
          new Thread(() -> {
              int stamp = atomicInteger.getStamp();  // 获取当前的戳
              System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
  
              try {
                  TimeUnit.SECONDS.sleep(2);
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
  
              atomicInteger.compareAndSet(i, //期望值
                      1, // 新值
                      atomicInteger.getStamp(), // 期望的stamp值
                      atomicInteger.getStamp() + 1); // 新Stamp值
  
              System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
  
              // 按照ABA问题的原理，把值再改回去
              atomicInteger.compareAndSet(1, //期望值
                      i, // 新值
                      atomicInteger.getStamp(), // 期望的stamp值
                      atomicInteger.getStamp() + 1); // 新Stamp值
  
          }, "Thread A").start();
  
          new Thread(() -> {
              int stamp = atomicInteger.getStamp();  // 获取当前的戳
              System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
  
              try {
                  TimeUnit.SECONDS.sleep(4);
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
  
              boolean result = atomicInteger.compareAndSet(i,
                      60,
                      stamp,  // 准备刷新值完成对值的修改，先看看时间戳有没有被别人动过
                      ++stamp);
  
              if (result) {
                  System.out.println("操作成功");
              } else {
                  System.out.println("操作失败，在" + Thread.currentThread().getName() + "操作期间，原值已经被别人动了手脚");
              }
  
              System.out.println(Thread.currentThread().getName() + " -> Stamp:" + atomicInteger.getStamp() + " | Value:" + atomicInteger.getReference());
          }, "Thread B").start();
      }
}

Thread A -> Stamp:0 | Value:2000
Thread B -> Stamp:0 | Value:2000
Thread A -> Stamp:1 | Value:1
操作失败，在Thread B操作期间，原值已经被别人动了手脚
Thread B -> Stamp:2 | Value:2000

CAS的缺点

自旋循环会耗时
一次性只能操作一个共享变量
存在ABA问题，需要特殊处理

CAS#

CAS的特性：乐观锁#

CAS自旋锁#

传统CAS：观察CAS在JUC原子类中的使用#

Unsafe类#

ABA问题#

CAS：采用原子引用解决ABA问题#

注意

CAS的缺点#

CAS

CAS的特性：乐观锁

CAS自旋锁

传统CAS：观察CAS在JUC原子类中的使用

Unsafe类

ABA问题

CAS：采用原子引用解决ABA问题

CAS的缺点