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

2020-10-28   15 次阅读


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

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 方法,这里使用 thisvalueOffSet 两个参数可以唯一确定共享变量内存地址

      /**
     * 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 , 失败返回 falseCAS 返回的则是写入前的值。

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

原子类概览

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

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

image-20200811092934933

1. 原子化的基本数据

相关实现包括:AtomicBooleanAtomicLongAtomicInteger,主要方法如下:


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)

原子化的对象引用类型

相关实现:AtomicReferenceAtomicStampedReferenceAtomicMarkableReference,利用它们可以实现对象引用的原子化更新

AtomicReference提供的方法和原子化基本数据类型差不多,需要注意的是,对象引用更新需要重点关注 ABA 问题,AtomicStampedReferenceAtomicMarkableReference 这两个原子类可以解决 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.原子化数组

相关实现:AtomicIntegerArrayAtomicLongArrrayAtomicReferenceArray,利用这些原子类,可以原子化地更新数组里的每一个元素

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

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

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

    @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 异常。

image-20200811100121969

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

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

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

5.原子化累加器

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

总结

无锁方案相对于互斥锁,优点很多:

  • 性能好
  • 不会出现死锁问题(但是可能出现活锁和饥饿,因为自旋会反复重试)

Java 提供的原子类大部分都实现了 compareAndSet() 方法,基于 compareAndSet,你可以构建自己的无锁数据结构,但是不建议这样做,因为无锁算法没有想象的那么简单,还是交给大佬去做,我们使用就好。

Java 提供的原子类可以解决一些简单的原子性问题,但是只能针对一个变量如果是多个变量,哪怕是多个原子变量,也不能保证一组操作是原子性的。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。