# 5.2 多处理器缓存一致性
<!-- source: p0405 -->

两个处理器分别通过各自的缓存观察内存，因此，对同一内存位置，它们最终可能看到不同的值，如图 5.3 所示。这一困难通常称为**缓存一致性问题（cache coherence problem）**。注意，一致性问题之所以存在，是因为系统既有主要由主存定义的全局状态，又有由各处理器核心的私有缓存定义的局部状态。因此，即使多核系统中某些缓存级别，例如 LLC，是共享的，而另一些级别，例如 L1 和 L2，是私有的，一致性问题仍然存在，仍必须解决。

| 时间 | 事件 | 处理器 A 的缓存内容 | 处理器 B 的缓存内容 | 内存位置 X 的内容 |
| ---: | --- | ---: | ---: | ---: |
| 0 | | | | 1 |
| 1 | 处理器 A 读 X | 1 | | 1 |
| 2 | 处理器 B 读 X | 1 | 1 | 1 |
| 3 | 处理器 A 向 X 存入 0 | 0 | 1 | 0 |
{#fig-5.3 num="5.3" caption="两个处理器 A 和 B 读写同一个内存位置 X 时的缓存一致性问题。" .wide .expand}

**图 5.3（续）。** 最初假定两个缓存都不包含该变量，X 的值为 1。还假定采用直写缓存；写回缓存会带来额外但类似的复杂性。A 写入 X 后，A 的缓存与内存都包含新值，但 B 的缓存没有更新。如果 B 读取 X，得到的仍然是 1！

非正式地说，如果对一个数据项的任何读取都返回该数据项最近写入的值，那么存储系统就是一致的。这个定义虽然直观，却含糊且过于简单；实际情况复杂得多。它包含存储系统行为的两个不同方面，而这两个方面对编写正确的共享内存程序都至关重要。第一个方面称为**缓存一致性（coherence）**，规定一次读操作可以返回哪些值。第二个方面称为**存储一致性（consistency）**，规定写入的值何时会被一次读操作返回。先来看 coherence。

<!-- source: p0406 -->

一个存储系统满足以下三个性质时，就具有缓存一致性：

1. **单处理器读一致性。** 处理器 P 向位置 X 写入后，再由 P 读取 X；如果 P 的这次写与读之间没有其他处理器写 X，那么读取必须返回 P 写入的值。
2. **多处理器读一致性。** 一个处理器向位置 X 写入后，另一个处理器再读取 X；如果两次操作在时间上相隔足够远，而且其间没有其他对 X 的写入，那么读取返回该写入值。
3. **多处理器写串行化。** 对同一位置的写操作必须串行化：任意两个处理器对同一位置的两次写入，在所有处理器看来顺序相同。例如，如果先后向某个位置写入 y 和 z，任何处理器都不可能先读到 z，随后又读到 y。

单处理器读一致性保持了程序顺序；即使在单处理器中，我们也要求这一性质成立。多处理器读一致性定义了“一致的内存视图”的含义：如果一个处理器能够不断读到旧值，我们显然会说内存是不一致的。

多处理器写串行化的必要性更为微妙，但同样重要。假设不对写操作串行化，处理器 P1 先写位置 X，随后 P2 也写位置 X。写串行化保证每个处理器最终都能看到 P2 的写入。如果不串行化，某些处理器可能先看到 P2 的写入，随后才看到 P1 的写入，并无限期地保留 P1 写入的值。避免这类困难最简单的办法，就是保证所有处理器都以相同顺序看到对同一位置的全部写操作；这一性质称为**写串行化（write serialization）**。

虽然上述三个性质足以确保 coherence，但一个写入值何时可见，也同样重要。原因在于，我们不可能要求对 X 的一次读取，立即看到另一个处理器刚写入 X 的值。例如，一个处理器写 X 后极短时间内，另一个处理器就读 X，此时可能无法保证读取返回新写入的数据，因为新数据甚至还没有离开发起写入的处理器。写入值究竟必须在何时对读取者可见，由**存储一致性模型（memory consistency model）**定义，5.6 节将讨论这一主题。

Coherence 与 consistency 相辅相成：前者定义对**同一个内存位置**的读写行为；后者定义读写操作与对**其他内存位置**的访问之间的关系。暂且作两个假设。第一，只有所有处理器都看到了某次写入的效果，该写操作才算完成，才允许下一次写操作发生。第二，处理器不改变任意写操作相对于其他任何内存访问的顺序。

<!-- source: p0407 -->

这两个条件意味着：如果一个处理器先写 A，再写 B，那么任何看到了 B 新值的处理器，也必须看到 A 的新值。这些限制允许处理器重排读操作，却要求处理器按照程序顺序完成写操作。在到达 5.6 节之前，我们一直采用这一假设；届时会准确分析它的含义，并讨论其他选择。

## 保证一致性的基本方案

多处理器与 I/O 的一致性问题，虽然起因相似，却具有不同特点，适用的解决办法也因此不同。I/O 中出现多个数据副本的情况较少，且应尽量避免；而在多个处理器上运行的程序，通常会在若干缓存中保留同一数据的副本。在具有一致性的多处理器中，缓存既支持共享数据项的迁移，也支持其复制。

一致性缓存支持**迁移（migration）**：数据项可以透明地移入本地缓存，并在那里使用。这样既降低了访问远程分配的共享数据项的延迟，也减少了对共享内存带宽的需求。迁移还能降低能耗，因为访问本地缓存比访问片外内存节能得多。

缓存会在本地保存数据项的一个副本，因此，一致性缓存也为同时被读取的共享数据提供**复制（replication）**。复制既减少访问延迟，也减轻对同一共享数据项的读取争用。支持迁移和复制，对共享数据访问的性能至关重要，同时也节省能量。因此，多处理器不会仅靠软件避免这个问题，而是引入维护缓存一致性的协议，在硬件中解决它。

## 保证一致性：失效与更新

有两种方法可以满足一致性要求。一种方法是在写入某个数据项之前，确保处理器对该数据项具有独占访问权。这种协议称为**写失效协议（write invalidate protocol）**，因为它会在写入前使其他副本失效。这是迄今最常见的协议。独占访问保证写入发生时，不存在其他可读或可写的副本：该数据项在其他缓存中的副本全部失效。

图 5.4 展示了采用写回缓存的失效协议如何工作。考虑一次写入之后，另一个处理器又进行读取，就可以看出该协议如何保证一致性：由于写入要求独占访问权，读取处理器保留的任何副本都必须失效。因此，当持有旧副本的缓存再次读取该数据时，会发生缓存未命中，被迫获取一个新副本。对于写操作，我们也要求写入处理器具有独占访问权，从而防止其他处理器同时写入。

<!-- source: p0408 -->

| 处理器操作 | 总线操作 | 处理器 A 的缓存内容 | 处理器 B 的缓存内容 | 内存位置 X 的内容 |
| --- | --- | ---: | ---: | ---: |
| | | | | 0 |
| 处理器 A 读 X | X 缓存未命中 | 0 | | 0 |
| 处理器 B 读 X | X 缓存未命中 | 0 | 0 | 0 |
| 处理器 A 向 X 写入 1 | 使 X 失效 | 1 | | 0 |
| 处理器 B 读 X | X 缓存未命中 | 1 | 1 | 1 |
{#fig-5.4 num="5.4" caption="在监听总线上，对单个缓存块 X 使用写回缓存的失效协议示例。" .wide .expand}

**图 5.4（续）。** 假定最初两个缓存都没有 X，内存中 X 的值为 0。表中处理器与内存的内容，是处理器操作和总线操作都完成后的值。空白表示没有操作，或没有缓存副本。B 第二次未命中时，处理器 A 返回该值，并取消来自内存的响应。此外，B 的缓存内容和内存中 X 的内容都得到更新。在块转为共享状态时更新内存，可以简化协议；也可以跟踪所有权，只有块被替换时才要求写回。后者需要增加一个状态位来表示块的所有权。所有权位表明，一个块可以被共享读取，但只有拥有它的处理器才能写入；该处理器在修改或替换这个块时，负责更新其他处理器和内存。如果多核处理器使用共享缓存，例如 L3，那么所有内存访问都经过共享缓存；L3 扮演本例中内存的角色，而需要维护一致性的，是各核心的私有 L1、L2 缓存。正是这一认识，使一些设计者选择在多核处理器内部使用目录协议。要使这种办法工作，L3 缓存必须具有包含性。回顾第 2 章：如果更高一级缓存中的任何位置，本例为 L1 和 L2，也都存在于 L3，那么缓存就具有包含性。5.7 节将再次讨论包含性。

如果两个处理器同时尝试写同一数据，其中一个会赢得竞争，如何决定胜者稍后介绍，并使另一个处理器的副本失效。后者若要完成写入，就必须取得新的数据副本，而该副本已经包含更新后的值。因此，这种协议实现了写串行化。

另一种办法是在写入一个数据项时，更新它在全部缓存中的副本。这称为**写更新协议（write update protocol）**或**写广播协议（write broadcast protocol）**。写更新协议必须广播对共享缓存行的所有写入，因此消耗的带宽大得多。正因如此，近期所有多处理器都默认采用写失效协议；本章其余部分只讨论失效协议。

## 缓存一致性协议

实现缓存一致性协议的关键，是跟踪所有共享数据块的状态。缓存块的状态通过与块关联的状态位保存，类似于单处理器缓存中的有效位和脏位。目前有两类协议，使用不同的方法跟踪共享状态：

<!-- source: p0409 -->

- **基于目录（directory based）。** 某个物理内存块的共享状态，集中保存在一个称为目录的位置。目录通常位于共享 LLC，或位于该块所在内存对应的内存接口。为了可扩展性，包含多个芯片的多数多处理器使用多个分布式目录，通常每个芯片一个。许多多核处理器将目录信息与 LLC 关联；由于 LLC 分散为多个存储体，单个多核处理器内部的目录也是分布式的！分布式目录比单一目录复杂，5.4 节将讨论这类设计。
- **监听（snooping）。** 共享状态不集中保存在一个目录中，而由每个持有某物理内存块副本的缓存跟踪该块的共享状态。因为这些信息仅保存在本地，每次一致性事务都必须向所有缓存广播。若使用总线等广播介质，每个缓存控制器就监视，也就是“监听”该介质，判断自己是否持有被请求块的副本。

监听协议曾广泛用于这样一类多处理器：它由单核微处理器和缓存构成，通过总线连接到一个共享内存。如今，大多数多核设计采用混合协议：用监听维持各个非共享缓存，即 L1 和 L2，的一致性；在 LLC 或内存接口处使用目录方案，决定必须监听哪些处理器，才能确保一致性。一些多核处理器的组织次序相反：在通过广播介质连接的 2–4 个插槽之间采用监听，而由目录指出各插槽内部需要监听哪些核心。5.4 节末尾将再次讨论混合方案。