ABA问题的本质及其解决办法

CAS 的全称是 compare and swap，它是 java 同步类的基础，java.util.concurrent 中的同步类基本上都是使用 CAS 来实现其原子性的。

CAS 的原理其实很简单，为了保证在多线程环境下我们的更新是符合预期的，或者说一个线程在更新某个对象的时候，没有其他的线程对该对象进行修改。在线程更新某个对象（或值）之前，先保存更新前的值，然后在实际更新的时候传入之前保存的值，进行比较，如果一致的话就进行更新，否则失败。

注意，CAS 在 java 中是用 native 方法来实现的，利用了系统本身提供的原子性操作。

那么 CAS 在使用中会有什么问题呢？一般来说 CAS 如果设计的不够完美的话，可能会产生 ABA 问题，而 ABA 问题又可以分为两类，我们先看来看一类问题。

更多精彩内容且看：

区块链从入门到放弃系列教程 - 涵盖密码学, 超级账本, 以太坊,Libra, 比特币等持续更新
Spring Boot 2.X 系列教程: 七天从无到有掌握 Spring Boot- 持续更新
Spring 5.X 系列教程: 满足你对 Spring5 的一切想象 - 持续更新
java 程序员从小工到专家成神之路（2020 版）- 持续更新中, 附详细文章教程

更多内容请访问 www.flydean.com

我们考虑下面一种 ABA 的情况：

在多线程的环境中，线程 a 从共享的地址 X 中读取到了对象 A。
在线程 a 准备对地址 X 进行更新之前，线程 b 将地址 X 中的值修改为了 B。
接着线程 b 将地址 X 中的值又修改回了 A。
最新线程 a 对地址 X 执行 CAS，发现 X 中存储的还是对象 A，对象匹配，CAS 成功。

上面的例子中 CAS 成功了，但是实际上这个 CAS 并不是原子操作，如果我们想要依赖 CAS 来实现原子操作的话可能就会出现隐藏的 bug。

第一类问题的关键就在 2 和 3 两步。这两步我们可以看到线程 b 直接替换了内存地址 X 中的内容。

在拥有自动 GC 环境的编程语言，比如说 java 中，2，3 的情况是不可能出现的，因为在 java 中，只要两个对象的地址一致，就表示这两个对象是相等的。

2，3 两步可能出现的情况就在像 C ++ 这种，不存在自动 GC 环境的编程语言中。因为可以自己控制对象的生命周期，如果我们从一个 list 中删除掉了一个对象，然后又重新分配了一个对象，并将其 add back 到 list 中去，那么根据 MRU memory allocation 算法，这个新的对象很有可能和之前删除对象的内存地址是一样的。这样就会导致 ABA 的问题。

如果我们在拥有自动 GC 的编程语言中，那么是否仍然存在 CAS 问题呢？

考虑下面的情况，有一个链表里面的数据是 A ->B->C, 我们希望执行一个 CAS 操作，将 A 替换成 D，生成链表 D ->B->C。考虑下面的步骤：

线程 a 读取链表头部节点 A。
线程 b 将链表中的 B 节点删掉，链表变成了 A ->C
线程 a 执行 CAS 操作，将 A 替换从 D。

最后我们的到的链表是 D ->C，而不是 D ->B->C。

问题出在哪呢？CAS 比较的节点 A 和最新的头部节点是不是同一个节点，它并没有关心节点 A 在步骤 1 和 3 之间是否内容发生变化。

我们举个例子：

public void useABAReference(){CustUser a= new CustUser();
        CustUser b= new CustUser();
        CustUser c= new CustUser();
        AtomicReference<CustUser> atomicReference= new AtomicReference<>(a);
        log.info("{}",atomicReference.compareAndSet(a,b));
        log.info("{}",atomicReference.compareAndSet(b,a));
        a.setName("change for new name");
        log.info("{}",atomicReference.compareAndSet(a,c));
    }

上面的例子中，我们使用了 AtomicReference 的 CAS 方法来判断对象是否发生变化。在 CAS b 和 a 之后，我们将 a 的 name 进行了修改，我们看下最后的输出结果：

[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true

三个 CAS 的结果都是 true。说明 CAS 确实比较的两者是否为统一对象，对其中内容的变化并不关心。

第二类问题可能会导致某些集合类的操作并不是原子性的，因为你并不能保证在 CAS 的过程中，有没有其他的节点发送变化。

第一类问题在存在自动 GC 的编程语言中是不存在的，我们主要看下怎么在 C ++ 之类的语言中解决这个问题。

根据官方的说法，第一类问题大概有四种解法：

使用中间节点 – 使用一些不代表任何数据的中间节点来表示某些节点是标记被删除的。
使用自动 GC。
使用 hazard pointers – hazard pointers 保存了当前线程正在访问的节点的地址，在这些 hazard pointers 中的节点不能够被修改和删除。
使用 read-copy update (RCU) – 在每次更新的之前，都做一份拷贝，每次更新的是拷贝出来的新结构。

第二类问题其实算是整体集合对象的 CAS 问题了。一个简单的解决办法就是每次做 CAS 更新的时候再添加一个版本号。如果版本号不是预期的版本，就说明有其他的线程更新了集合中的某些节点，这次 CAS 是失败的。

我们举个 AtomicStampedReference 的例子：

public void useABAStampReference(){Object a= new Object();
        Object b= new Object();
        Object c= new Object();
        AtomicStampedReference<Object> atomicStampedReference= new AtomicStampedReference(a,0);
        log.info("{}",atomicStampedReference.compareAndSet(a,b,0,1));
        log.info("{}",atomicStampedReference.compareAndSet(b,a,1,2));
        log.info("{}",atomicStampedReference.compareAndSet(a,c,0,1));
    }

AtomicStampedReference 的 compareAndSet 方法，多出了两个参数，分别是 expectedStamp 和 newStamp，两个参数都是 int 型的，需要我们手动传入。

ABA 问题其实是由两类问题组成的，需要我们分开来对待和解决。

本文的例子 [https://github.com/ddean2009/
learn-java-base-9-to-20](https://github.com/ddean2009/…

本文作者：flydean 程序那些事

本文链接：http://www.flydean.com/aba-cas-stamp/

本文来源：flydean 的博客

欢迎关注我的公众号: 程序那些事，更多精彩等着您！

ABA问题的本质及其解决办法

简介

第一类问题

第二类问题

第一类问题的解决

第二类问题的解决

总结