内存序

1. MESI 协议

CPU 中每个核有自己的 L1 和 L2 缓存，然后又有共享的 L3 缓存。这样一来，就可能出现缓存一致性的问题，比如一个核将某个地址的数据缓存到自己的 L2 缓存中，另一个核又把这个地址的数据修改了，而前者的 L2 缓存此时并没有更新，这就出现了不一致的问题。

为了使得多核之间的缓存保持一致，我们有 MESI 协议，每个缓存行有如下四种状态：

多个 CPU 之间通过在总线上发送消息来协调缓存行的状态，消息有如下几种类型：

缓存行可能有如下的状态转换：

• M -> E

  当前 CPU 发 Writeback

  将某个缓存行写回到内存，此时内存中的数据是最新的。这个转换的产生可能是 CPU 执行到主动写回缓存行的执行，又或是处理器的缓存控制器有一些策略，在总线空闲时将缓存写回内存。

  这个状态转换的必要性有：

  • 有的内存可能是非易失性的
  • 在进行 DMA 时，将内存更新是有必要的
  • 在空闲时就把内存更新，这样的话后续如果需要把缓存行驱逐，就可以直接把缓存行丢掉，无需再等待写回。

• M -> S

  当前 CPU 收到了 Read 消息

  回复 Read Response

• M -> I

当前 CPU 收到了 Read Invalidate 消息

回复 Read Response 和 Invalidate Acknowledge

• E -> M

  当前 CPU 写 E 状态的缓存行前直接将缓存行状态置为 M。这个状态转移不需要任何的消息传递。

• E -> S

  类似 M -> S 的状态转移，收到了 Read，回复 Read Response

• E -> I

  类似 M -> I 的状态转移，收到了 Read Invalidate，回复 Read Response 和 Invalidate Acknowledge

• S -> M

  当前 CPU 要写 S 状态的缓存行，发出 Invalidate 消息。当前 CPU 必须要等待收到 Invalidate Acknowledge 后才能完成状态的转移。

• S -> E

  当前 CPU 如果意识到某个 S 状态缓存行即将被修改，则发出 Invalidate 消息。当前 CPU 必须要等待收到 Invalidate Acknowledge 后才能完成状态的转移。

• S -> I

当前 CPU 收到了 Invalidate 消息，并回复 Invalidate Acknowledge。

• I -> M

  当前 CPU 要对一个未缓存的内存进行 Modify and Write，发出 Read Invalidate 消息。当前 CPU 必须等待收到 Read Response 和 Invalidate Acknowledge 后才能完成状态的转移。

• I -> E

  当前 CPU 要读一个未缓存的内存，并且发现没有其他 CPU 持有目标缓存行。当前 CPU 必须等待收到 Read Response 后才能完成状态的转移。

• I -> S

  当前 CPU 要读一个未缓存的内存，并且发现存在其他 CPU 持有目标缓存行。当前 CPU 必须等待收到 Read Response 后才能完成状态的转移。

MESI而不是MSI

E 状态的引入可以提高效率。CPU 要读一个没有被缓存的内存地址，且这个内存没有进入其他 CPU 的缓存的话，那么根据 MESI 的设计，缓存行会直接变为 E 状态。如果是 MSI 协议的话，缓存行会变为 S 状态，即使实际上该缓存行没有被共享。后续再对该缓存行进行写入的话，如果是 MESI 就会直接从 E 转为 M 状态，不需要传递消息。而如果是 MSI，则还需要广播 Invalidate 消息，等待回应才能变为 M 状态。

Read Invalidate 必要性

Read Invalidate 可以保证 Read and Modify 的原子性，一个 CPU 发 Read Invalidate 前会等待前面的 Read Invalidate 消息被 ACK 之后再发出去。

同时，对于需直接写一个没有缓存的内存地址的时候，直接使用一个 Read Invalidate 而不是 Read + Invalidate 也能提高效率。

2. Store Buffer

仅靠 MESI 虽然确保了 CPU 缓存一致性，但是却不够快。首先一个发现是，MESI 可能会引入一些不必要的停顿：

比如如果我们写缓存行时，其实无需等待其他 CPU 回复已经 Invalidate 了，即使是当前 CPU 中没有目标缓存行的数据，那也无需等待其他 CPU 来吧缓存行数据传过来，因为无论之前的缓存行数据是多少，我们后面都是要覆盖掉的。

所以我们可以引入 Store Buffer，如果 store 的时候目标内存没有在缓存中，就直接把要写入的内容丢进 Store Buffer 中：

后续当前 CPU 拿到了对应的缓存行，且缓存行状态为 E 或是 M ，CPU 会把 store buffer 里的内容写到缓存行中。

直接这么做可能会出现这种情况：前面先对一个变量进行写入，然后 CPU 发 Read Invalidate，然后把写入的操作放入 Store Buffer 继续执行下一个指令。然后其他 CPU 将目标缓存行传递给当前 CPU，当前 CPU 后面再 load 前面 store 的变量，此时如果直接走缓存行的话会把写入之前的数据读出来。

所以需要一个 forwarding 机制，如果 load 的变量在 store buffer 里有对应，则直接取 store buffer 里的内容。

同时 Store Buffer 还会引入另一个问题，比如：

c
1
2
3
4
5
6
7
8
9
void foo(void) {
    a = 1;
    b = 1;
}

void bar(void) {
    while (b == 0) continue;
    assert(a == 1);
}

当 CPU 0 运行 foo，CPU 1 运行 bar 的时候可能会出现这样一种情况：

• CPU 0 写 a = 1，但是由于 a 不在 CPU 0 的缓存中，所以写入了 store buffer 中，并发出 Read Invalidate 消息。
• CPU 0 随后写 b = 1，由于 b 在 CPU 0 的缓存中，所以直接写入，并且此时 CPU 0 独占 b 缓存行。
• CPU 1 读取 b 的值的时候，会先从 CPU 0 中获取到 b 的缓存行，看到 b 为 1 于是跳出循环。
• CPU 1 后面判断 a 是否为 1 的时候，可能 a 存在于 CPU 1 的缓存中，但是 CPU 1 还没收到 CPU 0 的 Read Invalidate 消息，所以还是基于旧的 a 的值进行 assert，assert 失败。

这其中的问题是，a = 1 先执行，b = 1 后执行，但是后者先被 CPU 1 看到。

为了解决这个问题，就需要引入内存屏障：

c
1
2
3
4
5
6
7
8
9
10
void foo(void) {
    a = 1;
    smp_mb();
    b = 1;
}

void bar(void) {
    while (b == 0) continue;
    assert(a == 1);
}

当 CPU 0 执行到 smp_mb() 的时候，会强制把 store buffer 中的操作应用到缓存行中。

3. Invalidate Queue

store buffer 本身还是比较小，容易变满，满了的话就需要等待 Invalidate Acknowledge 并写到缓存行。同时，使用内存屏障也会有这个问题。Invalidate Acknowledge 的响应速度比较关键，但是当前 CPU 正忙于执行大量的指令，可能延后才会响应 Invalidate Acknowledge。

于是又引入了 Invalidate Queue，当 CPU 收到了 Invalidate 消息后，会把这个消息放入 Invalidate Queue，而不去真的 Invalidate 掉某个缓存行，然后立刻回复 Invalidate Acknowledge。

但这又会带来一个新的问题：

c
1
2
3
4
5
6
7
8
9
10
void foo(void) {
    a = 1;
    smp_mb();
    b = 1;
}

void bar(void) {
    while (b == 0) continue;
    assert(a == 1);
}

还是这个代码，当 CPU 0 运行 foo，CPU 1 运行 bar 的时候可能会出现这样一种情况：

• CPU 0 写 a = 1，但是由于 a 不在 CPU 0 的缓存中，所以写入了 store buffer 中，并发出 Read Invalidate 消息。
• CPU 1 收到 Read Invalidate，将其放入 Invalidate Queue 中，然后立刻返回 Invalidate Acknowledge。
• CPU 0 于是独占了 a 所在缓存行，store buffer 中对 a 的修改于是应用。于是 CPU 0 轻松地通过了下一行的 smp_mb。
• CPU 0 写 b = 1，由于 b 所在缓存行已经在 CPU 0 中了，于是直接写了缓存行。
• CPU 1 读 b，发起 Read 消息并得到了响应，读到了 b 为 1。
• 后面再读 a，由于之前那个 Read Invalidate 被放入了 Invalidate Queue 中，可能还没应用，所以读到了 a 为 0，assert 失败。

其中的关键是，foo 那里的内存屏障保证了 a 修改的消息发出去了，但是由于 Invalidate Queue 的存在，这不能保证 bar 那里应用了这个消息。

在 bar 中读 a 前加内存屏障可以解决：

c
1
2
3
4
5
6
7
8
9
10
11
void foo(void) {
    a = 1;
    smp_mb();
    b = 1;
}

void bar(void) {
    while (b == 0) continue;
    smp_mb();
    assert(a == 1);
}

smp_mb 会将当前 CPU 的 Invalidate Queue 中的条目全部打上一个标记，后续的所有 load 操作都必须暂停，直到所有带有标记的 Invalidate 消息都被处理。

4. 内存序

内存序分为如下几种：

• SeqCst：像 smp_mb 这个内存屏障一样，将 Store Buffer 和 Invalidate Queue 都清空。smp_mb 就对应 Rust 的：

  rust
  1
  atomic::fence(Ordering::SeqCst);
  

• Release：保证执行后面的操作时，前面在 Store Buffer 里的内容都被排出。

• Acquire：将 Invalidate Queue 清空

• AcqRel：相当于是把 Acquire 和 Release 结合起来

• Relaxed：对 Store Buffer 和 Invalidate Queue 都不进行任何特殊行为，就是普通的读或写。

内存序可以用在内存屏障上，也可以用在原子操作上。Acquire Load 可以理解为是先有 Load 然后再 Acquire Fence，Release Store 可以理解为是先有 Release Fence 然后再 Store。

直觉上来说，如果我们只在乎原子变量本身，比如就作为一个计数器，那么直接使用 Relaxed 就行。

如果这个原子变量涉及到消息的传递，就需要用 Acquire 和 Release。比如原子变量 x 表示当前自旋锁是否被占有，这个自旋锁保护了数据 data。这个 x 其实就涉及到了消息的传递，传递了 data 能否被访问的消息。一般我们会在 Store 操作中使用 Release，我们一般的行为是先修改 data，再将 x 置为 0 来释放锁，Release 就相当于把 data 已经修改的这个消息附在 x 这个 Store 操作上面。通常在 Load 操作中使用 Acquire，Acquire 相当于就会让当前 CPU 收到前面 Release 发出去的消息，这样当前 CPU 就能看到 data 最新的值。此时 x 相当于一个同步点，Release 发送消息，Acquire 接收消息。

AcqRel 一般用于 read-modify-write 操作，可以让 read 过程有 Acquire 语义，modify 过程有 Release 语义。

注意一个细节，Release 并不保证 Store Buffer 一定被清空，于是 AcqRel 也不保证，这就是 AcqRel 和 SeqCst 的区别之一。准确来说，Release 是建立了一个 happens-before 的关系，比如你修改了 data，然后对 x 用 Release Store 设置了 0，Release 只能确保说，只要你读到 x 为 0，那么就一定能读到最新的 data，不能确保我 Release Store 后其他 CPU 再 Load 一定能读到 x 是 0，有可能 x 还是旧值。

SeqCst 更像是一种全局的同步。由于其会立刻刷新 Store Buffer，这相当于是让前面的 Store 立刻被应用到缓存行。同时 SeqCst 确保了一个全局的顺序，硬件层面会确保 同一时刻只有一个 SeqCst 在执行，前面的 SeqCst 搞完了才能执行下一个 SeqCst。这个很重要，这就意味着往往是 SeqCst 之间建立同步关系，其他内存序可能不能和 SeqCst 建立同步关系。比如一个 CPU 进行 Store SeqCst 之后，另一个 CPU 进行 Acquire Load，并不一定能立刻看到 Store 的值，因为可能有这个情况：Store SeqCst 执行之后，Store Buffer 确实刷新了，值确实被应用到缓存行上了，但是还需要向另一个 CPU 发送 Invalidate 消息。另一个 CPU 可能在收到这个 Invalidate 消息之前就执行了 Acquire，确实是把 Invalidate Queue 清空了，但是没有处理掉这个 Invalidate 消息，导致看到的还是旧的值。

5. 指令重排

现代 CPU 采用乱序执行指令，可能会对指令进行重排。甚至现代的编译器也会为了优化程序性能而对指令进行重排。

rust
1
2
data = 114514;
x.store(0, Ordering::Release);

我们希望在看到 x = 0 的同时也能看到 data = 114514，但是如果考虑到指令重排的话，这可就说不准了，因为 data = 114514 可能会被排到下面。

所以内存序不仅可以配置一个 CPU 眼中另一个 CPU 对内存修改的顺序，还对指令的重排进行了限制：

• Acquire：Acquire 下面的指令不能和上面的 Load 重排，也被称为阻止了 LS 和 LL 重排（可以理解为 L->S，就是一定是先 L 再 S，LL 也类似理解）。一般都是先 Load 再用 Acquire Fence，或者说 Acquire Load 直接把这两个合在一起了，所以也可以理解为是保证下面的指令不会被重排到上面。
• Release：和上面对应，表示 Release 上面的指令不能和 Store 重排，也被称为阻止了 LS 和 SS 重排。可以理解为上面的指令不会被重排到下面。
• AcqRel：将两者结合起来，但并不意味着 AcqRel Fence 能双向阻塞住两边的指令，其只能阻止 LS、LL、SS 重排，不能阻止 SL 重排。比如我们可以把 Acquire 看成是一个 $[y,+\infty)$ 的区间（$y$ 为 Load 操作），把 Release 看成是一个 $(-\infty, x]$ 的区间（$x$ 为 Store 操作），AcqRel 只能同时保证大于 $y$ 的都在 $y$ 后面，小于 $x$ 的都在 $x$ 前面，但并没有保证 $x\le y$ 一定成立，这也就是 SL 重排。
• SeqCst：区别于 AcqRel，能够阻止 SL 重排，即保证 $x\le y$ 一定成立。

6. RMW

RMW 指的是 read modify write，像是 compare and swap 和 fetch and add 这样既有读又有写的原子操作。

在 MESI 协议一节我们提到，RMW 操作会像其他 CPU 发送 read invalidate 消息，并且 CPU 只有在上一个 read invalidate 消息处理完毕之后才会回复 ack。这使得 RMW 操作不同于单纯地把 load 和 store 合成一个原子操作，会跳过 store buffer 和 invalidate queue（但并不意味着清空 store buffer 和 invalidate queue）。

比如，对于原子变量 x，初始值为 0。第一个 CPU 先进行 cas(0, 1) 的操作，将 x 变为 1。后面第二个 CPU 再进行 cas 操作的时候，读到的 x 必然是 1 而不可能是 0。RMW 操作在单个变量上面有类似 seqcst 一样的全局一致性。如果第二个 CPU 执行的是 load 的话，那么还是有可能读出来 x=0。