多处理机的Cache一致性问题及其解决方案

多处理机的Cache一致性问题及其解决方案1 多处理机体系结构2 Cache一致性问题3 监听一致性协议3.1 写作废方式3.1.1 具体流程3.1.2 状态转换图 3.2 写更新方式 4 目录一致性协议

多处理机的Cache一致性问题及其解决方案

1 多处理机体系结构

一种很朴素的提高计算机解决问题的性能的方法是，把多个小的计算机连接起来、并行执行相对独立的任务、必要时互相做到通信，就可以制造出一台功能强大、性能较高的计算机，这也是多处理机技术的基本思想。

在这，我们将讨论的多处理机局限于：

处理机的协调与使用由单一的处理器系统来控制。多处理机通过共享地址空间来共享存储器。各个处理机有自己的Cache。

在逻辑上，多处理机共享地址空间。而在物理上，可以采取两种方式布置主存储器，可以采取集中式和分布式。如下图：

对于图一的集中式结构，通常称其为集中式共享存储器体系结构，这种体系结构还有的一个特点是，所有的处理器访问存储器的延迟都是一致的，有时也被称为UMA结构（Uniform Memory Access）。

对于图二的集中式结构，通常称其为分布式共享存储器体系结构，这种体系结构采用了分布式处理器，各处理器间通过互联网络进行数据的传送，有时也被称为NUMA结构（Non-Uniform Memory Access）。

而无论是哪一种结构，都可能会出现数据共享的问题，即两个不同处理机的 Cache存放了缓存了同一个主存单元的块，即共享数据，这种情况就可能会导致Cache一致性问题的出现。

2 Cache一致性问题

通过下图，我们能理解什么是Cache一致性问题。

具体的过程描述如下：

初始时，CPU A Cache以及CPU B Cache中无缓存内容，而主存中的X单元处存储的内容为1。在1时间时，CPU A读取X单元，由于CPU A Cache中无缓存内容，因此将主存中的数据读入CPU A Cache中。在2时间时，CPU B读取X单元，由于CPU B Cache中无缓存内容，因此将主存中的数据读入CPU B Cache中。在3时间时，CPU A向X单元写入0，假设写策略为写直达法，由于主存是共享的，CPU A将更新其Cache的内容为0，且将主存的X单元的内容更新为0。但是CPU B Cache中缓存的X单元的值仍为旧值，这就导致不一致的情况出现了。

为实现Cache的一致性，针对两种体系结构，可以采用两种不同的方法保证Cache的一致性。

3 监听一致性协议

针对第一种体系结构，即集中式共享存储器体系结构，来说明这种协议，并且假设Cache的写命中策略是写回法。

所谓监听，就是每个CPU都有一个Cache控制器，随时对通过总线中的数据进行判断，判断自己这是否有总线上请求的数据块。

我们讨论两种保持一致性的方式：写作废方式、写更新方式。

3.1 写作废方式

这种方式的基本思想是，当某个CPU出现写请求时，将其它的副本直接作废。其详细过程如下，

为了更好地讨论协议，我们将每个CPU的Cache的每个块都归结为下述的三种状态：

未缓冲（U）：所有的Cache中都无此块。专有态（E）：即该块仅仅在该Cache中有副本，且该块的内容与主存中的不一致。共享态（S）：即该块在一个或多个Cache中有副本，且内容与主存中一致。

3.1.1 具体流程

假设CPU 1有一个读请求， 若命中，则Cache 1直接将值返回给CPU 1。若未命中，就把读失效信号、以及相应地址放到总线上，其他的的CPU一直监听着总线，CPU 1进行读取主存的操作， 若该地址不能在其他CPU的Cache中被匹配，则结果就是CPU 1能正常从主存中读取出数据，且将该块设置为共享态。若该地址在CPU 2中被匹配上，且该块在CPU 2的Cache中的状态是共享态，那么CPU 2将不会采取任何操作。若该地址在CPU 2中被匹配上，且该块在CPU 2的Cache中的状态是专有态，那么CPU 2将向CPU 1提供该块，并停止CPU 1访问主存的操作。同时，该块将被写回至主存，CPU 1 Cache以及CPU 2 Cache中该块的状态修改为共享态。 假设CPU 1有一个写请求， 若写命中， 若该块在CPU 1 Cache中的状态是共享态，那么CPU 1将该块状态改为专有态，且向总线发送写作废信号，使得别的CPU将其Cache中相应的共享块（若存在）设置为无效。若该块在CPU 1 Cache中的状态是专有态，那么CPU 1进行正常的写数据的操作，即将新数据写入该块。 若写缺失， 那么CPU 1将该块状态改为专有态，并且正常写入数据，且向总线发送写作废信号，使得别的CPU将其Cache中相应的块（若存在）设置为无效。

3.1.2 状态转换图

其状态转换图如下，

3.2 写更新方式

这种方式的思想是，当某个CPU出现写请求时，将其它的副本一并更新。

具体说来，就是当一个CPU写某数据时，若该块是共享块，通过广播使其他所有Cache中有对应副本的块都一并更新。

这种方式很需要总线和存储器的带宽，因为要经常性地广播修改的数据，这使得这种方法被采用地越来越少。

4 目录一致性协议

目录是一种数据结构，记录了Cache块的一些状态：

Cache块的访问状态，未缓冲、共享态、专有态。Cache块的位向量，用于记录该Cache块的共享情况，即位向量的每一位代表一个处理器（CPU），若其为1，则表明在该位置的CPU有该Cache块的副本。

同样地，目录一致性协议也有两种实现方式，即写作废方法、写更新方法，在这里，我们同样假设Cache的写策略是写回法。

此时，Cache每个块的状态转换模式和监听一致性协议是一样的。

基于目录的一致性协议要避免不必要的性能损失，比如避免广播，而是根据位向量，找到对应的CPU向其发送信息。

总结一下目录一致性协议的基本点：

每个CPU节点增加了目录存储器，用于存放目录。存储器的的每一块在目录中都有对应的一项。每一个目录项的组成成分是：访问状态、位向量。状态描述该目录项对应的存储块的访问状态：未缓冲、共享态、专有态。位向量的每一位对应于一个CPU的Cache，用于指出该CPU的Cache有无该块的缓存。当处理器对某一块进行写操作时，需要根据位向量，**”通知“**对应的CPU进行作废或更新操作。

基于目录的一致性协议配合分布式共享存储器体系结构，能很好地支持系统的可扩展性，然而，这种多处理机的实现模式，需要带宽较大的网络来实现，普通的以太网是远远达不到带宽要求的。