翻译《A Primer on Memory Consistency and Cache Coherence》第二版 第二章

我这段时间在找工作，尝试从外企调到互联网(虽然屡屡被拒绝 lol)，面试过程中发现很多人对于所谓的内存序，缓存一致性，顺序一致性很迷惑，他们对于多线程的理解只限于高层语言，不理解为什么会有这种内存序，抽象是怎么回事，底下怎么做的。此外看了《 C++并发实战》的不同版本的翻译，发现里面有很多的错误，这会破坏初学者对内存序的认识，因此打算翻译这本入门书。

在翻译的过程当中，我也遇到了一些问题，希望诸位能给我解答：

• 我希望能多找几个同行做检查和校验，那么应当如何进行这项工作呢？我目前把已经翻译好的，和部分翻译的都放在了自己的博客里。这样不方便别人校验和参与。如果放到 github 上，又怎样多选择几个人做编辑呢？
• 我是从网上直接下载的英文 pdf 版本进行的翻译，我应当按照哪种协议进行分享呢？
• 目前我发现从英文翻译到中文时，有大量的词语有多重含义和多种翻译，又由于很多中文资料当中有很多错误。因此打算建一个网站，用来提供英文和中文的查询。但是我想提供一种词条之间的联系，嗯，类似 cpp reference 那种。那么我应当怎么利用数据库实现这种存储这种类似图的关系呢？有大佬教教我吗？

下面是第二章的内容，我没有翻译侧边栏，详细侧边栏的计划放到后面。图片的链接是 github 的链接 有错误可以直接回复给我：

第二章：缓存一致性基础

本章我们会充分介绍缓存一致性来帮助理解强定序模型（也可被译为一致性内存模型，SC ）如何和缓存交互。从 2.1 节开始我们会展示本书一直涉及到的强定序模型。为了简化本章节和其他章节的理论复杂性，我们选择最简单的系统模型来展示需要关注的重要事项；到第九章我们才会涉及到更复杂的系统模型。2.2 讲述有哪些必须解决的缓存一致性问题及为什么会有缓存不一致问题出现。2.3 节给出了缓存一致性概念具体的定义。（这里多赘述一点，X86 硬件实现缓存一致性，而 ARM 并非如此！需要软件实现）

2.1 基线系统模型(BASELINE SYSTEM MODEL)

本书里，我们将系统视为一个拥有多个处理器，共享同一个物理内存，所有的处理器都可以对所有的物理地址进行载入和存储操作的模型。该基线系统包含一个单独的多核芯片和芯片外的物理内存，就如同图 2.1 展示的那样。多核芯片包含多个单线程的处理器，每个处理都有自己的私有数据缓存。每个核共享一个最低层级缓存（ last-level cache (LLC) ）。当我们谈到“缓存”这个词，我们指的是每个核上的私有数据缓存而不是最低层级缓存。每个核的私有数据成员通过物理地址生成索引和标记，采取写回策略(注，不明白什么是写回策略的可以看《现代体系结构上的 unix 系统》)。处理器们和最低层级缓存使用交互网络（ interconnection network ）通信。尽管最低层级缓存也在处理器芯片上，但从逻辑角度来看，是个“内存部分缓存”(memory-side cache)，因此并不会导致任何缓存一致性问题。从逻辑层面来看，最低层级缓存直接和内存交互，提供降低内存访问延迟和增加内存访问带宽的功能。它同样充当（多处理器芯片的）片上内存控制器角色。

我们的基线系统模型忽略了很多和本书内容无关，但是很常见的设计。这些设计包括指令缓存，多级缓存，多处理器共享一级缓存，虚拟地址缓存，TLB，DMA 。同时，我们忽略包含多个多核芯片的系统。这些会添加不必要复杂度的话题，以后再说。

2.2 关键问题：缓存不一致到底是怎样发生的？

缓存不一致之所以会出现是因为一个很基本的问题：多个角色可以并行地访问内存和缓存的入口。现代操作系统里，这些角色包括处理器，DMA 控制器，和一些其他的可读写缓存和内存的外部设备。在本书里，我们将目光投射于处理器，但这并不意味可以无视处理器以外的角色。

表 2.1 展示了一个缓存不一致的例子，一开始内存地址 A 和两个处理器的本地缓存都存储值 42 。在时刻 1，处理器 1 改变了其缓存和内存地址 A 储存的值，从 42 变到 43 。这使得处理器 2 缓存里的值过时。处理器 2 在执行一个 while 循环的载入，重复地从它自己的本地缓存中载入已经过时的 A 的值 42 。很明显，这个缓存不一致的例子，是由于处理器 1 对 A 的储存行为，对处理器 2 是不可见，而导致的。

为了避免这种缓存不一致问题，系统必须实现缓存一致性协议（ cache coherence protocol ）才能保证处理器 1 的结果对处理器 2 是可见的。设计和实现缓存一致性协议是第六章-第九章的主要话题。

2.3 缓存一致性协议接口

通俗的说，缓存一致性协议必须保证写操作对所有的处理器可见。本节，我们会正式地从缓存一致性接口中抽象出缓存一致性协议。

处理器通过缓存一致性协议提供的两个接口来进行交互：(1)读请求(read-request)，该请求将内存地址作为参数，该请求的结果是向处理器返回一个值。(2)写请求(write-request)将内存地址作为参数 1，将要写入的值作为参数 2，该请求的结果是向处理器返回一个确认值。

无论是学术还是工业界，目前已经由许多缓存一致性协议出现，我们会根据这些缓存一致性协议提供的接口进行区分，具体来说就是通过缓存一致性是否和内存一致性密不可分来区分。

• 一致性不可区分协议 这种协议，执行写请求时，即使没有返回确认，写入的结果立刻对其他核可见。因为写操作是同步传播的，第一种缓存一致性协议就如同工作在一个原子操作内存系统上(缓存仿佛不存在一样)。任何和这种缓存一致性协议交互的子系统-比方说处理器管线-可以认为它正在和一个没有缓存的原子操作内存系统交互。从追求实现代码顺序一致性的角度来看，这种协议免去了程序员对多核系统中变量值不同的担忧。这种缓存一致性协议将缓存透明化，仿佛移除了缓存的存在，只有原子操作内存系统。这种协议的实现，将问题丢给了处理器管线（硬件）解决。
• 一致性可区分协议 这种协议的写结果是异步传播的，因此写操作的确认可能在其他核可见之前就返回给当前核，从而可以在其他核上观测到过期的变量。然而，为了不违背内存一致性的要求，这种类型的缓存一致性协议必须保证写入的值所显示的顺序，和写入操作写入的顺序是一致的（我理解为，如果写入操作的顺序是 a,b,c,d,e，那么其他核看到的顺序也得是 a,b,c,d,e 。不能出现 a,d,c,b,e 这种混乱的顺序）。图 2.2 中，处理器管线和缓存一致性协议一起努力实现内存一致性。第二种类型的缓存一致性多见于 GPU 。

本书主要关注第一种缓存一致性协议，第二种类型的协议到第十章才会讨论。

2.4 缓存不变式

究竟缓存一致性协议应当满足什么不变式，才能使得缓存透明化，将物理内存和缓存系统抽象成一个原子内存系统呢？目前无论是工业界还是学术界，已经有多种缓存一致性的定义，我们可不想把他们都列出来。作为替代，我们会给出一种体现缓存一致性本质的定义。在侧边栏里，我们会讨论其他定义，展示他们和我们的定义有什么关系。

我们将缓存一致性协议定义为满足单写多读不变式（ SWMR(single-writer–multiple-reader )）的协议。任何一个时刻，对于特定的内存地址，在任何一个时刻，如果该地址的内容只被一个核修改，不存在其他核也在同时进行读或写操作，或者（这个或者对应于那个“如果该地址”）此时没有任何一个核进行写操作，多个核在对这块地址进行读操作。换另一种说法，对任何内存块而言，该块的生命周期被分为多个周期。每个周期里，该内存块只会处于两种状况：一种状况是只有一个核拥有读+写权限，另一种状况是有多个核(也可能一个都没有)拥有只读权限。图 2.3 展示了将内存块生命周期拆分开的例子。

除了 SWMR 不变式，缓存一致性协议同样要求操作内存块值的行为可以被正确的传播（）。设想图 2.3 中的例子，即使满足了 SWMR 不变式，如果第一个只读周期，核 2 和核 5 读到了不同的值，那么系统就不满足协议一致性了。相似地，如果核 1 没能成功读取核 3 在读+写周期写入的值，或者核 1，核 2，核 3 没能读取到核 1 存储的值，协议一致性再次被打破。

因此，必须满足 SWMR 不变式和数据值操作正确(Data-Value Invariant )不变式才能满足缓存一致性协议，数据值操作正确不变式保证了处理器在读周期，能正确读到该内存块处于读+写周期时最后写入的值。

其他的缓存一致性协议不变式的定义和我们的大同小异。（下面的翻译是我胡编的）虎符协议，只有拿到所有的虎符才能执行调兵操作（写操作），否则只能执行报数操作（读操作）。在任意时刻，只可能有一个调兵操作（写操作）或者多个报数操作（读操作）。

2.4.1 实现缓存不变式

上一节提到的几个不变式暗示了缓存一致性协议如何工作。大部分缓存一致性协议，被称为“无效化协议”，就满足这些不变式。如果一个核想读取一块内存，就向其他核发送消息请求获取该内存块的值并确保不会有其他核已经缓存了这个内存块的值，且（其他核）处于读+写状态。该消息会终止任何当前活跃的读+写状态，并开始一个只读周期。如何该核相对某个内存块写，它会对其他核发送请求获取该内存块的值，并确定其它核没有缓存该内存块，无论他们是出于只读还是读+写状态。该请求会终止任何活跃的读+写或只读的周期，并开始一个新的读+写周期。后续的章节(6-9 章)拓展了这种协议的抽象模型，但实现一致性基本的理念不变。

2.4.2 缓存的粒度

一个核可以以多种粒度执行载入和储存操作，粒度一般从 1-64 字节浮动。理论上来说，缓存一致性可以以任意粒度执行。然后现实环境里缓存一致性的粒度经常和缓存块大小保持一致---真实硬件以缓存块长度实现缓存一致性。对真实硬件而言，基本不可能出现一个核修改缓存块的第一个字节，其他核修改该缓存块的其他字节(对缓存的修改通常都是整行的，从实现角度和理论角度，效率更好实现简单)。尽管以缓存块长度为缓存一致性实行的粒度更为普遍，我们需要认识到缓存一致性协议可以以其他粒度实现。

2.4.3 缓存一致性何时重要

无论我们选择如何定义缓存一致性，缓存一致性只在特定情况下至关重要。架构设计者必须清楚缓存一致性是否生效。我们指出两条缓存一致性的准则(我理解为缓存一致性提供的保证)。

• 缓存一致性对任何层级的缓存和共享物理内存都适用。这些结构包括 L1 数据缓存，L2 级别缓存，共享的 LLC，和主存。此外诸如 L1 指令缓存和 TLB 同样适用。(这句话需要注意，这些结构并不包含 per core write buffer，也就是每个核的写缓存器。写缓冲器和 L1/L2/LLC cache 并不是一个东西，如果这个不清楚，看 TSO 和 PSO 的时候会产生很多疑问)
• 缓存一致性对程序员是透明的。处理器管线(pipeline)和一致性模型一同努力提供强定序的内存模型，程序员只能注意到强定序的内存模型。