CAS你知道吗？如何实现？

1. compareAndSet

在volatile当中我们提到，volatile不能保证原子语义，所以当用到变量自增时，如果用到synchronized会太”重“了，在多线程环境下我们一般用原子类如AtomicInteger，其底层是CAS，volatile见此篇

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

上述代码表示：

• 如果线程的期望值和物理内存的真实值一样，那么就修改为更新值
• 如果不一样，本次修改失败，就需要重新获取主物理内存的值

简单的代码例子：

package com.yuxue.juc.CASTest;

import java.util.concurrent.atomic.AtomicInteger;
/**
 * CAS:比较并交换
 */
public class CASDemo {
    public static void main(String[] args) {
        AtomicInteger atomicInteger = new AtomicInteger();
        //compareAndSet返回的是boolean类型，修改成功返回true，失败返回false
        System.out.println(atomicInteger.compareAndSet(0, 666) + "\t current data is " + atomicInteger.get());
        System.out.println(atomicInteger.compareAndSet(1, 777) + "\t current data is " + atomicInteger.get());
        System.out.println(atomicInteger.compareAndSet(666, 888) + "\t current data is " + atomicInteger.get());
    }
}

输出为：

//第一次期望值是0，原值默认0，所以CAS成功修改为666
true	 current data is 666
//第二次期望值是1，原值第一步修改为666，所以CAS不成功修改
false	 current data is 666
//第三次期望值是666，原值第一步修改为666，所以CAS成功修改为888
true	 current data is 888

2. CAS底层原理?对Unsafe的理解

我们都知道，atomicInteger.getAndIncrement()方法能够在多线程环境下保证变量的安全同时让其自增，但是源码当中也没有synchronized，那么如何保证底层安全？如果保证多线程环境下的变量安全？我们打开其源码：

2.1 compareAndSet

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

里面有用到unsafe对象的compareAndSwapInt方法，再找unsafe源码

其底层用到Unsafe类来保证线程安全！

2.2 Unsafe

• 是CAS核心类，由于Java方法无法直接访问底层系统，需要通过本地(native)方法来访问，Unsafe相当 于一个后门，基于该类可以直接操作特定内存数据。Unsafe类存在于sun.misc包中，其内部方法操作可 以像C的指针一样直接操作内存，因为Java中CAS操作的执行依赖于Unsafe类的方法。
• Unsafe类中的所有方法都是native修饰的，也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应任务
• 变量valueOffset，表示该变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的
• 变量value用volatile修饰，保证多线程之间的可见性

2.3 CAS是什么

CAS全称呼Compare-And-Swap，它是一条CPU并发原语

• 他的功能是判断内存某个位置的值是否为预期值，如果是则更改为新的值，这个过程是原子的
• CAS并发原语体现在JAVA语言中就是sun.misc.Unsafe类中各个方法。调用Unsafe类中的CAS方法，JVM会帮我们实现CAS汇编指令。这是一种完全依赖于硬件的功能，通过它实现了原子操作。
• 由于CAS是一种系统原语，原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成数据不一致问题

所以！CAS是通过Unsafe类的CPU指令源语来保证数据的原子性！

CAS源码：

//unsafe.getAndAddInt
//var1对应
public final int getAndAddInt(Object o, long offset, int delta) {
  int v;
  do {
    v = getIntVolatile(o, offset);
  } while (!compareAndSwapInt(o, offset, v, v + delta));
  return v;
}

o this即AtomicInteger对象本身

offset 该对象的引用地址（偏移地址）

delta 需要增加的变量

v通过AtomicInteger对象本身的offset偏移地址找出的主内存中真实的值，用该对象前的值与v比较; 如果相同，更新v+delta并且返回true， 如果不同，继续去之然后再比较，直到更新完成

2.4 总结

CAS：比较当前工作内存中的值和主物理内存中的值，如果相同则执行规定操作，否则的话继续比较直到主内存和工作内存中的值一值！（不清楚工作内存以及主内存的请移步查看volatile中的JMM模型

3. CAS缺点

3.1 循环时间长，开销大

例如getAndAddInt方法执行，有个do...while循环，如果CAS失败，一直会进行尝试，如果CAS长时间不成功， 可能会给CPU带来很大的开销(自旋！)

3.2 只能保证一个共享变量的原子操作

对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁来保证原子性

3.3 ABA问题

CAS算法实现一个重要前提需要去除内存中某个时刻的数据并在当下时刻比较并替换，那么在这个时间差类会导致数据的变化

例：比如线程1从内存位置V取出A，线程2同时也从内存取出A，并且线程2进行一些操作将值改为B，然后线程2又将V位置数据改成A，这时候线程1进行CAS操作发现内存中的值依然时A，然后线程1操作成功

尽管线程1的CAS操作成功，但是不代表这个过程没有问题

4. 原子类AtomicInteger的ABA问题?原子更新引用?

首先我们已经阐述了ABA的概念以及问题，首先我们要知道原子引用类的概念

4.1 原子引用

AtomicReference<V>

这里的V只要是其他的类均可使用AtomicReference作为其包装类

示例代码：

package com.yuxue.juc.CASTest;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.concurrent.atomic.AtomicReference;

@Data
@NoArgsConstructor
@AllArgsConstructor
class User{
    private String name;
    private int age;
}
/**
 * 测试原子引用类
 * */
public class AtomicReferenceTest {
    public static void main(String[] args) {
        User u1 = new User("张三",18);
        User u2 = new User("李四",23);
        AtomicReference<User> atomicReference = new AtomicReference<>();
        atomicReference.set(u1);
        System.out.println(atomicReference.compareAndSet(u1, u2) + "\t" + atomicReference.get().toString());
        System.out.println(atomicReference.compareAndSet(u1, u2) + "\t" + atomicReference.get().toString());
    }
}

输出结果为：

true	User(name=李四, age=23)
false	User(name=李四, age=23)

4.2 ABA问题代码实现

解决方案：带时间戳的原子引用

首先ABA问题代码展示:

package com.yuxue.juc.CASTest;

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

public class ABASolution {
    static AtomicReference<Integer> atomicReference = new AtomicReference<>(100);

    public static void main(String[] args) {
        new Thread(() -> {
            //ABA问题
            System.out.println(atomicReference.compareAndSet(100, 101) + "\t" + Thread.currentThread().getName() + "value is:" + atomicReference.get());
            System.out.println(atomicReference.compareAndSet(101, 100) + "\t" + Thread.currentThread().getName() + "value is:" + atomicReference.get());
        }, "t1").start();

        new Thread(() -> {
            //先休眠，让t1线程完成ABA操作
            try {
                Thread.sleep(1000);
                System.out.println(atomicReference.compareAndSet(100, 2019) + "\t" + Thread.currentThread().getName() + "value is:" + atomicReference.get());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "t2").start();
    }
}

结果为：

true	t1 value is:101
true	t1 value is:100
true	t2 value is:2019

可以看到t1首先修改值为101，之后又修改回来100，但是线程t2的工作内存中还是100，之后与主内存相比，发现主内存值也是100，之后放心修改值为2019，此时就会出现ABA问题

4.3 所以？怎么解决ABA问题？

采用内置的类AtomicStampedReference<V>其为携带时间戳的类，我们可以每次更改值时对时间戳进行操作，这样就可以保证不会出现ABA问题

package com.yuxue.juc.CASTest;

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

public class ABASolution {
    //创建变量，第一个是initialRef为初始值，第二个是initialStamp为初始化时间戳
    static AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(100, 1);

    public static void main(String[] args) {
        //atmoinReferenceMethod();
        new Thread(() -> {
            //获得时间戳，此时为1
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName() + "\t第1次版本号" + stamp);
            try {
                //此处休眠的目的是为了让t2获得初始版本号
                Thread.sleep(1000);
                //第一次修改，值改为101，版本号加1
                atomicStampedReference.compareAndSet(100, 101, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1);
                System.out.println(Thread.currentThread().getName() + "\t第2次版本号" + atomicStampedReference.getStamp());
                //第二次修改，值改为100，版本号加1
                atomicStampedReference.compareAndSet(101, 100, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1);
                System.out.println(Thread.currentThread().getName() + "\t第3次版本号" + atomicStampedReference.getStamp());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "t1").start();

        new Thread(() -> {
            //获得时间戳，此时为1
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName() + "\t第1次版本号" + stamp);
            try {
                //休眠2秒，此时线程t1已经将值改变但是又变回来，为ABA问题
                Thread.sleep(2000);
                //首先尝试是否可以根据值和时间戳进行更改
                boolean result = atomicStampedReference.compareAndSet(100, 2019, stamp, stamp + 1);
                System.out.println(Thread.currentThread().getName() + "\t修改是否成功" + result + "\t当前最新实际版本号" + atomicStampedReference.getStamp());
                System.out.println(Thread.currentThread().getName() + "\t当前最新实际值" + atomicStampedReference.getReference());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "t2").start();
    }
}

输出结果：

t1	第1次版本号1
t2	第1次版本号1
//t1修改两次，版本号加了2
t1	第2次版本号2
t1	第3次版本号3
//t2判断版本号，之后再决定能不能改
t2	修改是否成功false	当前最新实际版本号3
//实际并没有进行更改
t2	当前最新实际值100

这样，我们用JUC内置atomic下的AtomicStampedReference类来解决了ABA问题