CAS操作

什么是 CAS

CAS（Compare And Swap，比较并交换），通常指的是这样一种原子操作：针对一个变量，首先比较它的内存值与某个期望值是否相同，如果相同，就给它赋一个新值。CAS 的逻辑用伪代码描述如下：

if (value == expectedValue) {
   value = newValue;
}

以上伪代码描述了一个由比较和赋值两阶段组成的复合操作，CAS 可以看作是它们合并后的整体

——一个不可分割的原子操作，并且其原子性是直接在硬件层面得到保障的。

CAS可以看做是乐观锁（对比数据库的悲观、乐观锁）的一种实现方式，Java原子类中的递增操作就通过CAS自旋实现的。

CAS是一种无锁算法，在不使用锁（没有线程被阻塞）的情况下实现多线程之间的变量同步。

CAS应用

在 Java 中，CAS 操作是由 Unsafe 类提供支持的，该类定义了三种针对不同类型变量的 CAS 操作，

public final native boolean compareAndSwapObject(Object o, long offset, Object expected, Object x);

public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);

public final native boolean compareAndSwapLong(Object o, long offset, long expected, long x);

它们都是 native 方法，由 Java 虚拟机提供具体实现，这意味着不同的 Java 虚拟机对它们的实现可能会略有不同。

以 compareAndSwapInt 为例，Unsafe 的 compareAndSwapInt 方法接收 4 个参数，分别是：对象实例、内存偏移量、字段期望值、字段新值。该方法会针对指定对象实例中的相应偏移量的字段执行 CAS 操作。

public class UnsafeFactory {
    /**
     * 获取 Unsafe 对象 * @return
     */
    public static Unsafe getUnsafe() {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            return (Unsafe) field.get(null);

        } catch (Exception e) {
            e.printStackTrace();

        }
        return null;

    }

    /**
     * 获取字段的内存偏移量  
     * @param unsafe  
     * @param clazz  
     * @param fieldName  
     * @return
     */
    public static long getFieldOffset(Unsafe unsafe, Class clazz, String fieldNam e) {
        try {
            return unsafe.objectFieldOffset(clazz.getDeclaredField(fieldName));

        } catch (NoSuchFieldException e) {
            throw new Error(e);

        }
    }
}

测试

针对 entity.x 的 3 次 CAS 操作，分别试图将它从 0 改成 3、从 3 改成 5、从 3 改成 8。执行结果如下：

CAS 本质是一条CPU 的原子指令，由操作系统硬件来保证。不同操作系统和不同CPU会有不同的 实现。

CAS 在 Java 语言中的应用

在 Java 编程中我们通常不会直接使用到 CAS，都是通过 JDK 封装好的并发工具类来间接使用的，这些并发工具类都在java.util.concurrent包中。

J.U.C 是java.util.concurrent的简称，也就是大家常说的 Java 并发编程工具包，面试常考，非常非常重要。

在java.util.concurrent.atomic包里提供了一组原子操作类：

• 基本类型：AtomicInteger、AtomicLong、AtomicBoolean；
• 引用类型：AtomicReference、AtomicStampedRerence、AtomicMarkableReference；
• 数组类型：AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray
• 对象属性原子修改器：AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater
• 原子类型累加器（jdk1.8增加的类）：DoubleAccumulator、DoubleAdder、 LongAccumulator、LongAdder、Striped64

原子更新基本类型

以AtomicInteger为例总结常用的方法

    //以原子的方式将实例中的原值加1，返回的是自增前的旧值；
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

    //getAndSet(int newValue)：将实例中的值更新为新值，并返回旧值； 、
    public final boolean getAndSet(boolean newValue) {
        boolean prev;
        do {
            prev = get();
        } while (!compareAndSet(prev, newValue));
         return prev;

    }
    //incrementAndGet() ：以原子的方式将实例中的原值进行加1操作，并返回最终相加后的结果；
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;

    }

    //addAndGet(int delta) ：以原子方式将输入的数值与实例中原本的值相加，并返回最后的结 果；
    public final int addAndGet(int delta) {
        return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
    }

测试

public class AtomicIntegerTest {
    static AtomicInteger sum = new AtomicInteger(0);

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            new Thread(() ->{
                for (int j = 0; j < 10000; j++) {
                    // 原子自增 CAS 
                    sum.incrementAndGet();
                }
            }).start();
        } 
        try {
            Thread.sleep(3000);

        } catch (InterruptedException e) {
            e.printStackTrace();

        }
        System.out.println(sum.get());
    }
}

incrementAndGet()方法通过CAS自增实现，如果CAS失败，自旋直到成功+1。

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

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

CAS缺陷

CAS 虽然高效地解决了原子操作，但是还是存在一些缺陷的，主要表现在三个方面：

• 自旋 CAS 长时间地不成功，则会给 CPU 带来非常大的开销
• 只能保证一个共享变量原子操作
• ABA 问题

LongAdder/DoubleAdder

   CAS在高并发下，会出现大量失败并不断自旋的情况，此时自旋会成为瓶颈。 这就是LongAdder引入的初衷——解决高并发环境下AtomicInteger，AtomicLong的自旋瓶颈问题。

LongAdder的基本思路就是分散热点，将value值分散到一个数组中，不同线程会命中到数组的不同槽中，各个线程只对自己槽中的那个值进行CAS操作，这样热点就被分散了，冲突的概率就小很多。如果要获取真正的long值，只要将各个槽中的变量值累加返回。

LongAccumulator

LongAccumulator是LongAdder的增强版。LongAdder只能针对数值的进行加减运算，而LongAccumulator提供了自定义的函数操作。其构造函数如下：

通过LongBinaryOperator，可以自定义对入参的任意操作，并返回结果（LongBinaryOperator

接收2个long作为参数，并返回1个long）。LongAccumulator内部原理和LongAdder几乎完全一样，都是利用了父类Striped64的longAccumulate方法。

public static void main(String[] args) throws InterruptedException {
    // 累加 x+y
    LongAccumulator accumulator = new LongAccumulator((x, y) -> x + y, 0);
    ExecutorService executor = Executors.newFixedThreadPool(8); 
    // 1到9累加 
    IntStream.range(1, 10).forEach(i -> executor.submit(() -> accumulator.accumulate(i)));
    Thread.sleep(2000);
    System.out.println(accumulator.getThenReset());
}

ABA问题的解决方案

Java提供了相应的原子引用类AtomicStampedReference<V>；reference即我们实际存储的变量，stamp是版本，每次修改可以通过+1保证版本唯一性。这样就可以保证每次修改后的版本也会往上递增。

补充：AtomicMarkableReference可以理解为上面AtomicStampedReference的简化版，就是不关心修改过几次，仅仅关心是否修改过。因此变量mark是boolean类型，仅记录值是否有过修改。