CPU多级缓存-缓存一致性-蒲公英云

前言：为什么需要CPU cache？

因为：由于cpu频率太快，在处理器时钟周期内，cpu常常要等待主存，浪费资源，所以cache的出现，主要解决缓解cpu和主存之间速度不匹配的问题。

1.首先介绍一下操作系统高速缓存的配置

数据的读取和存储都经过高速缓存，CPU核心与高速缓存有一条特殊的快速通道；主存与高速缓存都连在系统总线上（BUS）这条总线同时还用于其他组件的通信。

由于系统变得复杂，高速缓存与主存之间的加入了另一级缓存，新加入的这级缓存比第一缓存更大，但是更慢，而且经济上不合适，所以有了二级缓存，甚至有些系统已经拥有了三级缓存，于是就演变成了多级缓存，如下图：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MzI3OTgxMTM_size_16_color_FFFFFF_t_70

CPU cache的局部性原理：

1.时间局部性：如果某个数据被访问，那么在不久的将来它很可能再次被访问
2.空间局部性：如果某个数据被访问，那么与它相邻的数据很快也可能被访问

3.多级缓存-缓存一致性

多级缓存-缓存一致性（MESI），MESI是一个协议，这协议用于保证多个CPU cache之间缓存共享数据的一致性。它定义了CacheLine的四种数据状态，而CPU对cache的四种操作可能会产生不一致的状态。因此缓存控制器监听到本地操作与远程操作的时候需要对地址一致的CacheLine状态做出一定的修改，从而保证数据在多个cache之间流转的一致性.

CacheLine的四种状态如下：

M: Modified 修改，指的是该缓存行只被缓存在该CPU的缓存中，并且是被修改过的，因此他与主存中的数据是不一致的，该缓存行中的数据需要在未来的某个时间点（允许其他CPU读取主存相应中的内容之前）写回主存，而当数据被写回主存之后，该缓存行的状态会变成E（独享）
E：Exclusive 独享缓存行只被缓存在该CPU的缓存中，是未被修改过的，与主存的数据是一致的，可以在任何时刻当有其他CPU读取该内存时，变成S（共享）状态，同样的当CPU修改该缓存行的内容时，会变成M（被修改）的状态
S：Share 共享，当前CPU和其他CPU中都有共同数据，并且和主存中的数据一致；意味着该缓存行可能会被多个CPU进行缓存，并且各缓存中的数据与主存数据是一致的，当有一个CPU修改该缓存行时，在其他CPU中的该缓存行是可以被作废的，变成I(无效的) 状态
I：Invalid 无效的，代表这个缓存是无效的，可能是有其他CPU修改了该缓存行；数据应该从主存中获取，其他CPU中可能有数据也可能无数据，当前CPU中的数据和主存被认为是不一致的；对于invalid而言，在MESI协议中采取的是写失效（write invalidate）。

MESI示意图：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MzI3OTgxMTM_size_16_color_FFFFFF_t_70 1

CacheLine有四种数据状态（MESI），而引起数据状态转换的CPU cache操作也有四种：

local read：读本地缓存中的数据
local write：将数据写到本地缓存里面
remote read：将内（主）存中的数据读取到缓存中来
remote write：将缓存中的数据写回到主存里面去

因此要完整的理解MESI这个协议，就需要把这16种状态转换的情况理解清楚，状态之间的相互转换关系，如图表示：

在一个典型的多核系统中，每一个核都会有自己的缓存来共享主存总线，每个相应的CPU会发出读写（I/O）请求，而缓存的目的是为了减少CPU读写共享主存的次数。一个缓存除了在 Invalid 状态之外，都可以满足CPU的读请求。

一个写请求只有在该缓存行是M状态，或者E状态的时候才能够被执行。如果当前状态是处在S状态的时候，它必须先将缓存中的该缓存行变成无效的（Invalid）状态，这个操作通常作用于广播的方式来完成。这个时候它既不允许不同的CPU同时修改同一个缓存行，即使修改该缓存行不同位置的数据也是不允许的，这里主要解决的是缓存一致性的问题。一个处于M状态的缓存行它必须时刻监听所有试图读该缓存行相对就主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S状态之前被延迟执行。

一个处于S状态的缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）。

一个处于E状态的缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S状态。

因此，对于M和E两种状态而言总是精确的，他们在和该缓存行的真正状态是一致的。而S状态可能是非一致的，如果一个缓存将处于S状态的缓存行作废了，而另一个缓存实际上可能已经独享了该缓存行，但是该缓存却不会将该缓存行升迁为E状态，这是因为其它缓存不会广播他们作废掉该缓存行的通知，同样由于缓存并没有保存该缓存行的copy的数量，因此（即使有这种通知）也没有办法确定自己是否已经独享了该缓存行。

从上面的意义看来E状态是一种投机性的优化：如果一个CPU想修改一个处于S状态的缓存行，总线事务需要将所有该缓存行的copy变成invalid状态，而修改E状态的缓存不需要使用总线事务。