并发基础（二）：CPU多级缓存与缓存一致性

「尺有所短，寸有所长；不忘初心，方得始终」。

在上一篇文章《并发基础（一）：线程安全》中提到了为了解决CPU处理器与内存之间的读写效率的问题，在CPU和内存之间加入了高速缓存。那么这个缓存是如何解决它们之间的问题的呢？又带来了什么问题呢？

一、Cache的作用

「缓存的作用就是为了解决CUP与内存之间的效率不匹配问题，提高CPU利用率的，(cpu ->cache->memory)」。

类似日常生活中的超市，超市从工厂把商品存储起来，人们可以直接购买，省掉人们从工厂购买所需要的时间开销。

随着现代半导体工艺的发展，「cpu cache已经发展到了三级缓存结构」，基本上现在买的个人电脑都是L3结构。

二、Cache的工作原理

「CPU cache既然是缓存，那么容量肯定是远远小于主存的」，因此肯定会出现缓存未命中的情况，基于此cache的意义在哪里呢？

缓存的容量要是能达到内存一样，那还要内存干啥？价格，技术都是限制缓存容量的条件

之前讲mysql的文章中，有一篇《MySQL十六：36张图理解Buffer Pool》在讲预读的时候，提到一个概念——局部性原理。「实际cache 的工作原理是也是基于【局部性原理】，它包含两个方面」：

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

也就是说：「CPU cache在一定程度上可以理解为预读，将数据从内存读取到缓存中，提供给执行引擎使用」。

三、Cache的结构

随着现代半导体工艺的发展，CPU也从最开始的单核发展到现在的多核，多核CUP的结构在单核CPU基础上也做了升级隔离

「单核CPU cache结构」

在单核CPU结构中，为了防止CPU指令流水中循环冲突，「一级缓存L1分成了指令（L1P）和数据（L1D）两部分，而二级缓存L2则是指令和数据共存」。示意图如下：
「多核CPU cache结构」

多核CPU的结构相比单核CPU，其结构多了三级缓存L3，「在多核CPU的结构中，L1和L2是CPU私有的，L3则是所有CPU核心共享的」。示意图如下：
「CPU读取数据的过程」

「cache中保存着cpu刚用过的数据或者是循环使用的数据，从cache中读取数据就会很快，减少了cpu等待的时间，提高了系统的性能」。

从上图可看出，内存中读取数据到缓存中的时候，需要经过总线，因此我们可以「通过缓存一致性(MESI)或者锁住总线的方式来解决缓存不一的问题」。

四、缓存一致性

「在多核CPU中，内存中的数据会在多个核心中存在数据副本，某一个核心发生修改操作，其他核心无法立即知晓，就产生了数据不一致的问题。而一致性协议则是用于保证多个CPU cache之间缓存共享数据的一致」。

常见的缓存一致性协议有如MSI、MESI、MOSI、MOESI、MERSI、MESIF、write-once、Synapse、Berkeley、Firefly和Dragon协议等，其中最经典的MESI协议。

「缓存不一致」

如上图，在共享内存多处理器系统中，每个处理器都有一个单独的缓存内存，共享数据可能有多个副本，「当两个CPU核心读取了数据副本后，当某个CPU修改了数据并且更新了内存资源的缓存时，可能会出现数据不一致的问题」。

「缓存一致性」

在共享内存多处理器系统中，每个处理器都有一个单独的缓存内存，共享数据可能有多个副本：「当数据的一个副本发生更改时，其他副本必须反映该更改。缓存一致性是确保共享操作数(数据)值的变化能够及时地在整个系统中传播的过程」。也就是【写传播】。

4.1 cache的写方式

在《计算机组成原理》一书中有提到cache的写操作方式包含write through和write back两种方式：

「Write-through（直写）」：每次CPU修改了cache中的内容，立即更新到内存，使cache和memory的数据保持一致。

也就意味着每次CPU写内存共享数据，都会导致总线事务，因此这种方式常常会引起总线事务的竞争，高一致性，但是效率非常低
「Write-back（回写）」：每次CPU修改了cache中的数据，不会立即更新到内存，而是等到cache line在某一个必须或合适的时机才会更新到内存中

「无论是直写通还是回写，在多核环境下都需要处理缓存cache一致性问题。为了保证缓存一致性，处理器还提供了写失效（write invalidate）和写更新（write update）两个操作来保证cache一致性」。

「写失效（write invalidate）」：当一个CPU修改了数据，如果其他CPU有该数据，则通知其为无效；
「写更新（write update）」：当一个CPU修改了数据，如果其他CPU有该数据，则通知其跟新数据，（写更新

会导致大量的更新操作）。

MESI协议就是使用的写失效（MESI中的I：ivalid），MESU协议使用的写更新

4.2 cache line

在write back（写回）中，CPU修改了数据后，会等到cache line在某一个必须或合适的时机才会更新到内存中，那cache line又是什么呢？

「cache line是cache与内存数据交换的最小单位，根据操作系统一般是32byte或64byte」。其结构如下

「cache line可分为状态，地址，数据三个部分，在MESI协议中，状态分为四种：M、E、S、I，地址则是cache line中映射的内存地址，数据则是从内存中读取的数据」。

「cache line工作方式」

当CPU从cache中读取数据的时候，会比较地址是否相同，如果相同则检查cache line的状态，再决定该数据是否有效，无效则从主存中获取数据，或者根据一致性协议发生一次cache-to–chache的数据推送。
「cache line工作效率」

当CPU能够从cache中拿到有效数据的时候，消耗几个CPU cycle（CPU指令周期），如果缓存未命中，则会消耗几十上百个CPU cycle。

五、MESI

5.1 MESI是什么

「MESI为了保证多个CPU缓存中共享数据的一致性，定义了cache line的四种状态，而CPU对cache line的四种操作可能会产生不一致的状态，因此缓存控制器监听到本地操作和远程操作的时候，需要对地址一致的cache line 状态进行一致性修改，从而保证数据在多个缓存之间保持一致性。」。

MESI是指4个状态的首字母(M:modified E:Exclusive S:shared I:invalid) ，每个cache line有4个状态，可以用2个bit表示：

状态	描述	监听任务
M(Modified)修改	数据有效，被修改了，和内存中的数据不一致，数据只存在于本Cache中。	缓存行必须监听所有视图中【读该缓存行所对应的主存】操作，这些操作必须在将【该缓存行写回主存并将状态改为S状态】之后执行
E(Exclusive)：独享	数据有效，数据和内存中的数据一致，数据只存在于本Cache中。	缓存行必须监听其他缓存【读取该缓存行对应的主存】操作，一旦有这种操作，该缓存行需要变成S状态
S(Shared)：共享	数据有效，数据和内存中的数据一致，并且数据存在于很多Cache中。	缓存行必须监听其他缓存使该缓存行无效的请求
I(Invalid)：无效	该缓存行无效

「E(Exclusive)」

只有Core 0访问变量x，它的Cache line状态为E(Exclusive)。
「S(Shared)」

3个Core都访问变量x，它们对应的Cache line为S(Shared)状态。
「M(Modified) 和I(Invalid)」

Core 0修改了x的值之后，这个Cache line变成了M(Modified)状态，其他Core对应的Cache line变成了I(Invalid)状态。