1、什么是原子操作

原子（atomic）本意是不能被进一步分割的最小粒子，而原子操作（atomic operation）为不可中断的一个或一系列操作。在多处理器上实现原子操作就变得有点复杂。接下来会讲解 Intel 处理器和 Java 里是如何实现操作的。

2、术语定义

在了解原子操作实现原理前，先了解一下相关术语，如表所示

image.png

3、处理器如何实现原子操作

32 位 IA-32 处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存中读取或者写入一个字节是原子的，意思是当一个处理器读取一个字节时，其他处理器不能访问这个字的内存地址。Pentium6 和最新的处理器能自动保证单处理器对同一个缓存行进行 16/32/64 位的操作是原子的，但是复杂的内存操作处理器是不能自动保证其原子性的，比如跨总线宽度、跨多个缓存行和跨页表的访问。但是，处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。

处理器使用三个相互依赖的机制来实现加锁的原子操作

  1. 保证原子操作
  2. 总线加锁，使用 lock# 信号和 lock 前缀指令
  3. 缓存一致性协议，确保对缓存中的数据结构执行原子操作（缓存锁）

IA-32 处理器提供有一个 lock# 信号，会在某些关键内存操作期间被自动激活，去锁定系统总线。当这个输出信号发出的时候，来自其他处理器或总线代理的控制请求将阻塞。软件能够预先在指令前添加 lock 前缀来指定需要 lock 语义的其他场合。

lock 指令做了什么，通过 IA-32 手册可知，在修改内存操作时，使用 lock 前缀去调用加锁的读-修改-写操作，这种机制用于多处理器系统中处理器进行可靠的通讯，具体如下

  1. 在 Pentium 和早期的 IA-32 处理器中，lock 前缀会使处理器执行当前指令时产生一个 lock# 信号，这种总是引起显示总线锁定出现
  2. 在 Pentium6 和最新的处理器中，加锁操作是由高速缓存锁或总线锁处理。如果内存访问有高速缓存且只影响一个单独的缓存行，那么操作中就回调用缓存锁，而系统总线和系统内存中的实际区域内不会被锁定。同时，这条总线上的其他 Pentium6 和最新的处理器就回写所有已修改的数据并使其他处理器的缓存失效，以保证系统内存一致性。

为显式地强制执行 lock 语义，软件可以在下列指令修改内存区域时使用 lock 前缀。当 lock 前缀被置于其他指令之前或者指令没有对内存进行写操作（也就是说目标操作数在寄存器中）时，会产生一个非法操作码异常 #UD。

  1. 位测试和修改指令：BTS、BTR、BTC
  2. 交换指令：XADD、CMPXCHG、CMPXCHG&B
  3. 自动假设有 lock 前缀的 XCHG 指令
  4. 单操作数的算数和逻辑指令：INC、DEC、NOT、NEG
  5. 双操作数的算数和逻辑指令：ADD、ADC、SUB、SBB、AND、OR、XOR

一个加锁的指令会保证对目标操作数所在的内存区域加锁，但是系统可能会将锁定区域解释得稍大一些。软件应该使用相同的地址和操作数长度来访问信号量（用作处理之间发送信号的共享内存）。例如当一个处理器正在使用一个字节来访问信号量，其他处理器此时就不能访问这个信号量。

3.1、通过总线锁保证原子性

如果多个处理器同时对共享变量进行读写操作（i++ 就是经典的读写操作），那么共享变量就回被多个处理器同时进行操作，这样读写操作就不是原子的，操作完之后共享变量的值会和预期的不一致。举个例子，如果 i=1，我们进行两次 i++ 操作，我们的结果是 3，但有可能结果是 2，如图所示。

image.png

原因可能是多个处理器同时从各自的缓存中读取变量 i，分别进行加 1 操作，然后分别写入系统内存中。那么想要保证读改写共享变量的操作是原子的，就必须保证 CPU1 读改写共享变量的时候，CPU2 不能操作缓存了该共享变量内存地址的缓存。

处理器使用总线锁就是来解决这个问题的。所谓总线锁就是使用处理器提供的一个 lock# 信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。总线锁的完整性不受内存区域对齐的影响。加锁语义会一直持续，以确保更新整个操作所需的总线周期个数。

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

在同一时刻，我们只需保证对某个内存地址的操作是原子性的即可，但总线锁定把 CPU 和内存之间的通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大，目前处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。

频繁使用的内存地址会缓存在处理器的 L1、L2 和 L3 高速缓存里，那么原子操作就可以直接在处理器内部缓存中进行，并不需要声明总线锁，在 Pentium6 和目前的处理器中可以使用缓存锁定的方式来实现复杂的原子性。

缓存锁定，指内存区域如果被缓存在处理器缓存行中，并且在 lock 操作期间被锁定，那么当执行锁操作回写到内存时，处理器不在总线上声言 lock# 信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改由两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效，如图上所示，当 CPU1 修改缓存行中的 i 时使用了缓存锁定，那么 CPU2 就不能同时缓存 i 的缓存行。

3.3 处理器不适用缓存锁定的情况

  1. 当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。
  2. 对于不支持缓存锁定的处理器（Intel486和Pentium处理器），就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。

针对以上两种机制，Intel 处理器提供了很多 lock 前缀的指令来实现。例如，位测试和修改指令：BTS、BTR、BTC；交换指令 XADD、CMPXCHG，以及其他一些操作数和逻辑指令（如 ADD、OR）等，被这些指令操作的内存区域就会加锁，导致其他处理器不能同时访问它。

4、Java 如何实现原子操作

4.1、使用循环 CAS 实现原子操作

JVM 中的 CAS 操作是利用了处理器提供的 CMPXCHG 指令实现的。自旋 CAS 实现的基本思路就是循环进行 CAS 操作直到成功为止。CAS 实现原子操作会存在 ABA、循环时间开销大和只能保证一个共享变量的原子操作三个问题。

基于 CAS 线程安全的计数器 safeCount 和一个非线程安全的计数器 count 的代码：

  1. package com.yj.cas;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.concurrent.atomic.AtomicInteger;
  7. /**
  8.  * @description:
  9.  * @author: erlang
  10.  * @since: 2021-01-05 22:55
  11.  */
  12. public class AtomicTest {
  14.     private AtomicInteger atomicI = new AtomicInteger(0);
  16.     private int i = 0;
  18.     public static void main(String[] args) {
  20.         final AtomicTest cas = new AtomicTest();
  22.         List<Thread> ts = new ArrayList<>(600);
  24.         long start = System.currentTimeMillis();
  26.         for (int j = 0; j < 100; j++) {
  27.             Thread t = new Thread(() -> {
  28.                 for (int i = 0; i < 10000; i++) {
  29.                     cas.count();
  30.                     cas.safeCount();
  31.                 }
  32.             });
  33.             ts.add(t);
  34.         }
  36.         for (Thread t : ts) {
  37.             t.start();
  38.         }
  40.         // 等待所有线程执行完成
  41.         for (Thread t : ts) {
  42.             try {
  43.                 t.join();
  44.             } catch (InterruptedException e) {
  45.                 e.printStackTrace();
  46.             }
  47.         }
  49.         System.out.println(cas.i);
  51.         System.out.println(cas.atomicI.get());
  53.         System.out.println(System.currentTimeMillis() - start);
  54.     }
  56.     /**
  57.      * 使用CAS实现线程安全计数器
  58.      */
  59.     private void safeCount() {
  60.         for (; ; ) {
  61.             int i = atomicI.get();
  62.             boolean suc = atomicI.compareAndSet(i, ++i);
  63.             if (suc) {
  64.                 break;
  65.             }
  66.         }
  67.     }
  69.     /**
  70.      * 非线程安全计数器
  71.      */
  72.     private void count() {
  73.         i++;
  74.     }
  76. }

4.1.1、ABA 问题

其他线程修改数次最后值和原值相同，即其他线程将变量值 A 修改为 B，但是又被改回了A。等到本线程使用期望值 A 与当前值进行比较时，发现变量 A 没有变，于是 CAS 就将 A 值进行了交换操作，但是实际该值已经被其他线程改变过，这与乐观锁的设计思想不符合。

ABA 问题的解决思路是，每次变量更新的时候把变量的版本号加 1，那么 A-B-A 就会变成 A1-B2-A3，只要变量被某一线程修改过，改变对应的版本号就会发生递增变化，从而解决了 ABA 问题，基础类型简单值不需要版本号。在 JDK 的 java.util.concurrent.atomic 包中提供了 AtomicStampedReference 来解决 ABA 问题，该类的 compareAndSet 是该类的核心方法，实现如下：

  1.     /**
  2.      * Atomically sets the value of both the reference and stamp
  3.      * to the given update values if the
  4.      * current reference is {@code ==} to the expected reference
  5.      * and the current stamp is equal to the expected stamp.
  6.      *
  7.      * @param expectedReference the expected value of the reference 预期引用
  8.      * @param newReference the new value for the reference 更新后的引用
  9.      * @param expectedStamp the expected value of the stamp 预期标志
  10.      * @param newStamp the new value for the stamp 更新后的标志
  11.      * @return {@code true} if successful
  12.      */
  13.     public boolean compareAndSet(V   expectedReference,
  14.                                  V   newReference,
  15.                                  int expectedStamp,
  16.                                  int newStamp) {
  17.         Pair<V> current = pair;
  18.         return
  19.             expectedReference == current.reference &&
  20.             expectedStamp == current.stamp &&
  21.             ((newReference == current.reference &&
  22.               newStamp == current.stamp) ||
  23.              casPair(current, Pair.of(newReference, newStamp)));
  24.     }

该类检查了当前引用与当前标志是否与预期相同，如果全部相等，才会以原子方式将该引用和该标志的值设为新的更新值，这样 CAS 操作中的比较就不依赖于变量的值了。

4.1.2、循环时间长开销大

自旋 CAS 如果长时间不成功，会给 CPU 带来非常大的执行开销。如果 JVM 能支持处理器提供的 pause 指令，那么效率会有一定的提升。其中 pause 指令有两个作用：

  1. 可以延迟流水线执行指令（de-pipeline），使 CPU 不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器延迟时间是零
  2. 可以避免在退出循环的时候因内存顺序冲突（Memory Order Violation）而引起 CPU 流水线被清空（CPU Pipeline Flush)，从而提高 CPU 的执行效率

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

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

如何保证多个共享变量的原子操作？

  1. 使用锁
  2. 把多个共享变量合并成一个共享变量来操作

比如，两个共享变量 i=2, j=a，合并一下 ij=2a，然后用 CAS 来操作 ij。从 JDK1.5 开始，JDK 提供了 AtomicReference 类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行 CAS 操作。

4.2、使用锁机制实现原子操作

锁机制保证了只有获得锁的线程才能操作锁定的内存区域。JVM 内部实现了多种锁机制，偏向锁、轻量级锁和互斥锁。除了偏向锁，JVM 实现锁的方式都用了循环 CAS。即当一个线程想进入同步块的时候使用循环 CAS 的方式来获取锁，当它退出同步块的时候使用循环 CAS 释放锁。