CAS 相关随笔

atomic::Ordering 相关

汇编层面的执行顺序

x86 CPU 的执行流程

1. 先按程序顺序抽取指令，并编码为微指令
2. 将指令中的逻辑寄存器分配为真正的物理寄存器，这过程确定了真正的 data dependency（表现为寄存器依赖）
3. 记录进 ROB （entry 记录为 uncompleted）记录了原始顺序，可以开始允许乱序执行
4. 发送各种类型的指令到各个 RS（比如加法操作 RS、读取 RS 等）
5. 各个执行单元每到空闲时，就从自己的保留站中抓取（操作数）已就绪的指令执行
6. 每个单元执行完一个指令，将其结果在 ROB 记为已完成
7. RU 会一直等待 ROB 队列头的指令直到其完成，如果完成则会将其提交并弹出 由 ROB 封装乱序执行细节，保证外部的顺序性

类似 consumer 将一系列任务发布到 message queue 中后，多个 consumer 在不同 topic 下乱序执行，最终汇总 ACK 到 message queue 中。

原子量的操作方式

原子量的操作有赖于 MESI 缓存一致性协议的实现。

比如一个原子量的 fetch_add 操作，其实 add 操作必然是原子的（CPU 的单指令），但是通过 fetch 这一过程，CPU 会尝试获取该原子量所在的缓存行的独占性，这一过程和获取 mutex 是一样，只不过这是一种高效的硬件锁。
它在获取到独占权后，会锁定总线，导致对对应缓存行的访问请求被拦截，直到 add 完成。

关于重排

x86 架构采用的是强内存模型/处理器顺序（processor order），仅允许将 load 指令不等待它前面的某个 store 完成。

因为 x86 存在 SB，一个 store 操作会在执行时挂起到 SB 中，等待真正被写入缓存或者内存。所以一个 load 可能不会等待 store 真正在其他核心可见（即真正的完成）之前，就已经完成。只要那个 store 的 dst，不是后面那个 load 的 src

• 编译器级别的汇编重排

编译器可能将一个函数内的多个访存操作不严格按照高级语言的顺序编译为汇编。

	编译器操作
Relaxed	无效果
Acquire	不把该语句后的 load 重排到其之前
Release	不把该语句前的 store 重排到其之后
SeqCst	Acquire + Release

• CPU 级别的乱序执行

x86 CPU 只会进行 Load Store 重排，因此 relaxed、acquire 以及 release 效果一致。

只需要专门说明 SeqCst。因为它不仅要保证一个核心上的顺序，还需要保证全局的顺序，因此必须强制操作内存这个全部核心共用的部分，这一部分通过 MESI 缓存一致性协议来达成。

	CPU 操作
Relaxed	无效果
Acquire	无效果
Release	无效果
SeqCst	该指令执行前，强制刷新整个 SB 到内存中

因此，其实原子操作本质上是在异步并发中，提供一些 确定的参照点，他们作用于自身的效果是次要的，对于程序其他部分代码的执行影响才是主要的功能。

在其中，可以认为 Acquire 和 Release 都是局部的影响因子，它们仅影响一个函数上下文中的代码。而 SeqCst 则要强势得多，他会强制清空 SB，等待总线仲裁完毕，以达成对于其他核心的 SeqCst 出现在同一视图下的目的（立刻可见只不过是副作用罢了）。

从而可知，AcqRel 在 单变量 的 RMW 操作上和 SeqCst 是等价的（比如 CAS）。但是在 多个变量 的、无关的非 RMW 操作时，必须使用 SeqCst，比如：

// thread A
x.store(1, SeqCst);
let rv = y.load(SeqCst);

// thread B
y.store(1, SeqCst);
let rv = x.load(SeqCst);

我们在特定情况下，必须使用 SeqCst，防止 store 的延迟写入导致 thread A 和 B 在 load 之后读才触发 store 的写入（load 这种非 RMW 操作不会在非 SeqCst 情况下强制触发刷新 SB）。