转载

一文彻底搞懂CAS

在上次的一文看懂CouncurrentHashMap 里面对CAS做了一个简单的介绍，之后打算着手写的java.util.concurrent包下的AQS以及其它一些都用到了CAS算法，因此今天就来深入研究一下，本文会介绍以下几个问题：

什么是CAS
ABA问题
CAS优化

正文

CAS可以看做是 乐观锁 的一种实现方式，Java原子类中的递增操作就通过CAS自旋实现的。

CAS全称 Compare And Swap （比较与交换），是一种无锁算法。在不使用锁（没有线程被阻塞）的情况下实现多线程之间的变量同步。

CAS涉及到三个属性：

需要读写的内存位置V
需要进行比较的预期值A
需要写入的新值U

CAS具体执行时，当且仅当预期值A符合内存地址V中存储的值时，就用新值U替换掉旧值，并写入到内存地址V中。否则不做更新。

一文彻底搞懂CAS

源码实现

那么在JDK源码里面又是如何实现CAS算法的呢？

CAS在JDK中是基于 Unsafe 类实现的，它是个跟底层硬件CPU指令通讯的复制工具类，源码如下：

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

我们一般用的比较多的就是上面3个本地方法，那么其中的参数又是什么意思呢？

在JDK中使用CAS比较多的应该是Atomicxxx相关的类，我们以 AtomicInteger 原子整型类为例，一起来分析下CAS底层实现机制:

AtomicInteger atomicInteger = new AtomicInteger();
atomicInteger.incrementAndGet();

incrementAndGet 是 Unsafe 类中的方法，它以原子方式对当前值加1，源码如下：

//以原子方式对当前值加1，返回的是更新后的值
 public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
 }

this
valueOffset
1

ps:最后还要+1是因为getAndAddInt方法返回的是更新前的值，而我们要的是更新后的值

valueOffset内存偏移量就是用来获取value的，如下所示：

//获取unfase对象
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
private volatile int value;//实际变量的值
    static {
        try {// 获得value在AtomicInteger中的偏移量
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

value 是由 volatile 关键字修饰的，为了保证在多线程下的内存可见性。

从static代码块可以看到 valueOffset 在类加载时就已经进行初始化了。

最后来看看 getAndAddInt 方法

//var1-对象、var2-内存偏移量、var4-增加的值
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;
    }
//根据偏移量获取value    
public native int getIntVolatile(Object var1, long var2);

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

源码也不是很复杂，主要搞懂各个参数的意思， getIntVolatile 方法获取到期望值 value 后去调用 compareAndSwapInt 方法，失败则进行重试。

那来看看 compareAndSwapInt 方法：

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

老实说我也不知道为什么参数要用var1、var2....表示，看起来的确不太好理解，咱们换个参数名来重新看一下：

unsafe.compareAndSwapInt(this, valueOffset, expect, update)

this：Unsafe 对象本身，需要通过这个类来获取 value 的内存偏移地址。
valueOffset：value 变量的内存偏移地址。
expect：期望更新的值。
update：要更新的最新值。

如果原子变量中的 value 值等于 expect，则使用 update 值更新该值并返回 true，否则返回 false。

ABA

CAS也不是万能的，它也存在着一些问题，比如ABA，我们来看看什么是ABA？

A-->B--->A 问题，假设有一个变量 A ，修改为B，然后又修改为了 A，实际已经修改过了，但 CAS 可能无法感知，造成了不合理的值修改操作。

为了解决这个 ABA 的问题，我们可以引入版本控制，例如，每次有线程修改了引用的值，就会进行版本的更新，虽然两个线程持有相同的引用，但他们的版本不同，这样，我们就可以预防 ABA 问题了。Java 中提供了 AtomicStampedReference 这个类，就可以进行版本控制了。

开销

CAS算法需要不断地自旋来读取最新的内存值，当长时间读取不到就会造成不必要的CPU开销。

Java 8推出了一个新的类 LongAdder ，他就是尝试使用分段CAS以及自动分段迁移的方式来大幅度提升多线程高并发执行CAS操作的性能！

简单来说就是如果发现并发更新的线程数量过多，就会开始施行 分段CAS的机制 ，也就是内部会搞一个Cell数组，每个数组是一个数值分段。这时，让大量的线程分别去对不同Cell内部的value值进行CAS累加操作，这样就把CAS计算压力分散到了不同的Cell分段数值中了！感兴趣的同学可以去查找相关资料。