线程级并行-量化第5章

目录

  • 并行计算机的基本概念与体系结构分类
  • 线程级并行面临的主要挑战
  • 集中式共享存储器与 Cache 一致性
  • 监听一致性协议：写作废、MSI、MESI 与 MOESI
  • 对称共享存储器多处理器的性能与可扩展性
  • 分布式共享存储器与目录式一致性协议
  • 存储连贯性模型：SC、TSO/PSO 与弱序模型
  • 同步机制：互斥、信号量、原子操作与锁性能
  • 总结与对比

1 并行计算机的基本概念与体系结构分类

线程级并行（Thread-Level Parallelism, TLP）讨论的是如何让多个线程、多个核心或多个处理器协同执行同一个计算任务。它和指令级并行（ILP）的关注点不同：ILP 主要在一个处理器内部让多条指令重叠执行，而 TLP 是把计算拆成多个线程，让多个处理单元同时工作。单处理器依靠频率提升、复杂流水线和硅工艺改进获得性能增长的空间越来越有限，因此把多个处理器连接起来，利用程序中更粗粒度的并行性，就成为体系结构提升性能的重要方向。

1.1 Flynn 分类法与 MIMD 的地位

Flynn 分类法从“指令流”和“数据流”两个维度描述计算机体系结构：

类型 含义 典型理解
SISD 单指令流、单数据流 传统单处理器顺序执行程序
SIMD 单指令流、多数据流 同一条指令同时作用于多个数据，如向量处理器、GPU 中的部分执行模式
MISD 多指令流、单数据流 实际通用系统中较少见
MIMD 多指令流、多数据流 多核、多处理器、集群等通用并行系统

MIMD 已成为通用多处理机体系结构的主要选择。原因有两个：

  • 第一，MIMD 很灵活，不同处理器可以执行不同线程、不同程序段，适合通用软件。

  • 第二，它可以直接利用商品化微处理器，以较好的性能价格比堆叠系统性能。也就是说，MIMD 不是把所有处理器锁死在同一条指令上，而是允许每个处理器独立推进，只在需要共享数据或同步时进行通信。

1.2 地址空间组织：共享存储与非共享存储

多处理器之间要合作，核心问题是“线程之间如何交换数据”。从地址空间看，主要有两种组织方案。

共享存储 机器把物理上可能分离的多个存储器组织成一个逻辑共享地址空间。任意处理器只要有访问权限，就可以通过普通的 Load/Store 指令访问共享地址空间中的任意位置。对于程序员来说，这种模型比较自然：线程之间通过共享变量通信，像访问本地内存一样访问共享数据。

非共享存储 机器则由多个独立地址空间构成。一个节点不能直接用 Load/Store 访问另一个节点的内存，而需要通过消息传递显式通信。每个“处理器-存储器”模块更像一台独立计算机，因此这类系统也称为多计算机或消息传递机器。

对比维度 共享地址空间 独立地址空间
通信方式 通过 Load/Store 隐式通信 通过 Send/Receive 等消息显式通信
编程难度 对动态、复杂通信模式更友好 程序员必须显式管理通信
硬件复杂度 需要维护 Cache 一致性和存储顺序 硬件相对简单
通信开销暴露程度 容易被程序员忽略 通信显式出现，更容易针对性优化
典型系统 SMP、DSM、NUMA 集群、仓库级计算机、MPI 系统

共享存储器通信的优点在于编程容易，尤其当通信关系复杂或运行时动态变化时，程序员不必显式安排每一次数据传递。当通信数据较小时，共享变量也常常比消息打包更轻便；同时硬件 Cache 可以缓存共享数据，减少远程访问频率。

消息传递的优点则是硬件简单，并且通信开销不会被隐藏，程序员和编译器会更主动地优化数据布局与通信次数。

1.3 共享存储 MIMD：SMP/UMA 与 DSM/NUMA

基于共享存储的 MIMD 机器可以分为集中式共享存储器结构和分布式共享存储器结构。

image-20260529114929748

集中式共享存储器结构通常称为 SMP（Symmetric Multiprocessor），也称 UMA（Uniform Memory Access）机器。它的特点是多个处理器共享同一个物理主存，访问任意主存位置的延迟大体相同。SMP 的结构简单、成本低，适合处理器数量较少的系统，但所有处理器都要竞争共享总线、共享内存控制器和一致性通信带宽，所以规模扩大后会遇到瓶颈。

image-20260529115035597

分布式共享存储器结构称为 DSM（Distributed Shared Memory），也常称 NUMA（Non-Uniform Memory Access）机器。每个节点包含处理器、局部存储器、I/O 和互连网络接口；所有节点的内存合起来形成一个逻辑共享地址空间。NUMA 的关键特征是访问时间不均匀：访问本地节点内存快，访问远程节点内存慢。如果程序具有良好的数据局部性，大多数访问都发生在本地节点，DSM 可以降低对中心存储器和总线的带宽需求；但代价是远程访问延迟高、处理器间通信复杂，并且需要高带宽互连网络支撑。

2 线程级并行面临的主要挑战

线程级并行并不是“处理器越多越快”。困难可以概括为两个挑战和一个核心问题：程序中的并行性有限、通信开销较高、存储器访问的顺序问题。

2.1 挑战一：程序并行性有限

并行程序总会有一部分代码无法并行，例如初始化、串行 I/O、关键区、必须按顺序执行的算法步骤。Amdahl 定律说明：如果程序中可并行部分比例为 \(f\)，使用 \(N\) 个处理器，那么理论加速比为

\[ S=\frac{1}{(1-f)+\frac{f}{N}} \]

其中 \((1-f)\) 是串行部分比例。这个公式的含义很尖锐：只要串行部分不够小，处理器数量再多也会被串行部分限制。

例如一个场景要求用 \(100\) 个处理器达到 \(80\) 的加速比：

\[ 80=\frac{1}{(1-f)+\frac{f}{100}} \]

解得 \(f=0.9975\)，也就是串行部分只能占 \(0.25\%\)。这说明当目标加速比非常高时，哪怕只有一点点串行代码，也会成为性能上限。

2.2 挑战二：通信开销较高

多个处理器协作时，线程之间必须交换数据。共享存储系统中，数据通信可能表现为远程存储访问、Cache 一致性事务、失效消息、写回消息等。经验数据是：在共享存储多处理器中，分离核心之间的数据通信可能需要约 \(35\sim 50\) 个时钟周期；如果核心在不同芯片上，通信可能需要约 \(100\sim 500\) 个时钟周期。这个开销取决于通信机制、互连网络类型和多处理器规模。

通信开销对 CPI 的影响可以用“基本 CPI + 远程访问惩罚”理解。假设处理器频率为 \(3.3\text{ GHz}\)，时钟周期约为 \(0.3\text{ ns}\)，远程访问时间为 \(200\text{ ns}\)，远程访问开销约为

\[ \frac{200\text{ ns}}{0.3\text{ ns}}\approx 666 \]

个时钟周期。若基本 CPI 为 \(0.5\)，且 \(0.2\%\) 的指令需要远程访问，则实际 CPI 为

\[ CPI=0.5+0.002\times 666\approx 1.7 \]

没有远程访问时 CPI 为 \(0.5\)，因此前者比后者快

\[ \frac{1.7}{0.5}=3.4 \]

因此，远程访问比例看起来只有 \(0.2\%\)，但每次远程访问太贵，最终会让机器慢很多。

2.3 核心问题：存储器访问顺序

当多个处理器访问共享变量时，正确性不仅取决于“读到了哪个值”，还取决于“不同处理器看到读写操作的顺序是否一致”。例如一个线程先写数据，再写标志位；另一个线程看到标志位后去读数据。如果硬件或编译器为了提高性能重排了写操作，那么消费者可能先看到标志位，却读不到真正的数据。这就是存储连贯性模型和同步机制要解决的问题。

解决这些挑战的思路可以概括为：

  • 并行性不足 主要靠软件算法和并行程序设计解决；
  • 通信开销 靠体系结构和编程共同降低，例如缓存共享数据、优化数据结构、提升本地访问比例、用预取或多线程隐藏延迟；
  • 存储顺序问题 则靠一致性协议、连贯性模型和同步原语共同保证。

3 集中式共享存储器与 Cache 一致性

集中式共享存储器系统中，多个处理器共享一个存储器。为了减少访问主存的延迟，每个处理器通常有私有 Cache。私有数据只被一个处理器使用，缓存起来没有一致性问题；共享数据会被多个处理器访问，一旦共享数据被复制到多个 Cache，就会产生 Cache 一致性问题。

3.1 Cache 一致性问题从哪里来

假设主存中变量 \(X=1\)。处理器 A 读 \(X\) 后，A 的 Cache 中有 \(X=1\)；处理器 B 也读 \(X\) 后，B 的 Cache 中也有 \(X=1\)。如果 A 接着把 \(X\) 写成 \(0\)，但 B 的 Cache 副本没有被更新或作废，那么 B 后续读取 \(X\) 时仍可能读到旧值 \(1\)。这就违反了程序员对共享变量的直觉：某个处理器已经写了新值，其他处理器不应该永远读到旧值。

不一致主要来自两类场景。

  • 第一类是 I/O 操作，I/O 子系统可能直接修改内存，使 Cache 中副本与主存内容不同。
  • 第二类是 共享数据，多个处理器的 Cache 同时保存同一内存块副本，一个处理器修改后，其他副本就可能过期。

3.2 Coherence 与 Consistency 的区别

这里有一个非常重要的区分：存储一致性（Coherence）和存储连贯性（Memory Consistency）不是同一个概念。

概念 关注范围 解决的问题
Coherence，一致性 同一个存储单元或同一个 Cache 块 多个处理器对同一地址的读写顺序是否一致
Consistency，连贯性 所有存储单元上的所有访问 不同地址之间的读写顺序是否应被保留

Cache coherence 关心“同一个变量 \(X\) 的所有读写是否看起来合理”。Memory consistency 进一步关心“对 \(A\) 的写和对 \(B\) 的写之间，其他处理器应该按什么顺序观察到”。换句话说，一致性是每个地址上的局部顺序，连贯性是整个共享内存系统的全局顺序约束。

3.2.1 Consistency 的例子

这个例子讨论的是不同地址之间的访问顺序：

1
2
3
4
5
// 初始 x = 0, y = 0

// Core C1				// Core C2
S1: x = NEW;			S2: y = NEW;
L1: r1 = y;				L2: r2 = x;

这个例子问的是：\(r_1\) 和 \(r_2\) 能不能都等于 \(0\)？如果采用顺序连贯性模型（Sequential Consistency, SC），每个核心内部的程序顺序必须保留，所以 \(C_1\) 中必须有 \(S_1 \rightarrow L_1\)，\(C_2\) 中必须有 \(S_2 \rightarrow L_2\)。同时，所有内存访问还必须能排成一个全局顺序。在这种约束下，\(r_1=0\) 表示 \(L_1\) 没看到 \(S_2\)，因此全局顺序里应有 \(L_1 \rightarrow S_2\)；\(r_2=0\) 表示 \(L_2\) 没看到 \(S_1\)，因此应有 \(L_2 \rightarrow S_1\)。如果两个读都为 \(0\)，就会形成

\[ S_1 \rightarrow L_1 \rightarrow S_2 \rightarrow L_2 \rightarrow S_1 \]

这样的循环顺序。这是不可能的。因此在 SC 模型下，\(r_1\) 和 \(r_2\) 不能同时为 \(0\)。但如果硬件允许写缓冲或乱序执行，使两个写暂时没有被对方看到，那么两个核心都可能先读到旧值 \(0\)。

这个例子要说明：即使 \(x\) 自己的一致性没问题，\(y\) 自己的一致性也没问题，不同地址 \(x\) 和 \(y\) 的可见顺序仍然会影响程序结果，这就是 consistency 要研究的问题。

3.2.2 Coherence 的例子

这个例子讨论的是同一个地址 \(A\) 的多个缓存副本是否保持一致。开始时，Core 1 读取地址 \(A\)，假设读到 \(A=42\)，于是 Core 1 的 Cache 中有 \(A=42\)。随后 Core 2 也读取地址 \(A\)，Core 2 的 Cache 中也有 \(A=42\)。接着 Core 1 执行：

1
2
3
load r1, mem[A]
add  r1, r1, #1
store r1, mem[A]

这会把 \(A\) 从 \(42\) 改成 \(43\)。如果没有 Cache 一致性协议，Core 1 的 Cache 中可能已经是 \(A=43\)，但 Core 2 的 Cache 中仍然保留旧副本 \(A=42\)。此时两个核心对同一个地址 \(A\) 看到了不同的值，这就是 incoherence。Coherence 要解决的正是这个问题：当某个核心修改了 \(A\)，其他核心中关于 \(A\) 的旧副本必须被作废或更新；否则其他核心继续读自己的 Cache，就会读到过期值。

因此，Coherence 是 Consistency 的基础，但不能替代 Consistency。Coherence 能保证“同一个地址不要出现 42 和 43 这种互相矛盾的副本”；Consistency 则进一步规定“不同地址上的读写，其他处理器应该按什么顺序观察到”。

3.3 一个一致的存储系统必须满足什么

Cache 一致性的三个条件可以理解为“自己读自己要正确、别人读我也要正确、所有人看到写入顺序要一致”。

  • 第一，如果处理器 \(P\) 对单元 \(X\) 写入后又读取 \(X\)，且中间没有其他处理器写 \(X\)，那么 \(P\) 应读到自己刚写入的值。这保证了单处理器内部最基本的直觉。

  • 第二，如果处理器 \(P\) 对 \(X\) 写入后，处理器 \(Q\) 在足够长时间后读取 \(X\)，且中间没有其他处理器写 \(X\)，那么 \(Q\) 应读到 \(P\) 写入的值。这保证写传播最终能被其他处理器看见。

  • 第三，对同一单元的所有写操作必须被顺序化。也就是说，任意两个处理器对同一单元的两次写，从所有处理器角度看顺序都应该相同。否则处理器 \(A\) 认为 \(X\) 先写成 \(1\) 后写成 \(2\)，处理器 \(B\) 却认为 \(X\) 先写成 \(2\) 后写成 \(1\)，程序就没有统一语义。

为简化讨论，这里还采用两个假设：

  • 一次写操作直到所有处理器都看到写的结果才算完成，这叫写传播；
  • 允许处理器无序读，但写必须按程序序进行，这叫写串行化。

3.4 Cache 在一致性系统中的作用

在一致性多处理器中，Cache 不只是加速私有访问，还承担两种共享数据优化功能。

  • 共享数据项的迁移指把数据项移动到正在使用它的处理器本地 Cache 中。这样可以减少远程访问延迟，也降低共享存储器带宽压力。
  • 共享数据项的复制指为多个处理器同时读取的数据建立多个本地副本。比如多个线程只读一个查找表时，每个核心都缓存一份副本，可以减少对共享内存的争用。

但是迁移和复制会让系统必须跟踪每个共享块的状态，因此需要 Cache 一致性协议。协议的关键是记录共享数据块的状态，并在读缺失、写缺失、替换、总线事务等事件发生时改变状态。

一致性的基本实现方案有两类，它们的区别在于“共享块状态信息放在哪里、由谁来跟踪”：

  • 目录法（directory）。把物理存储器中共享数据块的状态以及相关信息保存在一个称为目录的地方。目录会记录某个块当前是未缓存、共享还是被某个处理器独占修改，以及哪些处理器拥有该块副本。这样当某个处理器要写共享块时，系统不必广播给所有处理器，只需要根据目录通知真正持有副本的处理器作废。
  • 监听法（snooping）。每个 Cache 除了保存数据副本之外，还保存该块的共享状态信息，并监听共享总线或互连上的请求。当别的处理器要读、写或作废某个块时，相关 Cache 控制器通过监听发现这件事，然后更新自己的状态、提供数据或作废副本。

简要地说，目录法是“集中登记每个块在哪些节点中”，更适合大规模分布式共享存储；监听法是“每个 Cache 自己听总线、自己反应”，更适合小规模总线式共享存储系统。后面的第 4 节会详细讲监听协议，第 6 节会详细讲目录协议。

4 监听一致性协议：写作废、MSI、MESI 与 MOESI

集中式共享存储器系统常使用监听法（snooping）实现 Cache 一致性。每个 Cache 控制器不仅保存数据和标记，还保存块状态，并监听共享总线上的事务。因为总线广播给所有 Cache，所有控制器能以同样顺序看到事务，这天然有助于实现写串行化。

4.1 写作废协议与写更新协议

监听协议处理写共享数据通常有两种策略：写作废（write invalidate）和写更新（write update）。

写作废协议 要求处理器在写入某个数据项前，先取得该数据项的独占访问权，并让其他 Cache 中的副本失效。这样写入者之后可以连续多次写同一块而无需每次广播数据。若其他处理器之后要读该块，它会发生 Cache 缺失，再去获取新副本。

写更新协议 则在写入某个数据项时，把新值广播给所有持有该数据项副本的 Cache。这样其他处理器之后读数据时延迟较低，因为副本已经被更新；但如果同一个处理器连续写多次，或写同一 Cache 块中的多个字，就会产生多次广播，带宽开销较大。

4.1.1 写作废协议例子

假设只有一个共享数据块 \(X\)，初始时主存中 \(X=0\)，处理器 A 和处理器 B 都还没有缓存 \(X\)。系统采用写回 Cache，也就是说写入后不一定立刻更新主存。

步骤 处理器行为 总线行为 A 的 Cache B 的 Cache 主存 \(X\)
初始 无 无 无 无 \(0\)
1 A 读 \(X\) Cache 缺失，取入 \(X\) \(0\) 无 \(0\)
2 B 读 \(X\) Cache 缺失，取入 \(X\) \(0\) \(0\) \(0\)
3 A 将 \(1\) 写入 \(X\) 作废 B 中的 \(X\) 副本 \(1\) 无效 \(0\)
4 B 读 \(X\) Cache 缺失，重新取最新值 \(1\) \(1\) \(1\)

4.1.2 写更新协议例子

初始条件仍然是主存 \(X=0\)，A 和 B 先后读取 \(X\)，因此两个 Cache 中都有 \(X=0\)。区别出现在 A 写 \(X=1\) 时。

步骤 处理器行为 总线行为 A 的 Cache B 的 Cache 主存 \(X\)
初始 无 无 无 无 \(0\)
1 A 读 \(X\) Cache 缺失，取入 \(X\) \(0\) 无 \(0\)
2 B 读 \(X\) Cache 缺失，取入 \(X\) \(0\) \(0\) \(0\)
3 A 将 \(1\) 写入 \(X\) 对 \(X\) 进行写广播 \(1\) \(1\) \(1\)
4 B 读 \(X\) 无缺失，直接命中 \(1\) \(1\) \(1\)

4.1.3 对比

场景 写作废协议 写更新协议
同一数据连续多次写，中间没有读 第一次作废后，后续写可本地完成 每次写都要广播
同一 Cache 块多个字被写 通常第一次写时作废整个块 每个字的写都可能广播
一个处理器写后另一个处理器很快读 读者会缺失，需要取新副本 读者副本已更新，读延迟低
总线带宽压力 通常较低 通常较高

因此，在基于总线的多处理机中，写作废协议是绝大多数系统设计的选择。

4.2 监听协议的基本实现

监听 Cache 控制器有两个输入来源：一个是本地处理器发出的 Load/Store 请求，另一个是总线上的 snoop 请求或响应。控制器根据当前块状态和输入事件决定动作，例如更新状态、发出 BusRd 或 BusRdX、提供数据、作废块、写回脏块等。

image-20260529120834226

在写回 Cache 中，最新值不一定在主存中，可能只在某个处理器的 Cache 中。因此当其他处理器读缺失时，拥有最新值的 Cache 需要通过总线提供数据，这就是 Cache-to-cache 传送。若某个修改过的块被替换，也必须写回下一级存储层。

4.3 MSI 协议

MSI 是一个典型的写回、写作废监听协议。每个 Cache 块有三种状态：

状态 含义 主存是否最新
M，Modified 当前 Cache 拥有该块唯一有效副本，且已经修改 主存不是最新
S，Shared 该块是干净块，其他 Cache 也可能有副本 主存是最新
I，Invalid 当前 Cache 中该块无效 不适用

MSI 协议常见总线事务包括 BusRd、BusRdX、BusWB 和 Flush。

BusRd，Bus Read，读请求。当某个处理器要读一个 Cache 块，但该块在本地 Cache 中处于 I 状态，或者本地根本没有这个块时，就会发生读缺失。此时本地 Cache 控制器在总线上发出 BusRd，意思是“我想读这个地址对应的 Cache 块，谁能提供最新数据”。

  • 如果其他 Cache 没有这个块，或者只有 S 状态的干净副本，那么主存可以提供数据，请求方得到数据后进入 S 状态。
  • 如果某个 Cache 中该块处于 M 状态，说明最新值只在那个 Cache 中，主存是旧的；这个 M 状态 Cache 监听到 BusRd 后必须把数据 Flush 到总线上，供请求方读取，并且自己通常从 M 降为 S。这样读者和原拥有者都变成共享读副本。

BusRdX，Bus Read Exclusive，排他读请求。当某个处理器想写一个块，但本地没有可写权限时，会发出 BusRdX。典型情况有两种：

  • 第一，本地块是 I，说明写缺失，需要先把块读进来并立即获得独占权限；
  • 第二，本地块是 S，说明自己有干净副本，但别人也可能有副本，不能直接写，必须先让其他副本失效。

其他 Cache 监听到 BusRdX 后，

  • 如果自己有该块的 S 副本，就把它置为 I；
  • 如果自己有 M 副本，就先 Flush 最新数据，再把该块置为 I。

请求方拿到独占权限后会进入 M 状态。BusRdX 是写作废协议实现“写传播”的关键，因为它通过作废其他副本迫使其他处理器以后重新取新值。

BusWB，Bus Write Back，写回。BusWB 通常不是别人来读写时发起的，而是 Cache 自己要替换某个块引起的。

  • 如果要替换一个 M 状态块，因为 M 状态表示该块已被修改，主存里还是旧值；如果直接把这个块从 Cache 中丢掉，最新数据就丢失了。所以替换前必须通过 BusWB 把脏块写回到下一级存储器，通常是共享 Cache 或主存。写回完成后，本地 Cache 才能安全地把该块移除或置为 I。
  • 如果被替换的是 S 状态块，因为主存本来就是最新的，通常不需要 BusWB。

Flush，提供或冲刷数据。Flush 表示某个 Cache 把自己手里的数据块放到总线上。它通常由监听别人的总线请求触发，尤其是当前 Cache 持有 M 状态块时。因为 M 状态块的最新值不在主存中，所以当别人发 BusRd 想读它时，M 状态 Cache 必须 Flush 数据，让请求者获得最新值，同时该块通常从 M 变为 S；当别人发 BusRdX 想独占写它时，M 状态 Cache 也要先 Flush 最新数据，然后把自己的副本作废为 I。可以把 Flush 理解为“我这里有最新版本，不能让你去主存拿旧版本，我把最新块放到总线上给你”。

总线事务 谁通常发起 触发场景 其他 Cache 监听后的典型动作 请求方最终状态
BusRd 读缺失的 Cache 本地为 I，但处理器要读 若有 M 副本则 Flush 并降为 S；S 副本保持 S S
BusRdX 写缺失或写升级的 Cache 本地为 I 或 S，但处理器要写 S 副本作废为 I；M 副本 Flush 后作废为 I M
BusWB 要替换脏块的 Cache M 状态块被替换 通常只是下一级存储器接收数据 I 或被替换掉
Flush 持有最新脏数据的 Cache 监听到别人 BusRd 或 BusRdX，且自己为 M 把最新数据放到总线上，必要时更新主存 不是请求方动作

处理器读时，

  • 如果块在 S 或 M 状态，读命中，不需要总线动作；
  • 如果在 I 状态，则发出 BusRd。

处理器写时，

  • 如果块已经在 M 状态，可以本地写，不需要总线动作；
  • 如果在 S 或 I 状态，需要发出 BusRdX，使其他副本失效并取得独占权限。

从总线监听角度看，如果本 Cache 中某块处于 M 状态，而观察到其他处理器的 BusRd，则必须 Flush，把最新数据提供出去，并通常转为 S 状态；如果观察到 BusRdX，则需要提供数据并转为 I 状态。若处于 S 状态而观察到 BusRdX，则直接作废为 I。

MSI 协议的状态机如下：

image-20260529121615957

PrRd/PrWr是“自己家的 CPU 要读/写”；BusRd/BusRdX 是“别人家的 CPU 通过总线发来的读/写请求”。

Replace 是 Cache 块替换事件。

MSI 的核心是写传播和写串行化。写传播通过 BusRdX 作废其他副本实现：其他处理器若没有看到新值，至少会在下次访问时发生缺失，从而被迫获取新值。写串行化通过共享总线实现：所有出现在总线上的 BusRdX 事务被所有处理器以相同顺序观察。

4.3.1 例子

4.4 MESI 协议：为什么要增加 E 状态

MSI 的一个缺陷是：即使某个块实际上只存在于当前 Cache 中，第一次读缺失后也会进入 S 状态；如果随后要写，还要再发一次 BusRdX 从 S 转为 M。也就是说，一个“读进来马上修改”的常见场景会产生两个总线事务。

MESI 在 MSI 基础上增加 E（Exclusive 或 Exclusive Clean）状态。E 表示只有当前 Cache 拥有该块，且该块未被修改，主存中的数据仍是最新的。这样，如果处理器读缺失时发现其他 Cache 没有该块，就可以进入 E 状态；随后本地写时可从 E 静默转为 M，不产生总线事务。

状态 含义
M，Modified 仅当前 Cache 有该块，且已修改，主存旧
E，Exclusive clean 仅当前 Cache 有该块，未修改，主存新
S，Shared 多个 Cache 可能有该块，未修改，主存新
I，Invalid 无效

MESI 也称 Illinois protocol，它的价值在于减少私有或独占数据的无意义总线升级事务。现代多核处理器普遍采用 MESI 或其变体。其状态机如下：

image-20260529155353417

4.5 MOESI 协议：Owned 状态的作用

MOESI 在 MESI 基础上增加 O（Owned）状态。Owned 表示当前 Cache 拥有系统中的最新数据副本，但该块也被其他 Cache 以 Shared 状态共享。与 MESI 中的 Shared 不同，MOESI 的 Shared 副本不一定与主存一致；如果系统中存在 Owned 副本，则主存可能是旧值。

引入 O 状态的目的是减少不必要的写回。MESI 中如果 M 状态块被其他处理器读取，拥有者往往需要把数据写回到更高层共享缓存或主存，并转为 S；MOESI 则可以让拥有者转为 O，继续负责向其他读者提供最新数据，而不必立即更新主存。

可以这样记忆：M 是“我独占且改过”，E 是“我独占但没改”，S 是“大家都可读”，I 是“没有”，O 是“我负责保管最新脏数据，别人可以共享读”。

4.6 监听协议的局限性

监听协议依赖广播。处理器数量增加后，共享总线带宽和监听通信会成为瓶颈。即使不使用集中式总线，而采用多根总线、交叉开关或其他互连网络，监听协议仍然需要把相关请求广播给所有缓存控制器，因此一致性通信本身会限制处理器规模和速度。

为了提高可扩展性，可以采用复制标记、在外层缓存层级放目录、使用多总线和互连网络等方法。但从体系结构方向看，大规模共享存储系统通常会转向目录式一致性协议，因为目录可以只把消息发送给真正相关的节点。

5 对称共享存储器多处理器的性能与可扩展性

对称共享存储器多处理器的总体缓存性能由两类流量决定：单处理器自身 Cache 缺失造成的流量，以及一致性协议通信造成的流量。后者会导致额外的失效、写回和后续缺失，这类缺失称为 coherence misses，也常称 communication misses，即除了 compulsory、capacity、conflict 之外的第 4 类 Cache miss。

5.1 真共享缺失与假共享缺失

一致性缺失可以分为真共享缺失和假共享缺失。

真共享缺失来自处理器之间确实通过同一个数据项通信。例如处理器 P1 写变量 \(x\)，处理器 P2 随后读 \(x\)。P2 的旧副本被作废后再次读取，发生缺失，这是程序真实数据依赖导致的通信。

假共享缺失则来自 Cache 块粒度过大。假设变量 \(x\) 和 \(y\) 位于同一个 Cache 块，P1 只写 \(x\)，P2 只读写 \(y\)。从程序变量角度看，\(x\) 和 \(y\) 没有共享；但一致性协议以 Cache 块为单位作废，P1 写 \(x\) 会让 P2 中包含 \(y\) 的整个块失效，于是 P2 访问 \(y\) 时也可能缺失。这种缺失是“共享了同一个块，而不是共享了同一个变量”，所以叫假共享。

例如：假设 \(x\) 和 \(y\) 两个字位于同一个 Cache 块中，并且这个块一开始在处理器 P1 和 P2 的 Cache 中都处于共享状态。访问序列如下：

时序 P1 P2
1 写 \(x\)
2 读 \(y\)
3 写 \(x\)
4 写 \(y\)
5 读 \(y\)

  • 第 1 步，P1 写 \(x\)。由于该块一开始是共享状态，P1 不能直接在共享副本上写，它需要获得独占权限，因此会使 P2 中同一个 Cache 块的副本失效。严格说，P1 本地已经有这个块，所以从“是否需要取数据”的角度看它像一次写命中；但从一致性协议角度看，它需要一次写升级或作废事务。如果把这种升级也计入 coherence miss，那么它属于真共享缺失，因为写的是块中的真实共享字 \(x\)。

  • 第 2 步，P2 读 \(y\)。P2 原本有包含 \(y\) 的 Cache 块，但这个块在第 1 步被 P1 写 \(x\) 时整体作废了，所以 P2 读 \(y\) 会发生缺失。注意，P2 并不是要读 P1 刚刚写过的 \(x\)，它只是要读同一块里的另一个字 \(y\)。如果 Cache 块大小只有一个字，\(x\) 和 \(y\) 不会被放在同一个块里，那么 P1 写 \(x\) 就不会影响 P2 读 \(y\)。因此这次缺失是假共享缺失。

  • 第 3 步，P1 再次写 \(x\)。第 2 步 P2 只是读了 \(y\)，并没有读 \(x\)，但由于 \(x\) 和 \(y\) 在同一个 Cache 块中，P2 读 \(y\) 时会把整个块 \((x,y)\) 重新取入 P2，使 P1 和 P2 再次共享同一个块。于是 P1 再写 \(x\) 时，又必须作废 P2 的整个块。这里造成 P1 需要重新获得独占权限的根源，不是 P2 真的需要 \(x\)，而是 P2 为了读 \(y\) 顺带拿到了包含 \(x\) 的整块，所以属于假共享缺失。

  • 第 4 步，P2 写 \(y\)。P2 的块在第 3 步又被 P1 写 \(x\) 作废，因此 P2 写 \(y\) 时需要重新取得该块并获得独占权限。由于导致它缺失的是 P1 对同一块中另一个字 \(x\) 的写，而不是对 \(y\) 的真实通信，所以这是假共享缺失。

  • 第 5 步，P1 读 \(y\)。第 4 步 P2 写的正是 \(y\)，而 P1 此时要读的也是 \(y\)。P1 的副本已经因 P2 写 \(y\) 被作废，必须重新获得包含 \(y\) 的最新块。这一次即使 Cache 块只有一个字也仍然会发生，因为 P1 确实要读取 P2 刚写过的同一个变量 \(y\)，所以它是真共享缺失。

减少假共享的典型方法是调整数据布局，例如让不同线程频繁写入的变量分散到不同 Cache line，或者用 padding 对齐结构体字段。

5.2 性能分析的基本思路

分析多处理器 Cache 性能时，不能只看单处理器的命中率，还要看一致性协议产生了多少总线事务、失效消息和远程访问。一个程序如果线程之间频繁写同一块，即使每个处理器本地 Cache 很大，也可能被一致性流量拖慢。

因此，提升 SMP 性能的关键包括：提高数据局部性，减少远程共享；区分只读共享和可写共享；减少临界区内共享数据写入；避免假共享；尽量让线程长时间处理本地数据。

6 分布式共享存储器与目录式一致性协议

分布式共享存储器体系结构把存储器分布在各个节点中，所有节点通过互连网络相连。节点是指 CPU/Core + Cache + 本地内存 + 目录 + 网络接口。访问可以是本地的，也可以是远程的。它比集中式共享存储更可扩展，但不能再依赖一个所有 Cache 都能监听的共享总线，因此需要目录式一致性协议。

6.1 目录在系统中的作用

目录（directory）为每个内存块记录一致性状态和共享者信息。常见信息包括：该块是否未缓存、共享或独占；哪些节点拥有该块副本；如果块被修改，哪个节点是拥有者。目录可以放在内存所在的主节点，也可以放在共享缓存中。

目录式协议涉及三类节点：

节点 含义
本地节点 发出访问请求的节点
主节点 包含被访问存储单元及其目录项的节点
远程节点 拥有该存储块副本的节点

本地节点和主节点可能是同一个节点，此时访问的是本地内存；远程节点也可能和主节点或本地节点重合。协议逻辑不必因此改变，只是跨节点消息变成本地消息。

image-20260529162157199

6.2 目录协议中的基本消息

本地节点发给主节点的常见消息有三种。Read miss 表示处理器读取地址 \(A\) 时不命中，请求主节点提供数据，并把请求者加入共享者集合。Write miss 表示处理器写地址 \(A\) 时不命中，请求主节点提供数据，并让请求者成为独占者。Invalidate 表示要求缓存了地址 \(A\) 的远程节点作废副本。

主节点发给远程节点的消息包括 Invalidate、Fetch、Fetch/Invalidate。Invalidate 只作废远程副本；Fetch 从远程 Cache 中取回数据，并把远程副本状态改为共享；Fetch/Invalidate 则取回数据并作废远程副本。

主节点发给本地节点的消息通常是 Data value reply，即返回数据内容。

远程节点发给主节点的消息常见为 Data write-back，即把远程 Cache 中的脏块写回主节点。

6.3 读缺失如何处理

当处理器 \(P\) 发生读缺失时，它向 home directory 发送 Read miss。

如果目录中该块处于 Modified 状态，说明最新数据不在主存或目录处，而在某个远程 Cache 中。目录需要向拥有者发送 Fetch，远程 Cache 把数据写回目录或共享缓存，并把本地状态改为 Shared。目录再把数据发给 \(P\)，并把 \(P\) 的 presence bit 置位，\(P\) 的本地 Cache 将该块置为 Shared。

如果目录中该块处于 Shared 或 Owned 状态，目录可以直接把数据发给 \(P\)，并把 \(P\) 加入共享者集合。如果处于 Uncached，则从存储器中取数据并返回。

image-20260529162902346

6.4 写缺失如何处理

当处理器 \(P\) 发生写缺失时，它向目录发送 Write miss，目标是获得唯一可写副本。

如果该块处于 Modified 状态，目录知道某个处理器 \(Q\) 是旧拥有者。目录向 \(Q\) 发送 Fetch/Invalidate，\(Q\) 把最新数据发送给 \(P\) 或主节点，并把自己的块置为 Invalid。目录更新 presence bit：清除 \(Q\)，置位 \(P\)。最后 \(P\) 的本地 Cache 状态变为 Modified。

image-20260529163112995

如果该块处于 Shared 或 Owned 状态，目录根据 presence bit 向所有共享者发送 Invalidate，并等待确认。所有共享副本作废后，目录把数据发给 \(P\)，将共享集合改为只含 \(P\)，并把目录状态改为 Modified 或 Exclusive。

如果该块处于 Uncached，则目录直接从存储器取数据给 \(P\)，并将 \(P\) 设为拥有者。

6.5 目录状态：简化三状态

目录协议基本过程可以先用一个简化的三状态模型说明。这里目录记录的块状态可以理解为未缓存、共享、已修改/独占拥有。这个三状态模型是为了先讲清楚目录协议的基本逻辑；后面 6.6.2 的状态图会把目录状态进一步细分成 MOSI。

  • 未缓存（Uncached）表示没有任何 Cache 保存该块副本。读缺失时，主节点把内存数据发给请求者，并让该请求者成为唯一共享节点，状态转为共享。写缺失时，主节点把内存数据发给请求者，状态转为独占，共享集合只包含该处理器。

  • 共享（Shared）表示多个 Cache 可能有该块副本，且主存数据是最新的。读缺失时，只需要把数据发给请求者并把它加入共享集合。写缺失时，必须向共享集合中所有处理器发送写作废消息，然后把共享集合改为只含请求者，状态转为独占。

  • 已修改/独占拥有（Modified 或 Exclusive owner）表示最新值保存在共享集合所指向的唯一拥有者 Cache 中，主存中的值可能已经过期。读缺失时，目录向拥有者发送取数据消息，把返回数据写入主节点或共享缓存，再发给请求者，并把请求者加入共享集合，状态转为共享类状态。写缺失时，新请求者将成为新拥有者，目录要求旧拥有者返回数据并作废旧副本，然后把新请求者设为唯一拥有者。若拥有者替换该块，则必须写回主节点，使主节点重新拥有最新值，目录状态转为未缓存。

因此，6.5 的“三状态”可以简写为 \(U/S/M\)：\(U\) 表示没有缓存副本，\(S\) 表示有一个或多个干净共享副本，\(M\) 表示某个处理器拥有唯一最新脏副本。这里不要把第三个状态写成 \(O\)，否则会和后面 MOSI 状态机里的 Owned 状态混淆。

6.6 目录协议的消息与状态机

6.6.1 本地节点的 MSI 状态机

本地 Cache 状态机描述的是“某个节点自己的私有 Cache 块如何变化”。它仍然使用 MSI 三种状态：Invalid、Shared、Modified。图中黑色箭头表示本地处理器发出的请求，红色箭头表示目录发来的请求。

image-20260529165505363

本地处理器的读写：

  • 本地处理器读一个 Invalid 块时，本地 Cache 不能直接满足访问，于是向主目录发送 Read miss message。主目录返回数据后，该块进入 Shared 状态。Shared 表示本地有一个只读副本，别的节点也可能有副本。

  • 本地处理器读一个 Shared 块时，就是 CPU read hit，状态保持 Shared。

  • 本地处理器写一个 Invalid 块时，需要向主目录发送 Write miss message。主目录会负责取回数据、作废其他副本，并把写权限交给本节点；本地 Cache 收到数据和权限后进入 Modified 状态。

  • 本地处理器写一个 Shared 块时，也不能直接写，因为其他节点可能还有副本，所以要发送 Invalidate message 或 Write-miss message，请目录作废其他共享副本；作废完成后，本地块进入 Modified 状态。

  • 本地处理器读/写 Modified 块时，都是命中，因为该节点已经拥有唯一最新副本，不需要发消息。

目录发来的请求会让本地 Cache 被动改变状态：

  • 如果目录发来 Invalidate，说明别的节点要获得写权限，本地 Shared 副本必须作废为 Invalid，并向目录返回 acknowledge。
  • 如果目录对一个 Modified 块发来 Fetch，说明别的节点要读这个块；本地 Cache 需要把最新数据写回或发送给目录，同时从 Modified 降为 Shared。
  • 如果目录发来 Fetch-Invalidate，说明别的节点要写这个块；本地 Cache 既要提供最新数据，又要把本地副本作废为 Invalid。

可以把本地 Cache 状态机总结成下面这张表：

当前状态 事件 本地动作 新状态
Invalid CPU read 向主目录发 Read miss，等待数据 Shared
Invalid CPU write 向主目录发 Write miss，等待数据和独占权 Modified
Shared CPU read 本地命中 Shared
Shared CPU write 请求目录作废其他副本，取得写权限 Modified
Shared Directory Invalidate 作废本地副本，回复确认 Invalid
Modified CPU read/write 本地命中 Modified
Modified Directory Fetch 提供最新数据，允许其他节点共享 Shared
Modified Directory Fetch-Invalidate 提供最新数据，并作废本地副本 Invalid
Modified Replace 写回主目录 Invalid

这张状态机和监听协议中的 MSI 很像，但差别在于：监听协议通过总线事务让所有 Cache 同时看见事件；目录协议中，本地 Cache 只响应主目录发给自己的定向消息。

6.6.2 目录节点的 MOSI 状态机

image-20260529165853993

\(presence[P]=1\) 表示目录认为节点 \(P\) 当前持有该块的一个有效副本；若目录状态是 Shared，则 \(P\) 就是共享者集合中的一个成员。相反，\(presence[P]=0\) 表示节点 \(P\) 当前不持有该块副本。

目录端状态机描述的是“主目录如何记录某个内存块在整个系统中的共享情况”。MOSI 目录状态比 6.5 中的简化模型更细，包含 Uncached、Shared、Modified 和 Owned by shared cache。需要注意，这些状态不是某个私有 Cache 的状态，而是目录对该块全局情况的记录。

  • Uncached 表示没有任何节点缓存该块，数据只在主存中。
    • 若节点 \(P\) 读缺失，目录从主存取出块，把数据回复给 \(P\)，并设置 \(presence[P]=1\)，目录状态转为 Shared。
    • 若节点 \(P\) 写缺失，目录同样从主存取出块并回复给 \(P\)，但因为 \(P\) 要写，所以目录把 \(P\) 设为唯一拥有者，状态转为 Modified。
  • Shared 表示一个或多个节点有只读副本，主存数据是最新的。
    • 若另一个节点 \(P\) 读缺失，目录直接把数据回复给 \(P\)，并把 \(presence[P]\) 置为 \(1\)，状态仍为 Shared。
    • 若节点 \(P\) 写缺失或请求失效，目录需要向所有当前共享者发送 Invalidate，清除这些节点的 presence bit，然后把数据和写权限交给 \(P\)，设置 \(presence[P]=1\)，状态转为 Modified。
  • Modified 表示某个节点 \(P\) 拥有唯一最新副本，主存可能是旧的。
    • 若另一个节点 \(Q\) 读缺失，目录不能直接从主存给数据，而要向拥有者 \(P\) 发送 Fetch，取回最新数据并回复给 \(Q\)。此后 \(P\) 和 \(Q\) 都可以拥有只读副本，目录进入 Owned by shared cache 或 Shared 类状态，具体取决于实现是否让共享缓存或目录持有最新值。
    • 若节点 \(Q\) 写缺失，目录向旧拥有者 \(P\) 发送 Fetch-Invalidate，把最新数据转交给 \(Q\)，清除 \(presence[P]\)，设置 \(presence[Q]=1\)，目录仍保持 Modified，但拥有者变成 \(Q\)。
  • Owned by shared cache 是 6.5 简化三状态里没有单独拆出来的状态。它表示最新数据已经由共享缓存或目录侧掌握，同时可能有多个节点持有共享副本。
    • 读缺失时，目录可以直接回复数据并加入新的共享者。
    • 写缺失时，目录要作废所有共享者，清空旧 presence bits，再把写权限交给请求节点，状态转为 Modified。

目录端状态机可以总结为：

目录状态 请求 目录动作 新状态
Uncached Read miss by \(P\) 从主存取数据，回复 \(P\)，设置 \(presence[P]=1\) Shared
Uncached Write miss by \(P\) 从主存取数据，回复 \(P\)，设置 \(presence[P]=1\) Modified，拥有者为 \(P\)
Shared Read miss by \(P\) 回复数据，加入共享者集合 Shared
Shared Write miss by \(P\) 作废所有共享者，清除旧 presence bits，回复 \(P\) Modified，拥有者为 \(P\)
Modified，拥有者为 \(P\) Read miss by \(Q\) 向 \(P\) 取数据，回复 \(Q\)，保留/更新共享者信息 Owned 或 Shared
Modified，拥有者为 \(P\) Write miss by \(Q\) 向 \(P\) 取数据并使其失效，回复 \(Q\) Modified，拥有者为 \(Q\)
Modified，拥有者为 \(P\) Write-back by \(P\) 接收写回数据，清除 \(presence[P]\) Uncached
Owned Read miss by \(P\) 回复数据，设置 \(presence[P]=1\) Owned
Owned Write miss by \(P\) 作废所有共享者，回复数据，设置 \(presence[P]=1\) Modified，拥有者为 \(P\)

因此，目录式协议的状态机有两个视角：本地 Cache 状态机回答“我这个节点手里的块是什么状态”；目录状态机回答“从全系统看，这个块被哪些节点缓存，谁有最新值”。两者通过 Read miss、Write miss、Invalidate、Fetch、Fetch-Invalidate、Data reply、Write-back 等消息配合，完成和监听协议类似的一致性目标。

6.6.3 远程节点的 MSI 状态机

远程节点上的 Cache 仍然使用本地 Cache 的 MSI 状态机；只是从某次目录协议事务的视角看，它被称为“远程节点”。

7 存储连贯性模型：SC、TSO/PSO 与弱序模型

Cache 一致性解决的是“同一个地址”的顺序问题，但并行程序还会依赖不同地址之间的顺序。例如一个线程先写数据 \(A=1\)，再写标志 \(Ready=1\)；另一个线程等待 \(Ready=1\) 后读取 \(A\)。这里 \(A\) 和 \(Ready\) 是不同地址，如果硬件允许它们的可见顺序被重排，程序就可能出错。

7.1 为什么要讨论存储连贯性

现代处理器为了隐藏存储延迟，会采用写缓冲、乱序执行、预取、推测执行等机制。单处理器中，只要最终结果符合单线程语义，内部重排通常不会被程序员观察到。但在共享地址空间多处理器中，一个线程的内存访问顺序可能被另一个线程观察到，重排就可能影响正确性。

例如初始 \(A=0,B=0\)：

1
2
3
4
5
6
7
// P1
A = 1;
if (B == 0) { ... }

// P2
B = 1;
if (A == 0) { ... }

如果写入总是立即对所有处理器可见，那么两个 if 不可能同时为真。但如果写入因为写缓冲或失效延迟而没有及时被对方看到，P1 可能读到 \(B=0\)，P2 也可能读到 \(A=0\)。这说明正确性不仅取决于每个变量自身的一致性，还取决于不同变量访问之间的可见顺序。

7.2 顺序连贯性 SC

顺序连贯性（Sequential Consistency, SC）由 Lamport 提出。它要求：

  1. 每个处理器的内存访问按程序顺序出现。
  2. 所有处理器的内存访问看起来可以排列成一个全局顺序。

更直观地说，SC 好像所有处理器轮流把 Load/Store 放入一个全局内存序列中；每个处理器自己的操作顺序不能变，但不同处理器之间可以交错。

image-20260608102332281

在简单同步例子中：

1
2
3
4
5
6
7
// P0
A = 1;        // a
Ready = 1;    // b

// P1
x = Ready;    // c
y = A;        // d

初始 \(A=Ready=0\)。在 SC 下，可能结果包括 \((x,y)=(0,0),(0,1),(1,1)\)，但 \((1,0)\) 不可能出现。因为 \(x=1\) 意味着 P1 的读 Ready 看到了 P0 的写 Ready=1，在程序序中 A=1 发生在 Ready=1 之前，而 P1 中 x=Ready 发生在 y=A 之前，所以 y 不应再读到旧的 \(A=0\)。

SC 的优点是程序员容易理解，缺点是它对硬件和编译器优化限制很强。若每个处理器都必须一次只发起一个内存访问，并等待前一个访问完成后才能开始下一个访问，那么写缓冲、乱序流水、内存级并行等优化都会受限，处理器利用率会显著下降。

7.3 放松存储连贯性：TSO、PSO 与弱序

为了提高性能，很多体系结构采用放松的存储连贯性模型。放松模型允许某些内存访问重排，只要程序在需要顺序的地方使用同步操作或 fence。

  • TSO（Total Store Ordering）常被用来描述类似 x86 的较强模型。它通常允许 Store 后面的 Load 提前执行，借助写缓冲隐藏写延迟，但仍保留较多顺序约束。

  • PSO（Partial Store Ordering）比 TSO 更放松，可以进一步允许不同地址的 Store-Store 顺序被放松。不同体系结构的精确定义有所不同，核心思想是：越放松，硬件越容易优化，程序员越需要显式同步。

  • 弱序（Weak Ordering）进一步利用同步操作划分程序。同步操作之间的普通读写可以重排，只要保持线程内部真实依赖；但在同步操作前后，必须等待相关内存操作完成。这样程序员用 lock、unlock、barrier、fence 标出“顺序边界”，硬件在边界内部获得优化空间。

假设初始时 \(A=0\)、\(B=0\)、\(Ready=0\)，两个处理器执行下面的代码：

1
2
3
4
5
6
7
8
9
// P1
A = 100;      // S1: 写数据
Ready = 1;    // S2: 发布标志
r1 = B;       // L1: 再读另一个变量

// P2
B = 1;        // S3: 写变量 B
r2 = Ready;   // L2: 查看 P1 是否发布
r3 = A;       // L3: 如果看到了 Ready，希望能读到 A=100

7.3.1 TSO

在 TSO 中，最典型的放松是 Store 后面的 Load 可以先执行，也就是 Write -> Read 顺序可能被放松。对应到 P1，A=100 和 Ready=1 可能还在写缓冲中，P1 就先执行了 r1=B，因此 P1 可能暂时读不到 P2 对 \(B\) 的写入。这种模型的好处是处理器不用等写操作对全系统可见，就可以继续执行后面的读，从而隐藏写延迟。

可是 TSO 一般仍然保持同一个处理器内部 Store 之间的顺序，所以从 P2 的角度看，如果它已经看到了 Ready=1，通常也应该能看到 P1 更早写出的 A=100。

7.3.2 PSO

在 PSO 中，约束更弱，不仅 Write -> Read 可能放松，不同地址之间的 Write -> Write 也可能放松。对应到 P1，程序顺序是先写 A=100，再写 Ready=1，但其他处理器可能先看到 Ready=1，还没有看到 A=100。于是 P2 可能出现：

1
2
r2 = 1
r3 = 0

这表示 P2 已经看到“数据准备好了”的标志，却还没看到真正的数据。这就是 PSO 比 TSO 更危险的地方：它可能破坏“先写数据、再写标志”这种发布顺序。因此在 PSO 下，生产者通常需要在 A=100 和 Ready=1 之间加 Store fence，保证数据先于标志对外可见。

7.3.3 弱序

在 Weak Ordering 中，普通读写之间的顺序限制更少。硬件可以在同步操作之间重排内存访问，只要不破坏单线程内部的真实数据依赖。所以上面这种只靠普通变量 Ready 做同步的写法是不可靠的。正确写法应该显式加入同步边界，例如：

1
2
3
4
5
6
7
8
9
// P1
A = 100;
fence();      // 或 release-store / unlock
Ready = 1;

// P2
while (Ready == 0) {}
fence();      // 或 acquire-load / lock
r3 = A;

这个例子可以这样总结：

模型 主要放松什么 这个例子中可能出的问题 需要怎样修正
TSO 允许 Write -> Read 放松 P1 的 r1=B 可能先于自己的写真正可见 一般不用为 Store-Store 发布顺序额外加 fence
PSO 进一步允许 Write -> Write 放松 P2 可能看到 Ready=1，却仍读到 A=0 在 A=100 和 Ready=1 之间加 Store fence
Weak Ordering 普通读写可在同步边界之间更自由重排 普通变量 Ready 不能可靠充当同步 用 lock/unlock、barrier、fence 或 acquire/release 原子操作

因此，三者的差别不是“谁对谁错”，而是性能和顺序保证之间的取舍：TSO 保留较多顺序，PSO 放松更多写顺序，弱序模型则把普通访问尽量放开，只要求程序用同步操作标出真正不能重排的位置。

7.4 数据竞争与正确同步程序

两个访问发生冲突，需要满足两个条件：访问同一存储位置，并且至少一个是写。数据竞争（data race）是指不同处理器上的两个冲突访问之间没有被同步操作建立顺序。数据竞争会让程序结果依赖具体硬件的重排、缓存、时序和编译器优化，因此很难推理。

正确同步程序要求所有同步操作被显式标识，所有共享数据访问都通过同步建立顺序。这样即使硬件采用放松模型，程序在同步边界处仍能表现得像在 SC 机器上执行。

7.5 Fence 的作用与误解

Fence 或 memory barrier 用来强制某些内存访问之间的顺序。以 Intel 的 MFENCE 为例，它要求该线程之前的读写完成后，MFENCE 才能完成；MFENCE 之后的读写也必须等它完成后才能开始。LFENCE 主要约束 Load，SFENCE 主要约束 Store。

需要注意，MFENCE 不是“把所有线程的值都刷新到最新”的魔法操作。它主要阻塞执行该 fence 的线程，直到该线程之前的相关内存操作按模型要求完成，例如写缓冲清空。它建立的是可被其他线程观察到的部分顺序，而不是让所有 Cache 瞬间同步。

Fence 通常就是和弱序、TSO、PSO 这类放松存储连贯性模型配合使用的。放松模型允许硬件为了性能重排普通读写；fence 则告诉硬件“这里是顺序边界，前后的某些访问不能跨过去”。也就是说，弱序模型给硬件自由度，fence 在程序真正需要同步的地方把自由度收回来。

7.5.1 例子：先写数据，再发布标志

考虑最常见的生产者-消费者同步：

1
2
3
4
5
6
7
8
9
// 初始 data = 0, ready = 0

// Producer
data = 100;
ready = 1;

// Consumer
while (ready == 0) {}
r = data;

程序员希望消费者只要看到 ready == 1，就一定能读到 data == 100。但在放松存储模型下，生产者对 ready 的写可能先于 data 的写被消费者观察到；消费者也可能在确认 ready 前后发生读重排。这样就可能出现 ready == 1 但 r == 0 的错误结果。

加入 fence 后，可以明确建立发布顺序：

1
2
3
4
5
6
7
8
9
// Producer
data = 100;
fence();       // 保证 data 的写先完成或先对外可见
ready = 1;

// Consumer
while (ready == 0) {}
fence();       // 保证先看到 ready，再读取 data
r = data;

第一个 fence 的作用是防止 ready=1 越过 data=100，否则消费者可能收到“数据好了”的通知，却读不到真正的数据。第二个 fence 的作用是防止消费者对 data 的读取跑到检查 ready 之前。用更现代的说法，生产者侧相当于 release，消费者侧相当于 acquire。

在生产者-消费者式代码中，如果生产者先写数据再更新指针或标志位，就需要在两者之间建立 Store-Store 顺序；消费者看到指针或标志位后再读数据，需要建立 Load-Load 或 acquire 顺序。可以用 MembarSS 和 MembarLL 表达这个思想。

1
2
3
4
5
6
7
8
9
// Producer
buffer[tail] = x;
MembarSS;       // 保证数据先于 tail 可见
tail = tail + 1;

// Consumer
while (head == tail) { }
MembarLL;       // 保证先确认 tail，再读取数据
r = buffer[head];

可以把 fence 理解成“顺序闸门”：它不负责创造数据，只负责禁止某些前后访问越过这道门。

8 同步机制：互斥、信号量、原子操作与锁性能

只要系统中存在并发进程或线程，即使是单核系统也需要同步。同步解决的基本问题有两类：生产者-消费者问题和互斥问题。生产者-消费者要求消费者等待生产者产生数据；互斥要求同一时间只有一个线程进入临界区访问共享资源。

8.1 队列、head 和 tail 的作用

生产者-消费者问题中的队列，本质上是两个线程之间传递数据的缓冲区。生产者负责把任务、消息或数据放进队列，消费者负责从队列中取出这些数据并处理。因为生产者和消费者的速度不一定相同，所以需要队列暂时保存“已经产生但还没被消费”的数据。

在这个队列中，tail 指向生产者下一个要写入的位置，head 指向消费者下一个要读取的位置。生产者放入一个元素时，会先执行类似 buffer[tail] = x 的操作，把数据写到队尾；然后执行 tail = tail + 1，表示队列多了一个元素。消费者取出一个元素时，会先执行类似 x = buffer[head] 的操作，从队头取数据；然后执行 head = head + 1，表示这个元素已经被消费。

当 head == tail 时，说明队列为空，因为消费者要读的位置和生产者下一个要写的位置重合，没有尚未消费的元素。比如初始时 head=0, tail=0，队列为空；生产者写入一个元素后 tail=1，消费者发现 head != tail，就知道有数据可读；消费者读完后把 head 加到 1，此时 head==tail，队列又变为空。

这一节真正要引出的同步问题是：生产者必须先把数据写进队列，再更新 tail；消费者必须先看到 tail 变化，再读取队列数据。如果在弱存储模型下顺序被打乱，消费者可能先看到 tail 已经更新，以为队列非空，但生产者写入 buffer[tail] = x 的结果还没有对消费者可见，于是消费者就可能读到旧数据或无效数据。因此，队列不仅需要 head 和 tail 来表达结构，还需要 fence、原子操作或锁来保证关键的内存顺序。

8.2 生产者-消费者问题

生产者-消费者队列使用 head 和 tail 指针。生产者把数据写入 tail 指向的位置，然后递增并存储 tail；消费者读取 tail 判断队列是否为空，再从 head 指向的位置取数据。

image-20260608105314452

问题在于，程序员假设“如果消费者看到了新的 tail，就一定能读到生产者写入的数据”。但在放松存储模型下，tail 的更新可能先于数据写入被其他处理器观察到，或者消费者的读取可能被提前。于是可能出现消费者读到未初始化或旧数据的情况。因此队列这种看似简单的数据结构，也必须用 fence 或原子同步保证发布顺序。

当有多个消费者时，还会出现另一个问题：多个消费者可能同时看到队列非空，并同时读取、更新同一个 head。此时更新 head 的代码必须作为临界区原子执行，否则两个消费者可能取走同一个元素，或丢失某次 head 更新。

image-20260608105355892

8.3 用普通 Load/Store 实现互斥为什么困难

下面用两个共享变量 c1 和 c2 实现双进程互斥的尝试。

8.3.1 方法一

第一种方法中，进程 1 设置 c1=1 后等待 c2=0，进程 2 设置 c2=1 后等待 c1=0。如果两个进程几乎同时设置自己的标志，就会互相等待，产生死锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 初始 c1 = 0, c2 = 0

// Process 1
c1 = 1;
while (c2 == 1) {
    // 等待 Process 2 离开或放弃
}
// critical section
c1 = 0;

// Process 2
c2 = 1;
while (c1 == 1) {
    // 等待 Process 1 离开或放弃
}
// critical section
c2 = 0;

这段代码的意图很自然：c1=1 表示 Process 1 想进入临界区，c2=1 表示 Process 2 想进入临界区；进入前先看对方是不是也想进。如果只有一个进程想进，它可以顺利进入；但如果两个进程几乎同时执行 c1=1 和 c2=1，随后 Process 1 看到 c2==1，Process 2 看到 c1==1，两边都会在 while 中等待。因为谁也不会先把自己的标志改回 0，所以发生死锁。

8.3.2 方法二

第二种方法为避免死锁，让进程在发现对方也想进入时放弃自己的标志并重试。这样死锁消失了，但可能出现活锁：两个进程不断同时让步、同时重试，谁也进不去；也可能出现饥饿：某个进程长期竞争失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 初始 c1 = 0, c2 = 0

// Process 1
retry1:
c1 = 1;
if (c2 == 1) {
    c1 = 0;
    goto retry1;
}
// critical section
c1 = 0;

// Process 2
retry2:
c2 = 1;
if (c1 == 1) {
    c2 = 0;
    goto retry2;
}
// critical section
c2 = 0;

这次如果两个进程同时想进入，发现对方也想进后，会先撤销自己的请求，再重新尝试，所以不像第一次那样永久互等。但是它会带来活锁。比如两个进程节奏完全一致：同时设置标志，同时看到对方标志为 1，同时把自己的标志清 0，然后又同时重试。表面上两个进程一直在执行代码，没有阻塞，但谁也进不了临界区，这就是活锁。即使没有活锁，也可能发生饥饿：某个进程每次刚准备进入，就碰巧被另一个进程抢先，长期得不到进入临界区的机会。

8.3.3 Dekker 协议

Dekker 协议加入 turn 变量解决双进程互斥问题。c1 和 c2 表示进程是否想进入临界区，turn 决定发生竞争时谁等待。这个例子说明，只用普通读写也能设计互斥协议，但非常精巧、难以推广，并且在现代弱存储模型下还需要额外的内存顺序保证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 初始 c1 = 0, c2 = 0, turn = 0

// Process 1
c1 = 1;
turn = 1;
while (c2 == 1 && turn == 1) {
    // 如果 Process 2 也想进，并且轮到自己等待，就等待
}
// critical section
c1 = 0;

// Process 2
c2 = 1;
turn = 2;
while (c1 == 1 && turn == 2) {
    // 如果 Process 1 也想进，并且轮到自己等待，就等待
}
// critical section
c2 = 0;

Dekker 协议的关键是 turn。当两个进程都想进入临界区时，c1 和 c2 都为 1，仅靠这两个标志无法决定谁让谁。turn 用来打破平局：turn=1 表示 Process 1 等待，turn=2 表示 Process 2 等待。这样两个进程不会同时进入临界区，也不会像第一次尝试那样互相永久等待。

不过，这类协议说明的不是“普通 Load/Store 很适合做同步”，恰好相反，它说明普通 Load/Store 做同步非常脆弱。第一，协议设计很复杂，稍微改错就会死锁、活锁或饥饿；第二，它只适合很小规模的特定场景；第三，在现代处理器的弱存储模型下，普通读写可能被重排，编译器也可能优化访问顺序，所以还需要 fence 或原子操作来保证这些标志变量的读写顺序。因此实际系统更倾向于使用硬件提供的原子 read-modify-write 指令来实现锁和信号量。

8.4 信号量

信号量（semaphore）是一个非负整数，支持两个原子操作：

\[ P(s): \text{若 }s>0\text{，则 }s=s-1\text{；否则等待} \]

\[ V(s): s=s+1\text{，并唤醒一个等待进程} \]

这里的 \(s\) 是信号量变量，表示“当前还允许多少个进程进入临界区或使用某个共享资源”。

这里的资源可以是多个进程/线程都可能访问、但不能无限制同时访问的对象，例如共享变量、队列、链表、哈希表、文件、打印机、数据库连接、缓冲区槽位或 I/O 设备。它也可以不是一个具体硬件，而是一段需要互斥执行的代码。

\(s\) 的值 含义
\(s=0\) 资源正在被占用，后来进程必须等待
\(s=1\) 资源空闲，可以让一个进程进入；常用于互斥锁
\(s=n\) 最多允许 \(n\) 个进程同时使用该资源

\(P(s)\) 是申请进入或申请使用资源的操作，也常叫 wait、down 或 acquire。它的含义是：如果 \(s>0\)，就把 \(s\) 减 \(1\)，表示占用一个可用名额并继续执行；如果 \(s=0\)，说明当前没有可用名额，进程必须等待。\(V(s)\) 是释放资源的操作，也常叫 signal、up 或 release。它的含义是：使用完资源后把 \(s\) 加 \(1\)，表示释放一个名额，并在有进程等待时唤醒其中一个。

用信号量保护临界区时，代码通常写成：

1
2
3
4
5
6
7
// s 的初始值为 1，表示同一时刻最多允许一个进程进入
P(s);

// critical section
// 访问共享资源

V(s);

这段代码的意思是：进入临界区前先执行 \(P(s)\)。若 \(s=1\)，执行后 \(s\) 变为 \(0\)，当前进程进入临界区；在它离开之前，其他进程再执行 \(P(s)\) 会因为 \(s=0\) 而等待。离开临界区时执行 \(V(s)\)，把 \(s\) 从 \(0\) 加回 \(1\)，表示资源重新空闲，并可以唤醒一个等待进程。这样就能保证同一时刻最多只有一个进程访问共享资源。

如果 \(s\) 初始值为 \(1\)，信号量就是互斥锁；如果 \(s\) 初始值大于 \(1\)，它表示最多允许多少个进程同时访问某类资源。关键点是 \(P\) 和 \(V\) 必须是原子的，不能被中断，也不能被多个处理器交叉执行，否则多个线程可能同时认为自己获得了资源。

8.5 原子读-改-写指令

顺序一致性本身不保证一个操作序列具有原子性。所谓“原子”，意思是这个操作在其他处理器看来不可分割：要么还没发生，要么已经完整发生，中间状态不会被别人看到。锁、信号量、并发队列都需要这种能力，因为它们要先读取共享变量，再根据旧值修改共享变量；如果这两步之间被其他处理器插入，就可能多个线程同时以为自己获得了资源。

8.5.1 用 Exchange 实现自旋锁

先用 exchange(r, M) 说明最基本的原子交换。它会把寄存器 r 和内存位置 M 的值交换，而且整个交换过程是原子的。假设共享内存位置 S 表示锁变量，S=0 表示锁空闲，S=1 表示锁已经被占用。线程进入临界区前把自己的寄存器 r0 设为 1，表示“我想把锁改成占用状态”。

1
2
3
4
5
6
7
8
r0 = 1;
do {
    exchange(r0, S);
} while (r0 != 0);

// critical section

S = 0;

如果锁原来空闲，即 S=0，执行 exchange(r0, S) 后，S 变成 1，表示当前线程占有锁；同时旧的 S=0 被换到 r0 中，所以循环条件 r0 != 0 不成立，线程进入临界区。如果锁原来已经被别人占用，即 S=1，交换后 r0 仍然得到 1，线程继续循环等待。离开临界区时执行 S=0，表示释放锁。

这个例子要抓住两点。第一，exchange 不是普通的“读一下再写一下”，而是硬件保证的原子交换。第二，循环等待的线程没有睡眠，而是在不断尝试获得锁，所以这种锁也叫自旋锁。

8.5.2 Test&Set、Fetch&Add 和 Swap

常见的原子 read-modify-write 指令包括几类。它们的共同点是：先读共享内存旧值，再修改共享内存，并且这整个过程不可被其他处理器打断。

1
2
3
4
5
6
7
8
9
10
11
12
Test&Set(m), R:
    R <- M[m];
    if R == 0 then M[m] <- 1;

Fetch&Add(m), Rv, R:
    R <- M[m];
    M[m] <- R + Rv;

Swap(m), R:
    Rt <- M[m];
    M[m] <- R;
    R <- Rt;

Test&Set(m), R 的意思是：把内存位置 m 的旧值读到寄存器 R，如果旧值为 0，就把 m 置为 1。因此它很适合实现锁：0 表示锁空闲，1 表示锁占用。Fetch&Add 适合实现共享计数器或票据锁，因为它能原子地“取走旧号码，同时把号码加一”。Swap 和上一小节的 exchange 含义相近，都是交换寄存器和内存中的值。

8.5.3 例子：用 Test&Set 保护多消费者队列

在多消费者队列例子中，多个消费者会同时竞争同一个 head。如果没有互斥，两个消费者可能同时读到相同的 head，从而取走同一个队列元素，或者把 head 的更新覆盖掉。因此，读取并更新 head 的部分必须放入临界区。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
P:
    Test&Set(mutex), Rtemp
    if (Rtemp != 0) goto P

    Load Rhead, (head)

spin:
    Load Rtail, (tail)
    if Rhead == Rtail goto spin

    Load R, (Rhead)
    Rhead = Rhead + 1
    Store (head), Rhead

V:
    Store (mutex), 0
    process(R)

这段代码中，mutex 是互斥锁变量。执行 Test&Set(mutex), Rtemp 后，如果 Rtemp != 0，说明旧的 mutex 不是 0，锁已经被其他消费者占有，当前消费者只能回到 P 继续等待。如果 Rtemp == 0，说明当前消费者成功把 mutex 从 0 改成 1，于是进入临界区。

临界区真正保护的是 head 相关操作：读取 head、判断队列是否为空、读取 head 指向的元素、递增并写回 head。这些步骤必须作为一个整体执行，否则多个消费者会抢同一个队头元素。注意 process(R) 放在释放锁之后执行，因为处理数据本身通常不需要继续占用队列锁；这样可以缩短临界区，提高并发度。

8.5.4 例子：用 Compare&Swap 实现非阻塞队列同步

Compare&Swap（CAS）是非阻塞同步的重要基础。它的语义是：只有当内存位置 m 的当前值仍然等于期望旧值 Rt 时，才把它改成新值 Rs；如果中途已经被别人改过，就失败。

1
2
3
4
5
6
Compare&Swap(m), Rt, Rs:
    if (Rt == M[m])
        then M[m] = Rs;
             Rs = Rt;
             status <- success;
    else status <- fail;

用 CAS 改写多消费者队列时，它不再先获得一个全局 mutex，而是让每个消费者直接尝试更新 head。

1
2
3
4
5
6
7
8
9
10
11
12
13
try:
    Load Rhead, (head)

spin:
    Load Rtail, (tail)
    if Rhead == Rtail goto spin

    Load R, (Rhead)
    Rnewhead = Rhead + 1
    Compare&Swap(head), Rhead, Rnewhead
    if (status == fail) goto try

    process(R)

这里的关键是 Compare&Swap(head), Rhead, Rnewhead。消费者先把旧的 head 读到 Rhead，并计算新值 Rnewhead = Rhead + 1。执行 CAS 时，如果共享变量 head 仍然等于 Rhead，说明在这段时间里没有其他消费者抢先取走这个元素，当前消费者就成功把 head 推进一格。如果 CAS 失败，说明别的消费者已经更新了 head，当前消费者刚才读到的队头元素不再属于自己，所以必须回到 try 重新读取新的 head。

因此，CAS 版本和 Test&Set 版本的差别不在于“需不需要同步”，而在于同步方式不同。Test&Set 版本先抢锁，再在锁内操作队列；CAS 版本不持有全局锁，而是在最后更新 head 时用一次原子比较交换来确认“我读到的旧状态还没过期”。这就是非阻塞同步的基本思想。

8.6 阻塞同步与非阻塞同步的性能

同步实现大致可以分成三类：阻塞式原子 read-modify-write 指令、非阻塞式原子 read-modify-write 指令，以及只基于普通 Load/Store 的协议。这里的“阻塞”和“非阻塞”主要是在说同步算法的行为，而不是说硬件指令一定会让线程睡眠。

阻塞式原子指令包括 Test&Set、Fetch&Add、Swap。以 8.5.3 的 Test&Set 队列为例，如果一个消费者已经持有 mutex，其他消费者会在 P 处反复执行 Test&Set(mutex), Rtemp。它们没有真正推进队列，只是在等锁变成空闲；一旦竞争很激烈，许多处理器会反复访问同一个 mutex 所在的 Cache 行，使这个 Cache 行在多个 Cache 之间来回迁移，产生大量一致性流量。因此，自旋锁在临界区很短、竞争不高时可以很快；但如果竞争高或临界区长，它会把大量时间浪费在抢锁上。

非阻塞式原子指令包括 Compare&Swap 和 Load-Reserve/Store-Conditional。以 8.5.4 的 CAS 队列为例，消费者不需要先获得 mutex，而是读取 head、读取队列元素，然后用 CAS 尝试提交 head 的新值。如果 CAS 成功，它就完成了一次消费；如果 CAS 失败，说明其他消费者已经改变了 head，它重新开始。这样做的好处是没有一个线程长时间占有全局锁，某个线程被延迟时也不会阻止所有线程继续尝试前进。但它也不是免费午餐：在竞争很激烈时，很多消费者可能同时读到相近的 head，最后只有一个 CAS 成功，其他消费者都要重试。

只用普通 Load/Store 也可以设计同步协议，例如前面 8.3 的 Dekker 协议，但这类协议非常难写对。在现代处理器中，Load 和 Store 还可能被乱序执行，所以往往还需要 fence 来保证顺序。同步性能不仅取决于指令名字，还取决于竞争程度、Cache 结构、Cache 一致性协议造成的通信开销，以及处理器对 Load/Store 的乱序执行能力。可以这样比较：阻塞式锁把竞争集中到锁变量上，容易造成锁变量热点；非阻塞算法把竞争集中到 CAS 提交点上，失败者会重试；普通 Load/Store 协议硬件要求低，但正确性设计最困难。

9 总结

9.1 核心概念对照

概念 一句话理解
TLP 让多个线程在多个处理器或核心上并行执行
SMP/UMA 集中共享存储，访问延迟较均匀，规模受共享总线和内存带宽限制
DSM/NUMA 存储分布在各节点，逻辑共享地址空间，本地快远程慢
Cache coherence 保证同一地址或同一 Cache 块的读写顺序正确
Memory consistency 规定不同地址读写在多处理器中应以什么顺序被观察
Write invalidate 写前作废其他副本，主流方案
Write update 写时更新其他副本，读延迟低但广播开销大
MSI Modified、Shared、Invalid 三状态协议
MESI 在 MSI 上增加 Exclusive，减少独占干净块的升级事务
MOESI 在 MESI 上增加 Owned，允许脏数据被共享而不立即写回主存
Directory 记录块状态和共享者，适合大规模分布式共享存储
Sequential Consistency 每个处理器按程序序，所有访问存在一个全局顺序
Relaxed Consistency 放松部分顺序约束，用同步或 fence 恢复必要顺序
Data race 不同线程对同一位置的冲突访问之间缺少同步顺序
Fence 禁止某些内存操作越过同步边界
CAS 比较并交换，非阻塞同步常用原语

9.2 常见分析场景

Amdahl 定律常用于分析处理器数量、目标加速比和程序并行比例之间的关系。基本公式是：

\[ S=\frac{1}{(1-f)+\frac{f}{N}} \]

代入后可以求出可并行比例 \(f\)，串行比例则是 \(1-f\)。

CPI 与远程访问开销分析通常需要基本 CPI、远程访问比例、远程访问时间和频率。先用频率求时钟周期，再把远程访问时间换算成周期数，最后使用：

\[ CPI_{\text{实际}}=CPI_{\text{基本}}+\text{远程访问率}\times \text{远程访问开销} \]

分析 Cache 一致性读写序列时，可以先标出初始状态，再逐条看事件：读缺失发 BusRd，写共享块发 BusRdX 或升级，M 状态被别人读要 Flush，别人写要作废。不要只看变量值，还要看块状态。

区分真共享和假共享时，要看访问的是不是同一个变量。如果是同一变量在线程间传递，是真共享；如果不同变量落在同一 Cache line，因块级作废造成缺失，就是假共享。

分析存储连贯性时，可以先按 SC 假设列出每个线程程序序，再看这些序能否组成一个无矛盾的全局序。如果在 SC 下不可能但现实硬件可能出现，通常原因是写缓冲、乱序执行或放松模型允许某些重排。

同步机制要抓住两个问题：互斥是否保证同一时刻只有一个线程进入临界区，顺序是否保证发布的数据先于标志位对其他线程可见。普通 Load/Store 难以同时解决这两个问题，所以需要原子 read-modify-write 指令和 fence。

9.3 本章主线总结

线程级并行的根本目标是把多个处理器组织起来共同完成任务，但处理器数量增加后，性能瓶颈从单核执行速度转向并行性、通信和共享存储正确性。共享地址空间让编程更自然，却要求硬件维护 Cache 一致性；集中式系统可以用监听协议，规模扩大后则需要目录协议。即使 Cache 一致性保证了同一地址的行为，多线程程序仍然需要存储连贯性模型来规定不同地址访问的顺序。为了兼顾性能和正确性，现代系统通常采用放松的存储模型，并要求程序通过锁、原子操作、fence 等同步机制明确指出必要的顺序边界。梳理时把“并行性有限、通信昂贵、顺序难保证”这三件事串起来，本章大多数概念都能落到同一条逻辑线上。