如何解决CAS ABA问题?

cas的ABA问题就是 假设初始值为A，线程3和线程1都获取到了初始值A，然后线程1将A改为了B，线程2将B又改回了A，这时候线程3做修改时，是感知不到这个值从A改为了B又改回了A的过程： AtomicStampedReference 本质是有一个int 值作为版本号，每次更改前先取到这个int值的版本号，等到修改的时候，比较当前版本号与当前线程持有的版本号是否一致，如果一致，则进行修改，并将版本号+1（当然加多少或减多少都是可以自己定义的），在zookeeper中保持数据的一致性也是用的这种方式； AtomicMarkableReference则是将一个boolean值作是否有更改的标记，本质就是它的版本号只有两个，true和false，修改的时候在这两个版本号之间来回切换，这样做并不能解决ABA的问题，只是会降低ABA问题发生的几率而已； 看下面这个例子里面有主要源码的解析： ```java import java.util.concurrent.atomic.AtomicMarkableReference; import java.util.concurrent.atomic.AtomicStampedReference; /** * 解决atomic类cas操作aba问题，解决方式是在更新时设置版本号的方式来解决，每次更新就要设置一个不一样的版本号，修改的时候，不但要比较值有没有变，还要比较版本号对不对，这个思想在zookeeper中也有体现； * @author Administrator * */ public class AtomicStampedReferenceTest { public final static AtomicStampedReference<String> ATOMIC_REFERENCE = new AtomicStampedReference<String>("abc", 0); /** * 它里面只有一个成员变量,要做原子更新的对象会被封装为Pair对象，并赋值给pair； private volatile Pair<V> pair; 先看它的一个内部类Pair ，要进行原子操作的对象会被封装为Pair对象 private static class Pair<T> { final T reference; //要进行原子操作的对象 final int stamp; //当前的版本号 private Pair(T reference, int stamp) { this.reference = reference; this.stamp = stamp; } static <T> Pair<T> of(T reference, int stamp) { //该静态方法会在AtomicStampedReference的构造方法中被调用，返回一个Pair对象； return new Pair<T>(reference, stamp); } } 现在再看构造方法就明白了，就是将原子操作的对象封装为pair对象 public AtomicStampedReference(V initialRef, int initialStamp) { pair = Pair.of(initialRef, initialStamp); } 获取版本号 就是返回成员变量pair的stamp的值 public int getStamp() { return pair.stamp; } 原子修改操作，四个参数分别是旧的对象，将要修改的新的对象，原始的版本号，新的版本号 这个操作如果成功就会将expectedReference修改为newReference，将版本号expectedStamp修改为newStamp； public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) { Pair<V> current = pair; return expectedReference == current.reference && expectedStamp == current.stamp //如果原子操作的对象没有更改，并且版本号也没有更改， && ( (newReference == current.reference &&newStamp == current.stamp) //如果要修改的对象与就的对象相同，并且新的版本号也与旧的版本号相同，也就是重复操作，这时候什么也不干 || casPair(current, Pair.of(newReference, newStamp)) //cas操作，生成一个新的Pair对象，替换掉旧的，修改成功返回true，修改失败返回false； ); } * @param args */ public static void main1(String[] args) { for (int i = 0; i < 100; i++) { final int num = i; final int stamp = ATOMIC_REFERENCE.getStamp(); new Thread() { public void run() { try { Thread.sleep(Math.abs((int) (Math.random() * 100))); } catch (InterruptedException e) { e.printStackTrace(); } if (ATOMIC_REFERENCE.compareAndSet("abc", "abc2", stamp, stamp + 1)) { System.out.println("我是线程：" + num + ",我获得了锁进行了对象修改！"); } } }.start(); } new Thread() { public void run() { int stamp = ATOMIC_REFERENCE.getStamp(); while (!ATOMIC_REFERENCE.compareAndSet("abc2", "abc", stamp, stamp + 1)) ; System.out.println("已经改回为原始值！"); } }.start(); } /**AtomicMarkableReference 解决aba问题，注意，它并不能解决aba的问题 ，它是通过一个boolean来标记是否更改，本质就是只有true和false两种版本来回切换，只能降低aba问题发生的几率，并不能阻止aba问题的发生，看下面的例子**/ public final static AtomicMarkableReference<String> ATOMIC_MARKABLE_REFERENCE = new AtomicMarkableReference<String>("abc" , false); public static void main(String[] args){ //假设以下操作由不同线程执行 System.out.println("mark:"+ATOMIC_MARKABLE_REFERENCE.isMarked()); //线程1 获取到mark状态为false，原始值为“abc” boolean thread1 = ATOMIC_MARKABLE_REFERENCE.isMarked(); System.out.println("mark:"+ATOMIC_MARKABLE_REFERENCE.isMarked()); //线程3获取到mark状态为false ，原始值为“abc” boolean thread2 = ATOMIC_MARKABLE_REFERENCE.isMarked(); System.out.println("change result:"+ATOMIC_MARKABLE_REFERENCE.compareAndSet("abc", "abc2", thread1, !thread1)); //线程1 更改abc为abc2 System.out.println("mark:"+ATOMIC_MARKABLE_REFERENCE.isMarked()); //线程2获取到mark状态为true ，原始值为“abc2” boolean thread3 = ATOMIC_MARKABLE_REFERENCE.isMarked(); System.out.println("change result:"+ATOMIC_MARKABLE_REFERENCE.compareAndSet("abc2", "abc", thread3, !thread3));//线程2 更改abc2为abc System.out.println("change result:"+ATOMIC_MARKABLE_REFERENCE.compareAndSet("abc", "abc2", thread2, !thread2));//线程3更改abc为abc2； //按照上面的执行顺序，3此修改都修改成功了，线程1与线程2拿到的mark状态都是false，他俩要做的操作都是将“abc”更改为“abc2”， 只是线程2在线程1和线程3中间做了一次更改，最后线程2做操作的时候并没有感知到线程1与线程3的更改； } } ```

### 一 ABA问题 CAS看起来很爽，但是会导致“ABA问题”。 利用版本号比较可以有效解决ABA问题。 CAS算法实现一个重要前提需要取出内存中某时刻的数据，而在下时刻比较并替换，那么在这个时间差类会导致数据的变化。 比如说一个线程one从内存位置V中取出A，这时候另一个线程two也从内存中取出A，并且two进行了一些操作变成了B，然后two又将V位置的数据变成A，这时候线程one进行CAS操作发现内存中仍然是A，然后one操作成功。尽管线程one的CAS操作成功，但是不代表这个过程就是没有问题的。如果链表的头在变化了两次后恢复了原值，但是不代表链表就没有变化。因此前面提到的原子操作AtomicStampedReference/AtomicMarkableReference就很有用了。这允许一对变化的元素进行原子操作。 在运用CAS做Lock-Free操作中有一个经典的ABA问题： 线程1准备用CAS将变量的值由A替换为B，在此之前，线程2将变量的值由A替换为C，又由C替换为A，然后线程1执行CAS时发现变量的值仍然为A，所以CAS成功。但实际上这时的现场已经和最初不同了，尽管CAS成功，但可能存在潜藏的问题。 由于ABA问题带来的隐患，各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记，避免并发操作带来的问题，在Java中，AtomicStampedReference也实现了这个作用，它通过包装[E,Integer]的元组来对对象标记版本戳stamp，从而避免ABA问题，例如下面的代码分别用AtomicInteger和AtomicStampedReference来对初始值为100的原子整型变量进行更新，AtomicInteger会成功执行CAS操作，而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败： ### 二、解决方案 JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。如果当前引用 == 预期引用，并且当前标志等于预期标志，则以原子方式将该引用和该标志的值设置为给定的更新值。源码如下： ```java /** *expectedReference - 该引用的预期值 *newReference - 该引用的新值 *expectedStamp - 该标志的预期值 *newStamp - 该标志的新值 */ public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) { Pair<V> current = pair; return expectedReference == current.reference && expectedStamp == current.stamp && ((newReference == current.reference && newStamp == current.stamp) || casPair(current, Pair.of(newReference, newStamp))); } ``` ### 三、最佳实践 ```java package com.concurrent; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicStampedReference; /** * @author riemann * @date 2019/08/03 17:35 */ public class ABATest { private static AtomicInteger atomicInteger = new AtomicInteger(100); private static AtomicStampedReference<Integer> atomicStampedRef = new AtomicStampedReference<Integer>(100,0); public static void main(String[] args) throws InterruptedException { Thread intT1 = new Thread(new Runnable() { @Override public void run() { atomicInteger.compareAndSet(100,101); atomicInteger.compareAndSet(101,100); } }); Thread intT2 = new Thread(new Runnable() { @Override public void run() { try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } boolean flag = atomicInteger.compareAndSet(100,101);// true System.out.println("flag is " + flag); } }); intT1.start(); intT2.start(); intT1.join(); intT2.join(); Thread refT1 = new Thread(new Runnable() { @Override public void run() { try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } atomicStampedRef.compareAndSet(100,101,atomicStampedRef.getStamp(),atomicStampedRef.getStamp() + 1); atomicStampedRef.compareAndSet(101,100,atomicStampedRef.getStamp(),atomicStampedRef.getStamp() + 1); } }); Thread refT2 = new Thread(new Runnable() { @Override public void run() { int stamp = atomicStampedRef.getStamp(); System.out.println("before sleep : stamp = " + stamp); try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("after sleep : stamp = " + atomicStampedRef.getStamp()); boolean flag = atomicStampedRef.compareAndSet(100,101,stamp,stamp + 1); System.out.println("thread refT2: " + atomicStampedRef.getReference() + ", flag is " + flag); } }); refT1.start(); refT2.start(); } } ``` 输出结果： ```java flag is true before sleep : stamp = 0 after sleep : stamp = 2 thread refT2: 100, flag is false ``` 可以看到refT2的值和expect是相同的，但是由于版本号发生了变化，所以更新失败。

使用CAS更新是没法解决ABA的问题，就是其他调用方对数据修改成其他值后又改回原来的值。AtomicStampedReference的compareAndSet会先判断对象的引用是否相同，相同才进行CAS更新。实现原理主要是AtomicStampedReference会保存之前对象的的引用，及一个修改版本号，只有当引用和版本号都相等的情况下，才会进行CAS更新操作。