全方位探究似懂非懂的 CAS 机制～-六虎

”本文正在参与「金石计划」”

前言

肄业、面试的时候会无法回避 CAS 话题，但对于其原理，总有种似懂非懂的感觉。

CAS 机制全称： Compare and Swap，即 比较并替换， 。也有叫做 Compare and Set 的，即比较并设置。望文生义，分为两步：

比较：读取到了一个值 A，在将其更新为 B 之前，查看原值是否仍为 A
替换 / 设置：YES 则将 A 更新为 B，结束；反之，重复上述操作直到成功为止

这种机制在确保原子化操作、完结达观锁的一起也无法防止一些缺点，我们从源码入手剖析一下其原理、达观锁和缺点等各个细节。

源码解读

以 JDK 中最常用的 AtomicInteger 类的源码为例进行讨论，版本为 JDK 8。

1. Unsafe

首要 AtomicInteger 将经过 Unsafe 供给的静态办法 getUnsafe() 取得其单例。

// java.util.concurrent.atomic.AtomicInteger
public class AtomicInteger extends Number implements java.io.Serializable {
  private static final Unsafe unsafe = Unsafe.getUnsafe();
   ...
}

// jdk.internal.misc.Unsafe
public final class Unsafe {
   ...
  private Unsafe() {}

  private static final Unsafe theUnsafe = new Unsafe();

  @CallerSensitive
  public static Unsafe getUnsafe() {
     ...
    return theUnsafe;
   }
}

为什么叫 Unsafe 呢？

由于它供给了针对恣意地址的数据进行不安全读写等内存操作、线程调度、CAS 等操作的入口，假如调用是不受信任的，那么使得代码犯错的概率变大，也更会引发 JVM 等级的 exception。

所以要求只有可信任的代码能够获取其单例并进行调用，所以将其命名为 Unsafe，给调用者以提醒。

正由于此，getUnsafe() 内部在回来 Unsafe 单例前会先去查看调用 Class 其是否可信任，假如不是体系 ClassLoader 加载的 Class 的话，会抛出 SecurityException。

// jdk.internal.misc.Unsafe
public final class Unsafe {
   ...
  @CallerSensitive
  public static Unsafe getUnsafe() {
    Class<?> caller = Reflection.getCallerClass();
    if (!VM.isSystemDomainLoader(caller.getClassLoader()))
      throw new SecurityException("Unsafe");
    return theUnsafe;
   }
}

// sun.misc.VM
public class VM {
   ...
  public static boolean isSystemDomainLoader(ClassLoader loader) {
    return loader == null;
   }
}

并建议像如下示例代码相同进行运用：

class MyTrustedClass {
  private static final Unsafe unsafe = Unsafe.getUnsafe();
   ...
  private long myCountAddress = ...;
  public int getCount() { return unsafe.getByte(myCountAddress); }
}

2. valueOffset & value

其次，赋值内部持有相关变量，包含方针的 int 型数值 value 和关联该 value 地址的 long 型的 valueOffset：

value 运用 volatile 修饰，默以为 0，反之为 AtomicInteger 构造时指定的初始值 initialValue
valueOffset 是寄存 value 的内存相对地址：在 static 块中经过 Unsafe 的 objectFieldOffset() 传入的 value 的 Field 字段得到

// java.util.concurrent.atomic.AtomicInteger
public class AtomicInteger extends Number implements java.io.Serializable {
   ...
  private volatile int value;

  public AtomicInteger(int initialValue) {
    value = initialValue;
   }

  public AtomicInteger() { }

  private static final long valueOffset;

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

// jdk.internal.misc.Unsafe
public final class Unsafe {
   ...
  public native long objectFieldOffset(Field f);
}

Unsafe_ObjectFieldOffset 的完结是调用 find_field_offset 进行，其将进行 Field 的非空查看，以及 Klass 的转化。最后还要转换成 InstanceKlass 实例，并获取其间的 field_offset 并回来。

// unsafe.cpp
UNSAFE_ENTRY(jlong, Unsafe_ObjectFieldOffset(JNIEnv *env, jobject unsafe, jobject field))
 UnsafeWrapper("Unsafe_ObjectFieldOffset");
 return find_field_offset(field, 0, THREAD);
UNSAFE_END
  
jint find_field_offset(jobject field, int must_be_static, TRAPS) {
 if (field == NULL) {
  THROW_0(vmSymbols::java_lang_NullPointerException());
  }

 oop reflected  = JNIHandles::resolve_non_null(field);
 oop mirror   = java_lang_reflect_Field::clazz(reflected);
 Klass* k   = java_lang_Class::as_Klass(mirror);
 int slot    = java_lang_reflect_Field::slot(reflected);
 int modifiers  = java_lang_reflect_Field::modifiers(reflected);

 if (must_be_static >= 0) {
  int really_is_static = ((modifiers & JVM_ACC_STATIC) != 0);
  if (must_be_static != really_is_static) {
   THROW_0(vmSymbols::java_lang_IllegalArgumentException());
   }
  }

 int offset = InstanceKlass::cast(k)->field_offset(slot);
 return field_offset_from_byte_offset(offset);
}

// instanceKlass.h
class InstanceKlass: public Klass {
  ...
 public:
 int   field_offset    (int index) const { return field(index)->offset(); }

  // Casting from Klass*
 static InstanceKlass* cast(Klass* k) {
  assert(k == NULL || k->is_klass(), "must be");
  assert(k == NULL || k->oop_is_instance(), "cast to InstanceKlass");
  return (InstanceKlass*) k;
  }
}

3. compareAndSwap

后面是在写值的时候持续调用 Unsafe，关键在于其 native 侧的完结。

比如 compareAndSet() 将传递实例自身，value 的内存相对地址，当时的等待值和方针的更新值四者传递给 Unsafe：

回来 false 表明当时的值并非等待值，无法完结更新
回来 true 表明更新成功

// java.util.concurrent.atomic.AtomicInteger
public class AtomicInteger extends Number implements java.io.Serializable {
  private static final long valueOffset;
   ...

  public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
   }
}

// jdk.internal.misc.Unsafe
public final class Unsafe {
   ...
  public final native boolean compareAndSwapInt(Object o, long offset,
                         int expected,
                         int x);
}

native 的完结是 compareAndSwapInt()。

先经过 JNIHandles 找到 AtomicInteger 实例的地址 oop
将该 oop 和 value 的相对地址作为参数调用 index_oop_from_field_offset_long() 并得到 value 的内存绝对地址 aadr
将更新值、addr 和等待值作为参数调用 cmpxchg() 持续

// 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
  
inline void* index_oop_from_field_offset_long(oop p, jlong field_offset) {
 jlong byte_offset = field_offset_to_byte_offset(field_offset);
#ifdef ASSERT
 if (p != NULL) {
  assert(byte_offset >= 0 && byte_offset <= (jlong)MAX_OBJECT_SIZE, "sane offset");
  if (byte_offset == (jint)byte_offset) {
   void* ptr_plus_disp = (address)p + byte_offset;
   assert((void*)p->obj_field_addr<oop>((jint)byte_offset) == ptr_plus_disp,
       "raw [ptr+disp] must be consistent with oop::field_base");
   }
  jlong p_size = HeapWordSize * (jlong)(p->size());
  assert(byte_offset < p_size, err_msg("Unsafe access: offset " INT64_FORMAT " > object's size " INT64_FORMAT, byte_offset, p_size));
  }
#endif
 if (sizeof(char*) == sizeof(jint))  // (this constant folds!)
  return (address)p + (jint) byte_offset;
 else
  return (address)p +    byte_offset;
}

cmpxchg() 的完结在 atomic.cpp 中，其间 value 的地址用 volatile 关键字描绘，意味着方针数据的变化将立即反映到内存、并要求读取时应当从内存中取出。

首要计算得到 value 地址的当时数值，即 cur_as_bytes[offset]
倘若当时数值等于等待值 compare_value：
- 调用 cmpxchg CPU 指令将 dest_int 地址对应的数值履行等待值为 cur，更新值为 new_val 的 CAS 操作
- 该操作回来的是等待值的话，表明更新成功，跳过循环并回来等待值。Unsafe_CompareAndSwapInt() 将收到匹配等待值的成果，并向 Java 侧回来 true
- 反之，将 cur 更新为 CPU 指令回来的当时值，再持续下一次循环，直到成功为止
反之即不等于等待值，直接回来
- Unsafe_CompareAndSwapInt() 将收到不匹配等待值的成果，并向 Java 侧回来 false

// atomic.cpp
jbyte Atomic::cmpxchg(jbyte exchange_value, volatile jbyte* dest, jbyte compare_value) {
 uintptr_t dest_addr = (uintptr_t)dest;
 uintptr_t offset = dest_addr % sizeof(jint);
  
 volatile jint* dest_int = (volatile jint*)(dest_addr - offset);
 jint cur = *dest_int;
  
 jbyte* cur_as_bytes = (jbyte*)(&cur);
 jint new_val = cur;
  
 jbyte* new_val_as_bytes = (jbyte*)(&new_val);
 new_val_as_bytes[offset] = exchange_value;
  
 while (cur_as_bytes[offset] == compare_value) {
  jint res = cmpxchg(new_val, dest_int, cur);
  if (res == cur) break;
  cur = res;
  new_val = cur;
  new_val_as_bytes[offset] = exchange_value;
  }
 return cur_as_bytes[offset];
}

事实上，Android 中 AtomicInteger 的完结稍稍不同，没有只用 Unsafe 而是采用了 VarHandle，这里不再打开。

// android/libcore/ojluni/src/main/java/java/
// util/concurrent/atomic/AtomicInteger.java
public class AtomicInteger extends Number implements java.io.Serializable {
   ...
  public final boolean compareAndSet(int expectedValue, int newValue) {
     // Android-changed: Using VarHandle instead of Unsafe
     // return U.compareAndSetInt(this, VALUE, expectedValue, newValue);
     return VALUE.compareAndSet(this, expectedValue, newValue);
   }
}

达观锁

利用 CAS 机制能够完结一个达观锁，即无需加锁可完结多个线程一起读取、可是仅有一个线程能够成功写入数据，并导致其他要卸乳数据的线程回滚重试。

例如 Unsafe 经过上述的 compareAndSwapInt() 完结的自增 1 的原子操作的逻辑。

// java.util.concurrent.atomic.AtomicInteger
public class AtomicInteger extends Number implements java.io.Serializable {
   ...
  public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
   }
}

// jdk.internal.misc.Unsafe
public final class Unsafe {
   ...
  public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
      v = getIntVolatile(o, offset);
     } while (!compareAndSwapInt(o, offset, v, v + delta));
    return v;
   }
}

由于整个过程中不触及加/解锁的操作，达观锁也被称为无锁编程。

实质上说，达观锁其实不是“锁”，它仅仅是一个循环重试 CAS 的算法而已！

缺点

CAS 机制能够高效地完结原子操作，但仍不完美：

循环时间长开支大：CAS 大量失利后长时间占用 CPU 资源，加大了体系性能开支
只能确保一个同享变量的原子操作：当对一个同享变量履行操作时，我们能够运用循环 CAS 的办法来确保原子操作，可是对多个同享变量操作时，循环 CAS 就无法确保操作的原子性
ABA 问题：CAS 机制实质上依赖值有没有发生变化的操作条件。可是假如值原来是 A、被改成变成了 B、最后又变回了 A，那么运用 CAS 进行查看时会发现它的值没有发生变化进行了操作，可是实际上却变化了，这其实违反了约定的条件。

Java 1.5 开始供给了一个类AtomicStampedReference 来处理该问题，其供给的 compareAndSet() 会首要查看当时引用是否等于预期引用，并且当时标志是否等于预期标志，假如全部相等，才进行值的更新操作

结语

能够看到无论是初始化还是写值都是经过 Unsafe 调度完结，整理了如下的流程图以加深理解：

AtomicInteger 经过静态办法 getUnsafe() 取得 Unsafe 实例

接着经过 Unsafe 实例的 native 办法 objectFieldOffset() 传入运用 volatie 修饰的数值 value 的 Field 字段得到其内存相对地址
关键的 compareAndSet() 亦由 Unsafe 调度，即 native 办法 compareAndSwapInt()。主要是传入 AtomicInteger 实例，value 内存相对地址，等待值以及更新值。

native 的完结由 atomic.cpp 的 cmpxchg() 完结，当时 value 内存地址回来的值匹配等待值的话，履行更新操作；反之，直接回来 false。

履行更新的操作采用 cmpxchg CPU 指令，假如得到的值不符合等待值的话，更新等待值持续下一次循环，直到匹配为止。

参考文章

Java双刃剑之Unsafe类详解
通俗易懂各种锁及其Java完结！
C/C++ 中 volatile 关键字详解
一文完全搞懂CAS完结原理
JAVA CAS完结原理与运用

全方位探究似懂非懂的 CAS 机制～

前言

源码解读

1. Unsafe

2. valueOffset & value

3. compareAndSwap

达观锁

缺点

结语

参考文章

相关文章

Go 原生插件使用问题全解析

Android实现动态换肤

去哪儿旅行微服务架构实践

一文搞懂 Android 手势监听

作者信息