多处理器一致性

一、多处理器系统架构：从对称式到分布式

1.1 单芯片多核架构

对称式多处理器（Symmetric Multiprocessor, SMP）架构中，多个 CPU core 集成在同一芯片内部：

• 每个 core 有自己的私有缓存（private cache），通常是 L1；
• 所有 core 共享一个大的共享内存（shared memory）；
• core 通过总线（bus）访问 memory；
• 缓存一致性通过侦听协议（snooping protocol）维护。

这种总线式对称架构的瓶颈在于总线本身。总线能连接的处理器数量受物理扇出（fan-out）能力限制，同时多个处理器竞争同一条总线也会降低效率。随着核心数量从单芯片的少量 core 扩展到数十甚至上百 core，单一共享总线不再可扩展。

1.2 分布式存储器架构的动机

当服务器中插入多个 CPU 芯片或板卡时，继续依赖共享总线会导致通信效率急剧下降。更可扩展的方案是使用分布式存储器架构：

• 每个 CPU 节点或板卡有自己的本地存储器（local memory）和本地 IO；
• 节点之间通过互联网络（interconnect network）连接；
• 数据分布在不同节点的本地 memory 中，不再全部经过公共总线。

架构对比如下：

1.3 分布式架构的核心挑战

分布式多处理器架构面临三个核心问题：

1. 总线可扩展性受限：物理扇出能力决定了总线能挂载多少设备。
2. 总线竞争严重：共享总线的占用率会随着处理器数量增加而上升，整体效率下降。
3. 广播式侦听不可行：在非总线、非环状网络中，所有节点无法自然监听到所有通信，传统 snooping 协议难以直接使用。

因此，分布式系统需要使用目录式缓存一致性协议来替代广播侦听。

二、目录式缓存一致性协议

2.1 为什么需要目录

在总线架构中，所有节点都能监听总线上的通信，因此可以通过 snooping 维护一致性。但在分布式互联网络中，通信往往是点对点的：节点 A 与节点 B 的通信不会自动广播给节点 C。

除非网络本身是环状结构，否则依靠全局监听维护一致性非常困难。目录式协议的核心思想是：为每个 cache block 建立一个目录（directory），记录该数据块被哪些节点持有副本，以及这些副本处于什么状态。

2.2 目录的基本结构

目录记录每个 cache block 的共享状态信息，典型内容包括：

• Present bits：若系统有 8 个核，则每个 cache block 配 8 个 bit。某一位为 1 表示对应核持有该块副本，为 0 表示没有副本。
• 状态位：记录该块在目录层面的状态，例如 Uncached、Shared、Exclusive。
• 数据块元数据：原有 cache block 已经包含 tag、state（MSI/MESI/MOESI）和 data，目录会额外带来存储开销。

目录信息通常可以放在共享 cache 或 home node 的 memory 旁边。随着处理器数量增加，present bits 和目录状态都会增加额外空间开销，但它避免了全系统广播带来的通信瓶颈。

2.3 集中式目录与分布式目录

集中式目录将所有目录信息集中存放在一个位置：

• 优点：结构简单，所有节点都知道去哪里查询；
• 缺点：目录节点容易成为性能瓶颈和单点热点。

分布式目录将目录信息分散在多个节点上：

• 每个节点负责一部分 memory 及其对应 cache block 的目录；
• 访问某个数据块时，需要找到对应的 home node；
• 目录访问压力被分摊，但协议实现和消息路由更复杂。

分布式目录是大规模多处理器系统中更常见的设计方向，因为它能随着节点数量增加而扩展。

2.4 目录协议的三种逻辑角色

目录协议中通常涉及三种逻辑角色：

• 本地节点（Local node）：发起请求的处理器节点；
• 主节点（Home node）：持有该数据块目录和 memory 的节点；
• 远程节点（Remote node）：持有该数据块副本的其他节点。

这些角色是逻辑概念，物理上可以重合。例如，本地节点可能正好也是某个数据块的 home node；某个 remote node 也可能在另一个访问场景中成为 local node。

2.5 基本操作流程

读缺失（Read Miss）

读缺失的基本流程如下：

1. 本地节点发起读请求，并定位到该数据块的 home node。
2. 主节点查看目录状态：
   • 若该块处于 Modified 状态，说明最新数据在某个远程节点中。主节点通知持有者写回或转发数据，然后将数据传给请求者，并将相关节点状态更新为 Shared。
   • 若该块处于 Shared 状态，主节点可直接提供或协调提供数据，并更新 present bit，把新请求者标为持有者。
   • 若该块未被缓存（Uncached/Invalid），主节点从 memory 读取数据传给请求者，并在 MSI 协议中将状态设为 Shared。
3. 请求者收到数据，目录更新 present bits。

写缺失（Write Miss）

写缺失要求请求者获得该数据块的独占修改权限：

1. 本地节点向 home node 发起写请求。
2. 主节点根据当前状态处理：
   • 若该块处于 Shared 状态，主节点向所有持有者发送 Invalidate 消息，等待确认后将数据传给请求者，并将请求者设为 Modified。
   • 若该块处于 Modified 状态且由其他节点持有，主节点要求持有者写回或转发数据，并使旧持有者失效，再把独占权限交给请求者。
3. 请求者获得 Modified 状态，可以执行写入。

Shared 状态下的写命中（Write Hit）

如果 CPU 本身持有 Shared 副本，但现在要写该数据块，它不能直接写入，因为其他节点可能也持有副本。正确流程是：

1. 请求者向目录发起升级请求；
2. 目录向其他持有者发送 Invalidate；
3. 等待所有失效确认；
4. 请求者升级为 Modified；
5. 请求者执行写入。

这些操作包含多个消息往返，因此必须考虑原子性和并发请求冲突。例如，在某个节点等待 Invalidate 确认期间，另一个节点也可能发起读写请求，协议实现需要定义清晰的中间状态和仲裁规则。

2.6 MSI/MESI 状态与目录的结合

目录协议仍可使用前面介绍过的 MSI/MESI 状态：

在 MESI 基础上加入 O (Owned) 状态得到 MOESI：

• O 状态：cache 中的数据与 memory 不一致，但该 cache 负责在其他节点读取时提供数据。它允许脏数据暂时不写回 memory，而由 owner 向其他节点供应数据。

目录本身也维护状态，例如：

• Uncached：没有任何节点缓存该块；
• Shared：一个或多个节点持有共享副本；
• Exclusive/Modified：某个节点独占该块，可能已经修改。

2.7 目录状态转换的理解方式

目录常见请求包括：

1. Read Miss：找到最新数据，将其传给请求者，并更新共享者集合。
2. Write Miss：获取独占权限，失效其他副本，并把数据传给请求者。
3. Data Write-back：某节点把修改后的数据写回 home node 或 memory，目录状态随之更新。

目录状态转换表通常线条较多，但核心只有两件事：

• 数据当前在哪里，谁拥有最新版本；
• 请求完成后，应当让哪些节点变成 Shared，哪些节点变成 Invalid，哪个节点变成 Modified/Exclusive。

只要明确数据流向、持有者集合和写权限归属，状态转换表就可以从协议逻辑自然推导出来。

三、内存一致性模型

3.1 问题的提出

在多处理器系统中，不同处理器访问共享 memory 的顺序会影响程序结果。考虑经典的双核代码：

1
2
3
4
5
6
7
// P1
A = 1;
ready = 1;

// P2
while (ready != 1) ;
print(A);

程序员通常期望 P2 看到 ready == 1 后，输出的 A 一定是 1。但在真实硬件中，输出可能是 0。

原因在于：“写完”并不只是某个 CPU 执行了 store 指令。若 A = 1 进入了 write buffer 但尚未对其他处理器可见，而 ready = 1 更早变得可见，P2 就可能先看到 ready == 1，再读取到旧的 A == 0。

因此，多处理器系统需要定义：一个处理器的访存操作以什么顺序对其他处理器可见。这就是内存一致性模型（memory consistency model）要解决的问题。

3.2 顺序一致性

顺序一致性（Sequential Consistency, SC）是最严格、最直观的模型。它要求：

• 每个处理器内部的访存操作按程序序（program order）执行；
• 全局来看，所有处理器的访存操作好像按照某种串行交错顺序执行；
• 结果等价于所有处理器共享一个 memory，并按某个全局顺序排队访问。

SC 要求满足四种顺序约束，其中 R 表示 Read，W 表示 Write：

1. R → R：先读后读，不乱序；
2. R → W：先读后写，不乱序；
3. W → R：先写后读，不乱序；
4. W → W：先写后写，不乱序。

SC 对程序员最友好，但对硬件性能限制很强。

3.3 Write Buffer 与顺序破坏

写 memory 是慢操作。为了避免 CPU 等待，硬件中会设置写缓冲（write buffer）：CPU 将要写的数据放入 buffer 后即可继续执行，之后再由硬件把数据写入 cache 或 memory。

write buffer 会破坏 W → R 顺序：

• CPU 认为 A = 1 已经执行，因为 store 已进入 write buffer；
• 实际上，其他处理器可能还看不到 A = 1；
• 后续写入 ready = 1 可能更快对其他处理器可见；
• 另一个处理器看到 ready = 1 后读取 A，仍可能读到旧值。

再次考虑：

1
2
3
4
5
6
7
// P1
A = 1;
ready = 1;

// P2
while (ready != 1) ;
print(A);

即使 P1 按程序序先执行 A = 1 再执行 ready = 1，由于 write buffer、cache miss、总线竞争和一致性协议消息延迟，两个写入对 P2 的可见顺序仍可能发生变化。

3.4 顺序一致性的性能代价

严格顺序一致性会限制乱序执行、写缓冲、预取和缓存优化。若所有访存都必须严格保持程序序并对全局可见，处理器大量时间会浪费在等待 memory 操作完成上。

相关实验中，严格 SC 下的处理器利用率可能只有约 17% 到 42%。多核系统的目标是提高吞吐和并行度，但过强的一致性约束会抵消大量性能收益。

四、松弛一致性模型

4.1 松弛的基本思路

硬件希望放松某些顺序约束，以提升性能，同时仍然提供程序员可以理解和控制的语义。

四种约束中，最常见的放松对象是 W → R：

• R → R 乱序会改变读取逻辑，风险较高；
• W → W 乱序会改变多个写入对外可见的顺序，也很危险；
• R → W 可能涉及数据依赖；
• W → R 在没有数据依赖时相对更容易通过硬件机制处理。

放松 W → R 的核心是：允许后续 load 不必等待前面的 store 完全对全局可见。

4.2 TSO：Total Store Order

TSO（Total Store Ordering）模型放松了 W → R 的顺序约束。它允许：

• store 先进入 write buffer；
• 后续 load 可以在 pending store 尚未写入 cache/memory 时先执行；
• CPU 可以从自己的 write buffer 中读回刚写入但尚未全局可见的数据，这称为 store-to-load forwarding 或 bypass。

TSO 可以理解为让 write buffer 的存在对程序语义可见：处理器不必等待 store 真正写入 cache，后续 load 可以继续执行，只要满足模型规定的约束。

这种设计提高了性能，但也意味着跨线程通信不能仅依赖普通 load/store 的代码顺序。需要同步变量、原子操作和 fence 指令来建立明确的可见性顺序。

4.3 更多松弛模型

不同内存模型会放松不同的顺序约束：

• TSO：主要放松 W → R；
• PSO（Partial Store Order）：在 TSO 基础上进一步放松 W → W；
• Weak Ordering / Relaxed Model：放松更多约束，通常只强制保留必要的数据依赖和显式同步顺序。

松弛模型可以显著提升硬件性能。相关 benchmark 中，放松顺序约束后处理器利用率可从严格 SC 下的低利用率提升到约 70% 到 100%。代价是软件必须在共享数据通信处显式使用同步机制。

五、内存栅栏与同步机制

5.1 Memory Fence

为了在松弛内存模型中保证特定代码段的有序执行，指令集需要提供内存栅栏（Memory Fence / Barrier）指令。

Fence 的作用是：

• 确保 fence 之前的访存操作在 fence 之后的访存操作之前完成；
• 在关键同步点阻止不安全的乱序；
• 允许非关键区域继续利用硬件乱序和缓冲优化。

常见 fence 类型包括：

• Store Fence（sfence）：确保 fence 前的 store 操作按要求完成；
• Load Fence（lfence）：确保 fence 前的 load 操作按要求完成；
• Memory Fence（mfence）：同时约束 load 和 store。

Fence 的关键不在于指令本身复杂，而在于插入位置必须正确。插得太少会产生竞态和可见性错误；插得太多会损失性能。

5.2 Lock/Unlock 与 happens-before

Lock/Unlock 机制依赖底层原子指令和内存顺序约束来实现同步。

例如生产者先写数据再释放锁，消费者获取锁后读取数据：

1
2
3
4
5
6
7
8
9
// Producer
A = 1;
ready = 1;
unlock();  // release

// Consumer
lock();    // acquire
while (ready != 1) ;
print(A);

在语义上，unlock 和 lock 之间建立了 happens-before 关系：unlock 前的写入必须对成功 lock 后的线程可见。

Fence 插入原则可以概括为：

• 在需要跨线程传递信息的位置建立顺序约束；
• fence 之间的普通代码仍可由硬件和编译器优化；
• 同步点必须阻止会破坏可见性的乱序。

编译器和硬件都可能重排访存操作，因此高层同步原语必须明确映射到底层 fence、原子读改写和内存模型约束。

5.3 软件锁为什么需要硬件支持

操作系统层面的锁不能只靠普通软件实现。锁的本质需要某些操作具备原子性：读、判断、写必须作为不可分割的整体完成。

如果没有指令集支持，普通 load/store 可能被中断、被其他处理器观察到中间状态，无法保证多个线程不会同时进入临界区。

典型硬件原子指令包括：

• Exchange（xchg）：交换寄存器和 memory 的值；
• CAS（Compare And Swap）：比较 memory 中的旧值，若匹配则写入新值；
• Test-and-set：读取旧值并设置新值；
• Fetch-and-add：读取旧值并加上指定增量。

这些指令通常还会配合 acquire/release 语义或 fence 使用，从而同时保证互斥和内存可见性。

六、生产者-消费者问题与同步实例

6.1 问题描述

生产者-消费者问题（Producer-Consumer）是经典同步场景：

• 生产者不断产生数据，放入队列尾部；
• 消费者不断从队列头部取出数据；
• 队列通常通过 head 和 tail 指针管理；
• 当 head == tail 时，队列为空。

6.2 并发访问的竞争

关键竞争点是生产者和消费者会并发访问 head、tail 以及缓冲区数据。

1
2
3
4
5
6
7
8
9
10
11
// Producer
1. store X to buffer[tail];
2. tail = tail + 1;

// Consumer
3. load tail;
4. load head;
5. if (head != tail) {
6.     load data from buffer[head];
7.     head = head + 1;
   }

可能出现的问题包括：

• Producer 执行了步骤 1，但步骤 2 的 tail++ 尚未对 Consumer 可见，Consumer 会认为队列仍为空，从而漏掉新数据；
• Producer 的 tail++ 先对 Consumer 可见，但数据 X 尚未真正写入或尚未对 Consumer 可见，Consumer 可能读到未完成或旧的数据；
• Consumer 对 tail/head 的读取和后续读数据之间若被乱序，也可能破坏队列状态判断。

6.3 Fence 的正确插入位置

Producer 端需要确保数据先写入，再更新 tail：

1
2
3
4
// Producer
store X to buffer[tail];
store_fence();      // 确保 X 对外可见后再更新 tail
tail = tail + 1;

Consumer 端需要确保先读取队列边界，再根据边界读取数据：

1
2
3
4
5
6
7
8
9
// Consumer
t = load tail;
h = load head;
load_fence();       // 确保先读完 tail/head 再读取数据

if (h != t) {
    X = load buffer[h];
    head = h + 1;
}

Producer 端的 store fence 保证“数据写入”发生在“发布 tail 更新”之前；Consumer 端的 load fence 保证“观察队列状态”发生在“读取队列数据”之前。两者共同建立生产者与消费者之间的可见性顺序。

更一般地，生产者-消费者同步依赖三类底层机制：

• cache 一致性协议保证不同 core 最终能看到一致的数据块；
• 内存一致性模型规定访存操作的可见顺序；
• fence、原子指令和锁在关键位置建立强顺序约束。

• Previous
  商环与分式域
• Next
  图数据库查询