极客时间 ——《Java并发编程实战》 21 | 原子类：无锁工具类的典范

之前第一个讲竞态条件的时候有个累加器的例子屡屡被提到：

public class Test{
  long count = 0;
  void add10k() {
    int idx = 0;
    while(idx++ < 10000) {
      count += 1;
    }
  }
}

add10k 方法存在着竞态条件，count += 1 这个操作是一个组合操作，需要保证其原子性，但是这个方法没有使用同步机制，所以在并发环境下会出现问题。count 的可见性也会出现问题，可见性可以使用 volatile 解决，原子性之前我们一直使用的是 互斥锁方案。

对于只有一个变量的原子操作我们可以使用原子类来解决，在 《JCIP Java 并发编程实战》 中第一个例子就是使用 AtomicLong 这个原子变量来替换基础类型变量 long，这种方案是无锁方案，JDK 中的原子类就是在无锁方案的基础上提炼而来。

下面的代码中，将 long 替换为 AtomicLong，原来的 count += 1换成了 count.getAndIncrement()，只需要改动这两处，就可以使 add10K() 方法变成线程安全的：

public class Test {
  AtomicLong count = new AtomicLong(0);
  void add10K() {
    int idx = 0;
    while(idx++ < 10000) {
      count.getAndIncrement();
    }
  }
}

无锁方案相比于使用互斥锁方案，最大的好处就是性能，如果使用互斥锁，需要执行加锁、解锁操作，同时无法获取到锁的线程进入阻塞状态，线程切换还有额外消耗，并且降低伸缩性，将并行方法串行化。

相比之下，无锁方案没有任何额外的消耗，它是如何做到呢？

无锁方案的实现原理

原子性类性能高的原因很简单 —— 硬件支持。CPU 为了解决并发问题，提供了 CAS 指令（Compare And Swap 比较并交换）。

CAS 指令包含3个参数：①共享变量内存地址 A、②用于比较的值 B、③共享变量的新值 C。并且只有当内存地址 A 处的值等于 B 时，才能将内存中地址A 处的值更新为 C。作为一条 CPU 指令，CAS 指令本身是原子性的。

作者给出了一个 CAS 指令的伪代码用于说明：下面的模拟程序中有两个参数：

期望值 expect
需要些入的新值 newValue

只有当 count 的值 == 期望值 expect 时，才会将 count 更新为 newValue。

class SimulatedCAS {
  int count;
  synchronized int cas(int expect int newValue) {
    // 读取目前count的值
    int curValue = count;
    // 比较count的值是否和期望值相等
    if(curValue == expect) {
      // 如果相等，更新count值
      count = newValue;
    }
    // 返回写入前的值
    return curValue;
  }
}

继续思考上面那句：只有当 count 的值 == 期望值 expect 时，才会将 count 更新为 newValue。

对于之前累加器的例子， count += 1 的核心问题是内存中 count 的当前值 A 计算出来的 count +=1 的结果是 A+1 ，当将 A+1 写入内存时，很可能此时内存中的 count 已经被其他线程更新了，这样就会导致错误地覆盖其他线程写入的值。

只有当内存中的 count 的值 等于期望值 A 时，才能将内存中的 count 更新为 A+1 ，这就是 CAS 的语义。

使用 CAS 解决并发问题，一般都伴随着自旋。所谓自旋，指的就是循环尝试。

例如需求是「实现一个线程安全的 count += 1 操作」，使用 CAS + 自旋的实现方案如下所示：

计算 newValue = count+1 ，如果 cas(count,newValue) 返回的值 != count ，则意味着线程在执行完①处代码之后，执行②处代码之前，count 的值被其他线程更新过。

此时需要采用自旋方案：重新读 count 最新的值然后来计算 newValue，并尝试再次更新，直到更新成功。

public class SimulatedCAS {
    volatile int count;

    // 实现count+=1
    void addOne() {
        int newValue;
        do {
            newValue = count + 1; // ①
        } while (count != cas(count, newValue)); // ②
    }

    synchronized int cas(int expect, int newValue) {
        // 读取当前count的值
        int curValue = count;
        // 比较当前count是否和期望值相等
        if (curValue == expect) {
            count = newValue;
        }
        // 返回写入前的值
        return curValue;
    }
}

通过上面的代码可以看到，CAS 这种方案完全没有加锁、解锁操作。即使两个线程同时执行 addOne 方法，也不会有线程被阻塞，所以相对于使用互斥锁，这种方案的性能好了很多。

但是 CAS 方案中存在一个 ABA 问题，什么是 ABA 问题呢？我自制了一个简单的示意图：

之前提到了，如果 cas(count,newValue) 的返回值不等于 之前内存中的 count 也就是示意图中的 99，那么意味着线程在执行完 ①处代码之后，执行 ②处代码之前，count 的值被其他线程更新过。

但是 cas(count,newValue) 的返回值与当前内存中的 count 值一致，也并不能一定保证这个值没有被其他线程更新过，可能是被更新过之后又被更新为了之前的值，count 被线程 T2 更新为了 100，又被 T3更新回 99，这样虽然线程 T1 看到的 count 一直是 99，但是其实count 的值已经被更新过了一次，这就是 ABA问题。

虽然大多数情况下我们并不关心 ABA 问题，例如数值的原子递增，但是当 ABA 问题发生时，虽然 count 的值相等，但是可能有其他的属性发生了变化，所以在使用 CAS 方案时，一定要进行 check。【这里的check 指的是什么？关键属性的验证吗？】

Java 如何实现原子化的 count += 1

下面分析Java 中的 AtomicLong类的 getAndIncrement 方法怎样使用 CAS 实现原子化的 count += 1。

JDK8中，getAndIncrement会调用 unsafe.getAndAddLong 方法,这里使用 this 和 valueOffSet 两个参数可以唯一确定共享变量的内存地址。

      /**
     * Atomically increments by one the current value.
     *
     * @return the previous value
     */
    public final long getAndIncrement() {
        return unsafe.getAndAddLong(this, valueOffset, 1L);
    }

下面是 unsafe.getAndAddLong 的源码：该方法首先在**内存**中读取共享变量的值，之后循环调用 compareAndSwapLong 尝试给共享变量赋值，直到成功为止。

compareAndSwapLong 是一个 native方法，只有当内存中共享变量的值等于 expected 时，才会将共享变量值更新为 x 并返回true，否则返回 false。

compareAndSwapLong 的语义和 CAS 指令的语义区别只是返回值不同。

    public final long getAndAddLong(Object o, long offset, long delta) {
        long v;
        do {
            // 读取内存中的值
            v = this.getLongVolatile(o, offset);
        } while(!this.compareAndSwapLong(o, offset, v, v + delta));

        return v;
    }
    // 原子性地将变量更新为 x ，条件是内存中的值等于 expect，更新成功返回 true
    public final native boolean compareAndSwapLong(Object o, long offset, long expect, long x);

另外需要注意的是，getAndAddLong 方法的实现，基本就是 CAS 使用的经典范例，所以将这个例子抽象提取后，就是无锁方法的使用范式，它在很多无锁程序中都会出现。

Java 提供的原子类中的 CAS 一般被实现为 compareAndSet()，compareAndSet 的语义和 CAS 的语义之间的差别仅仅是返回值的不同，compareAndSet 中如果变量更新成功返回 ture ，失败返回 false，CAS 返回的则是写入前的值。

do {
  // 获取当前值
  oldValue = xxx;
  // 根据当前值计算新值
  newValue = oldValue ...;
} while(!compareAndSet(oldValue,newValue));

原子类概览

JDK 并发包中提供的原子类内容很丰富，可以将其分为五类：

原子化的基本数据类型
原子化的引用数据类型
原子化数组
原子化对象属性更新器
原子化累加器

1. 原子化的基本数据

相关实现包括：AtomicBoolean、AtomicLong、AtomicInteger，主要方法如下：


getAndIncrement() //原子化i++
getAndDecrement() //原子化的i--
incrementAndGet() //原子化的++i
decrementAndGet() //原子化的--i
//当前值+=delta，返回+=前的值
getAndAdd(delta) 
//当前值+=delta，返回+=后的值
addAndGet(delta)
//CAS操作，返回是否成功
compareAndSet(expect, update)
//以下四个方法
//新值可以通过传入func函数来计算
getAndUpdate(func)
updateAndGet(func)
getAndAccumulate(x,func)
accumulateAndGet(x,func)

原子化的对象引用类型

相关实现：AtomicReference、AtomicStampedReference、AtomicMarkableReference，利用它们可以实现对象引用的原子化更新。

AtomicReference提供的方法和原子化基本数据类型差不多，需要注意的是，对象引用更新需要重点关注 ABA 问题，AtomicStampedReference 和 AtomicMarkableReference 这两个原子类可以解决 ABA 问题。

解决 ABA 问题的思路很简单：给对象增加一个版本号字段就可以，这和之前介绍的乐观锁机制很类似，每次执行 CAS 操作，附加再更新一个版本号，只要保证版本号是递增的，即便 A变成B之后再变回A，版本号也是会发生改变的。

AtomicStampedReference 实现的 CAS 方法就增加了版本号参数：

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

AtomicMarkableReference 实现机制更简单，将版本号简化成了一个 Boolean 值：

    public boolean compareAndSet(V       expectedReference,
                                 V       newReference,
                                 boolean expectedMark,
                                 boolean newMark) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedMark == current.mark &&
            ((newReference == current.reference &&
              newMark == current.mark) ||
             casPair(current, Pair.of(newReference, newMark)));
    }

3.原子化数组

相关实现：AtomicIntegerArray、AtomicLongArrray、AtomicReferenceArray，利用这些原子类，可以原子化地更新数组里的每一个元素。

这些类提供的方法和原子化基本数据类型的区别是：每个方法多了一个数组索引参数。

4.原子化对象属性更新器

相关实现：AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater，利用它们可以原子化地更新对象属性，这三个方法都是利用反射机制实现的，创建更新器的方法如下：

    @CallerSensitive
    public static <U> AtomicLongFieldUpdater<U> newUpdater(Class<U> tclass,
                                                           String fieldName) {
        Class<?> caller = Reflection.getCallerClass();
        if (AtomicLong.VM_SUPPORTS_LONG_CAS)
            return new CASUpdater<U>(tclass, fieldName, caller);
        else
            return new LockedUpdater<U>(tclass, fieldName, caller);
    }

需要注意的是，更新的对象属性必须是 volatile 类型，这样才能保证可见性，如果对象属性不是 volatile 类型，则 newUpdater() 方法抛出 IllegalArgumentException 异常。

newUpdate() 方法参数值有类信息，没有对象引用，但是更新对象的属性是一定要获取对象引用的，这个参数是怎也传入的呢？是在原子操作的方法中传入的。

例如 compareAndSet() 这个原子操作，相比原子化的基本数据类型多了一个对象引用 obj。原子化对象属性更新器的相关方法，相比原子化基本数据类型仅仅多了对象引用参数。

public abstract boolean compareAndSet(T obj, long expect, long update);

5.原子化累加器

DoubleAccumulator、DoubleAdder、LongAccumulator、LongAdder 这4个类仅仅用来执行计数累加操作，相比原子化的基本数据类型，优势是速度更快，但是不支持 compareAndSet() 方法，如果仅需要做计数器功能，使用原子化累加器性能更好。