Java并发——缓存一致性

ゝ一世哀愁。 2022-04-14 03:51 206阅读 0赞

## I. CPU多级缓存 ##

CPU的时钟频率非常的快，跑起来的速度远远超过了内存、硬盘。《码农翻身》形象的比喻CPU为阿甘，跑的速度是内存的100倍，硬盘的1000多万倍。如果直接靠CPU直接和内存打交道，那么CPU要等待太久，浪费资源。

我们平时编写的程序中，包含着很多连续创建的数组、对象，各种循环、递归、调用同一函数等，其实本质上符合了**局部性原理**。**局部性原理**具体是指在CPU访问存储设备时，无论是存取数据还是存取指令，都趋于聚集在一片连续的区域中，主要包含时间与空间上的局部性。

*  **时间局部性 (Temporal Locality)**：如果一个数据被访问，那么在近期它很可能还会被再次访问。
 *  **空间局部性 (Spatial Locality)**：如果一个数据被访问，那么与它相邻的数据也很快会被访问。

有了这样的特性，就可以在CPU和内存之间添加高速缓存存储CPU经常访问的数据，如下图所示，缓解CPU和内存速度严重差异的问题。

![高速缓存][20181124105403147.png]

CPU和cache之间进行数据/指令存取，而内存(主存)和高速缓存则通过系统总线来实现通信。程序员编写的程序以及数据被加载到内存中后，随后被加载到高速缓存，CPU执行完指令处理完数据将结果写回高速缓存中，最后高速缓存再写回内存。

然而，由于CPU的运算速度不断提升，很快超越了一级缓存的数据 I\\O 能力，CPU厂商们又开始引入了多级的缓存结构。多核的CPU至少拥有着不止一个一级缓存，当高速缓存中拷贝了内存中同一个数据多个副本时，CPU操作的是每一个副本，而如何保证副本与副本之间，以及副本与主存的数据一致呢？

![多级缓存][20181124105417698.png]

主要利用的是**缓存一致性**的原则。

## II. 缓存一致性 ##

### MESI协议中的缓存状态 ###

<table> 
 <thead> 
 <tr> 
 <th>状态</th> 
 <th>含义</th> 
 <th>监听任务</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>M 被修改 Modified</td> 
 <td>因为缓存行刚被修改，数据应是独一无二的，与主存中的数据不一致，与其他CPU的缓存中对应数据也不相同。但是一定会在将来某个时间点写回主存中，这个时间点一定是在其他CPU读取自己的(主存相应的)缓存之前。</td> 
 <td>被修改的缓存行必须时刻监听所有想读该缓存行对应的主存/其他CPU缓存的操作，因为要确保在CPU读取操作之前把被修改的缓存行写回主存并将状态变为 S。</td> 
 </tr> 
 <tr> 
 <td>E 独享的 Exclusive</td> 
 <td>被修改状态的缓存行要将数据写回主存，此时可以认为是独享的状态。只有自己的缓存和主存中数据一致，其他CPU对应的缓存行还没有更新。但是一定会在将来其他CPU读取对应的缓存行之前变为共享状态。</td> 
 <td>独享的缓存行也必须监听其他CPU缓存读取主存中对应缓存行的操作，一旦有了这种操作，该缓存行需要变成 S 状态。</td> 
 </tr> 
 <tr> 
 <td>S 共享的 Shared</td> 
 <td>该状态意味该缓存行可能被多个CPU缓存，并且各个缓存中的数据与主存中的数据是一致的。当有一个CPU修改了该缓存行中的数据，该缓存行变为被修改状态，其他CPU中对应的缓存作废，变为无效状态 I。</td> 
 <td>对于该缓存行来说，要监听其他缓存使该缓存行无效。</td> 
 </tr> 
 <tr> 
 <td>I 无效的 Invalid</td> 
 <td>缓存行作废，无效。</td> 
 <td>\</td> 
 </tr> 
 </tbody> 
</table>

### 缓存行状态变化 ###

<table> 
 <tbody> 
 <tr> 
 <td>本地缓存当前状态</td> 
 <td>事件</td> 
 <td>行为</td> 
 <td>本地缓存状态变化</td> 
 <td>触发缓存行状态变化</td> 
 <td>其他缓存行状态变化</td> 
 </tr> 
 <tr> 
 <td>M</td> 
 <td align="left">本地缓存读取本地缓存数据</td> 
 <td align="left">从本地缓存读取数据，状态不变。触发缓存就是本身。其他缓存则因为本地缓存是M，早就是I了。</td> 
 <td>M-&gt;M</td> 
 <td>M-&gt;M</td> 
 <td>I</td> 
 </tr> 
 <tr> 
 <td align="left">本地缓存写入本地缓存数据</td> 
 <td align="left">本地缓存行状态为M，继续修改数据，状态还是M。触发缓存就是本身。其他缓存则因为本地缓存是M，早就是I了。</td> 
 <td>M-&gt;M</td> 
 <td>M-&gt;M</td> 
 <td>I</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存读取本地缓存对应数据</td> 
 <td align="left">触发缓存行和其他缓存行状态都为I，触发缓存行想要读取对应数据，必然得从主存走。本地缓存行中数据将回写到主存，本地状态变为E。等到触发缓存从主存中获取到数据，所有缓存行都同步，状态变为S。</td> 
 <td>M-&gt;E-&gt;S</td> 
 <td>I-&gt;S</td> 
 <td>I-&gt;S</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存写入本地缓存对应数据</td> 
 <td align="left">触发缓存行想要先写对应缓存，发现本地缓存数据还没同步，所有先走触发缓存读取本地缓存对应数据的流程。由于触发缓存要写入数据，所以本地缓存和其他缓存会变为I,此时触发缓存行状态相当于E，等触发缓存写入成功最后会变为M，。</td> 
 <td>M-&gt;E-&gt;S-&gt;I</td> 
 <td>I-&gt;S-&gt;E-&gt;M</td> 
 <td>I-&gt;S-&gt;I</td> 
 </tr> 
 <tr> 
 <td>E</td> 
 <td align="left">本地缓存读取本地缓存数据</td> 
 <td align="left">从本地缓存读取数据，状态不变。触发缓存就是本身。其他缓存则因为本地缓存是E，早就是I了。</td> 
 <td>E-&gt;E</td> 
 <td>E-&gt;E</td> 
 <td>I</td> 
 </tr> 
 <tr> 
 <td align="left">本地缓存写入本地缓存数据</td> 
 <td align="left">本地缓存行已经回写到主存，又继续修改，状态又变为M，其他缓存行继续I。触发缓存就是本身。</td> 
 <td>E-&gt;M</td> 
 <td>E-&gt;M</td> 
 <td>I</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存读取本地缓存对应数据</td> 
 <td align="left">本地缓存行已经回写到主存，触发缓存读取数据之前需要先进行本地缓存行数据的同步，所有缓存行数据变为S。同步完成，触发缓存行也就正好读完。</td> 
 <td>E-&gt;S</td> 
 <td>I-&gt;S</td> 
 <td>I-&gt;S</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存写入本地缓存对应数据</td> 
 <td align="left">触发缓存行想要写对应数据，先经历触发缓存读取本地缓存对应数据的过程。当共享完成，触发缓存行对数据进行更新，其他缓存行都变为I，随后自身变为E再变为M。</td> 
 <td>E-&gt;S-&gt;I</td> 
 <td>I-&gt;S-&gt;E-&gt;M</td> 
 <td>I-&gt;S-&gt;I</td> 
 </tr> 
 <tr> 
 <td>S</td> 
 <td align="left">本地缓存读取本地缓存数据</td> 
 <td align="left">共享状态读取不影响。</td> 
 <td>S</td> 
 <td>S</td> 
 <td>S</td> 
 </tr> 
 <tr> 
 <td align="left">本地缓存写入本地缓存数据</td> 
 <td align="left">共享状态下，本地缓存进行修改，其他缓存行将先变成I，此时相当于本地缓存行为E，修改后再变成M。触发缓存就是本地缓存。</td> 
 <td>S-&gt;E-&gt;M</td> 
 <td>S-&gt;E-&gt;M</td> 
 <td>S-&gt;I</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存读取本地缓存对应数据</td> 
 <td align="left">共享状态读取不影响。</td> 
 <td>S</td> 
 <td>S</td> 
 <td>S</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存写入本地缓存对应数据</td> 
 <td align="left">共享状态下，触发缓存想要修改，则本地缓存和其他缓存先变为I，触发缓存则变成E。修改完成后，触发缓存继续变成M。</td> 
 <td>S-&gt;I</td> 
 <td>S-&gt;E-&gt;M</td> 
 <td>S-&gt;I</td> 
 </tr> 
 <tr> 
 <td>I</td> 
 <td align="left">本地缓存读取本地缓存数据</td> 
 <td align="left">1. 如果其他缓存没有对应数据，状态为I，本地缓存从主存读取数据，缓存行变成E； 2. 如果其他缓存有对应数据，且状态为M，则先将数据更新到主存，本地缓存再从主存中读取，两个缓存对应的缓存行都变为S； 3. 如果其他缓存有对应数据，且状态为S/E，意味着主存已经更新，可以直接读取，这时两个缓存对应的缓存行都变为S。</td> 
 <td>I-&gt;E I-&gt;S I-&gt;S</td> 
 <td>I-&gt;E I-&gt;S I-&gt;S</td> 
 <td>I-&gt;I M-&gt;E-&gt;S E-&gt;S/S-&gt;S</td> 
 </tr> 
 <tr> 
 <td align="left">本地缓存写入本地缓存数据</td> 
 <td align="left">1. 如果其他缓存没有对应数据，一开始所有缓存行都为无效，所以需要先从主存中取数据同步，写入所有缓存，缓存行状态变为E。随后进行本地缓存更新，状态变为M； 2. 如果其他缓存有数据但是缓存行状态为E，本地缓存行为无效，所以需要先从主存中取数据同步，写入本地缓存，缓存行状态变为E。随后进行本地缓存更新，状态变为M； 3. 如果其他缓存中有对应数据，且状态为M，则先将其他缓存中的数据更新到主存，本地缓存再从主存中读取，所有缓存行都为S。随后进行本地缓存更新，本地缓存行状态变为M，其他缓存变为I。</td> 
 <td>I-&gt;S-&gt;E-&gt;I I-&gt;S-&gt;E-&gt;I I-&gt;S-&gt;E-&gt;I</td> 
 <td>I-&gt;S-&gt;E-&gt;I I-&gt;S-&gt;E-&gt;I I-&gt;S-&gt;E-&gt;I</td> 
 <td>I-&gt;S-&gt;I E-&gt;S-&gt;I M-&gt;E-&gt;S-&gt;I</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存读取本地缓存对应数据</td> 
 <td align="left">既然是本地缓存行是I，触发缓存行的操作与它无关。</td> 
 <td>I</td> 
 <td>\</td> 
 <td>\</td> 
 </tr> 
 <tr> 
 <td align="left">触发缓存写入本地缓存对应数据</td> 
 <td align="left">既然是本地缓存行是I，触发缓存行的操作与它无关。</td> 
 <td>I</td> 
 <td>\</td> 
 <td>\</td> 
 </tr> 
 </tbody> 
</table>

## 参考文章 ##

*  [MESI–CPU缓存一致性协议][MESI_CPU]
 *  [CPU缓存一致性协议MESI][CPU_MESI]

[20181124105403147.png]: /images/20220414/787b8494c132410c9b5ecc9c8a97f37f.png
[20181124105417698.png]: /images/20220414/0bf830cb691b4849ae4739f319fe4150.png
[MESI_CPU]: https://www.cnblogs.com/z00377750/p/9180644.html
[CPU_MESI]: https://www.cnblogs.com/yanlong300/p/8986041.html