主要介绍CPU和缓存之间的交互所遵循的协议。

1 CPU的存储层次结构

参考《深入理解计算机系统》。 早期计算机系统的存储器层次结构只有三层：CPU寄存器，主DRAM存储器和磁盘存储设备。不过，随着CPU和主存之间逐渐增大的差距，系统设计者被迫在CPU寄存器和主存之间插入缓存。

1.1 CPU访问主存

下图是一个典型的桌面系统结构，主要部件是CPU芯片，I/O桥接器芯片组（其中包括存储控制器），以及组成主存的DRAM存储器模块。I/O桥接器将系统总线的电信号翻译成存储器总线的电信号。 数据流通过总线（bus）的共享电路在处理器和DRAM主存之间来来回回。每次CPU和主存之间的数据传输都是通过一系列步骤来完成的，这些步骤称为总线事务（bus transaction）。读事务（read transaction）从主存传送数据到CPU，写事务（write transaction）从CPU传送数据到主存。

1.1.1 读事务

mov A %eax，将地址A的内容加载到寄存器%eax的过程如下图所示。

1.1.2 写事务

mov %eax A，将寄存器%eax的内容写入到地址A的过程如下图。

1.2 存储器层次结构

在如上图所示的存储器山结构中，从高层往底层走，存储设备变得更慢，更便宜，更大。

• 在最高层（L0）是少量的快速CPU寄存器，CPU可以在一个时钟周期内访问它们。
• 接下来是一个或多个小型或中型的基于SRAM的高速缓存存储器，可以在几个时钟周期内访问它们。
• 然后是一个大的基于DRAM的主存，可以在几十或几百个时钟周期内访问它们。
• 接下来是慢速但容量很大的本地磁盘。
• 最后有些系统甚至包括了一层附加的远程服务器上的磁盘，要通过网络来访问它们。例如像AFS和NFS这样的分布式文件系统，允许程序访问存储在远程网络服务器上的文件。

1.3 存储器层次结构中的缓存

在存储器层次结构中，对于每个k，位于k层的更快更小的存储设备作为k+1层的更大更慢的存储设备的缓存。 下图展示了存储器层次结构中缓存的一般性概念。第k+1层的存储器被划分为连续的数据对象组块（chunks），称为块（blocks）。每个块都有一个唯一的地址或者名字以区别于其它的块。 在任何时刻，第k层的缓存包含第k+1层块的一个子集的拷贝。数据总以块大小为传送单元（transfer unit）在第k层和第k+1层之间来回拷贝。

1.3.1 缓存的读

缓存命中

当程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d。如果d刚好缓存在第k层中，那么就是我们所说的缓存命中（cache hit）。

缓存不命中

如果第k层中没有缓存数据d，那么就是我们所说的缓存不命中（cache miss）。

缓存不命中的种类

强制性不命中或冷不命中：如果第k层的缓存是空的，即冷缓存，此时对任何数据的访问都不会命中。（冷不命中通常是短暂事件，不会在稳定状态中出现） 冲突不命中：由限制性放置策略所引起的一种不命中，缓存足够大，能够保存被引用的数据对象，但是因为这些对象会映射到同一缓存块，缓存会一直不命中。例如：在图6.22中，如果程序请求块0，块8，然后块0，然后块4，依次类推，在第k层缓存中，对这两个块的引用都不会命中，即使这个缓存可以容纳4个块。

限制性放置策略：当发生不命中的时候，第k层的缓存就必须执行某种替换策略，确定把它从第k+1层中取出的块放在第k层的哪个位置。（如果随意放置，定位就会比较困难，比如如果我想查找缓存块0中数据，那么我必须得遍历整个k层缓存，才能发现缓存不命中。）因此硬件缓存通常使用的是更严格的放置策略，这个策略将第k+1层的某个块限制放置在第k层块的一个小子集中。在图6.22中，第k+1层的块必须放置在第k层的块（i mod 4）中。例如，第k+1层的块0、4、8、12会映射到第k层的块0，块1、5、9、13会映射到块1，以此类推。

容量不命中：如果一个嵌套循环可能会反复地访问同一个数组元素。这个块地集合被称为这个阶段的工作集（working set）。当工作集的大小超过缓存的大小时，缓存会经历容量不命中。

1.3.2 高速缓存中的写问题

写的情况也分两种情况：

1. 写命中（write hit）： CPU写一个已经缓存的字w，在高速缓存更新了它的w的拷贝之后，怎么更新w在存储器中的拷贝呢？有一下两种方式：
   • 直写（write-through） 立即将w的高速缓存块写入到存储器中。缺点：每条存储指令都会引起总线的上的一个写事务。
   • 写回（write-back） 尽可能地推迟存储器更新，只有当替换算法要驱逐已更新的块时，才把它写到存储器。
2. 写不命中： 写分配方法（write-alloc）：加载相应的存储器块到高速缓存，然后更新这个高速缓存。 非写分配（not-write-alloc）：避开高速缓存，直接把这个字写到存储器中。 write-through通常和not-write-alloc相配合，而write-back和write-alloc相配合

2 缓存一致性协议

MESI（缓存一致性协议）

2.1 缓存一致

如图，在SMP架构中，CPU每个核都有属于自己的高速缓存L1和L2，但是共享同一个L3高速缓存。当两个CPU核心操作同一个数据对象，并采用的是写回（write-back)的方式，这种情况下，其缓存中的数据可能出现不一致性。因此出现了缓存一致性的协议，该协议 保证多核CPU的情况下，保持缓存内部数据的一致性。

2.2 MESI缓存一致性协议

缓存一致性协议用于管理多个 CPU cache 之间数据的一致性，这些协议十分复杂，在这里我们仅讨论 MESI 协议的四种状态。

缓存行的四个状态：

MESI中每个缓存行都有四个状态，分别是E（exclusive）、M（modified）、S（shared）、I（invalid）。下面我们介绍一下这四个状态分别代表什么意思。

M：代表该缓存行中的内容被修改了，并且该缓存行只被缓存在该CPU中。这个状态的缓存行中的数据和内存中的不一样，在未来的某个时刻它会被写入到内存中（当其他CPU要读取该缓存行的内容时。或者其他CPU要修改该缓存对应的内存中的内容时）。

E：E代表该缓存行对应内存中的内容只被该CPU缓存，其他CPU没有缓存该缓存对应内存行中的内容。这个状态的缓存行中的内容和内存中的内容一致。该缓存可以在任何其他CPU读取该缓存对应内存中的内容时变成S状态。或者本地处理器写该缓存就会变成M状态。

S:该状态意味着数据不止存在本地CPU缓存中，还存在别的CPU的缓存中。这个状态的数据和内存中的数据是一致的。当有一个CPU修改该缓存行对应的内存的内容时会使该缓存行变成 I 状态。

I：代表该缓存行中的内容时无效的。

EMSI状态转移图：

local read和local write分别代表本地CPU读写。remote read和remote write分别代表其他CPU读写。