5.2 缓存一致性与伪共享

缓存映射解决一个核心怎样复用近期数据。本篇加入私有 cache 的多个核心，解释 MESI 的稳定状态、ownership 转移与 false sharing。

多份副本必须像一个内存位置

两名维修员分别在 Core 0 和 Core 1 上运行线程。两边都把地址 X 的 cache line 读进私有 L1。若 Core 0 随后写 X，Core 1 不能永远读到旧副本。

cache coherence 通常要为每个可缓存物理位置提供两类保证：

对同一位置的写入最终能按一个一致顺序被各参与者观察；
一个核心的读不能无限使用已被其他核心取代的旧副本。

精确定义随体系结构而异，但重点是单个位置的副本协调。它不等于 memory consistency model，后者规定不同地址的读写可以怎样重排和被观察；它也不等于 C/Java 语言内存模型，语言还要定义 data race、atomic、happens-before 和编译器变换。

硬件有 coherence，不代表带数据竞争的 C 程序就正确。编译器可以缓存变量、重排访问，语言层未定义行为不会被 MESI 自动修复。

MESI 的四种稳定状态

经典 MESI 给每个 cache line 副本标记一种稳定状态：

状态	本核可读	本核可直接写	其他 cache 是否可有有效副本	与下一层是否一致
Modified	是	是	否	否，本副本较新
Exclusive	是	是，随后变 M	否	是
Shared	是	否，先取得 ownership	可以	是
Invalid	否	否	不适用	本副本不可用

这是稳定状态的入门表。真实协议还有 transient state、请求队列、重试、目录或 snoop filter；MESIF、MOESI 等会添加转发者或 owned 状态。

读取一个 Invalid line

本核发出 read request。若没有其他 cache 持有有效副本，通常可得到 Exclusive；若已有共享者，则得到 Shared。若另一核持有 Modified 数据，最新值可能由拥有者直接转发或经某级 cache 处理，不一定先完整写回 DRAM。

写一个 Shared line

本核需要取得独占写权限，向其他 sharer 发出 invalidation，并等待协议所需的确认。之后本核进入 Modified，其他副本变 Invalid。

写一个 Exclusive line

由于没有其他有效副本，本核通常可静默从 E 转到 M，不必为这一写先广播 invalidation。

协议协调的是整条 cache line。即使线程写的是 line 内不同 byte，ownership 仍以 line 为颗粒迁移，这正是伪共享的根源。

coherence 不自动提供所有原子性

“cache line 有一致性”不能推出“line 内任意读改写都是原子的”。counter++ 至少包含读取、计算与写回；两个线程交错时仍会丢失更新。

C 中应使用 <stdatomic.h> 的原子类型和操作，或用锁建立同步。具体原子宽度是否 lock-free、对象对齐要求和跨 line 行为由实现与 ISA 决定。

#include <stdatomic.h>

static atomic_ulong counter = 0;

static void increment(void) {
    atomic_fetch_add_explicit(&counter, 1UL, memory_order_relaxed);
}

memory_order_relaxed 保证这个对象的原子读改写，不建立与其他普通数据之间的跨线程发布顺序。若 counter 同时充当“数据已准备好”的信号，就需要根据协议选择 release/acquire 或更强顺序。

原子指令也需要 cache line ownership。多个核心高频更新同一个原子计数器时，line 会在核心之间迁移，成为串行瓶颈；“lock-free”只描述进展性质，不承诺没有竞争成本。

伪共享：两名维修员没碰同一变量，line 却来回跑

Core 0 只更新计数 A，Core 1 只更新计数 B；源码看不到共享写。若 A、B 恰好落在同一 cache line，两边仍会轮流争夺这整条 line 的 ownership。问题发生在硬件传输粒度，不在变量名。

假设 left 和 right 是两个独立原子计数器，却落在同一 cache line：

text

line N: [ left ][ right ][ unused bytes ... ]
          Core 0   Core 1

Core 0 每次写 left 都需要 line 的写权限，使 Core 1 的副本失效；Core 1 随后写 right，又把 ownership 取回。程序没有共享逻辑变量，却在硬件颗粒上共享了 line，因此叫 false sharing。

它与 true sharing 不同。两个线程更新同一个队列头或锁，本来就需要同步；把对象 padding 到不同 line 无法消除语义上的共享。

对齐只是修复的一个条件

若目标平台确认 coherence line 为 64 byte，可让每个热写计数器拥有至少一个独立的 64-byte 对齐对象。C11 示例：

#include <stdalign.h>
#include <stdatomic.h>
#include <stddef.h>

enum { CACHE_LINE_BYTES = 64 };

typedef struct {
    alignas(CACHE_LINE_BYTES) atomic_ulong value;
} PaddedCounter;

_Static_assert(alignof(PaddedCounter) >= CACHE_LINE_BYTES,
               "counter alignment is too small");
_Static_assert(sizeof(PaddedCounter) % CACHE_LINE_BYTES == 0,
               "array elements may share a line");

static PaddedCounter counters[2];

提高类型 alignment 通常也会把 sizeof 向 alignment 的倍数取整，第二个断言把数组 stride 的要求写明。仍要注意：

64 来自部署目标，不是 ISO C 给出的 cache 常量；
allocator 必须满足扩展 alignment，动态分配可用 aligned_alloc 并遵守 size 倍数要求；
相邻的其他对象、链接器布局和更大的 coherence granule 仍可能影响结果；
padding 增加内存占用，过度使用会降低容量局部性。

仅给整个“两计数器结构体”加一次 alignas(64) 不会把内部两个字段分开；它只保证结构体起点对齐。每个热写槽位需要独立 stride。

更好的办法常是减少共享写

padding 适合线程确实需要频繁写各自槽位的场景。计数、统计与批量处理还可以减少 ownership 转移次数：

每个线程在私有变量或私有数组中累计；
每处理一批数据才写入共享结果；
最后由一个归约阶段合并。

#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>

static atomic_ulong total = 0;

static void publish_batch(size_t items,
                          bool (*do_one_item)(size_t index)) {
    unsigned long local = 0;
    for (size_t index = 0; index < items; index++) {
        local += do_one_item(index) ? 1UL : 0UL;
    }
    atomic_fetch_add_explicit(&total, local, memory_order_relaxed);
}

这里省略了 do_one_item 的具体业务实现。关键是每批只争夺一次共享 line，而不是每个 item 一次。批量大小在吞吐、可见延迟和溢出范围之间取舍。

分片计数器、per-CPU data、thread-local storage 和分层归约都沿用同一思路。读者若要求每一刻都得到严格全局最新值，就要接受更高同步成本或设计另一种一致性语义。

MESI 之外还有目录与互连

少量核心可以通过 snooping 观察共享互连上的请求；核心数增加后，广播成本过高，系统常用 directory 记录哪些 cache 可能持有副本，只向相关节点发送消息。

芯片内部还可能有 mesh/ring interconnect、多 cluster cache、snoop filter 和 home agent。多插槽 NUMA 系统让远端内存与跨 socket ownership 转移更昂贵。程序看到的“同一份共享内存”背后，物理距离并不相同。

coherence 协议保证正确协调副本，却不保证访问延迟均匀。线程放置、数据 first-touch 和分片方式会影响请求走多远。

store buffer 为什么不破坏 coherence

处理器常先把 store 放入 store buffer，让执行流水线不必等待 ownership 与下层 cache 全部完成。本核随后 load 同一地址时，可通过 store-to-load forwarding 读到自己的新值。

这会让“完成执行”和“其他核心可观察”不是同一时刻。coherence 与内存模型共同约束最终可见顺序，memory fence 则在特定场景建立需要的排序。fence 不是“把所有 cache 清空”，也不应作为不理解原子语义时的万能补丁。

同样，write-back cache 的 dirty 数据何时到 DRAM，与另一个 coherent 核何时能读到新值是两件事。其他核可以从拥有者或共享 cache 获得最新数据，无需等待 DRAM 成为最新副本。

怎样证明性能问题真是伪共享

只看“多线程比单线程慢”不够。可信诊断需要多种证据：

确认线程确实并行运行在不同核心，而不是调度或配额问题；
查看热写地址，证明它们落在同一 coherence line；
用平台支持的 HITM、snoop、cache-to-cache 等性能事件观察 line 转移；
只改变布局或分片方式，保持算法与工作量不变；
重复测量并报告 CPU 型号、拓扑、编译选项与线程绑定。

某些计数器只在特定微架构可用，事件名字也会改变。墙钟时间改善是结果，ownership 事件下降才更接近因果证据。

benchmark 中用 volatile 不能替代原子操作，也不能防止 data race。若两个线程写同一个非原子对象，C 程序已经没有定义良好的并发语义，测到的数字不值得解释。

coherence、consistency、durability 三条轴

问题	主要机制
多个 cache 副本是否协调	cache coherence
不同地址的操作以何种顺序可见	ISA/语言 memory model、atomics、fence
断电后数据是否仍存在	持久存储协议、flush、barrier、设备保证

write-back 的“最终写回下一层”不等于 durable。DRAM 通常断电即失，SSD 控制器也可能有 volatile buffer。数据库的 WAL、fsync 与持久内存 flush 讨论的是第三条轴，不能用 MESI 状态解释。

动手追踪 ownership

从两个 Core 都持有 S 状态开始，画出 Core 0 写、Core 1 读、Core 1 写的稳定状态序列。
解释为什么 Modified owner 可以向请求者提供数据而不必先更新 DRAM。
比较同一 atomic counter 的 true sharing 与两个相邻 counter 的 false sharing；padding 能修哪一个？
设计 per-thread counter 的合并协议，说明读者能获得的是实时精确值还是周期性快照。
找出“对整个结构体 alignas(64)”仍可能让内部字段共享 line 的原因。
写一个 release/acquire 发布例子，说明 relaxed counter 为什么不能自动发布另一块普通数据。

地址接下来还要经过一次翻译

cache 通常以物理地址或物理 tag 维持一致副本，程序却使用进程自己的虚拟地址。下一章进入虚拟内存，沿着虚拟页、TLB、页表和 page fault 追踪一次 load 的另一半旅程。

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算