并发第四弹 Java原子类中的CAS算法

CAS算法与原子类

先来介绍一下CAS算法。

compare and swap，比较并交换，CAS是一种无锁算法，在没有线程被阻塞的情况下实现变量的同步，即非阻塞同步。

CAS有3个操作数：内存值V、预期值A、更新值B。当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做或自旋。

CAS其实是一种先检查后操作模式的体现，先检查后操作的意思是：首先检查一个变量的值，然后再基于这个值做一些操作。先检查后操作模式必须是原子性的。

Java中提供了很多原子类，内部就是用CAS来实现的，例如AtomicInteger类，下面看看AtomicInteger::getAndIncrement()方法源码。

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;

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

可以看到，AtomicInteger::getAndIncrement()方法的原子性是交由Unsafe类完成的，JDK 的rt.jar 包中的Unsafe 类提供了硬件级别的原子性操作（即CAS中的先检查后操作模式的原子性是通过处理器提供的一个原子性指令来保证的），Unsafe 类中的方法大部分都是native 方法，它们使用JNI的方式访问本地C++实现库。

valueOffset是value属性相对于AtomicInteger对象的内存位置偏移量，下面看一下Unsafe::getAndAddInt方法源码（看注释即可一目了然）。

// 参数含义：对象、value偏移量
public native int getIntVolatile(Object var1, long var2);

// 参数含义：对象、value偏移量、期望值、更新值
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

//参数含义：对象、value偏移量、新增值
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;
}

Java提供的synchronized锁是重量级的，十分消耗性能，我们提倡能不用锁就不用锁，因此大部分情况下可以用CAS来替代synchronized，但CAS自身也有一些问题：

自旋消耗CPU，开销大；
只能保证一个变量的原子操作。解决办法：将多个变量封装成对象，通过 AtomicReference来保证原子性
ABA问题：在CAS比较过程中，另一个线程将内存值V由A改成了B,又由B改成了A。如果变量的值只能朝着一个方向转换，比如A->B->C，不构成环形，就不会存在问题ABA。JDK的AtomicStampedReference类给每个变量的状态值都配备了一个时间戳，从而避免了ABA 问题的产生。

AtomicReference 的使用如下所示。

import java.util.concurrent.atomic.AtomicReference;

public class AtomicReferenceTest {
    public static void main(String[] args) {
        Counter initCounter = new Counter();
        initCounter.count1 = 5;
        initCounter.count2 = 10;

        Counter counter = new Counter();
        counter.count1 = 2;
        counter.count2 = 3;

        AtomicReference<Counter> ar = new AtomicReference<>(initCounter);

        for(int i=0;i<5;i++){
            new Thread(()->{
                ar.getAndAccumulate(counter,(a,b)->{
                    a.count1 *= b.count1;
                    a.count2 += b.count2;
                   return a;
                });
            }).start();
        }

        Runtime.getRuntime().addShutdownHook(new Thread(()->{
            System.out.println(ar.get().count1);
            System.out.println(ar.get().count2);
        }));
    }
}

class Counter{
    int count1;
    long count2;
}

LongAdder与LongAccumulator

对于JDK提供的原子类，例如AtomicLong，在高并发的情况下由于大量线程竞争同一个资源，由于同时只会有一个线程竞争成功，这就造成了大量线程竞争失败后，会无限自旋重试CAS，这会白白浪费CPU 资源。因此JDK 8 新增了一个原子递增类LongAdder 用来克服在高并发下使用AtomicLong 的缺点。

既然AtomicLong 的性能瓶颈是由于过多线程同时去竞争一个变量而产生的，LongAdder的做法是把一个变量分解为多个变量，让同样多的线程去竞争多个资源。

LongAdder内部维护了一个惰性加载的原子性更新数组(Cell数组)和一个基值变量base，如果Cell数组是null并且并发线程较少时，所有的累加操作都是对base变量进行的。

LongAdder通过Cell数组维护多个Cell变量，每个Cell里面有一个初始值为0的long型变量，当多个线程在争夺同一个Cell原子变量时如果失败了，它并不是在当前Cell变量上一直自旋CAS重试，而是尝试在其他Cell变量上进行CAS重试，这个改变增加了当前线程重试CAS成功的可能性。

最后，在获取LongAdder当前值时，是把所有Cell变量的value值累加后再加上base 返回的。

LongAdder工作原理如下图所示。

另外还有一个LongAccumulator类，它的功能更强大，可以自定义初始值和计算方式，LongAdder其实是LongAccumulator的一个特例。

LongAdder和LongAccumulator的使用方式如下所示。

// 不能自定义初始值，只能进行累加
LongAdder la = new LongAdder();
// 可以自定义计算方式和初始值
LongAccumulator lac = new LongAccumulator((a,b)->{return a*b;},2);

for (int i=0;i<10;i++){
  new Thread(()->{
    la.increment();
    lac.accumulate(2);
  }).start();

}
Runtime.getRuntime().addShutdownHook(new Thread(()->{
  // 求和
  System.out.println(la.sum());
  System.out.println(lac.get());
}));