【Java】手把手理解CAS实现原理

《手把手模拟CAS，瞬间理解CAS的机制》中用案例模拟了CAS，感兴趣的同学课先看看这个

先来看看概念，【CAS】全称“CompareAndSwap”，中文翻译即“比较并替换”。

定义：CAS操作包含三个操作数 —— 内存位置（V），期望值（A），和新值（B）。

如果内存位置的值与期望值匹配，那么处理器会自动将该位置值更新为新值。否则，

处理器不作任何操作。无论哪种情况，它都会在CAS指令之前返回该位置的值。

（CAS在一些特殊情况下，仅返回CAS是否成功，而不提去当前值）CAS有效说明了

“我认为【位置V】应该包含【值A】：如果包含【值A】，则将【新值B】放到这个位置；

否则，不要更改该位置的值，只告诉我这个位置现在的值即可”。

怎么使用JDK提供CAS支持？

Java中提供了对CAS操作的支持，具体在【sun.misc.unsafe】类中（官方不建议直接使用）

    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);

参数var1：表示要操作的对象 

参数var2：表示要操作对象中属性地址的偏移量

参数var4：表示需要修改数据的期望的值

参数var5：表示需要修改为的新值

此处描述一下偏移量的概念？

 这里的偏移量就像我们【new】一个对象，对象的地址就是【0x001】，那么value的地址就是【0x002 = 0x001 + 1】，

【+1】就是偏移量。

CAS的实现原理是什么？

CAS通过调用JNI的代码实现（JNI：Java Native Interface），允许java调用其他语言，

而【compareAndSwapXXX】系列的方法就是借助“C语言”来调用cpu底层指令实现的。

以常用的【Intel x86】平台来说，最终映射到cpu的指令为【cmpxchg】（compareAndChange），

这是一个原子指令，cpu执行此命令时，实现比较替换操作。

那么问题来了，现在计算机动不动就上百核，【cmpxchg】怎么保证多核下的线程安全？

系统底层进行CAS操作时，会判断当前系统是否为多核系统，如果是，就给【总线】加锁，

只有一个线程对总线加锁成功，加锁成功之后会执行CAS操作，也就是说CAS的原子性是平台级别的。

那么问题又来了，CAS这么流批，就不会有什么问题么？

1》高并发下，：在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，线程会一直处于自旋阻塞状态循环往复，会给CPU带来很到的压力。

2》ABA问题（重要）

什么是ABA问题呢？

CAS需要在操作值的时候，检查下值有没有发生变化，如果没有发生变化则更新，

但是可能会有这样一个情况，如果一个值原来是A，在CAS方法执行之前，被其他线程修改为了B，然后又修改回成A，

此时CAS方法执行之前，检查的时候发现它的值并没有发生变化，但实际却变化了，这就是【CAS的ABA】问题。

话不多说，我们这里用代码来模拟一下ABA问题：

public class CasABADemo1 {

    private static AtomicInteger count = new AtomicInteger(0);

    public static void main(String[] args) {
        System.out.println("mainThread 当前count值为： " + count.get());
        Thread mainThread = new Thread(() -> {
            try {
                int expectCount = count.get();
                int updateCount = expectCount + 1;
                System.out.println("mainThread 期望值：" + expectCount + ", 修改值：" + updateCount);
                Thread.sleep(2000);//休眠2000s ，释放cpu

                boolean result = count.compareAndSet(expectCount, updateCount);
                System.out.println("mainThread 修改count ： " + result);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        });

        Thread otherThread = new Thread(() -> {
            try {
                Thread.sleep(20);//确保主线程先获取到cpu资源
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            count.incrementAndGet();
            System.out.println("其他线程先修改 count 为：" + count.get());
            count.decrementAndGet();
            System.out.println("其他线程又修改 count 为：" + count.get());
        });

        mainThread.start();
        otherThread.start();

    }

}

结果：
mainThread 当前count值为： 0
mainThread 期望值：0, 修改值：1
其他线程先修改 count 为：1
其他线程又修改 count 为：0
mainThread 修改count ： true

最后结果可以看出【mainThread】修改成功，但是【mainThread】获取到的【expectCount】虽然也是1，但已经不是曾经的【expectCount】。

单从【0 --> 1 --> 0】，我们可能看不来什么太大的问题，我们可以再看一个小案例，了解一下【ABA】的危害：

场景是用链表来实现一个栈，初始化向栈中压入B、A两个元素，栈顶【head】指向A元素。

在某一时刻，线程1试图将栈顶换成B，但它获取栈顶的oldValue（为A）后，被线程2中断了。

线程2依次将A、B弹出，然后压入C、D、A。然后换线程1继续运行，线程1执行compareAndSet发现head指向的元素

确实与oldValue一致，都是A，所以就将head指向B了。但是，注意我标黄的那行代码，线程2在弹出B的时候，将B的next置为null了，

因此在线程1将head指向B后，栈中只剩了一个孤零零的元素B。但按预期来说，栈中应该放的是A → D → C。

说的有些抽象，话不多说，直接撸代码：

class ListNode {
    String value;
    ListNode next;

    ListNode(String value) {
        this.value = value;
    }
}

public class CasABAStackDemo {

    private static ListNode A = new ListNode("A");
    private static ListNode B = new ListNode("B");
    private static ListNode C = new ListNode("C");
    private static ListNode D = new ListNode("D");
    private static AtomicReference<ListNode> head = new AtomicReference<>(A);

    public static void main(String[] args) {

        //现将B、A依次压入栈    (head)A->B
        head.get().next = B;//先压入B

        Thread mainThread = new Thread(() -> {
            try {
                ListNode expectValue = head.get();
                Thread.sleep(3000);
                boolean result = head.compareAndSet(expectValue, B);
                System.out.println("mainThread 修改期望值是否成功：" + result);
                System.out.println("mainThread 当前head值为：" + head.get().value + "； head->next为：" + head.get().next);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        Thread otherThread = new Thread(() -> {

//            try {
//                Thread.sleep(20);//确保主线程可以获取到锁
//            } catch (InterruptedException e) {
//                e.printStackTrace();
//            }
            //弹出A
            ListNode newHead = head.get().next;
            head.get().next = null;
            head.set(newHead);

            //弹出B
            newHead = head.get().next;
            head.get().next = null;
            head.set(newHead);

            //压入C
            head.set(C);

            //压入D
            newHead = head.get();
            head.set(D);
            head.get().next = newHead;

            // 压入A
            newHead = head.get();
            head.set(A);
            head.get().next = newHead;

            System.out.println("otherThread head 顺序为：" + head.get().value + head.get().next.value + head.get().next.next.value);
        });

        mainThread.start();
        otherThread.start();

    }

}

结果：
otherThread head 顺序为：ADC
mainThread 修改期望值是否成功：true
mainThread 当前head值为：B,head->next为：null

结果可以看出，这种情况下，不应该允许【mainThread】CAS成功，因为A（即曾经的head）已经被替换了

如何解决ABA问题呢？

解决ABA最简单的方案就是给值加一个版本号，每次值变化，都会修改他的版本号，

CAS操作时都去对比次版本号。

java中提供了一种版本号控制的方法，可以解决ABA问题：

    public boolean compareAndSet(V   expectedReference, V   newReference, int expectedStamp,  int newStamp)

我们对上述代码改造一下，再看看结果：

public class CasABADemo2 {

    private static AtomicStampedReference<Integer> count = new AtomicStampedReference<>(0, 1);

    public static void main(String[] args) {
        System.out.println("mainThread 当前count值为： " + count.getReference() + ",版本号为：" + count.getStamp());
        Thread mainThread = new Thread(() -> {
            try {
                int expectStamp = count.getStamp();
                int updateStamp = expectStamp + 1;
                int expectCount = count.getReference();
                int updateCount = expectCount + 1;
                System.out.println("mainThread 期望值：" + expectCount + ", 修改值：" + updateCount);
                Thread.sleep(2000);//休眠2000s ，释放cpu

                boolean result = count.compareAndSet(expectCount, updateCount, expectStamp, updateStamp);
                System.out.println("mainThread 修改count ： " + result);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        });

        Thread otherThread = new Thread(() -> {
            try {
                Thread.sleep(20);//确保主线程先获取到cpu资源
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            count.compareAndSet(count.getReference(), count.getReference() + 1, count.getStamp(), count.getStamp() + 1);
            System.out.println("其他线程先修改 count 为：" + count.getReference() + " ，版本号：" + count.getStamp());
            count.compareAndSet(count.getReference(), count.getReference() - 1, count.getStamp(), count.getStamp() + 1);
            System.out.println("其他线程又修改 count 为：" + count.getReference() + " ，版本号：" + count.getStamp());
        });

        mainThread.start();
        otherThread.start();

    }

}

结果：
mainThread 当前count值为： 0,版本号为：1
mainThread 期望值：0, 修改值：1
其他线程先修改 count 为：1 ，版本号：2
其他线程又修改 count 为：0 ，版本号：3
mainThread 修改count ： false

可见添加版本号可以完美的解决ABA问题！