回顾CAS中的ABA问题

墨蓝 2022-11-04 05:26 136阅读 0赞

## 一 概述 ##

CAS-(CompareAndSwap)，比较并交换，主要是通过处理器的指令来保证操作的原子性，它包含三个操作数：

*  变量内存地址，V
 *  变量的预期值与原本应该的值，A
 *  准备设置的新值，B

当执行CAS指令时，只有当内存V中的值同预期值A相同时，才会将内存中V的值更新为新值B，否则就不会执行更行操作。

## 二 CAS中的ABA问题 ##

在线程m执行当前CAS指令的更新过程中，当读取到的值A，当进行V和A值比较之前，会存在线程n将A的值改为新值B，又存在线程w将当前A的值从B改回原来的A，这个问题就是CAS中的ABA问题。

由ABA问题的过程总可以发现，它对CAS指令的最终结果影响并不大。

## 三 解决ABA问题 ##

Java中存在一个解决该问题的类AtomicStampedReference，该类中加入了预期标志**expectedStamp**和更新后的标志字段**newStamp**，更新时不光是进行之V和A的值比较，同时还要检查当前标志是否是预期标志，如果全部匹配才会进行CAS的更新操作。

**AtomicStampedReference源码**

public class AtomicStampedReference<V> {
    
        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) {
                return new Pair<T>(reference, stamp);
            }
        }
    
        private volatile Pair<V> pair;
        public AtomicStampedReference(V initialRef, int initialStamp) {
            pair = Pair.of(initialRef, initialStamp);
        }
    
        public V getReference() {
            return pair.reference;
        }
    
        public int getStamp() {
            return pair.stamp;
        }
    
        public V get(int[] stampHolder) {
            Pair<V> pair = this.pair;
            stampHolder[0] = pair.stamp;
            return pair.reference;
        }
    
        public boolean weakCompareAndSet(V   expectedReference,
                                         V   newReference,
                                         int expectedStamp,
                                         int newStamp) {
            return compareAndSet(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)));
        }
    
        public void set(V newReference, int newStamp) {
            Pair<V> current = pair;
            if (newReference != current.reference || newStamp != current.stamp)
                this.pair = Pair.of(newReference, newStamp);
        }
    
        public boolean attemptStamp(V expectedReference, int newStamp) {
            Pair<V> current = pair;
            return
                expectedReference == current.reference &&
                (newStamp == current.stamp ||
                 casPair(current, Pair.of(expectedReference, newStamp)));
        }
    
        // Unsafe mechanics
        private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
        private static final long pairOffset =
            objectFieldOffset(UNSAFE, "pair", AtomicStampedReference.class);
    
        private boolean casPair(Pair<V> cmp, Pair<V> val) {
            return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
        }
    
        static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
                                      String field, Class<?> klazz) {
            try {
                return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
            } catch (NoSuchFieldException e) {
                // Convert Exception to corresponding Error
                NoSuchFieldError error = new NoSuchFieldError(field);
                error.initCause(e);
                throw error;
            }
        }
    }

除此之外，我们可以借助分布式锁的原理，为A增加一个版本号，在进行CAS更新操作的时候，当每次A被修改之后，A的版本就会被同步修改更新，因此我们可以直接对比版本号而非直接进行值的比较，这样也可以解决CAS操作中的ABA问题。

**CAS除了存在ABA问题，还存在其他问题：**

*  循环时间长开销大：自旋CAS的方式如果长时间不成功，会给CPU带来很大的开销。
 *  只能保证一个共享变量的原子操作：只对一个共享变量操作可以保证原子性，而多个则不行，多个可以通过类AtomicReference来处理或者使用所synchronized实现。