关于程序员:并发专栏CAS

从 Atomic 到 CAS

CAS 晓得吗，如何实现？
讲一讲 AtomicInteger，为什么要用 CAS 而不是 synchronized？
CAS 底层原理，谈谈你对 UnSafe 的了解？
AtomicInteger 的ABA问题，能说一下吗，原子更新援用晓得吗？
CAS 有什么毛病吗？ 如何躲避 ABA 问题？

前言

Java 内存模型要保障可见性，原子性和有序性。

在 JDK 5之前 Java 语言是靠 synchronized 关键字保障同步的，但 synchronized 是一种独占锁，是一种乐观锁， 会导致其它所有须要锁的线程挂起，期待持有锁的线程开释锁 ，效率不是很高。

Java 虚拟机又提供了一个轻量级的同步机制——volatile（面试必问的 volatile，你真的了解了吗）

然而 volatile 算是乞丐版的 synchronized，并不能保障原子性 ，所以，又减少了java.util.concurrent.atomic包， 这个包下提供了一系列原子类。

1. Atomic 原子类

Atomic 原子类能够保障多线程环境下，当某个线程在执行 atomic 的办法时，不会被其余线程打断，而别的线程就像自旋锁一样，始终等到该办法执行实现，才由 JVM 从期待队列中抉择一个线程执行。Atomic 类在软件层面上是非阻塞的，它的原子性其实是在硬件层面上借助相干的指令来保障的。

Atomic 包中的类能够分成 4 组：

1. 根本类型：AtomicBoolean，AtomicInteger，AtomicLong
2. 数组类型：AtomicIntegerArray，AtomicLongArray，AtomicReferenceArray
3. 援用类型：AtomicReference，AtomicMarkableReference，AtomicStampedReference
4. 对象的属性批改类型（原子化对象属性更新器） ：AtomicIntegerFieldUpdater，AtomicLongFieldUpdater，AtomicReferenceFieldUpdater
5. JDK1.8 新增（原子化的累加器）：DoubleAccumulator、LongAccumulator、DoubleAdder、LongAdder、Striped64

以 AtomicInteger 为例理解罕用办法

Coding~~~

public class CASDemo {    public static void main(String[] args) {        System.out.println(num.compareAndSet(6, 7) + "\t + current num:" + num);        System.out.println(num.compareAndSet(6, 7) + "\t current num:" + num);    }}

true     + current num:7false     current num:7

执行两次后果却不同，Why?

compareAndSet() 尝试新增后比照，若减少胜利则返回true否则返回false。其实就是比拟并替换，判断用以后值和期望值（第一个参数），是否统一，如果统一，批改为更新值（第二个参数），这就是赫赫有名的 CAS。

2. CAS 是什么

2.1 CAS 算法

• CAS：全称 Compare and swap，即比拟并替换，它是一条 CPU 同步原语。 是一种硬件对并发的反对，针对多处理器操作而设计的一种非凡指令，用于治理对共享数据的并发拜访。
• CAS 是一种无锁的非阻塞算法的实现。

• CAS 蕴含了 3 个操作数：

  • 须要读写的内存值 V
  • 旧的预期值 A
  • 要批改的更新值 B
• 当且仅当 V 的值等于 A 时，CAS 通过原子形式用新值 B 来更新 V 的 值，否则不会执行任何操作（他的性能是判断内存某个地位的值是否为预期值，如果是则更改为新的值，这个过程是原子的。）

CAS 并发原语体现在 Java 语言中的 sum.misc.Unsafe 类中的各个办法。调用 Unsafe 类中的 CAS 办法， JVM 会帮忙咱们实现出 CAS 汇编指令。这是一种齐全依赖于硬件的性能，通过它实现了原子操作。再次强调，因为 CAS是一种零碎原语，原语属于操作系统用于领域，是由若干条指令组成的，用于实现某个性能的一个过程，并且原语的执行必须是间断的，在执行过程中不容许被中断，CAS 是一条 CPU 的原子指令，不会造成数据不统一问题。

咱们罕用的 java.util.concurrent 包就建设在CAS之上。

2.2 用 CAS 剖析 AtomicInteger 类

查看 AtomicInteger 代码如下，能够看到该类下的办法大部分是 调用了 Unsafe 类

2.2.1 UnSafe 类

是 CAS 的外围类，因为 Java 办法无奈间接拜访底层零碎，须要通过本地（native）办法来拜访，UnSafe 相当于一个后门，基于该类能够间接操作特定内存的数据。UnSafe 类存在与 sum.misc 包中，其外部办法能够像 C 语言的指针一样间接操作内存，因为 Java 中 CAS 操作的执行依赖于 UnSafe 类的办法。

UnSafe 类中的所有办法都是 native 润饰的，也就是说该类中的办法都是间接调用操作系统底层资源执行相应工作。

public final class Unsafe {    private static final Unsafe theUnsafe;    // ......    @CallerSensitive    public static Unsafe getUnsafe() {        Class var0 = Reflection.getCallerClass();        if (!VM.isSystemDomainLoader(var0.getClassLoader())) {            throw new SecurityException("Unsafe");        } else {            return theUnsafe;        }    }    public native int getInt(Object var1, long var2);    public native void putInt(Object var1, long var2, int var4);    public native Object getObject(Object var1, long var2);    public native void putObject(Object var1, long var2, Object var4);         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);    // ......}

Unsafe 类为一单例实现，提供静态方法 getUnsafe 获取 Unsafe 实例，当且仅当调用 getUnsafe 办法的类为疏导类加载器所加载时才非法，否则抛出 SecurityException 异样

2.2.2 valueOffset

AtomicInteger 中的变量 valueOffset 示意该变量值在内存中的偏移地址，因为 UnSafe 就是依据内存偏移地址获取数据。

public final int getAndIncrement() {    return unsafe.getAndAddInt(this, valueOffset, 1);}

2.2.3 volatile int value

变量 value 用 volatile 润饰，保障了多线程之间的内存可见性。

2.2.4 举个栗子

咱们用线程平安的 ++i 举例，也就是 AtomicInteger 中的 getAndAdd

逐层看 Unsafe 类中的 getAndAdd() 的源码如下

public final int getAndAddInt(Object var1, long var2, int var4) {    int var5;    do {        var5 = this.getIntVolatile(var1, var2);    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));    return var5;}

解毒：

能够看到 getAndAddInt 办法有 4 个参数

• val1：AtomicInteger 对象自身
• var2：该对象值的援用地址，内存偏移量
• var4： 须要变动的数量，即 ++i 的 i
• var5：用var1， var2 找出的主内存中实在的值（通过内存偏移量）

this.compareAndSwapInt 用该对象以后的值与 var5 比拟，如果雷同，更新 var5 + var4 并且返回 true，如果不同，持续取值而后再比拟，直到更新实现。

这一操作没有加锁，重复执行，既保证了一致性，又保障了并发性。

假如线程A和线程B两个线程同时执行 getAndAddInt 操作（别离跑在不同CPU上）：

1. AtomicInteger 外面的 value 原始值为 3，即主内存中 AtomicInteger 的 value 为 3，依据 JMM 模型，线程A和线程B各自持有一份值为 3 的 value 的正本别离到各自的工作内存；
2. 线程A通过 getIntVolatile(var1,var2) 拿到 value 值3，这时线程A被挂起；
3. 线程B也通过 getIntVolatile(var1,var2) 办法获取到 value 值 3，此时刚好线程B没有被挂起并执行compareAndSwapInt 办法比拟内存值为 3，胜利批改内存值为 4，线程B完结，一切正常
4. 这时线程A复原，执行compareAndSwapInt() 办法比拟，发现自己手里的3和主内存的值4不统一，阐明该值曾经被其余线程抢先一步批改过了，那线程A本次批改失败，从新读取；
5. 线程A从新获取value值，因为变量value 被 volatile 润饰，所以其余线程对它的批改，线程A总是可能看到，线程A继续执行compareAndSwapInt进行比拟替换，直到胜利

2.2.5 应用 UnSafe 类

那如若想应用这个类，该如何获取其实例？有如下两个可行计划

1. 从getUnsafe 办法的应用限度条件登程，通过Java命令行命令 -Xbootclasspath/a 把调用 Unsafe 相干办法的类A所在 jar 包门路追加到默认的 bootstrap 门路中，使得A被疏导类加载器加载，从而通过Unsafe.getUnsafe 办法平安的获取 Unsafe 实例。

   java -Xbootclasspath/a: ${path}   // 其中path为调用Unsafe相干办法的类所在jar包门路 

2. 通过反射技术暴力获取 Unsafe 对象

   private static Unsafe reflectGetUnsafe() {try {  Field field = Unsafe.class.getDeclaredField("theUnsafe");  field.setAccessible(true);  return (Unsafe) field.get(null);} catch (Exception e) {  log.error(e.getMessage(), e);  return null;}}

美团技术团队有一篇介绍Unsafe 类的文章：Java魔法类：Unsafe利用解析

3. CAS 毛病

• 循环工夫长，开销很大。CAS算法须要一直地自旋来读取最新的内存值，长时间读取不到就会造成不必要的CPU开销。

  do while 如果CAS失败，会始终进行尝试，如果CAS长时间始终不胜利，可能会给CPU带来很大的开销

• 只能保障一个共享变量的原子操作

  当对一个共享变量执行操作时，咱们能够应用循环CAS的形式来保障原子操作，然而，对多个共享变量操作时，循环CAS就无奈保障操作的原子性，这个时候就能够用锁来保障原子性。

• ABA 问题

ABA 问题

ABA 问题是什么？是如何产生的？

CAS算法实现一个重要前提是须要取出内存中某时刻的数据并在当下时刻比拟并替换，那么在这个时间差类会导致数据的变动。

比方线程1从内存地位 V 中取出A，这时线程2也从内存中取出A，并且线程2进行了一些操作将值变成了B，而后线程2又将V地位的数据变成A，这个时候线程1进行CAS操作发现内存中依然是A，线程1就会误认为它没有被批改过，这个破绽就是CAS操作的"ABA"问题。

只管线程1的CAS操作胜利，然而不代表这个过程就是没有问题的。

原子援用

咱们平时操作的不止是根本数据类型，大多数状况其实是类对象，Atomic 提供的援用类型 AtomicReference 通过泛型能够反对对对象的原子操作

public class AtomicRefrenceDemo {    public static void main(String[] args) {        User tom = new User("tom",18);        User jim = new User("jim",20);        AtomicReference<User> user = new AtomicReference<>();        user.set(tom);        System.out.println(user.compareAndSet(tom, jim)+"\t"+user.get().toString());        System.out.println(user.compareAndSet(tom, jim)+"\t"+user.get().toString());    }}class User{    String name;    int age;    public User(String tom, int i) {    }}

除了AtomicReference ，Atomic 还提供了AtomicStampedReference、AtomicMarkableReference

解决ABA 问题

各种乐观锁的实现中通常都会用版本戳 version 来对记录或对象标记，防止并发操作带来的问题

在Java中，AtomicStampedReference\<V> 也实现了这个作用，它通过包装[E,int]的元组来对对象标记版本戳stamp，从而防止ABA问题

public class AtomicStampedReferenceDemo {    static AtomicStampedReference<String> asf = new AtomicStampedReference<>("A", 1);    public static void main(String[] args) {        new Thread(() -> {            String value = asf.getReference();            System.out.println("Thread1 current value: " + asf.getReference() + ", stamp: " + asf.getStamp());            asf.compareAndSet(value, "B", asf.getStamp(), asf.getStamp() + 1);            System.out.println("Thread1： " + value + "——>" + asf.getReference() + ",stamp:" + asf.getStamp());            value = asf.getReference();            asf.compareAndSet(asf.getReference(), "A", asf.getStamp(), asf.getStamp() + 1);            System.out.println("Thread1： " + value + "——>" + asf.getReference() + ",stamp:" + asf.getStamp());        }).start();        new Thread(() -> {            String value = asf.getReference();            int stamp = asf.getStamp();            System.out.println("Thread2 current value: " + asf.getReference() + ", stamp: " + stamp);            try {                TimeUnit.SECONDS.sleep(3);            } catch (InterruptedException e) {                e.printStackTrace();            }            System.out.println("Thread2: " + value + "——>" + "B" + ",stamp:" + stamp + 1);            boolean flag = asf.compareAndSet(value, "B", stamp, stamp + 1);            if (flag) {                System.out.println("Thread2 update from " + value + " to B");            } else {                System.out.println("Thread2 update fail");            }        }).start();    }}

Thread1 current value: A, stamp: 1Thread2 current value: A, stamp: 1Thread1： A——>B,stamp:2Thread1： B——>A,stamp:3Thread2: A——>B,stamp:11Thread2 update fail

本文由mdnice多平台公布