今天要介绍一下无锁策略Compare And Set，简称CAS。它通过一种比较交换的技术来鉴别线程冲突，一旦检测到冲突发生，就重试当前操作直到没有冲突为止。

CAS

无锁的特点：

• 没有锁竞争，性能高
• 对死锁天然免疫，更安全

CAS底层依赖于CPU的原子指令，幸运的是，现代绝大多数CPU都已支持这个指令。
在Java中，主要通过Unsafe类中的compareAndSwap系列方法来调用CAS指令：

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

atomic包

Java1.5中新增了atomic包，提供了大量的原子操作。
以AtomicInteger为例，它提供了一个原子递增的计数器：

    static void incr() throws InterruptedException {
        AtomicInteger incr = new AtomicInteger();
        new Thread(()->{
            for(int i = 0; i < 10; i++) {
                incr.incrementAndGet();
            }
        }).start();
        new Thread(()->{
            for(int i = 0; i < 9; i++) {
                incr.decrementAndGet();
            }
        }).start();
        Thread.sleep(1000);
        System.out.println(incr.get());
    }

查看incrementAndGet方法的源码可以发现它调用的是Unsafe#getAndAddInt方法：

    public final int getAndAddInt(Object o, long offset, int delta) {
        int v;
        do {
            v = getIntVolatile(o, offset);
        } while (!weakCompareAndSetInt(o, offset, v, v + delta));
        return v;
    }

方法实现中对CAS进行了循环操作，因为CAS可能会失败，需要重试。

其他原子操作类还有AtomicIntegerArray、AtomicBoolean、AtomicLong、AtomicReference等。

AtomicReference的ABA问题

AtomicReference可以保证你在修改对象引用时的线程安全性。
AtomicReference的使用有个小小的例外：当你获得对象当前数据后，在准备修改新值前，对象的值被其他线程连续修改了两次，而经过这两次修改后，对象的值又恢复为旧值A。这样，当前线程就无法正确判断这个对象究竟是否被修改过。或者其他线程修改了对象的引用，但新引用的值和旧对象一致，这样会导致ABA问题。
ABA问题可能会导致实际逻辑出错，要解决这个问题，可以使用AtomicStampedReference，它内部不仅维护了对象值，还维护了一个时间戳，同时他会对比对象的引用，从而又解决了ABA问题。

LongAdder

AtomicInteger中的CAS操作，如果竞争激烈，修改失败的概率就很高。在大量的修改失败时，这些原子操作就会进行多次循环尝试，性能会受到影响。
那么竞争激烈时怎么办呢？我们可以想到热点分离，也就是ConcurrentHashMap的思想。例如，可以将AtomicInteger的内部核心数据value分离成一个数组，每个线程访问时，通过哈希等算法映射到其中一个数字进行计数，而最终的计数结果则为这个数组的求和累加。
Java 8中新增了LongAdder类，正是基于这种思想。
不过LongAdder在最开始时并不会用数组处理，而是将所有数据都记录在一个base变量中。在多线程条件下，如果base没有冲突，则不扩展cell数组。一旦base修改发生冲突，就会初始化cell数组，执行新的策略。

LongAdder的另一个优化是解决了伪共享，不过需要添加JVM参数-XX:-RestrictContended.
关于伪共享，这里不展开讲了，参考：Java 伪共享的原理深度解析以及避免方法 (opens new window)

LongAdder还有一个增强版：LongAccumulator，它可以实现任意函数操作：

    // 以Long#max函数操作举例
    static void accumulator() throws InterruptedException {
        LongAccumulator accumulator = new LongAccumulator(Long::max, Long.MAX_VALUE);
        new Thread(()->{
            for(int i = 0; i < 100; i++) {
                accumulator.accumulate(new Random().nextLong());
            }
        }).start();
        Thread.sleep(1000);
        System.out.println(accumulator.get());
    }

总结

从加锁到无锁，这是一种编程思路的跃升。同时我们也看到JDK内部工具类的迭代，向更快、更安全的方向上进步。

祝你变得更强！