浅析高速缓存一致性协议

【摘要】本文首先简单介绍cache的工作原理，分析产生cache不一致的三个原因，再简单介绍并比较两种目前普遍使用的一致性协议：侦听协议和目录协议。接着我们在本文中主要提出一种新的一致性协议框架，这种协议能够将系统性能从正确性中独立出来。我们将这种综合性能的协议称之为基于令牌的Cache 一致性协议。该协议Cache一致性是通过显式交换令牌和令牌计数的方式来实现的。

【关键词】共享存储；cache；一致性；令牌

在计算机经过多年发展的今天，单处理机的性能开发已经到了极限，而共享存储多处理机系统作为一种新的高端的技术，已经无可厚非的成为了主流。即使是低端的服务器也至少拥有两个处理器，而高端系统通常拥有十几个甚至几十个处理器。按照目前的趋势发展下去，多核或多处理机系统将取代单处理机系统而遍布市场，消费者也不太可能去购买一台单处理机的系统。

1.一致性相关概念

1.1一致性问题在多处理机系统中，如果不同处理机中的进程需要共享某些数据，那么同一数据就可能有多个副本分别存放在各个Cache中，当某个Cache 中的数据被更新后，而其他Cache中的相同数据副本并未作相应修改，造成了同一数据多个版本共存的现象。这就是所谓的Cache一致性问题。

1.2一致性协议共享存储多处理机系统采用了一些高速缓存一致性协议（cache coherence protocols）来协调cache跟主存的内容一致性，使其作为一个整体给处理机提供一个单一的地址空间。这种cache-memory结构给处理器提供的一致性视图称为“存储一致性模型”，其通常作为系统结构指令集设计的一个部分[1]。cache一致性协议维护着这种模型的一个全局统一性，虽然目前多处理器系统已经是很普遍了，但在为其设计cache一致性协议方面却没有一个统一的看法，目前来说有两大主流的cache一致性协议：侦听协议和目录协议。事实上，大部分的争论都是围绕这两类协议而展开的。

2.高速缓存的工作原理

2.1基本原理

在由主存和cache组成的存储器层次结构中，主存是多处理机共享的，而cache是每个处理机私有的。主存和cache都以块为单位进行划分，以映射的方式来检索。在主存和cache之间，是以块为单位进行搬送。

当处理机发出一个访问指令来访问主存的一个地址时，如果包含这个地址在内的模块在cache中，该cache可以使用。如果不在cache中，这时，必须把

这个模块从主存搬到cache中，叫做块搬送。如果cache已满，则必须按一定的置换算法挑出一个模块搬出cache到主存。

2.2写控制方式

cache的写控制有两种：写直达方式和写回方式。

2.2.1写直达方式是指处理机把数据写入cache的同时，也写入主存。这种方式控制简单是一优点，但如果写命令多，访问主存次数也会很多，这样就不能充分发挥cache的优势。影响整个系统的性能。

2.2.2写回方式是当cache不命中时，把所有要置换出的块都写回主存去，这又叫简单写回方式。而如果只把修改过的块，在被替换掉时写回主存，这时就要在cache目录中设一位标志，指示该模块是否被修改过。这种方式叫做标志写回方式。简单写回方式会产生多余的块交换，使总交换时间变长，而标志写回方式中，必须在cache目录中增加标志位，致使检索开销增加。

3.产生高速缓存不一致的三个原因

3.1共享可写数据（Sharing of writable data）引起的不一致

处理机P1 将一个新的数据X’写入高速缓冲器中时，如果采用写通过策略，则立即将此复本写回共享存储器，在这种情况下，两个高速缓存中的两份复本X 与X’就不一致了；如果采用写回策略，也会产生不一致性。只用当高速缓存器中修改的数据被替换或变成无效时，主存储器内容才被更新，如图3.1所示。

3.2进程迁移（Process migration）引起的不一致

如果采用写回策略，包含共享变量X 的进程从处理机P1 迁移到处理机P2 时，将会出现不一致性；如果采用写通过策略时，进程从处理机P2 迁移到处理机P1 时，也会出现不一致性。如图3.2所示。

图 3.1 共享可写数据引起的不一致性

图 3.2进程迁移后引起的不一致性

3.3 I/O操作（I/O operation）引起的不一致

绕过高速缓存的I/O 操作也会引起不一致性问题。当I/O 处理机将一个新的数据X’写入主存储器时，绕过采用写通过策略的高速缓存，则在共享缓存C1 和共享存储器之间产生了不一致性。当绕过高速缓存直接从共享存储器中输出数据时，采用写回策略的高速缓存也会产生不一致性。例如以DMA方式传送数据，DMA控制器直接对主存进行操作（读或写），但此时各个高速缓冲中可能有相应数据的复本，就会造成内存与高速缓存之间的不一致。如图3.3所示。

图3.3 绕过高速缓存的I/O 操作引起的不一致性

4.解决高速缓存一致性问题的方法

解决cache一致性问题的方法大体有两种：软件控制法和硬件控制法。[5]

4.1软件控制法

cache一致性问题可以采用软件来解决，包括主流的通过编译进行事先分析的办法、利用OS来保证cache数据一致性的方法、以及其它一些模仿硬件控制法来实现一致性的软件控制方法等。

Hakan Grahn和Per Stenstrom对软件实现硬件控制法中的基于目录的一致性协议进行了详细的分析和比较之后得出，用软件实现可以达到用硬件实现性能的63%到97%，而事实上，一些现实因素会影响软件实现的的性能，导致其具有一些局限。例如，为了维护一致性以及由于不统一的分布式节点的中断导致读取不平衡的开销，以及由于某些处理器比其它处理器处理更多的涉及一致性的重要操作，使软件控制需要同步操作的开销[2]。4.2硬件控制法

硬件控制法是目前使用较为广泛的解决cache一致性问题的方法，主要有侦听总线协议和目录协议，此外，还有用于单cache存储结构（cache-only memory architecture，COMA）的数据传播机制协议（data diffusion machine，DDM）以及基于SCI的协议等[3]。

5.一种新的可供选择的协议：令牌协议

5.1 令牌协议介绍

令牌协议允许竞争发生，但是它利用一种称为正确性基底（correctness substrate）的机制保证所有情况下系统能够正确的运行。该正确性基底确保：

（1）为保证共享变量（也就是内存块或其在Cache中的拷贝）的一致性，所有处理器适当地读写共享变量；

（2）避免饥饿：所有处理器最终能够获得需要共享变量。

正确性基底

正确性基底利用令牌计数方式来执行共享变量一致性保证，并且其利用永久性请求（persistent request）策略防止“饥饿”发生。这两种机制使得在系统中传输共享变量而不必考虑（竞争）访问该变量的顺序，允许处理器仅仅适时读或者写共享变量，但保证无论在何种情况下，某个对共享变量的（永久性）请求能够最终成功实现。