CAS 原理分析
Cache 基础
在分析 CAS 原理之前，我们需要先了解一下 CPU 和内存是怎么交互。在 CPU 和内存之间会有一个高速缓存层（CPU Cache），以便提升 CPU 访问内存的数据，Cache 的速度比内存要快很多，但是容量小很多，整个 Cache 通常都不到 20 MB。根据程序局部性原理，程序在运行时对于内存的访问不会一下子就要访问全部的内存，相反程序对于内存的访问会表现出明显的倾向性，更加倾向于访问最近访问过的数据以及热点数据附近的数据。因此通过 Cache 缓存热点数据能够获得很大的收益。
Cache 和内存之间交换数据的单位是缓存行（cacheline），通常 cacheline 是 64B，这意味着当 CPU 通过虚拟地址访问内存时，不仅会将该地址的数据加载至 Cache，还会将该地址附近的共计 64B 的数据加载至 Cache（cacheline 对齐）。
CPU 读写主存的流程如下：
- 当 CPU 读取数据时，会先查看是否命中 Cache，如果 hit，直接从 Cache 中读取，不需要再去访问内存，如果没有 miss，则需要从主存读取数据并加载到缓存中。
- 当 CPU 写入数据时，同样会先查看是否命中 Cache，如果 hit，则直接修改 Cache，如果 miss，则需要先从主存做一遍数据读取，然后再修改缓存。至于是否写回内存呢，有两种策略：写直达（write-through）和写回（write-back）。
- 写直达（write-through）：将数据写入 Cache 同时也将数据写回内存。
- 写回（write-back）：将数据只写入 Cache，不写入内存，并将 cacheline 标记为 dirty（脏），然后在必要时再写回主存。
写直达与写回相比，好处很明显，能够让 Cache 和内存保持强一致性，但缺点就是性能低。而写回能够提供较高的性能，但是需要额外的机制保证数据能够正确的写回主存（总线监听机制），实现复杂。Cache 通常会使用写回（write-back）策略。
Cache 中修改的数据什么时候写回主存呢？Cache 中的数据会在两种情况下将数据写回缓存：
- cacheline 发生替换。因 Cache 的容量远远小于内存，因此必定会有不同的内存区域映射到同一个 cacheline，此时就会发生 cacheline 的替换。
- 当其他 CPU 核心通过总线请求 cacheline 的数据时，此时当前 CPU 核心必须先将 cacheline 的数据写回主存，同时将数据通过总线发送给其他 CPU。
因为每个 CPU 核心都有自己私有的 L1、L2，读写都是访问的自己私有的 Cache，因此会存在 CPU 核心之间 Cache 不一致的情况。如执行一个变量自增操作，CPU0 将读取变量至自己的 Cache 中，然后执行自增操作并将结果写会 Cache，然后 CPU1 读取同一变量，发现自己的 Cache 中没有，此时会去主存读取，而主存中存放的还是修改之前的值，因此 CPU1 Cache 中得到的就是旧值，CPU0 和 CPU1 的 Cache 就不一致了。
MESI 协议
为了解决 CPU 核心之间 Cache 不一致的问题，Intel 提出了 MESI 协议，现在的 CPU 基本上都是使用的 MESI 协议（或者 MESI 变种）来维护一致性，我们可以将 MESI 看做是状态机，在该协议中，缓存行（cache line）有四种状态：
- 已修改(Modified)：表示缓存行是脏的（dirty），与主存的值不一致，如果别的 CPU 核心要读取主存中的这块数据，该缓存行必须写回主存，然后缓存行的状态变为共享（Shared）。
- 独占的(Exclusive)：表示缓存行只在当前核心的缓存中，与已修改不同的是，该缓存行是干净的，既没有发生修改。CPU 核心可以直接对其进行修改，然后状态变为已修改。
- 共享的(Shared)：表示缓存行也存在于其他核心的缓存中且都是干净的（与主存一致）。处于该状态的缓存行不能直接被修改，需要该 CPU 核心向其他核心广播一个消息，要求其它拥有相同数据的核心把各自对应的缓存行标记为无效（Invalid）。
- 无效的(Invalid)：表示缓存行是无效的，不可以再读取该状态的缓存行数据。另外，一般的 cache line 替换时会优先填充 Invalid 状态的缓存行
缓存行的状态转换可以通过一个有限状态机来描述，触发状态转换的场景有两种：缓存所在处理器的读写，其他处理器的读写。一个处理器根据缓存行不同的状态可能会产生总线请求，而总线监听（bus snooping）能够监听到总线请求从而进行处理。以下是某个 CPU 操作时（针对同一地址），它的缓存行的状态转换表：
| 初始状态 | 操作 | 响应 |
|---|---|---|
| Invalid | 读 | 此时向总线发送读缓存的请求，其他处理器监听到该请求后，会检查自己是否有有效的数据副本，如果有，则通过总线发送该数据副本，此时该缓存行状态变为 Shared；如果没有，则会请求主存获取数据并写入至缓存行，缓存行状态变为 Exclusive。 |
| Invalid | 写 | 此时向总线发送写缓存的请求，其他处理器监听到该请求后，会检查自己是否有有效的数据副本，如果有，则其中一个通过总线发送该数据副本，同时这些拥有有效副本的缓存都将设置为 Invalid，如果没有，则会请求主存获取数据。为什么要获取主存中的值？”因为此前没有该缓存，获取是为了独占缓存“。之后该处理器会向缓存行中写入修改后的值(Modified) 。 |
| Exclusive | 读 | 只有当前处理器拥有该缓存，因此不会发送总线请求，状态保持不变。 |
| Exclusive | 写 | 只有当前处理器拥有该缓存，因此不会发送总线请求，此时直接写入修改后的值，缓存行状态变为 Modified。 |
| Shared | 读 | 没有总线请求产生，状态保持不变。 |
| Shared | 写 | 其他处理器中拥有该缓存，因此需要发送总线请求，其他处理器监听到该请求后，会将对应的缓存行标记为 Invalid，然后再写入当前处理器缓存行，当前处理器缓存行的状态变为 Modified。 |
| Modified | 读 | 没有总线请求产生，直接读取缓存，状态保持不变。 |
| Modified | 写 | 同样没有总线请求产生，状态保持不变，直接修改缓存为新值即可。 |
- 写操作仅在缓存行处于已修改（M）或者独占状态（E）时才可以自由执行，如果在共享（S）状态，都需要广播通知其他处理器，让它们把缓存置为无效（I），这种广播操作称为 RFO（Request For Ownership）。
- 对于处于已修改状态的缓存行，还需要监听各处理器对其的读请求，发送其数据到总线的同时还要写回主存。如果发生缓存行的替换，数据也要写回主存，缓存行替换是缓存行中存放的数据对应的地址和本次请求的地址不一致，那么处理器知道不能简单的覆盖，必须先将之前修改的数据写回至主存，然后再写入新的值。
- 对于共享状态的缓存行，要监听使其无效或请求拥有的的广播，当匹配时把该缓存行置为无效（Invalid）。
总线监听（bus snooping）是指 CPU 核心的缓存控制器会监视总线上的数据传输，它会监视总线上每一条内存访问。当某个 CPU 修改自己私有的 Cache 时，如果产生了总线请求，硬件会广播通知到总线上其他所有的 CPU，对于每个 CPU 来说会有特殊的硬件来监听广播事件，并检查是否有相同的数据被缓存在自己的 Cache，然后进行相应的处理，这个过程就称为总线监视。
MESI 协议消息
Cache 之间数据和状态同步沟通，是通过发送消息（MESI Protocol Message）进行同步和沟通。MESI 主要涉及一下几种 message：
- Read：如果 CPU 需要读取某个地址的数据（如果其他 CPU 有就读取其他 CPU 的，否则从主存读取）。
- Read Response：答复一个读消息，并且返回需要读取的数据。
- Invalidate：请求其他 CPU invalid 地址对应的 cacheline。
- Invalidate Acknowledge：回复 Invalidate 消息，表明对应的 cacheline 已经被 invalidate。
- Read Invalidate：Read + Invalidate 消息的组合。
- Writeback：该消息包含要回写到内存的地址和数据。
Store Buffer
当某个处理器尝试修改 cacheline 中的数据时，如果在其他处理器也存在，那么需要通过总线广播 Invalidate 消息，MESI 的广播操作带来的延迟对于处理器来说是难以忍受的。为了解决这个问题，在 CPU 和 Cache 之间又引入了 Store Buffer（写缓存器），这是一个容量比 Cache 更小的私有部件，当处理器需要修改数据时，会先将数据写入 Store Buffer（不再是写入 L1 Cache），然后继续处理其他事情，当收到其他处理器的响应时，才将数据从 Store Buffer 写入 cacheline 中。
Store Forwarding
在同一个处理器中，Store Buffer 的引入必然会带来一个问题，即异步操作引发的数据滞后性。从处理器的写操作会将最新的数据放入 Store Buffer 开始，Cache 中的数据就已经过时，此后所有的操作看到的都是旧的数据，直到 Store Buffer 将数据同步至 Cache 中。 为了解决这个问题，硬件工程师在 Store Buffer 基础上又实现了 Store Forwarding 技术，它使得 CPU 可以直接从 Store Buffer 读取数据，即支持将 CPU 放入 Store Buffer 的数据传递给后续的操作而不需要经过 Cache。
需要注意的是，虽然处理器可以直接读取其 Store Buffer 中自己以前的写操作，但是在这些操作从 Store Buffer 刷新到 Cache 中之前，其他处理器是无法看到这些写操作的，这意味着，Store Forwarding 技术只能解决单个处理器中的缓存数据滞后问题，无法解决多核处理器的此类问题。
Invalid Queue
由于 Store Buffer 的容量很小，因此它很容易就会被填满，此时处理器必须等待它发出的使缓存无效的广播请求得到响应，才可以将 Store Buffer 中的数据转移到高速缓存（Cache），从而释放空间。
为了解决这个同步操作带来的延迟问题，硬件工程师又为每个处理器添加了一个无效队列（Invalid Queue），处理器在监听到使缓存无效的消息后，直接将消息放入无效队列中排队，然后立即发送回复消息，这就大大降低了响应的延迟。
注意，有些处理器并没有实现 Invalid Queue。
无效队列也可能会导致数据滞后性，无效队列用于缓存 cacheline 的失效消息。假设 x=0 是共享的，当 CPU0 写入 x=1，并广播 Invalidate 消息，收到回复后从 Store Buffer 将修改刷入 cache，此时 CPU1 读取 x=0 仍是允许的，因为使得 cacheline 失效的消息被缓冲在了 Invalid Queue 中，可能还未被应用到 cacheline 上。同时这也是指令乱序的表现，CPU0 的 store(写) 是发生在 CPU 1 的 load(读) 之前的，但是 CPU1 的 load 还是读到了 CPU0 store(写) 之前的数据。下面的内存屏障就可以用于解决这种问题，load 屏障的作用就是将 Invalid Queue 缓冲刷新。
Memory Barrier
内存屏障（Memory Barrier）又称为内存栅栏（Memory Fence），其目的为了阻止 CPU 对指令的重排序（在有些编译器里也有指令重排序的概念）。根据 CPU 对变量的操作读（load） 和写（store），两两组合共有 4 种内存屏障：
| 名称 | 指令示例 | 描述 |
|---|---|---|
| LoadLoad Barrier(读屏障) | Load1; LoadLoad; Load2 | 保证 Load1 的数据读取先于 Load2 及其之后的数据读取。（配合 StoreStore，使所有 Store Barrier 之前发生的内存更新，对 Load Barrier 之后的 load 操作都是可见的）。 |
| StoreStore Barrier(写屏障) | Store1; StoreStore; Store2 | a. 保证 Store1 的数据写入立即刷入内存。 b. 保证 Store1 先于 Store2 及其后的存储操作，因此屏障后的写操作对屏障前的结果是可见。 |
| LoadStore 屏障 | Load1; LoadStore; Store2 | 保证 Load1 的数据读取先于 Store2 的数据写入。 |
| StoreLoad 屏障 | Store1; StoreLoad; Load2 | a. 保证 Store1 的数据写入立即刷入内存。 b. 保证 Store1 先于 Load2 及其之后所有的数据读写操作。使得该屏障之前的读写操作都在屏障前结束，屏障之后的读写操作都在屏障后开始，因此屏障后的读写操作对屏障前的结果是可见。 |
StoreLoad 屏障同时具备其他三个屏障的效果，因此也称之为全能屏障（full Barrier，mfence），是目前大多数处理器所支持的，但是相对其他屏障，该屏障的开销相对较高。
内存屏障除了有阻止指令重排序的作用，还与 MESI 协议有关，我们知道 MESI 为了优化性能，引入了 Store Buffer 和 Invalid Queue，而通过写类型的内存屏障能触发内存的强制更新，因此也会让 Store Buffer 中的数据立刻写回到高速缓存中。读类型的内存屏障会让 Invalid Queue 中的对于同一缓存行最新一次 load 操作之前的全部标记为失效（因为一定会被最后一次覆盖）。
指令重排序和指令乱序是两个东西，指令重排序是由于 CPU 做的优化（有些编译器中也有），对指令的顺序进行调整以提升执行效率，而指令乱序是由于 Store Buffer 和 Invalid Queue 导致的错误顺序的执行。指令重排序和指令乱序在并发/行场景都有可能导致未预期的结果。
上面说的内存屏障是抽象概念，下图是各平台对于内存屏障的支持（no-op 表示没有相关指令）：
CAS 原理分析
CAS 全称是 Compare And Swap（比较并交换），CAS 用于将一个变量的值与我们期望的值进行比较（Compare），如果相等则使用新的值去替换（Swap）变量的值，否则不做任何操作。虽然 CAS 分为比较和交换，但整个过程是原子执行的（atomic），在硬件层级会提供相应的原子指令，来保证在多核 CPU 系统并行下的一致性。如 x86 架构下的 compxchg，本节我们就来分析一下 CAS 的原理，它是如何保证原子性的。
compxchg
compxchg 是 x86 平台下对于 CAS 的实现，这是一条原子指令（多核环境下会自动添加 lock指令前缀保证原子性），compxchg 指令定义如下：
cmpxchg destination, sourcecompxchg 指令会将内存地址 destination 的值（也就是内存中存储的变量的值）和寄存器中的值（也就是我们期望的值）进行比较，如果相等，则将新值 source 写入指定的内存地址 destination（也就是使用新值去替换变量的值），否则，则什么都不执行。
假设有一个变量 lock，初始值为 1，我们希望如果 lock 等于 1 则将其修改为 0，用 compxchg 指令的伪代码实现如下：
mov 1 %eax
compxchg [lock] 0- 将我们期望的值 1 设置到寄存器中，不同字节大小的数据类型使用不同的寄存器，eax 用于处理整型（4 字节）。
- compxchg 会读取 eax 寄存器的值，然后和 lock 的值进行比较，如果相等则将新值 0 写入 lock，否则什么都不做。
在 x86 架构中，cmpxchg 指令仅能操作 32 位或 64 位的数据，像 byte 等需要包装为 32 位或 64 位的，因此，你可以看到 juc 包中只有 AtomicInteger 和 AtomicLong，没有 AtomicByte、AtomicShort 等。
原子性问题
现代的计算机 CPU 通常包含多个处理器核心，因此存在多个处理器同时执行 CAS 指令时，我们先来看看如果 CAS 指令不是原子的，那么会导致什么问题。在 CPU 执行 CAS 指令时至少会分为以下步骤：
- 从内存 read 变量的值到 CPU 内部的寄存器。
- 将变量的值和我们期望的值进行比较。
- 如果比较相等，则需要将新值写回变量。
还是以使用 CAS 指令修改 lock 为例，假设在两个 CPU 核心上同时执行 CAS 指令，可能会出现以下情况：
两个 CPU 核心都能够成功的修改 lock 变量的值，这不是我们期望的结果，我们期望只有一个修改成功，出现这个问题就是因为不是原子操作导致的，在 CPU0 执行过程中 CPU1 也可以穿插执行。
可见性问题
现代多核 CPU 计算机为提升内存的访问速度，会在 CPU 和内存中间增加一层高速缓存（CPU Cache），Cache 是分级的，分为 L1、L2、L3，其中 L1、L2 是每个 CPU 核心私有的，L3 是所有核心共享的。CPU 核心在读取内存时，会先将数据加载到自己的缓存，当写入数据时，同样会先写入自己的缓存，当必要时才会将数据写回内存（缓存行替换时或其他 CPU 请求缓存行时）。因此，在多核 CPU 中，会存在 Cache 的一致性问题。依然以上述 CAS 修改 lock 为例：
因为每个 CPU 都有自己私有的 Cache，当 CPU0 执行完毕后，lock = 0 并没有立即写回主存，而是先写入自己的 Cache，当 CPU 1 执行时，从内存中读取到的还是旧数据 lock = 1，导致两个 CPU 核心都能够成功的修改 lock 变量的值。出现这个问题就是因为私有 Cache 导致 CPU0 的修改对 CPU1 不可见。尽管 MESI 能够保证大部分情况下的多核一致性，但由于 Store Buffer 和 Invalid Queue 的引入还是可能会导致缓存不一致的。
保证原子性
我们说过 compxchg 操作是原子的，那硬件是如何实现操作的原子性呢？
总线锁定（Bus Locking）
当 CPU 发出一个原子操作时，可以先锁住 Bus（总线），这样就可以防止其他 CPU 的内存操作，等原子操作结束后，释放 Bus，这样后续的操作就可以进行，通过总线锁定可以实现原子操作，但是会导致其他无关的内存操作也无法继续。实际上，我们只关心我们操作的地址数据，只要把我们操作的地址锁住即可，而无关的内存地址访问仍然可以继续，所以引入了另一种解决办法。
缓存锁定（Cache Locking）
为了实现多核 Cache 一致性，现在的硬件基本采用 MESI 协议（或者MESI变种）维护一致性。因此我们可以借助多核 Cache 一致性协议 MESI 实现原子操作。我们知道 cacheline 的状态处于 Exclusive 或者 Modified 时，可以说明该变量只有当前 CPU 私有 Cache 缓存了该数据。所以我们可以直接修改 cacheline 即可更新数据。并且 MESI 协议可以帮我们保证互斥。当然这不能保证 CAS 操作期间不被打断，因此我们还需要做些手脚实现原子操作。
依然以上述 CAS 修改 lock 为例，当 CPU0 试图执行 compxchg 操作时：
- CPU0 发出“Read Invalidate”消息，从其他 CPU Cache 或主存读取数据，并要求其他 CPU 将 lock 变量所在的缓存行 Invalid。CPU0 将 cacheline 置成 Exclusive 状态，然后将该 cacheline 标记 locked。
- 然后 CPU0 读取原子变量、比较、修改，最后写入 cacheline。
- 将 cacheline 置为 unlocked。
在步骤 1 和 3 之间，如果其他 CPU（如 CPU1） 尝试执行一个原子 CAS 操作，CPU1 同样会发送一个“Read Invalidate”消息，CPU0 收到消息后，检查对应的 cacheline 的状态发现是 locked，暂时不回复消息（CPU1 会一直等待 CPU0 回复 Invalidate Acknowledge 消息），直到 cacheline 变成 unlocked，这样就可以实现原子操作。我们称这种方式为缓存锁定或缓存行锁定（Cacheline Lock）。缓存锁定要求操作的数据要位于一个 cacheline，不能跨缓存行（cross cacheline），如果跨缓存行还是会使用总线锁定。在 nocache 的系统或内存区域中也是使用总线锁定。
以下是 Intel 手册的描述，从 P6 系列处理器开始，如果访问的内存区域是完全包含在处理器的一个缓存行，并不需要已经在缓存中（可以稍后再 load 到 cache），而是要求数据没有跨缓存行（cross cacheline）存储，并采用 write-back 模式，那么执行 atomic 操作时 Lock# 信号不会被发送，即不会锁定总线，而是依赖于缓存一致性协议来保证，这个操作被称为 cache locking，也就是上面我们说的缓存行锁定（Cacheline Lock）。
Intel SDM 卷3A chapter 8.1.4 For the P6 and more recent processor families, if the area of memory being locked during a LOCK operation is cached in the processor that is performing the LOCK operation as write-back memory and is completely contained in a cache line, the processor may not assert the LOCK# signal on the bus. Instead, it will modify the memory location internally and allow its cache coherency mechanism to ensure that the operation is carried out atomically. This operation is called“cache locking.” The cache coherency mechanism automatically prevents two or more processors that have cached the same area of memory from simultaneously modifying data in that area.
如果多个 CPU 同时执行对同一地址的原子操作怎么办？
当多个 CPU 同时执行针对同一地址的原子操作时，其实他们就是在试图修改自己持有的 cacheline，假设两个 CPU 都持有相同地址对应的 cacheline，且状态为 S，如果想要修改就需要向其他 CPU 发送 Invalidate 消息，将自己变成 E 或 M，如果两个 CPU 同时向总线发起 Invalidate 消息，总线根据特定的仲裁协议来裁决是 CPU0 还是 CPU1 能赢得这个操作了， 胜者完成操作，失败者需要接受结果，Invalid 自己对应的 cacheline。
在总线冲裁协议中会实现缓存行的锁定，总线仲裁协议会保证所有处理器都能公平的访问内存，而不会出现处理器饥饿问题（starving core）。虽然 bus lock 没了，但如果出现大量的多核针对同一 cacheline 的竞争操作，也会导致反复互相的 Invalidate。同样会降低性能。
保证可见性
了解了如何保证原子性，现在我们还面临可见性的问题，这里就涉及到内存屏障了。
在实现 CAS 指令时，会通过内存屏障保证可见性，在多核环境，compxchg 会自动添加 lock 指令前缀，该指令前缀有两个功能，第一个就是保证修饰指令的原子性，也就是我们上一节说的原子性实现，在 x86 中也是通过 lock 指令前缀体现的。第二个就是会启用全屏障（StoreLoad Barrier），还记得 Memory Barrier 那一节的那张图吗，lock 指令前缀就拥有全屏障的效果，因此它会保证在 CAS 指令执行之前所有关于该变量的修改都已经刷入主存，即可见的。