I.7 缓存一致性的实现

本节研究实现缓存一致性的挑战，先讨论第 5 章只是略作提及的监听一致性协议。目录协议在监听协议之上又增加了一些复杂性，主要原因是没有广播，必须用其他机制解决竞争。此外，目录式多处理器的处理器数量更多，不能再假定缓冲空间无限，必须寻找避免死锁的新方法。先从监听协议谈起。

如第 5 章所述，不使用总线时，监听协议处理未命中的难点，在于如何让包含多个步骤的未命中处理过程表现为原子操作。升级未命中与写未命中需要相同的基本处理，也产生相同的实现难题；为简化讨论，这里集中分析升级未命中。处理步骤如下：

检测到未命中，构造发往其他缓存的失效消息。

获得广播通信链路的使用权后，发送消息。
所有失效请求处理完毕后，处理器更新缓存块状态，再执行引起升级未命中的写入。

这里有两个相关难题。第一，若 P1、P2 同时试图升级同一缓存块，如何解决竞争？第二，在第 3 步，处理器如何知道全部失效请求都已处理完毕，从而可以完成这一步？

判定竞争获胜者的办法，在于广播介质施加的顺序。通信介质必须把每次缓存未命中广播到所有节点。若 P1、P2 同时尝试广播，必须保证：或者 P1 的消息先到达 P2，或者 P2 的消息先到达 P1。以下条件可以保证这一性质：每个节点的全部传入、传出请求都必须通过同一个通道；网络只有在能够保证交付时才接受消息，亦即实际上采用电路交换，见附录 F。如果 P1、P2 同时发起失效广播，网络就只能接受其中一个，推迟另一个。这种排序保证 P1、P2 中有一个先完成第 2 步的通信。网络可以在接受消息且保证它成为下一次传输时显式发信号；也可以让处理器监听网络中的自身请求：一旦看见该请求，就知道在任何后续消息之前，它会完整传到全部处理器。

假设 P1 赢得发送失效消息的竞争；一旦知道自己获胜，就能继续第 3 步，完成未命中处理。但 P2 有潜在问题：它开始第 1 步时，相信块处于共享状态；而 P1 要在第 3 步继续，必须知道 P2 已处理失效请求，也就是 P2 的块必须已经变成无效！一种简单方法是让 P2 观察到 P1 的失效广播先于自己的广播，意识到自己输了。P2 随后使块失效，并发出写未命中来获取数据。P1 先看到自己的失效请求，再看到 P2 的请求，因此会先将块改为已修改状态并更新数据，这保证了执行进展，避免死锁。P1 随后看到对已修改块的失效请求时，就知道自己赢得过一场竞争；第 5 章的基本协议中不会出现这种情况。它可以直接忽略此失效请求，因为后面会有写未命中；也可以将块写回存储器，并把状态改为无效。

另一种办法是让传入请求优先于传出请求。因此，P2 在发送自身失效请求之前，必须先处理所有待处理的失效或写未命中。如果某个传入请求与待发消息指向同一块，处理器就必须准备好重启写操作，因为传入请求可能改变该块的状态。注意，由于传入失效优先于传出请求，P1 成功完成广播后，就知道失效会被处理。目录协议不采用广播，处理器无法由此知道失效何时到达；它需要显式确认，下一部分会讨论。实际上，在请求得到确认之前，处理器连自己是否赢得所有权竞争都无法确定。

读取也需要多个步骤，因为数据必须从存储器，或在写回缓存系统中从远程缓存取回；不过，读取没有引入写入之外根本不同的问题。

还有一些棘手的边界情况必须正确处理。例如，写回缓存发生读未命中时可能需要写回一个块；处理器可能优先处理读未命中，推迟写回。若此时出现针对待写回块的监听请求，处理器必须发现它并返回数据，否则可能死锁。类似地，处理器发出写未命中，准备让一个块成为独占状态，但在接收数据并更新块之前，其他处理器又对该块发出读未命中。此时，必须等写入处理器收到数据并完成更新后，才能处理那些读未命中。

另一项较难的问题是：在写回缓存系统中，读未命中或写未命中的数据可能来自存储器，也可能来自某个处理器缓存，但请求者事先不知道来源。多数总线系统使用一个全局信号，表示是否有处理器持有独占、因而也是最新的副本；若没有，才由存储器响应。对于流水化互连，可以要求各处理器在未命中广播后的固定周期数内报告是否持有独占副本，从而使用这种方案。

但现代多处理器基本无法给出监听请求处理时间的严格上限。因此，需要另一种机制判断存储器副本是否最新。一种方法是在存储器中增加一致性位，指示数据是否被某个远程缓存独占。这已经开始接近目录方法，下面就讨论其实现挑战。

DSM 多处理器中的缓存一致性实现

实现目录式缓存一致性协议，需要解决监听协议中所有由非原子操作造成的问题，却不能依赖广播。广播曾经强制竞争写入串行化，也保证了存储一致性模型所要求的顺序，见第 5 章。避免广播是目录系统的核心目标，因此必须用其他方法保证串行化。

对某内存块的独占访问请求很容易排序，因为它们到达该块唯一的目录时，就会被串行处理。只要目录控制器保证一个请求被完整处理后再开始下一个，写入就会串行化。

请求者事先不知道谁会赢，而且通信不是广播，所以目录处理完获胜者的请求后，必须通知它。这可以通过写未命中的数据响应完成，也可以用针对失效请求、显式授予所有权的确认消息完成。

竞争失败者怎么办？最简单的方法是返回否定确认，即 NAK，让请求节点重新发出请求。这相当于监听方案中广播网络发生冲突，需要其中一个发送节点重试。下一部分将说明，为什么与缓冲请求相比，NAK 是有吸引力的方案。

发送写未命中响应或所有权确认后，虽然已通知请求节点获得所有权，但仍不知道共享者集合中的各节点是否收到并处理了失效请求。所有存储一致性模型最终都会要求处理器知道这次写入的全部失效已完成，例如在下一次缓存未命中之前，或者在同步点。监听方案由广播网络本身提供这种保证。

目录方案如何知道失效已完成？唯一的办法，是让失效消息的接收节点，也就是共享者集合成员，显式确认目录发来的失效消息。确认应发给谁？有两种选择。第一种发给目录，由目录计数，全部确认收齐后，再向最初的请求者发送一条确认。第二种是在授予所有权时，目录告知请求者应收到多少条确认；各失效接收方直接向请求者确认，请求者身份由目录提供。多数现有实现采用后者，因为它降低了目录成为瓶颈的可能性。显式确认虽然增加了目录协议的复杂性，但这是避免监听广播这类串行化机制的代价；而这类机制本身正是扩展性的限制。

避免有限缓冲引起的死锁

目录式多处理器可能具有很大规模，因此实现中又多了一项复杂性。第 5 章假定网络总能接受一致性消息，而且请求最终会得到处理。在更大型多处理器中，无限缓冲的假设可能不合理。缓冲空间有限会怎样？主要影响是，缓存控制器或目录控制器可能无法完成消息发送，从而导致死锁。

潜在死锁来自以下三个性质，它们也是许多死锁场景的共同特征：

完成事务需要不止一种资源。 生成请求、生成回复与确认，以及接收回复，都需要消息缓冲区。
资源一直持有到非原子事务完成。 生成回复所用的缓冲区，在回复被接受之前不能释放，原因稍后说明。
资源获取不存在全局偏序。 节点可以自由产生请求和回复。

这些性质会导致死锁；要避免死锁，必须破坏其中至少一项。在事务未完成时释放资源很困难，因为必须完整撤销事务，不能把它留在半完成状态。因此，我们尝试解决对多种资源的需要。不能简单取消这种需要，但可以设法保证所需资源始终可用。

保证事务最终完成的一种办法，是始终预留足够缓冲区来接收消息。对小型多处理器，如果处理器在缓存未命中时阻塞，或只有少量尚未完成的未命中请求，这或许可行；但对目录协议未必实用，因为一次写入就可能产生大量失效消息。此外，预取和多个尚未完成的未命中请求等特性，还会进一步增加缓冲需求。多数系统采用另一种策略：只有在能够保证具备完成事务所需资源后，才真正启动事务。这一策略由四部分组成：

请求与回复使用分开的物理或虚拟网络。这里的“回复”，是控制器进行状态转换时必须等待的任何消息。这样，新请求就不会堵住那些能够释放缓冲区的回复。
每个预期会收到回复的请求，在生成时就分配接收回复的空间。如果没有空间，请求必须等待。这保证节点总能接收回复，让回复方释放缓冲区。
控制器可以对任何请求返回 NAK，但绝不能拒绝回复。这防止控制器在无法保证回复缓冲空间时启动事务。
收到 NAK 的请求直接重试。

要理解为什么这四项能避免死锁，必须保证所有回复都能被接受，而且每个请求最终都能获得服务。缓存或目录控制器总在发出请求之前分配回复缓冲区，所以回复返回时一定能接受。要说明每个请求最终都能得到服务，需要说明任一个请求都可以完成。每个请求都起源于缓存的读未命中或写未命中，因此只需说明二者最终可获服务。写未命中包含了读未命中的动作，下面只讨论写未命中。块未缓存是最简单的情况，而共享块情况包含了它，因此重点讨论共享和独占两种情况。

先看块处于共享状态时：

CPU 尝试写入，产生发往目录的写未命中。为简化讨论，假设处理器已经停顿；即便继续发请求，在第一次请求完成之前，也不应再对同一缓存块发请求。不同块的请求可以独立处理。
写未命中被发送到该内存块的目录控制器。一个缓存控制器负责同一缓存块位置的所有请求，而不论其中当前存放的是哪一个内存块的数据；目录控制器则把不同块的请求视为独立事件，前提是有足够缓冲，并在代表该请求进一步发消息前就分配好。目录控制器的冲突只发生在两个请求针对同一块时。它必须等待第一个操作完成；第二个请求可以被 NAK，也可以被缓冲，但不能在第一个完成前获得服务。
假设该写未命中是目录控制器接下来处理的事件。控制器发出失效请求，缓存控制器总能在有限延迟后接受。一种可能是，缓存控制器对同一块也有尚未完成的未命中请求。这与监听方案中的竞争相对应；仍须强制缓存控制器接受并执行目录请求来打破竞争。根据具体时序，该缓存控制器要么稍后从目录取得缓存行，要么收到 NAK 并重新启动过程。

块处于独占状态时稍复杂。分析从写未命中到达目录控制器开始，有两种情况：

目录控制器向持有者发送取回／失效消息。消息到达时，块仍处于独占状态。缓存控制器将数据写回归属目录，并使本地状态无效。归属目录已预先分配缓冲区，所以一定能接收回复；随后把数据发给请求处理器，请求者同样一定能接收。更新缓存后，请求方缓存控制器通知处理器。
目录控制器向记录中的所有者发出取回／失效消息。但消息到达时，该缓存控制器已经因另一次读未命中或写未命中而替换了该块。此时，它已经把块以数据写回消息发往归属目录，并使本地数据不可用。这与取回／失效消息所要求的效果完全相同，因此协议在这种情况下也能正确工作。

上述分析说明：只要缓存和目录控制器能够接受那些没有其他未完成操作的块的请求、总能接受回复，并允许请求被 NAK 后重试，一致性机制就能正常工作。和监听协议一样，缓存控制器必须能打破竞争；这里始终让目录发来的指令优先。能够对请求返回 NAK，使有限缓冲实现得以避免死锁。

目录控制器的实现

缓存控制器仍需具备监听方案中的能力：在等待本地处理器请求的响应时，能处理其他独立块的请求。传入请求仍按顺序处理，每个请求处理完再开始下一个。如果短时间到达的请求太多，缓存控制器可以返回 NAK，因为目录稍后会重新生成请求。

目录也必须支持多个活动事务，独立处理不同块的请求。这与缓存控制器处理独立块的传入请求略有不同：目录在较早请求仍未完成时，就需要开始处理另一个请求。它不能总等一个请求完成后才处理下一个，否则可能死锁。因此目录控制器必须可重入：等待回复时可以挂起当前执行，接收另一项事务。必须这样做的地方，是响应读未命中或写未命中、等待所有者回复时。由此得到三点重要结论：

只有在远程取回，或取回／失效操作尚未完成时，才需要保存、恢复控制器状态。
对于会让未完成请求数超出上限的读、写未命中，可以直接 NAK，从而限制目录同时处理的事务数量。

如果所有者不经目录转送数据，而是直接向请求者转发，同时也把数据返回目录，就可以避免要求目录处理多个未完成请求。这一点与降低延迟一起，构成采用转发式协议的动机。不过，请求到达时间非常接近时，转发式协议也会引入其他复杂情况。

剩下的主要难点是处理 NAK。一种方案是让每个处理器跟踪自身未完成事务，从而在 NAK 到达时知道对应的请求；另一种是在 NAK 中附上原始请求，让接收控制器据此恢复。由于每个请求都已预留接收回复的槽位，而 NAK 也是回复，因此总能收到 NAK。实际上，这个回复槽位还可以保存请求信息，让处理器在被拒绝后重新发出请求。

实践中，要正确实现这些协议并避免死锁，必须十分谨慎。本节的核心思想——处理非原子性与有限缓冲——对保证实现正确至关重要。设计者发现，形式化和非形式化验证技术都有助于确认实现的正确性。