一、什么是CAS

1.1、说明

CAS的全称为：Compare And Swap，直译就是比较交换。

是一条CPU的原子指令，其作用是让CPU先进行比较两个值是否相等，然后原子地更新某个位置的值，其实现方式是基于硬件平台的汇编指令，在intel的CPU中，使用的是cmpxchg指令，就是说CAS是靠硬件实现的，从而在硬件层面提升效率。

1.2、原子算法

CAS （Compare And Swap）一种无锁原子算法。

过程是这样：它包含 3 个参数 CAS（V，E，N），V表示要更新变量的值，E表示预期值，N表示新值。仅当 V值等于E值时，才会将V的值设为N，如果V值和E值不同，则说明已经有其他线程做两个更新，则当前线程则什么都不做。最后，CAS 返回当前V的真实值。CAS 操作时抱着乐观的态度进行的，它总是认为自己可以成功完成操作。

1.3、多线程中

当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败。失败的线程不会挂起，仅是被告知失败，并且允许再次尝试，当然也允许实现的线程放弃操作。基于这样的原理，CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰。

与锁相比，使用CAS会使程序看起来更加复杂一些，但由于其非阻塞的，它对死锁问题天生免疫，并且，线程间的相互影响也非常小。更为重要的是，使用无锁的方式完全没有锁竞争带来的系统开销，也没有线程间频繁调度带来的开销，因此，他要比基于锁的方式拥有更优越的性能。

简单的说，CAS 需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的。如果变量不是你想象的那样，哪说明它已经被别人修改过了。你就需要重新读取，再次尝试修改就好了。

1.4、优点

1. 非阻塞。
   

2. 免疫死锁。
   

3. 线程间的相互影响也非常小。
   

4. 比基于锁的方式拥有更优越的性能。
   

二、CPU是如何保证原子性的？

2.1、通过总线锁定来保证原子性

总线锁定其实就是处理器使用了总线锁，所谓总线锁就是使用处理器提供的一个 LOCK#信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。但是该方法成本太大。因此有了下面的方式。

2.2、通过缓存锁定来保证原子性

所谓缓存锁定是指内存区域，如果被缓存在处理器的缓存行中，并且在Lock操作期间被锁定，那么当他执行锁操作写回到主内存时，处理器不在总线上声言 LOCK# 信号，而时修改内部的内存地址，并允许他的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改两个以上处理器缓存的内存区域数据（这里和 volatile 的可见性原理相同），当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效(也就是说当CPU1修改缓存行中的i时，使用了缓存锁定，那么CPU2就不能同时缓存了i)。

注意：有两种情况下处理器不会使用缓存锁定。

1. 当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。
   

2. 有些处理器不支持缓存锁定，对于 Intel 486 和 Pentium 处理器，就是锁定的内存区域在处理器的缓存行也会调用总线锁定。

三、CAS原理

public class CASDemo01 {
    //volatile保证了可见性，无法保证原子性。
    public static volatile int m = 0;

    public static void addM(){
        //m++非原子性操作。
        m++;
    }

    public static void main(String[] args){
        //初始化10个线程
        Thread[] threads = new Thread[10];
        for (int i = 0; i < threads.length; i++) {
            threads[i] = new Thread(() -> {
                //每个线程+5次m
                for (int j = 0; j < 5 ; j++) {
                    CASDemo01.addM();
                    System.out.println("m:" + m);
                    try {
                        Thread.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
            threads[i].start();
        }
    }
}

3.1、使用CAS保证原子性

public class CASDemo02 {
    public static AtomicInteger m = new AtomicInteger(0);

    public static int addM(){
        //先++再获取
        return m.incrementAndGet();
    }

    public static void main(String[] args){
        //初始化10个线程
        Thread[] threads = new Thread[10];
        for (int i = 0; i < threads.length; i++) {
            threads[i] = new Thread(() -> {
                //每个线程+5次m
                for (int j = 0; j < 5 ; j++) {
                    System.out.println("m:" + CASDemo02.addM());
                    try {
                        Thread.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
            threads[i].start();
        }
    }
}

3.2、源码分析

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;
    // 后门类，用于直接操作内存中的数据。Unsafe类提供了硬件级别的原子操作，提高了Java对底层操作的能力。
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    // 内存首地址的偏移量，在AtomicInteger被加载时就被赋值了。
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }
	// 存放的值，volatile保证了值的可见性。
    private volatile int value;
    
    /**
     * Atomically increments by one the current value.
     *
     * @return the updated value
     */
    public final int incrementAndGet() {
        //对AtomicInteger原子的加1并返回加1后的值
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }
    
    //忽略本次为使用的方法
    //......
}

1. unsafe：用于直接操作内存中的数据。Unsafe是CAS的核心类，Java是无法直接访问底层操作系统，而是通过本地（native）方法来访问。不过尽管如此，JVM还是开了一个后门：Unsafe类，它提供了硬件级别的原子操作。

1. 

2. public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

2. valueOffset：变量value的内存首地址的偏移量。它在AtomicInteger被加载时就被赋值了。Unsafe就是通过偏移地址来获取到数据的原值的。

3. value：存放实际值的变量，它被volatile关键字修饰，保证可见性。

/**
* 这是Unsafe类中的方法。
* @param var1 当前对象
* @param var2 地址的偏移量
* @param var4 增加的值
* @return 修改后的值
*/
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        // 这个方法根据对象(var1)和偏移量(var2)得到在主内存的快照值var5
        var5 = this.getIntVolatile(var1, var2);
        // var2表示要更新变量的值，var5表示预期值(快照值)，var5 + var4表示新值。
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

getAndAddInt()方法底层还是通过compareAndSwapInt这个CAS机制来完成的增加操作。
getIntVolatile()这个方法的var1和var2，就是根据对象和偏移量得到在主内存的快照值var5。compareAndSwapInt方法如果这个var2值跟快照值var5相等，那么就更新主内存的值为：var5+var4。如果不等，那么就一直循环，一直获取快照，一直对比，直到实际值和快照值相等为止。

四、CAS带来的问题

CAS虽然高效地解决了原子操作，但是还是存在一些缺陷的，主要表现在三个方面：循环时间太长、只能保证一个共享变量原子操作、ABA问题。

4.1、循环时间太长

如果CAS一直不成功呢？这种情况绝对有可能发生，如果自旋CAS，长时间的不成功，则会给CPU带来非常大的开销(在JUC中有些地方就限制了CAS自旋的次数，例如BlockingQueue的SynchronousQueue)。

4.2、只能保证一个共享变量的原子性操作

看了CAS的实现就知道这只能针对一个共享变量，如果是多个共享变量就只能使用锁了。

4.3、ABA问题

CAS需要检查操作值有没有发生改变，如果没有发生改变则更新。

但是存在这样一种情况：如果一个值原来是A，变成了B，然后又变成了A，那么在CAS检查的时候会发现没有改变，但是实质上它已经发生了改变，这就是所谓的ABA问题。对于ABA问题其解决方案是加上版本号，即在每个变量都加上一个版本号，每次改变时加1，即A —> B —> A，变成1A —> 2B —> 3A。

下面的代码阐述了ABA问题

public class CASDemo03 {
    public static AtomicInteger m = new AtomicInteger(100);

    public static void main(String[] args){
        Thread t1 = new Thread(() ->{
            //期望值100，修改值200
            System.out.println(m.compareAndSet(100, 200));
        });
        t1.start();

        Thread t2 = new Thread(() ->{
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //期望值200，修改值100
            System.out.println(m.compareAndSet(200, 100));
        });
        t2.start();

        Thread t3 = new Thread(() ->{
            try {
                TimeUnit.SECONDS.sleep(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //期望值100，修改值120
            System.out.println(m.compareAndSet(100, 120));
        });
        t3.start();
    }
}

compareAndSet()方法：如果当前状态值等于预期值expect，则以原子方式将同步状态设置为给定的更新值update。

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

JDK提供了一个带有标记的原子引用类“AtomicStampedReference”，它可以通过控制变量值的版本来保证CAS的正确性。

public class CASDemo04 {
    /**
     * 参数1 初始值
     * 参数2 版本号
     */
    public static AtomicStampedReference<Integer> m = new AtomicStampedReference<>(100, 1);

    public static void main(String[] args){
        Thread t1 = new Thread(() ->{
            int stamp = m.getStamp();
            //期望值100，修改值200，版本号+1
            System.out.println(m.compareAndSet(100, 200, stamp, stamp + 1));
        });
        t1.start();

        Thread t2 = new Thread(() ->{
            int stamp = m.getStamp();
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //期望值200，修改值100，版本号+1
            System.out.println(m.compareAndSet(200, 100, stamp, stamp + 1));
        });
        t2.start();

        Thread t3 = new Thread(() ->{
            int stamp = m.getStamp();
            try {
                TimeUnit.SECONDS.sleep(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //期望值100，修改值120，版本号+1
            System.out.println(m.compareAndSet(100, 120, stamp, stamp + 1));
        });
        t3.start();
    }
}

五、CAS适用场景