CAS算法简介

• CAS（Compare And Swap）算法是一条原子的CPU指令（Atomic::cmpxchg(x, addr, e) == e;），需要三个操作数：变量的内存地址（或者是偏移量valueOffset） V ，预期值 A 和更新值 B，CAS指令执行时：当且仅当对象偏移量V上的值和预期值A相等时，才会用更新值B更新V内存上的值，否则不执行更新。但是无论是否更新了V内存上的值，最终都会返回V内存上的旧值。

1. 为什么使用CAS代替synchronized

• synchronized加锁，同一时间段只允许一个线程访问，能够保证一致性但是并发性下降。而是用CAS算法使用do-while不断判断而没有加锁（实际是一个自旋锁），保证一致性和并发性。
• 原子性保证：CAS算法依赖于rt.jar包下的sun.misc.Unsafe类，该类中的所有方法都是native修饰的，直接调用操作系统底层资源执行相应的任务。

// unsafe.class
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        // 获取对象var1，偏移量为var2地址上的值，并赋值给var5
        var5 = this.getIntVolatile(var1, var2);
        /**
         * 再次获取对象var1，偏移量var2地址上的值，并和var5进行比较：
         * - 如果不相等，返回false，继续执行do-while循环
         * - 如果相等，将返回的var5数值和var4相加并返回
         */
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    // 最终总是返回对象var1，偏移量为var2地址上的值，即上述所说的V。
    return var5;
}

• 内存可见性和禁止指令重排序的保证：AtomicXxx类中的成员变量value是由volatile修饰的：private volatile int value;上一小节中已经介绍过。

2. CAS算法的缺点

• do-while循环，如果CAS失败就会一直进行尝试，即一直在自旋，导致CPU开销，这也是自旋锁的缺点；
• 只能保证一个共享变量的原子操作，如果操作多个共享变量则需要加锁实现；
• ABA问题：如果一个线程在初次读取时的值为A，并且在准备赋值的时候检查该值仍然是A，但是可能在这两次操作之间，有另外一个线程现将变量的值改成了B，然后又将该值改回为A，那么CAS会误认为该变量没有变化过。

3. ABA问题解决方案

• 可以使用AtomicStampedReference或者AtomicMarkableReference来解决CAS的ABA问题，思路类似于SVN版本号，SpringBoot热部署中trigger.txt：

• AtomicStampedReference解决方案：每次修改都会让stamp值加1，类似于版本控制号

/**
 * ABA问题解决方案，AtomicStampedReference
 *
 * @author sherman
 */
public class AtomicStampedReferenceABA {
    private static AtomicReference<Integer> ar = new AtomicReference<>(0);
    private static AtomicStampedReference<Integer> asr =
            new AtomicStampedReference<>(0, 1);

    public static void main(String[] args) {
        System.out.println("=============演示ABA问题（AtomicReference）===========");
        new Thread(() -> {
            ar.compareAndSet(0, 1);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            ar.compareAndSet(1, 0);
            System.out.println(Thread.currentThread().getName() + "进行了一次ABA操作");
        }, "子线程").start();

        try {
            Thread.sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        boolean res = ar.compareAndSet(0, 100);
        if (res) {
            System.out.println("main成功修改, 未察觉到子线程进行了ABA操作");
        }

        System.out.println("=============解决ABA问题（AtomicStampReference）===========");
        new Thread(() -> {
            int curStamp = asr.getStamp();
            System.out.println("当前stamp: " + curStamp);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            asr.compareAndSet(0, 1, curStamp, curStamp + 1);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            asr.compareAndSet(1, 0, asr.getStamp(), asr.getStamp() + 1);
        }, "t1").start();

        new Thread(() -> {
            int curStamp = asr.getStamp();
            System.out.println("当前stamp: " + curStamp);
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean result = asr.compareAndSet(0, 100, curStamp, curStamp + 1);
            if (!result) {
                System.out.println("修改失败! 预期stamp: " + curStamp + ", 实际stamp: " + asr.getStamp());
            }
        }, "t2").start();
    }
}

• AtomicMarkableReference：如果不关心引用变量中途被修改了多少次，而只关心是否被修改过，可以使用AtomicMarkableReference：

/**
 * ABA问题解决方案，AtomicMarkableReference
 *
 * @author  sherman
 */
public class AtomicMarkableReferenceABA {
    private static AtomicMarkableReference<Integer> amr = new AtomicMarkableReference<>(0, false);

    public static void main(String[] args) {
        new Thread(() -> {
            amr.compareAndSet(0, 1, false, true);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            amr.compareAndSet(1, 0, true, true);
            System.out.println("子线程进行了ABA修改!");
        }, "子线程").start();

        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        boolean res = amr.compareAndSet(0, 100, false, true);
        if (!res) {
            System.out.println("修改失败! 当前isMarked: " + amr.isMarked());
        }
    }
}

3.3 补充：CAS算法实际使用

在Spring容器刷新方法 refresh() 方法中：obtainFreshBeanFactory()->refreshBeanFactory()【GenericApplicationContext实现类】:

@Override
protected final void refreshBeanFactory() throws IllegalStateException {
    // cas算法
    // private final AtomicBoolean refreshed = new AtomicBoolean();
    if (!this.refreshed.compareAndSet(false, true)) {
        throw new IllegalStateException(
                "GenericApplicationContext does not support multiple refresh attempts: just call 'refresh' once");
    }
    this.beanFactory.setSerializationId(getId());
}