浅谈Store Buffer与Cache Coherence

本文只讨论一个问题：

1 2	CPU 0 Store Buffer：x = 1 CPU 1 Store Buffer：x = 2

这两个 Store 能否同时存在？

答案是：

可以同时存在于两个 CPU 各自的 Store Buffer 中；但当它们真正排出并进入共享的 coherent memory system 时，必须由 Cache Coherence 决定先后顺序。

本文只讨论 x86-64 上自然对齐的普通 Store，以及普通 WB（Write-Back）cacheable memory。

本文示例是硬件模型，不表示普通非原子 C/C++ 程序可以直接这样访问共享变量。

Prerequisite

浅谈 x86 的 TSO memory ordering

What

假设初始状态是：

x = 0

两个 CPU 同时执行：

1
2
3

CPU 0                       CPU 1

x = 1                       x = 2

每个 CPU 都有自己的私有 Store Buffer。Store 可以先进入本地 Store Buffer，而不需要立即对其他 CPU 可见。

因此，某个时刻完全可能出现：

CPU 0                                      CPU 1
┌───────────────────┐                      ┌───────────────────┐
│ Store Buffer      │                      │ Store Buffer      │
│                   │                      │                   │
│ x = 1             │                      │ x = 2             │
└───────────────────┘                      └───────────────────┘

                    Shared coherent state
                            x = 0

也就是说：

1 2	CPU 0 SB：x = 1 CPU 1 SB：x = 2

可以同时存在。

x86-TSO 可以抽象成每个硬件线程拥有一个私有 FIFO Store Buffer，Store 随后再从各自的 Buffer 传播到共享内存。

为什么不会冲突？

容易产生的误解是：

Cache Coherence 只允许一个 CPU 修改某条 Cache Line，因此两个 CPU 不可能同时保存对 x 的 Store。

这里混淆了两件事：

Store 位于本核 Store Buffer 中

和

Store 已经获得 Cache Line 的写权限，并对外可见

它们不是一回事。

Store Buffer 是 CPU 的私有结构：

Store 进入 Store Buffer
        ≠
CPU 已经获得 Cache Line 的写权限
        ≠
Store 已经对其他 CPU 可见

因此，两个 CPU 可以分别暂存：

1
2
3

CPU 0：我准备写 x = 1

CPU 1：我准备写 x = 2

但是，它们不能无序地同时更新共享的 coherent Cache Line。

真正排出 Store Buffer 时，Cache Coherence 会对包含 x 的 Cache Line 进行所有权仲裁。

基础 Example

初始状态：

x = 0

两个 CPU 分别执行：

1
2
3

CPU 0                       CPU 1

W(x) = 1                    W(x) = 2

首先，两个 Store 都进入各自的 Store Buffer：

时间
 │
 ▼

CPU 0                                      CPU 1

Store Buffer：x = 1                        Store Buffer：x = 2
        │                                          │
        │ 尚未全局可见                             │ 尚未全局可见
        │                                          │
        └───────────────┬──────────────────────────┘
                        │
                        ▼
                Cache Coherence 仲裁

此时两个 Store 可以同时处于 pending 状态。

接下来，Cache Coherence 必须决定谁先获得包含 x 的 Cache Line 的写权限。

最终只有两种顺序。

情况一：CPU 0 先排出

假设 CPU 0 先获得写权限：

CPU 0 的 x = 1
        │
        ▼
先排出 Store Buffer
        │
        ▼
x = 1 对外可见

随后 CPU 1 获得写权限：

CPU 1 的 x = 2
        │
        ▼
后排出 Store Buffer
        │
        ▼
x = 2 对外可见

同一地址上的 coherence order 是：

CPU 0：W(x) = 1
        │
        │ coherence order
        ▼
CPU 1：W(x) = 2

可以表示为：

1	W0(x = 1) →co W1(x = 2)

最终：

x = 2

情况二：CPU 1 先排出

也可能是 CPU 1 先获得写权限：

CPU 1：W(x) = 2
        │
        │ coherence order
        ▼
CPU 0：W(x) = 1

可以表示为：

1	W1(x = 2) →co W0(x = 1)

最终：

x = 1

因此，两个 Store 可以同时位于各自的 Store Buffer 中，但一旦传播到共享 coherent state，同一地址上的 Store 必须形成一个确定的顺序。x86-TSO 相关模型和一致性约束都禁止同一地址上的 Store 处于相互矛盾的全局顺序中。

“串行化”的含义

这里的串行化不是说：

1 2	CPU 0 必须执行完全部指令然后 CPU 1 才能开始执行

它只表示：

对同一个地址 x 的两个 Store，在 coherent memory system 中必须存在明确的先后顺序。

合法情况是：

1
2
3

x = 1
然后
x = 2

或者：

1
2
3

x = 2
然后
x = 1

不允许存在：

1
2
3

CPU 2 认为：x = 1 在 x = 2 前面

CPU 3 认为：x = 2 在 x = 1 前面

对于同一个内存位置，Cache Coherence 要求相关 Store 被序列化到一致的 coherence order 中。

需要注意：

其他 CPU 不一定真的读取到中间值。

例如实际顺序是：

1	x = 0 -> x = 1 -> x = 2

某个 CPU 可能一直没有读取 x，等它真正读取时只看到：

x = 2

但在 coherence order 中，x = 1 仍然排在 x = 2 前面。

排出 Store Buffer 不等于写入 DRAM

这里所说的：

1	Store 排出 Store Buffer

不要简单理解成：

1	数据立即写入 DRAM

对于普通 Write-Back Cache，Store 排出通常意味着：

获得包含 x 的 Cache Line 的写权限
        │
        ▼
将 Store 合并到本核的 Cache Line
        │
        ▼
Store 按照 Cache Coherence 规则对外可见

此时最新数据可能仍然位于某个 CPU 的 Cache 中，并没有立即写回 DRAM。

所以，更准确的理解是：

Store 从 CPU 的私有 pending 状态，进入了由 Cache Coherence 管理的共享可见状态。

记忆图

CPU 0                                      CPU 1

┌──────────────────┐                       ┌──────────────────┐
│ Store Buffer     │                       │ Store Buffer     │
│                  │                       │                  │
│ x = 1            │                       │ x = 2            │
└────────┬─────────┘                       └────────┬─────────┘
         │                                          │
         │       两个 pending Store 可以共存        │
         │                                          │
         └──────────────────┬───────────────────────┘
                            │
                            ▼
                  Cache Coherence 仲裁
                            │
                 ┌──────────┴──────────┐
                 │                     │
                 ▼                     ▼

          x = 1 →co x = 2       x = 2 →co x = 1

              最终 x = 2            最终 x = 1

可以简单记成：

私有 Store Buffer 中：

CPU 0：x = 1
CPU 1：x = 2

可以同时存在。

进入共享 coherent state 时：

x = 1 → x = 2

或者：

x = 2 → x = 1

必须二选一。

总结

双 Store Buffer 场景的核心是：

“同时存在”描述的是两个 CPU 的私有 pending 状态；”串行化”描述的是这些 Store 对共享 coherent state 生效时的全局顺序。

因此：

1 2	CPU 0 SB：x = 1 CPU 1 SB：x = 2

可以同时存在。

但真正排出时，同一地址上的 Store 必须由 Cache Coherence 排成：

1	x = 1 →co x = 2

或者：

1	x = 2 →co x = 1

不会存在两个互相矛盾的全局顺序。

一句话概括：

两个 CPU 可以同时”准备写”同一个地址，但不能无序地同时”完成对外可见的写”；最终由 Cache Coherence 串行化。

参考资料:

文章目录