CAS原理

看了几篇文章，拼接到一起的，加上一点点点点自己总结。主要还是别人的东西

参考了:
https://blog.csdn.net/weixin_41832850/article/details/100095677
https://www.cnblogs.com/java20130722/p/3206742.html// 这个解决ABA问题代码有问题，线程的join使用错了。
https://www.cnblogs.com/javalyy/p/8882172.html
https://www.jianshu.com/p/ab2c8fce878b

导读：

一：什么是CAS?
二：JAVA中如何实现CAS操作
三：CAS在JUC中的运用
四：CAS回来缺点、带来的问题
五：java中怎样解决ABA问题

一、什么是CAS？

CAS：Compare and Swap，即比较再交换。

jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。JDK 5之前Java语言是靠synchronized关键字保证同步的，这是一种独占锁，也是是悲观锁。
对CAS的理解， CAS是一种无锁算法，CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。
CAS比较与交换的伪代码可以表示为：
do{
备份旧数据；
基于旧数据构造新数据；
}while(!CAS( 内存地址，备份的旧数据，新数据 ))

image

注：t1，t2线程是同时更新同一变量56的值

因为t1和t2线程都同时去访问同一变量56，所以他们会把主内存的值完全拷贝一份到自己的工作内存空间，所以t1和t2线程的预期值都为56。

假设t1在与t2线程竞争中线程t1能去更新变量的值，而其他线程都失败。（失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次发起尝试）。t1线程去更新变量值改为57，然后写到内存中。此时对于t2来说，内存值变为了57，与预期值56不一致，就操作失败了（想改的值不再是原来的值）。

（上图通俗的解释是：CPU去更新一个值，但如果想改的值不再是原来的值，操作就失败，因为很明显，有其它操作先改变了这个值。）

就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设，采用了类似于数据库的commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。

JAVA1.5开始引入了CAS，主要代码都放在JUC的atomic包下，如下图：

image

二、JAVA底层如何实现CAS操作

以比较简单的AtomicInteger为例，我们看一下都有哪些方法：
从图中可以看出JAVA中的CAS操作都是通过sun包下Unsafe类实现，而Unsafe类中的方法都是native方法，由JVM本地实现，笔者为了弄清楚真正的实现原理，查看了openJDK7的源码，下面就稍作分析：

Unsafe中对CAS的实现是C++写的，从上图可以看出最后调用的是Atomic:comxchg这个方法，这个方法的实现放在hotspot下的os_cpu包中，说明这个方法的实现和操作系统、CPU都有关系，我们以linux的X86处理器的实现为例来进行分析

Linux的X86下主要是通过cmpxchgl这个指令在CPU级完成CAS操作的，但在多处理器情况下必须使用lock指令加锁来完成。从这个例子就可以比较清晰的了解CAS的底层实现了，当然不同的操作系统和处理器的实现会有所不同，大家可以自行了解。

三、缺点、问题

1. CPU开销过大：

自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。
在并发量比较高的时候，如果许多线程都尝试去更新一个变量的值，却又一直比较失败，导致提交失败，产生自旋，循环往复，会对CPU造成很大的压力和开销。

2. 不能确保代码块的原子性（注意是代码块）

CAS机制所确保的是一个变量的原子性操作，而不能保证整个代码块的原子性，比如需要保证3个变量共同进行原子性的更新，就不得不使用synchronized或者lock了。

3. ABA问题。这就是CAS最大的问题所在。

如线程1从内存X中取出A，这时候另一个线程2也从内存X中取出A，并且线程2进行了一些操作将内存X中的值变成了B，然后线程2又将内存X中的数据变成A，这时候线程1进行CAS操作发现内存X中仍然是A，然后线程1操作成功。虽然线程1的CAS操作成功，但是整个过程就是有问题的。比如链表的头在变化了两次后恢复了原值，但是不代表链表就没有变化。
java解决办法：所以JAVA中提供了AtomicStampedReference/AtomicMarkableReference来处理会发生ABA问题的场景，主要是在对象中额外再增加一个标记来标识对象是否有过变更。

四、ABA问题的解决

JDK1.5可以利用类AtomicStampedReference来解决这个问题，AtomicStampedReference内部不仅维护了对象值，还维护了一个时间戳。当AtomicStampedReference对应的数值被修改时，除了更新数据本身外，还必须要更新时间戳，对象值和时间戳都必须满足期望值，写入才会成功。所以下面代码AtomiStampedReference的compareAndSet函数是三个参数

各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记，避免并发操作带来的问题，例如下面的代码分别用AtomicInteger和AtomicStampedReference来对初始值为100的原子整型变量进行更新，AtomicInteger会成功执行CAS操作，而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败：

package com.salix.crawler;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;

public class Main {
    private static AtomicInteger atomicInt = new AtomicInteger(100);
    private static AtomicStampedReference atomicStampedRef = new AtomicStampedReference(100, 0);

    public static void main(String[] args) throws InterruptedException {
        Thread intT1 = new Thread(new Runnable() {
            @Override
            public void run() {
                atomicInt.compareAndSet(100, 101);
                atomicInt.compareAndSet(101, 100);
            }
        });

        Thread intT2 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    intT1.join();
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                }
                boolean c3 = atomicInt.compareAndSet(100, 101);
                System.out.println(c3+" atomicInt"); // true
            }
        });

        intT1.start();
        intT2.start();


        Thread refT1 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                }
                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();
                try {
                    refT1.join();
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                }
                boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);
                System.out.println(c3+" atomicStamedRef"); // false
            }
        });

        refT1.start();
        refT2.start();

    }
}