转载

深入理解Java并发编程（四）：CAS操作以及jdk1.8后的优化

说到CAS之前，先来看看乐观锁与悲观锁：

悲观锁认为：每个线程在对一数据进行操作时，都会有其他线程来并发修改，所以在获取数据的时候就上锁来进行操作，synchronized和lock就是一种悲观锁的策略。也就是先上锁再操作。

乐观锁认为：每个线程在对以数据进行操作时，没有其他线程来并发修改，这样就其实是所有线程都去读取共享区的数据，然后在本地工作内存操作，最后看共享区的数据有无被其他线程更新。如果没有则将修改后的数据写入，如果有的话就根据具体实现具体分析（报错或者自动重试）。即直接操作

我们不难得出：悲观锁适合大量写操作的场景，先加锁可以保证写操作时数据的正确。乐观锁适合大量读操作的场景，不加锁的特点能够使其读操作的性能大大提升。

二、什么是CAS操作

CAS操作，全称Compare and Swap，比较并交换。

CAS操作就是一个虚拟机实现的原子操作（一条硬件操作指令，不可被中断的一个或一系列操作），功能是将旧值替换为新值，如果旧值没有改变则替换成功，否则替换失败。

一般使用锁的时候，线程获取锁是一种悲观锁策略。即假设每一次在访问共享资源都会产生冲突，所以当前线程获取到锁的同时就会阻塞其他线程获取该锁。

而 CAS操作是一种乐观锁策略 。它假设每一次在访问共享资源时都不会产生冲突，那不冲突就不会阻塞其他线程获取该锁，这样线程就不会出现阻塞停顿状态。Java使用CAS来鉴别线程是否出现冲突，出现冲突就重试当前操作直到没有冲突为止。线程只会收到操作失败的信号并进行原地自旋，并不会阻塞。

三、CAS操作的过程

CAS操作离不开这三个值(V, O, N)：

V：内存地址存放的实际值
O：旧值
N：即将更新的新值

当且仅当VO相同时，即旧值和内存中实际存放的值相同，这表明该值没有被其他线程更改过，此时CAS通过原子的方式将N赋给V，并返回true 。这是一个比较+更新操作，是原子操作。如果VO不相同，则该值已经被其他线程修改，不能把N赋给V，此时 不进行操作，返回false 。多个线程使用CAS操作一个变量时，只有一个线程会成功，并且成功更新，其余会失败（并不会阻塞其他线程）。失败的线程会重新尝试，也可以选择挂起线程。

synchronized存在线程竞争的情况下会出现线程阻塞和唤醒锁带来的性能问题，因为这是一种互斥同步（阻塞同步）。而CAS在竞争时如果失败，会进行一定的尝试，而并不是单纯的进行挂起唤醒操作，因此也叫非阻塞同步。

四、CAS的问题

CAS主要有以下三个问题：

1.ABA问题

CAS会检查共享内存的值有无变化，如果我们的共享内存值由A变成了B，可是又由B变回来了，此时CAS检查的时候发现共享内存的值并没有变化依然为A，但是实际上却是发生了变化。如果基本类型倒无所谓，引用类型就会有一些问题。

解决方案： 对其进行版本控制 ，这样A-B-A就变成1A-2B-3A了。Java1.5后atomic包提供的AromicStampedReference来解决ABA问题，具体封装在compareAndSet()中。compareAndSet()首先检查当前引用和当前标志与预期引用和预期标志是否相等，如果都相等，则以原子方式将引用值和标志的值设置为给定的更新值。

2.自旋时间过长

CAS是一种非阻塞同步，线程不会自己被挂起，而是不停的尝试而产生自旋现象（会死循环），自旋时间过长就会造成CPU很大的性能消耗。解决方案请看夏庆文

3.只能保证一个共享变量的原子操作

如果对多个共享变量进行操作，CAS不能保证其原子性。解决方案：利用对象整合多个变量，即一个类中的成员就是这几个变量，然后对这个对象进行CAS操作，这么做就能保证其原子性。atomic提供了AtomicReference来保证引用对象的原子性

五、jdk1.8对于CAS的优化

jdk1.8提供了一个LongAdder类，尝试使用 分段CAS 以及 自动分段迁移 的方式来大幅度替身多线程高并发执行CAS的性能。

1.分段CAS：

public class LongAdder extends Striped64 implements Serializable 
复制代码

其继承的Striped64里面有两个重要变量：

/**
 * Table of cells. When non-null, size is a power of 2.
 * cell数组，大小总是2的幂次方
 */
transient volatile Cell[] cells;
/**
 * Base value, used mainly when there is no contention, but also as
 * a fallback during table initialization races. Updated via CAS.
 * 基本值，主要在没有争用的情况下使用，在表的初始化的时候也作为一个基础值。通过CAS更新。
 */
transient volatile long base;
复制代码

如果发现并发更新的线程数量不是很多，就直接给base值进行累加。如果发现并发更新的数量过多，就开始实行分段CAS机制，系统把这些线程分配到不同的cell数组元素中。

public void add(long x) {
    Cell[] cs; long b, v; int m; Cell c;
    if ((cs = cells) != null || !casBase(b = base, b + x)) {
        boolean uncontended = true;
        if (cs == null || (m = cs.length - 1) < 0 ||
            (c = cs[getProbe() & m]) == null ||
            !(uncontended = c.cas(v = c.value, v + x)))
            longAccumulate(x, null, uncontended);
    }
}
复制代码

源码大概流程就是首先通过CAS进行对base值的更新，此时只有一个线程会成功，然后保存进sum。其余的线程进行cell数组计算下标并分配，每个线程依次的对cell的元素进行累加，最后将 base + sum[i] 求出最后的总和。

看一下LongAdder中的求cell数组总和的源码：

public long sum() {
    Cell[] cs = cells;
    long sum = base;
    if (cs != null) {
        for (Cell c : cs)
            if (c != null)
                sum += c.value;
    }
    return sum;
}
复制代码

假设当前有80个线程进行一变量的自增操作，cell数组长度为8，则每一组都有10个线程，每一组对cell数组的其中一个元素做自增，最后cell数组8个元素的值都为10，累加得到80。这就等于80个线程对i进行了80次自增操作。