转载

CAS原理分析及ABA问题详解

CAS 即 Compare And Swap 的缩写，翻译成中文就是 比较并交换 ，其作用是让CPU比较内存中某个值是否和预期的值相同，如果相同则将这个值更新为新值，不相同则不做更新，也就是CAS是 原子性 的操作，其实现方式是通过借助 C/C++ 调用CPU指令完成的，所以效率很高。

CAS 的原理很简单，这里使用一段 Java 代码来描述

public boolean compareAndSwap(int value, int expect, int update) {
//        如果内存中的值value和期望值expect一样 则将值更新为新值update
    if (value == expect) {
        value = update;
        return true;
    } else {
        return false;
    }
}

大致过程是将内存中的值、我们的期望值、新值交给CPU进行运算，如果内存中的值和我们的期望值相同则将值更新为新值，否则不做任何操作。这个过程是在CPU中完成的，这里不好描述CPU的工作过程，就拿Java代码来描述了。

Unsafe源码分析

Java是在 Unsafe(sun.misc.Unsafe) 类实现 CAS 的操作，而我们知道Java是无法直接访问操作系统底层的API的(原因是Java的跨平台性限制了Java不能和操作系统耦合)，所以Java并没有在 Unsafe 类直接实现 CAS 的操作，而是通过 JDI(Java Native Interface) 本地调用 C/C++ 语言来实现 CAS 操作的。

Unsafe 有很多个 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);

我们拿 public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5); 进行分析，这个方法是比较内存中的一个值(整型)和我们的期望值(var4)是否一样，如果一样则将内存中的这个值更新为 var5 ，参数中的 var1 是值所在的对象， var2 是值在对象(var1)中的内存偏移量， 参数var1和参数var2是为了定位出值所在内存的地址 。

Unsafe.java在这里发挥的作用有：

将对象引用、值在对象中的偏移量、期望的值和欲更新的新值传递给 Unsafe.cpp
如果值更新成功则返回 true 给开发者，没有更新则返回 false

Unsafe.cpp在这里发挥的作用有：

接受从 Unsafe 传递过来的对象引用、偏移量、期望的值和欲更新的新值，根据对象引用和偏移量 计算出值的地址 ，然后将值的地址、期望的值、欲更新的新值传递给CPU
如果值更新成功则返回 true 给 Unsafe.java ，没有更新则返回 false

CPU在这里发挥的作用：

接受从 Unsafe.cpp 传递过来的地址、期望的值和欲更新的新值，执行指令 cmpxchg ，比较地址中的值是否和期望的值一样，一样则将值更新为新的值，不一样则不做任何操作
将操作结果返回给 Unsafe.cpp

CAS的缺点

CAS 虽然高效的实现了原子性操作，但是也存在一些缺点，主要表现在以下三个方面。

ABA问题

在多线程场景下 CAS 会出现 ABA 问题，关于ABA问题这里简单科普下，例如有2个线程同时对同一个值(初始值为A)进行CAS操作，这三个线程如下

线程1，期望值为A，欲更新的值为B
线程2，期望值为A，欲更新的值为B

线程 1 抢先获得CPU时间片，而线程 2 因为其他原因阻塞了，线程 1 取值与期望的A值比较，发现相等然后将值更新为B，然后这个时候 出现了线程 3 ，期望值为B，欲更新的值为A ，线程3取值与期望的值B比较，发现相等则将值更新为A，此时线程 2 从阻塞中恢复，并且获得了CPU时间片，这时候线程 2 取值与期望的值A比较，发现相等则将值更新为B，虽然线程 2 也完成了操作，但是线程 2 并不知道值已经经过了 A->B->A 的变化过程。

ABA 问题带来的危害：

小明在提款机，提取了50元，因为提款机问题，有两个线程，同时把余额从100变为50

线程1（提款机）：获取当前值100，期望更新为50，

线程2（提款机）：获取当前值100，期望更新为50，

线程1成功执行，线程2某种原因block了，这时，某人给小明汇款50

线程3（默认）：获取当前值50，期望更新为100，

这时候线程3成功执行，余额变为100，

线程2从Block中恢复，获取到的也是100，compare之后，继续更新余额为50！！！

此时可以看到，实际余额应该为100（100-50+50），但是实际上变为了50（100-50+50-50）这就是ABA问题带来的成功提交。

解决方法：

在变量前面加上版本号，每次变量更新的时候变量的 版本号都 +1 ，即 A->B->A 就变成了 1A->2B->3A 。

循环时间长开销大

如果 CAS 操作失败，就需要循环进行 CAS 操作(循环同时将期望值更新为最新的)，如果长时间都不成功的话，那么会造成CPU极大的开销。

这种循环也称为自旋

解决方法：

限制自旋次数，防止进入死循环。

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

CAS 的原子操作只能针对一个共享变量。

解决方法：

如果需要对多个共享变量进行操作，可以使用加锁方式(悲观锁)保证原子性，或者可以把多个共享变量合并成一个共享变量进行 CAS 操作。

CAS的应用

我们知道 CAS 操作并不会锁住共享变量，也就是一种 非阻塞 的同步机制， CAS 就是乐观锁的实现。

乐观锁
乐观锁 总是假设最好的情况，每次去操作数据都认为不会被别的线程修改数据， 所以在每次操作数据的时候都不会给数据加锁 ，即在线程对数据进行操作的时候， 别的线程不会阻塞 仍然可以对数据进行操作，只有在需要更新数据的时候才会去判断数据是否被别的线程修改过，如果数据被修改过则会拒绝操作并且返回错误信息给用户。
悲观锁
悲观锁 总是假设最坏的情况，每次去操作数据时候都认为会被的线程修改数据， 所以在每次操作数据的时候都会给数据加锁 ，让别的线程无法操作这个数据，别的线程会一直阻塞直到获取到这个数据的锁。这样的话就会影响效率，比如当有个线程发生一个很耗时的操作的时候，别的线程只是想获取这个数据的值而已都要等待很久。

Java 利用 CAS 的乐观锁、原子性的特性高效解决了多线程的安全性问题，例如JDK1.8中的集合类 ConcurrentHashMap 、关键字 volatile 、 ReentrantLock 等。

原文 http://ddnd.cn/2019/03/13/java-cas/

正文到此结束