【面试题】CAS 学习总结

CAS需要有3个操作数：内存地址V，旧的预期值A，即将要更新的目标值B。

什么是CAS？

简单说是一种思想，首先比较预期值A与内存地址V的值，如果相同则将内存地址V的值修改为目标值B，否则不执行。

1.1CAS介绍

CAS的全称为Compare-And-Swap（比较并交换） ,他是一条CPU并发原语。

它会【比较】主内存中指定位置的【值是否和预期值相等】，如果【true】则会将工作空间拷贝的副本值【更改】为新值，并写回主内存。整个过程不会被打断或分割，属于【原子性】操作。

CAS并发原语体现在JAVA语言中sun.misc.Unsafe类中的各个方法。调用Unsafe类中的CAS方法，JVM会执行CAS汇编指令。这是一种完全依赖于硬件的功能，通过它实现原子操作。

由于CAS是一种系统原语，原语属于操作系统用语范畴，由若干指令组成，用于完成某个功能的一个过程。
原语的执行必须是连续的，执行过程中不允许被中断，意味着CAS是一条CPU的原子指令，不会造成数据不一致问题。

1.2如何通过CAS解决原子性问题？

在解决volatile不保证原子性问题时，通过java.util.concurrent.atomic包下的AtomicInteger解决原子性问题。那么atomicInteger.getAndIncrement();是如何保证原子性的呢？

我们发现：getAndIncrement()方法中，调用了 sun.misc包下的Unsafe类的对象去执行方法getAndAddInt(this, valueOffset, 1)

//帮助我们调用本地方法的Unsafe类
private static final Unsafe unsafe = Unsafe.getUnsafe();
//volatile修饰的全线程可见变量
private volatile int value;
/**
     * Atomically increments by one the current value.
     *原子性地将当前值增加1
     * @return the previous value
     *返回之前的值
     */
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

Unsafe是CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地(native)方法来访问。通过该类，可以直接操作特定内存的数据。Unsafe存在于sun.misc包中，其内部方法可以像C语言的指针一样直接操作内存，Java中CAS的执行依赖于Unsafe类的方法。

注意Unsafe类中的所有方法都是native修饰的，也意味着该类中所有方法都直接调用操作系统底层资源执行相应任务。

valueOffset:表示该变量值在内存中的偏移位置，Unsafe是通过内存偏移的地址获取数据的。

value：使用volatile修饰，保证多线程之间的内存可见性。

以下是getAndAddInt()方法实现过程：

    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            //失败会重新获取最新值，进行重试
            var5 = this.getIntVolatile(var1, var2);
            //此处进行自旋，直到compareAndSwapInt方法返回true
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

getAndAddInt()调用了this.compareAndSwapInt()方法，该方法被final和native修饰。

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

以下是AtomicInteger.compareAndSet()方法的源码：

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

由此看出：AtomicInteger.compareAndSet()和getAndAddInt()底层都调用compareAndSwapInt()方法。

通过var1,var2来获取主内存中的最新值，再与 var4(expect)为期望值进行比较
相同则将内存中的值 修改为var5(update)。

compareAndSwapInt属于java最底层的执行方法，被native修饰，说明该方法非java语言实现，不会运行在虚拟机栈中，而是运行在本地方法区。

在getAndAddInt执行过程中，首先通过getIntVolatile(var1, var2)在内存中获取到该位置的值并用var5记录下来。
再通过compareAndSwapInt(var1, var2, var5, var5 + var4))，var1、var2用于获取内存中的最新值，var5记录了之前获取的预期值。
当var5预期值和底层再次获取的最新值不一致时，则修改失败返回false。
由于while循环条件取compareAndSwapInt方法返回值的相反值，如果失败则会一直循环。
do{ var5 = this.getIntVolatile(var1, var2);}会重新获取一次预期值，再次执行compareAndSwapInt(var1, var2, var5, var5 + var4))。
当预期值var5和最新值相同时，则把(var5+var4)修改为最新值，返回true。

整个执行过程为：

如果获取到内存中的最新值与预期值不一致，则失败。
失败后重新获取内存中的最新值作为预期值，重新执行compareAndSwapInt()直到执行成功。

CAS的缺点

2.1问题总结：

1.当线程过多，出现死循环时会导致CPU性能消耗。

2.只能保证一个变量的原子操作，如果是多个变量那么就要使用锁了。

(从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，可以把多个变量放在一个对象里来进行CAS操作)

3.可能会发生ABA问题。

2.2什么是ABA问题？

当多线程环境中，假设有两个线程A和B。A将共享变量改为B，又改回A。此时B线程无法感知A线程的操作，只会进行比较和修改。这样有可能会造成不可预期的错误。

CAS算法实现的一个重要前提是：

需要取出内存中【某时刻】的数据，与【当前时刻】内存中最新的值进行比较。

在这两个时刻的【时间差】中，他们的数据很可能发生变化。

当多个线程读取到主内存中的变量值A，拷贝回工作空间中。其中一个线程将值A改为值B。由于线程竞争关系，该线程抢到执行权，又将值B改回值A。
此时其他线程开始执行，读取到内存中的最新值A与预期值相同，修改成功后将数据写回主内存。

此时线程的CAS操作全部成功，并不代表整个过程没有问题。其他线程只会根据最新值和预期值进行比较，而无法感知该值的修改过程。

如何解决（避免）CAS的ABA问题？

3.1 原子引用

java.util.concurrent.atomic包下的AtomicReference是原子引用核心类。

通过该类可以封装任意对象进行原子性操作。

3.1.1 原子引用示例

package cn.litany.study.thread.cas;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

/**
 * @author Litany
 */
public class AtomicReferenceQuickStart {
    public static void main(String[] args) {

        AtomicReference<Teacher> atomicReferenceTeacher = new AtomicReference<Teacher>();
        Teacher z3=new Teacher("张三",18);
        Teacher l4=new Teacher("李四",19);
        //由于构造atomicReferenceTeacher没有初始值，所以需要设置z3，为其指定初始值
        atomicReferenceTeacher.set(z3);
        boolean a = atomicReferenceTeacher.compareAndSet(z3, l4);
        System.out.println("atomicReferenceTeacher 修改结果:"+a);

        //构造atomicReferenceInteger 为其指定初始值100
        AtomicReference<Integer> atomicReferenceInteger = new AtomicReference<>(100);
        boolean b = atomicReferenceInteger.compareAndSet(100, 101);
        System.out.println("atomicReferenceInteger 修改结果:"+b);

        AtomicInteger atomicInteger =new AtomicInteger(100);
        boolean c = atomicInteger.compareAndSet(100, 101);
        System.out.println("atomicInteger 修改结果:"+c);
    }
}

执行结果：

通过compareAndSet方法，比较内存中最新值与期望值是否相同，再将值更改为新值，返回true。

但是该方法仍然存在ABA问题。

3.2 解决ABA问题

分析：

因为只会根据主内存中的值与期望值进行比较，线程无法感知该值的修改过程，导致ABA问题。
让每次修改值相当于一次版本升级，在比较期望值的同时比较版本号是否相同。当期望值与最新值相同，版本号不同，说明该值被修改过。

通过AtomicStampedReference类可以解决版本不同问题。

//AtomicStampedReference有参构造方法
public AtomicStampedReference(V initialRef, int initialStamp) {
        pair = Pair.of(initialRef, initialStamp);
    }

AtomicStampedReference<Integer> atomicStampedReference = 
    //100为初始值，0为初始版本号。
    new AtomicStampedReference<>(100, 0);

//获取当前值
int i = atomicStampedReference.getReference();
//获取当前版本
int stamp = atomicStampedReference.getStamp();

以下是AtomicStampedReference.compareAndSet()方法的参数

/**
     * 如果当前引用与预期引用相同，并且当前版本等于预期版本，
     * 则原子地将引用和标记的值设置为给定的更新值。
     *
     * @param expectedReference :引用的预期值  
     * @param newReference :引用的新值
     * @param expectedStamp :预期版本号
     * @param newStamp :新版本号
     * @return 成功返回true
     */
public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp)

package cn.litany.study.thread.cas;

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

/**
 * @author Litany
 */
public class AtomicReferenceDemo {

    public static void main(String[] args) {
        AtomicReference<Integer> atomicReference = new AtomicReference<>(100);
        //atomicStampedReference 比 atomicReference 多出一个版本功能通过stamp比较版本
        AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(100, 0);
        new Thread(() -> {
            System.out.println("=======ABA问题发生start======");
            int i = atomicReference.get();
            System.out.println(Thread.currentThread().getName() + "修改前:" + i);
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean b = atomicReference.compareAndSet(i, 101);
            i = atomicReference.get();
            System.out.println(Thread.currentThread().getName() + "修改结果:" + b + "\t最新值:" + i);
            b = atomicReference.compareAndSet(i, 100);
            i = atomicReference.get();
            System.out.println(Thread.currentThread().getName() + "修改结果:" + b + "\t最新值:" + i);


        }, "t1").start();

        new Thread(() -> {
            int i = atomicReference.get();
            System.out.println(Thread.currentThread().getName() +"修改前:" + i);
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean b = atomicReference.compareAndSet(i, 101);
            System.out.println(Thread.currentThread().getName() + ":当前修改结果" + b + "\t最新值：" + atomicReference.get());
            System.out.println("=======ABA问题发生end======");
        }, "t2").start();
        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(3);
                System.out.println("=======ABA问题解决start======");
                int i = atomicStampedReference.getReference();
                int stamp = atomicStampedReference.getStamp();
                System.out.println(Thread.currentThread().getName()+"当前版本:"+atomicStampedReference.getStamp()+"修改前的值:"+atomicStampedReference.getReference());
                TimeUnit.SECONDS.sleep(2);
                boolean b = atomicStampedReference.compareAndSet(i, 101, stamp, stamp + 1);
                System.out.println(Thread.currentThread().getName() + ":当前修改结果" + b + "\t当前版本:" + atomicStampedReference.getStamp() + "\t修改后的值：" + atomicStampedReference.getReference());
                b = atomicStampedReference.compareAndSet(101, 100, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1);
                System.out.println(Thread.currentThread().getName() + ":当前修改结果" + b + "\t当前版本:" + atomicStampedReference.getStamp() + "\t修改后的值：" + atomicStampedReference.getReference());

            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        }, "t3").start();
        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(4);
                int stamp = atomicStampedReference.getStamp();
                Integer reference = atomicStampedReference.getReference();
                System.out.println(Thread.currentThread().getName()+"当前版本:"+ stamp
                        +"修改前的值:"+ reference);
                TimeUnit.SECONDS.sleep(3);
                boolean b = atomicStampedReference.compareAndSet(reference, 101, stamp, stamp + 1);
                System.out.println(Thread.currentThread().getName() + ":当前修改结果" + b + "\t当前版本:" + atomicStampedReference.getStamp() + "\t修改后的值：" + atomicStampedReference.getReference());
                System.out.println("=======ABA问题解决end======");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        }, "t4").start();

    }

}