林清扬的博客

目标 路径 时间 结果 信息 定位 闭环 复盘 精力 极限 稳态 框架 邮箱：linqingyang@datagov.top

大话并发 – CAS、Unsafe

account_circle 林清杨 schedulefolder_open高并发comment大话并发 – CAS、Unsafe有1条评论
内容纲要

一文读懂 CAS

把 CAS 放在整个并发系列的这个位置，主要原因就是接下来我们将要学习到的 J.U.C 并发包中的很多类都涉及到了 CAS，可以说没有 CAS 和 volatile 就没有 J.U.C 并发包。

乐观锁和悲观锁回顾

提到 CAS 就不得不说一嘴乐观锁和悲观锁，之前的文章【Java 并发中的各种 ”锁“ 事】中我们已经讲过，这里简单回顾下。

悲观锁是一种悲观思想，认为自己在使用数据的时候一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改。

synchronized 关键字和 Lock 接口的实现类就是悲观锁。

乐观锁是一种乐观思想，认为自己在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在提交修改的时候去判断一下，在此之前有没有其他的线程也修改了这个数据：

  • 如果其他的线程还没有提交修改，那么当前线程就将自己修改的数据成功写入；
  • 如果其他的线程已经提交了修改，则当前线程会根据不同的实现方式执行不同的操作（例如报错或者自动重试）。

换句话说，乐观锁的目的就是在不使用锁（悲观锁）的情况下保证线程安全。

乐观锁在 Java 中是采用 CAS 算法实现的，J.U.C 包中的原子类就是通过 CAS 算法来实现了乐观锁，关于原子类下篇文章会详细解释。

使用这种 CAS(Compare-And-Set) 算法的代码也常被称为 无锁 编程（Lock-Free）。

什么是 CAS

再强调一遍， CAS 是一种算法，不要把 CAS 和乐观锁直接画等号。事实上，现代处理器基本都已经内置了实现 CAS 的指令，比如 x86 指令集上的 CAMPXCHG。

首先，大家应该已经知道，JMM 中不仅有主内存，每个线程还有各自的本地内存。每个线程会先更新自己的本地内存，然后再同步更新到主内存。

那如果多个线程都想要同步更新到主内存怎么办呢？

CAS 就是用来保证这种情况下的线程安全的。当多个线程尝试使用 CAS 同时更新主内存中的同一个变量时，只有一个线程可以成功更新变量的值，其他的线程都会失败，失败的线程并不会挂起，而是会自旋重试。

具体来说，CAS（Compare And Set）：比较并替换，该算法中有重要的三个操作数：

  • 需要读写的主内存位置（某个变量的值）
  • 该变量原来应该有的值（检查值有没有发生变化）
  • 线程想要把这个变量更新为哪个值

首先线程先读取需要读写的某个变量的值，然后比较当前该变量的值和该变量原来应该有的值：

  • 如果当前该变量的值与原来应该有的值相匹配，那么这个线程就可以将该变量更新为新值
  • 如果当前该变量的值与原来应该有的值不匹配，那就更新失败，开始自旋重试。

听起来好像有点拗口，其实总结一下就是三步走：

  • 读取
  • 比较
  • 交换

举个例子：

1）假设当前主内存变量 var = 2，此时线程 T1 想要用 CAS 去更新这个值，于是他先 ”读取“ 到了 var = 2；

2）此时，发生了上下文交换，线程 T2 一口气完成了 CAS 的读取、比较、交换这个三个操作，把 var 改成了 3；

3）然后，线程上下文交换，线程 T1 开始执行 ”比较“ 操作，发现 var 原来等于 2，现在变成 3 了，即表示这个变量已经被别人修改过了，于是 T1 就不会再去执行更新了，开始自旋重试。

image.png

CAS 存在的三大问题

看起来 CAS 好像很不错，高效地解决了并发问题，但事实上，CAS 仍然存在三大问题：

  • ABA 问题
  • 循环时间长开销大
  • 只能保证一个共享变量的原子操作

ABA 问题

上文说过，CAS 需要在更新值之前，去检查值有没有发生变化嘛，如果没有发生变化才会进行更新。

那所谓 ABA 问题就出现 ”如果没有发生变化才会进行更新" 这里，假设线程 T1 想要修改变量 var，读取到 var = A，然后，线程上下文切换，var 被线程 T2 修改成了 B，然后 T2 又将其修改回了 A，那么当 T1 去进行比较检查时会发现 var 的值并没有发生变化，还是 A，但是实际上，var 已经被改过两次了。

image.png

针对线程 T1 来说，它第一次看见的 A 和第二次看见的 A 实际上并不是同一个 A。

那么很容易想到，如果想要解决这个 ABA 问题，我们只需要对这些值进行一下标识，即使用版本号，在变量值前面追加上版本号，每次变量更新的时候把版本号加 1，那么 A→B→A 就会变成 1A→2B→3A。

image.png

从 Java 1.5 开始，JDK 的 Atomic 包里提供了一个类 AtomicStampedReference 来解决 ABA 问题，把变量放在 AtomicStampedReference 类中即可。这个我们下篇文章会详细说。

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

当对一个共享变量执行操作时，我们确实可以使用循环 CAS 的方式来高效地保证原子操作，但是对多个共享变量操作时，循环 CAS 就无法保证操作的原子性了。

为什么呢？上文说过，x86 指令集上使用 CAMPCHG 来实现 CAS 操作，我们在一些源码里看到的 CAS 操作其实都是对这条底层指令的封装罢了，而这条指令的功能就是一次只原子地修改一个变量。

那如果想要同时原子地修改多个共享变量怎么办呢？

有两种方法：

1）最简单的一种：锁

2）第二种无锁方法，就是把多个共享变量合并成一个共享变量再来操作。比如，有两个共享变量 a = 1 和 b = 2，合并一下 ab = 12，然后用 CAS 来操作 ab。

同样地，针对这个问题，从 Java 1.5 开始，JDK 提供了 AtomicReference 类来保证引用对象之间的原子性，这样我们就可以把多个变量封装在一个对象里来进行 CAS 操作。

循环时间开销大

上面总结了 CAS 操作其实就是三步走嘛，在 “比较” 那一步，如果当前该变量的值与原来应该有的值不匹配，那就不会进行更新，开始自旋重试。自旋大家应该也都知道了，就是 CPU 空转，如果长时间自旋不成功，会给 CPU 带来相当大的执行开销。

至于如何解决循环时间开销大的问题，由于涉及的知识比较底层，所以各位做个了解即可，下文我也只是很浅地解释了一下。

其解决办法就是使 JVM 支持底层指令 pause，这个指令的功能就是当自旋失败时让 CPU 睡眠一小段时间再继续自旋，其有两个作用：

1）降低读操作的频率；

2）避免在退出循环的时候因 内存顺序冲突（Memory OrderViolation） 而引起 CPU 流水线被清空（CPU PipelineFlush）。

所谓内存顺序，就是 CPU 访问内存的顺序。对于 CAS 这种无锁方式来说，不同于 volatile 和 synchronized，它没有任何的 Happens-before 原则来约束重排序行为，所以在这种情况下可以说 CPU 是在乱序执行的。

当自旋锁快要释放的时候，持锁线程会有一个 store 命令，而外面自旋等待的线程会发出各自的 load 命令，如果发生重排序导致 load 出现在 store 之前，此时会进行流水线清空再重排序，显然这样会严重影响 CPU 的效率，而 pause 可以减少并行 load 的数量，从而减少重排序所耗费的时间。

Unsafe 与 原子类

我们先来回顾下 Java 中保证保证原子操作的两种方法：

  • 用锁来保证原子性
  • CAS

前文解释了 CAS 的基本原理，其对应的是底层的汇编指令 cmpxchg，而 Java 中有这样一个类对这个底层指令进行了封装，使得我们可以非常简单的去使用 CAS，它就是 Unsafe 类。当然了，Unsafe 并不是文题的原子类，但是与原子类密不可分。

下面，我们先从 Unsafe 类开始吧。

Unsafe 类浅析

Unsafe 类存在于 sun.misc 包中，单从名称看来就可以知道该类是非安全的，因为其内部方法操作可以像 C 的指针一样直接操作内存。所以事实上 Java 官方也不建议我们直接去使用 Unsafe 类。

但我们还是很有必要了解该类，因为 J.U.C 中 CAS 操作的执行依赖于 Unsafe 类的方法，关于 Unsafe 类的主要功能点如下：

图片来自美团技术团队

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

Unsafe 类中与 CAS 相关的主要有以下 3 个方法：

image.png

每个方法都有 4 个参数，三个方法的参数语义其实都是一样的，不过源码中命名好像不是很清晰，这里我重新命名一下：

public final native boolean compareAndSwapXxx(Object o, long offset, Object expected, Object update)
  • 第一个参数 o 为给定对象，即包含要修改字段的对象
  • 第二个参数 offset 为对象内存的偏移量，通过这个偏移量可以迅速定位字段并设置或获取该字段的值
  • 第三个参数 expected 表示期望值
  • 第四个参数 update 表示要设置的值

当然，除了 CAS 相关的方法，J.U.C 中很多类其实都会调用到 Unsafe 类的某个方法，比如 LockSupport 的 park 和 unpark 方法，其实际调用的就是 Unsafe 的 park、unpark 方法。所以，可以说 J.U.C 中的类大部分都是 Unsafe 的包装类。

原子类详解

原子类存在于 java.util.concurrent.atomic 包中，简称 Atomic 包，这个包中的原子操作类借助 UnSafe 提供的 CAS 操作来保证数据更新的时候是线程安全的，并且由于 CAS 是乐观锁策略，所以利用原子类这种更新方法也非常高效。

image.png

图片截的不全，事实上，因为变量的类型有很多种，所以在 Atomic 包里一共提供了 13 个类，属于 4 种类型的原子更新方式，分别是：

  • 原子更新基本类型
  • 原子更新数组
  • 原子更新引用
  • 原子更新属性（字段）

原子更新基本类型

Atomic 包提供了以下 3 个类用来原子更新基本类型：

  • AtomicBoolean：原子更新布尔类型
  • AtomicInteger：原子更新整型
  • AtomicLong：原子更新长整型

这三个类提供的方法几乎一模一样，这里我们就以 AtomicInteger 为例，先来看下构造函数：

image.png

构造函数的入参 initialValue 就是要原子更新的初始值。来看下基本用法：

public class AtomicIntegerTest {
    static AtomicInteger a = new AtomicInteger(1);
    public static void main(String[] args) {
        System.out.println(a.getAndIncrement()); // 输出 1            
        System.out.println(a.get()); // 输出 2
    }
}

常用方法如下：

1）addAndGet：以原子方式将方法入参与实例中的值（AtomicInteger 中的 value）相加，并返回相加后的结果

image.png

这个 Unsafe 类的 getAndAddInt 方法其实就是封装了一下 compareAndSwapInt：

image.png

而 addAndGet 方法传给 getAndAddInt 方法的参数 valueOffset 指向的地址对应的值其实就是原始变量的初值：

image.png

2）compareAndSet：如果输入的数值等于预期值（入参 1 expect），则原子地将该值设置为输入的值（入参 2 update）

image.png

3）getAndIncrement 、getAndDecrement：原子地将当前值加 1。需要注意的是，这两个方法的返回值都是自增/自减操作前的值（即 i ++ 、i -- 操作）

image.png

对应的，++ i、-- i 操作对应的原子方法是 incrementAndGet 和 decrementAndGet，返回自增 / 自减操作后的结果：

image.png

4）getAndSet：将旧值原子地设置为 newValue ，并返回旧值

image.png

看到这里不知道大家会不会和我有一样的疑惑，那就是 Atomic 只提供了 int、long、boolean 类型的原子类，并且 Unsafe 也只提供了 compareAndSwapObject、compareAndSwapInt、compareAndSwapLong 这三种 CAS 方法，那还有 float、char、double 怎么办呢？

我们可以从 AtomicBoolean 这个类中找到答案。

image.png

可以看到，它是先把 boolean 类型转换成 int 类型，再使用 compareAndSwapInt 进行 CAS 操作。所以原子更新char、float 和 double 变量也可以用类似的思路来实现。

原子更新数组

Atomic 包提供了以下 3 个类用来原子更新基本类型：

  • AtomicIntegerArray：原子更新整型数组里的元素
  • AtomicLongArray：原子更新长整型数组里的元素
  • AtomicReferenceArray：原子更新引用类型数组里的元素

同样的，这三个类提供的方法几乎一模一样，这里我们就以 AtomicIntegerArray 为例，先来看下构造函数：

image.png

注意图片中的第二个构造函数！AtomicIntegerArray 会将当前数组 clone 一份，所以当 AtomicIntegerArray 对内部的数组元素进行修改时，是不会对传入的数组造成影响的。

来看下基本用法：

public class AtomicIntegerArrayTest {
    static int[] value = new int[] {1, 2, 3};
    static AtomicIntegerArray array = new AtomicIntegerArray(value);
    public static void main(String[] args) {
        array.getAndSet(0, 3)
        System.out.println(array.get(0)); // 输出 3            
        System.out.println(value.get(0)); // 输出 1
    }
}

常用方法如下：

1）addAndGet：原子地将输入值（入参 2 delta）与数组中下标 i （入参 1）的元素相加

image.png

2）compareAndSet：如果当前值等于预期值，则原子地将数组下标 i 的元素设置成新值

image.png

原子更新引用

Atomic 包提供了以下 3 个类用来原子更新基本类型：

  • AtomicReference：原子更新引用类型
  • AtomicReferenceFieldUpdater：原子更新引用类型里的字段
  • AtomicMarkableReference：原子更新带有标记位的引用类型

同样的，这三个类提供的方法几乎一模一样，这里我们就以 AtomicReference 为例，先来看下构造函数：

image.png

构造函数的入参 initialValue 就是要原子更新的初始值。来看下基本用法：

public class AtomicDemo {

    private static AtomicReference<User> reference = new AtomicReference<>();

    public static void main(String[] args) {
        User user1 = new User("user1", 16);                
        reference.set(user1);            

        User user2 = new User("user2", 18);
        reference.compareAndSet(user1, user2);

        System.out.println(reference.get().getName()); // "user2"
    }

    static class User {
        private String userName;
        private int age;

        public User(String userName, int age) {
            this.userName = userName;
            this.age = age;
        }
    }
}

首先构建一个 user 对象，然后把 user 对象设置进 AtomicReference 中，最后调用 compareAndSet 方法进行原子更新操作，当然其底层也是一样地调用了 Unsafe 类的 compareAndSet 方法。

原子更新属性（字段）

Atomic 包提供了以下 3 个类用来原子地更新对象的某个字段：

  • AtomicIntegerFieldUpdater：原子更新整型字段
  • AtomicLongFieldUpdater：原子更新长整型字段
  • AtomicStampedReference：原子更新带有版本号的引用类型。这个类我们前文简单提到过，该类将整数值与引用关联起来，可用于原子的更新数据和数据的版本号，可以解决使用 CAS 进行原子更新时可能出现的 ABA 问题。

可以看到它们都是用 Updater 结尾的，也被称为原子更新器。

同样的，这三个类提供的方法几乎一模一样，这里我们就以 AtomicIntegerFieldUpdater 为例，不过不同于普通类的构造函数，原子更新器都是抽象类，所以它其实是通过静态的 newUpdater 方法（调用具体的是实现类）来创建原子更新器的：

image.png

入参 1 就是要更新字段所属的类，入参 2 就是要更新的字段。来看下基本用法：

public class AtomicIntegerFieldUpdaterTest {

    private static AtomicIntegerFieldUpdater updater = AtomicIntegerFieldUpdater.newUpdater(User.class, "age"); // 原子更新 User 类的 age 字段
    public static void main(String[] args) {
        User user = new User("user1", 1); // 旧值是 1
        int oldValue = updater.getAndAdd(user, 5); // 原子更新为 5 
        System.out.println(oldValue); // 1
        System.out.println(updater.get(user)); // 6
    }
}

1 Comment

  1. Pingback： 大话并发 - 目录 - 林清扬的博客

Leave a Comment

您的电子邮箱地址不会被公开。 必填项已用*标注

close
arrow_upward