cas原理以及Atomic原子类分析-菜鸟笔记

一、什么是CAS

CAS：Compare and Swap，即比较再交换。

CAS 的思想很简单：三个参数，一个当前内存值 V、旧的预期值 A、即将更新的值 B，当且仅当预期值 A 和内存值 V 相同时，将内存值修改为 B 并返回 true，否则什么都不做，并返回 false。

上面那段话来源于官方解析

Atomic原子类底层核心就是CAS,无锁化，乐观锁,每次尝试修改的时候，就对比一下，有没有人修改过这个值，没有人修改，自己就修改，如果有人修改过，就重新查出来最新的值，再次重复那个过程

二、CAS 底层原理

我们拿 AtomicInteger 类来分析，先来看看 AtomicInteger 静态代码块片段：

public class AtomicInteger extends Number implements java.io.Serializable {
  private static final long serialVersionUID = 6214790243416807050L;

  // setup to use Unsafe.compareAndSwapInt for updates
  private static final Unsafe unsafe = Unsafe.getUnsafe();
  private static final long valueOffset;

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

  private volatile int value;
  
  // 省略部分代码
}

这里用到了 sun.misc.Unsafe 类它可以提供硬件级别的原子操作，它可以获取某个属性在内存中的位置，也可以修改对象的字段值，只不过该类对一般开发而言，很少会用到，其底层是用 C/C++ 实现的，所以它的方式都是被 native 关键字修饰过的。

而且的话人家限制好了，不允许你去实例化他以及使用他里面的方法的，首先人家的构造函数是私有化，不能自己手动去实例化他，

其次，如果用Unsafe.getUnsafe()方法来获取一个实例是不行的，在那个源码里，他会判断一下，如果当前是属于我们的用户的应用系统，识别到有我们的那个类加载器以后，就会报错，不让我们来获取实例JDK源码里面，JDK自己内部来使用，不是对外的Unsafe，封装了一些不安全的操作，指针相关的一些操作，就是比较底层了，主要就是Atomic原子类底层大量的运用了Unsafe

如果想使用Unsafe可以通过反射获取：

//自己定义一个类获取Unsafe
public class UnsafeInstance {
    public static Unsafe reflectGetUnsafe() {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            return (Unsafe) field.get(null);
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
        return null;
    }
}

//调用使用方式
private static final Unsafe unsafe = UnsafeInstance.reflectGetUnsafe();

private static long stateOffset;

static {

    try {
        stateOffset = unsafe.objectFieldOffset(AQSLock.class.getDeclaredField("state"));
    } catch (NoSuchFieldException e) {
        e.printStackTrace();
    }

}

我们看到AtomicInteger初始化的时候来进行执行的，valueOffset，value这个字段在AtomicInteger这个类中的偏移量，在底层，这个类是有自己对应的结构的，无论是在磁盘的.class文件里，还是在jvm内存中

大概可以理解为：value这个字段具体是在AtomicInteger这个类的哪个位置，offset，偏移量，这个是很底层的操作，是通过unsafe来实现的。刚刚在类初始化的时候，就会完成这个操作的，final的，一旦初始化完毕，就不会再变更了

#############

接下来看一下AtomicInteger 中的getAndIncrement 方法

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

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;
}

var5 通过 this.getIntVolatile(var1, var2)方法获取，认为当前的value值。去跟底层当前目前AtomicInteger对象实例中的value值比较，如果是一样的话这就是compare的过程，就是set的过程，也就是将value的值设置为i+1(递增的值),如果var5(获取到的值)跟AtomicInteger + valueOffset获取到的当前的值，不一样的话,此时compareAndSwapInt方法就会返回false,进入下一轮循环，重新执行getIntVolatile(var1, var2)再次获取 value 值，因为变量 value 被 volatile 修饰，所以其它线程对它的修改，线程 A 总是能够看到，线程A继续执行compareAndSwapInt进行比较替换，直到成功。

compareAndSwapInt 方法是一个本地方法：

public final native boolean compareAndSwapInt(Object paramObject, long paramLong, int paramInt1, int paramInt2);

Java 并没有直接实现 CAS，CAS 相关的实现是通过 C++ 内联汇编的形式实现的。Java 代码需通过 JNI 才能调用，位于 unsafe.cpp，查看源码：

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

看不懂具体是啥意思，网上资料总结：

1、先想办法拿到变量 value 在内存中的地址。

2、通过Atomic::cmpxchg实现比较替换，其中参数 x 是即将更新的值，参数 e 是原内存的值。

以上1、2解析步骤来源于：https://www.jianshu.com/p/fb6e91b013cc

三、CAS的缺点

此处参考 https://objcoding.com/2018/11/29/cas/#similar_posts

1、ABA问题

线程1 查询A的值为a，与旧值a比较，
线程2 查询A的值为a，与旧值a比较，相等，更新为b值
线程2 查询A的值为b，与旧值b比较，相等，更新为a值
线程1 相等，更新B的值为c，尽管线程 1 也更改成功了，但是不代表这个过程就是没有问题的。
仔细思考，这样可能带来的问题是，如果需要关注A值变化过程，是会漏掉一段时间窗口的监控

举例分析：

现有一个用单向链表实现的栈，栈顶元素为 A，A.next 为 B，期望用 CAS 将栈顶替换成 B。

有线程 1 获取了元素 A，此时线程 1 被挂起，线程 2 也获取了元素 A，并将 A、B 出栈，再 push D、C、A，这时线程 1 恢复执行 CAS，因为此时栈顶元素依然为 A，线程 1 执行成功，栈顶元素变成了 B，但 B.next 为 null，这就会导致 C、D 被丢掉了。

这个例子充分说明了 CAS 的 ABA 问退带来的隐患，通常，我们的乐观锁实现中都会带一个 version 字段来记录更改的版本，避免并发操作带来的问题。在 Java 中，AtomicStampedReference 也实现了这个处理方式。

AtomicStampedReference 的内部类 Pair：

private static class Pair<T> {
  final T reference;
  final int stamp;
  private Pair(T reference, int stamp) {
    this.reference = reference;
    this.stamp = stamp;
  }
  static <T> Pair<T> of(T reference, int stamp) {
    return new Pair<T>(reference, stamp);
  }
}

如上，每个 Pair 维护一个值，其中 reference 维护对象的引用，stamp 维护修改的版本号。

compareAndSet 方法：

/**
     * Atomically sets the value of both the reference and stamp
     * to the given update values if the
     * current reference is {@code ==} to the expected reference
     * and the current stamp is equal to the expected stamp.
     *
     * @param expectedReference the expected value of the reference
     * @param newReference the new value for the reference
     * @param expectedStamp the expected value of the stamp
     * @param newStamp the new value for the stamp
     * @return {@code true} if successful
     */
public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
  Pair<V> current = pair;
  return
    expectedReference == current.reference &&
    expectedStamp == current.stamp &&
    ((newReference == current.reference &&
      newStamp == current.stamp) ||
     casPair(current, Pair.of(newReference, newStamp)));
}

从 compareAndSet 方法得知，如果要更改内存中的值，不但要值相同，还要版本号相同。

举例分析：

public class AtomicStampedReferenceTest {

  // 初始值为1，版本号为0
  private static AtomicStampedReference<Integer> a = new AtomicStampedReference<>(1, 0);

  // 计数器
  private static CountDownLatch countDownLatch = new CountDownLatch(1);

  public static void main(String[] args) {

    new Thread(() -> {
      System.out.println("线程名字：" + Thread.currentThread() + ", 当前 value = " + a.getReference());
      // 获取当前版本号
      int stamp = a.getStamp();

      // 计数器阻塞，直到计数器为0，才执行
      try {
        countDownLatch.await();
      } catch (InterruptedException e) {
        e.printStackTrace();
      }

      System.out.println("线程名字：" + Thread.currentThread() + ",CAS操作结果: " + a.compareAndSet(1, 2, stamp, stamp + 1));
    }, "线程1").start();

    // 线程2
    new Thread(() -> {
      // 将 value 值改成 2
      a.compareAndSet(1, 2, a.getStamp(), a.getStamp() + 1);
      System.out.println("线程名字" + Thread.currentThread() + "value = " + a.getReference());
      // 将 value 值又改成 1
      a.compareAndSet(2, 1, a.getStamp(), a.getStamp() + 1);
      System.out.println("线程名字" + Thread.currentThread() + "value = " + a.getReference());
      // 线程计数器
      countDownLatch.countDown();
    }, "线程2").start();

  }
}

2、无限循环问题：大家看源码就知道Atomic类设置值的时候会进入一个无限循环，只要不成功，就不停循环再次尝试，这个在高并发修改一个值的时候其实挺常见的，比如你用AtomicInteger在内存里搞一个原子变量，然后高并发下，多线程频繁修改，其实可能会导致这个compareAndSet()里要循环N次才设置成功，所以还是要考虑到的。

JDK 1.8引入的LongAdder来解决，是一个重点，分段CAS思路

3、多变量原子问题：一般的AtomicInteger，只能保证一个变量的原子性，但是如果多个变量呢？你可以用AtomicReference，这个是封装自定义对象的，多个变量可以放一个自定义对象里，然后他会检查这个对象的引用是不是一个。

操作系统笔记

cas原理以及Atomic原子类分析

笔记导航