共计 4120 个字符，预计需要花费 11 分钟才能阅读完成。
起源：https://zhuanlan.zhihu.com/p/…
能够轻易到网上查一查，各大互联网公司口试面试特地喜爱考一道算法题，即 LRU 缓存机制，又棘手查了一下 LRU 缓存机制最近有哪些企业喜爱考查，超级大热门！
明天给大家分享一篇对于 Cache 的硬核的技术文，基本上对于 Cache 的所有知识点都能够在这篇文章里看到。
对于 Cache 这方面内容图比拟多，不想本人画了，所以图都来自《Computer Architecture : A Quantitative Approach》。
这是一本体系架构方面的神书，举荐大家看一下。
本文次要内容如下，根本波及了 Cache 的概念，工作原理，以及放弃一致性的入门内容。
为什么须要 Cache
1.1 为什么须要 Cache
咱们首先从一张图来开始讲为什么须要 Cache。
上图是 CPU 性能和 Memory 存储器拜访性能的倒退。
咱们能够看到，随着工艺和设计的演进，CPU 计算性能其实产生了天翻地覆的变动，然而 DRAM 存储性能的倒退没有那么快。
所以造成了一个问题，存储限度了计算的倒退。
容量与速度不可兼得。
如何解决这个问题呢？能够从计算拜访数据的法则动手。
咱们轻易贴段代码:
for (j = 0; j < 100; j = j + 1)
for(i = 0; i < 5000; i = i + 1)
x[i][j] = 2 * x[i][j];能够看到，因为大量循环的存在，咱们拜访的数据其实在内存中的地位是相近的。
换句业余点的话说，咱们拜访的数据有局部性。
咱们只须要将这些数据放入一个小而快的存储中，这样就能够快速访问相干数据了。
总结起来，Cache 是为了给 CPU 提供高速存储拜访，利用数据局部性而设计的小存储单元。
1.2 理论零碎中的 Cache
咱们展现一下理论零碎中的 Cache。
如上图所示，整个零碎的存储架构包含了 CPU 的寄存器，L1/L2/L3 CACHE，DRAM 和硬盘。
数据拜访时先找寄存器，寄存器里没有找 L1 Cache, L1 Cache 里没有找 L2 Cache 顺次类推，最初找到硬盘中。
同时，咱们能够看到，速度与存储容量的折衷关系。容量越小，访问速度越快！
其中，一个概念须要搞清楚。
CPU 和 Cache 是 word 传输的，而 Cache 到主存是以块传输的，一块大概 64Byte。
现有 SOC 中的 Cache 个别组成如下。
1.3 Cache 的分类
Cache 依照不同规范分类能够分为若干类。
- 依照数据类型划分：I-Cache 与 D -Cache。其中 I -Cache 负责搁置指令，D-Cache 负责形式数据。两者最大的不同是 D -Cache 里的数据能够写回，I-Cache 是只读的。
- 依照大小划分：分为 small Cache 和 large Cache。没路组（后文组相连介绍）<4KB 叫 small Cache, 多用于 L1 Cache, 大于 4KB 叫 large Cache。多用于 L2 及其他 Cache.
- 依照地位划分：Inner Cache 和 Outer Cache。个别独属于 CPU 微架构的叫 Inner Cache, 例如上图的 L1 L2 CACHE。不属于 CPU 微架构的叫 outer Cache.
- 依照数据关系划分：Inclusive/exclusive Cache: 上级 Cache 蕴含下级的数据叫 inclusive Cache。不蕴含叫 exclusive Cache。举个例子，L3 Cache 里有 L2 Cache 的数据，则 L2 Cache 叫 exclusive Cache。
Cache 的工作原理
要讲清楚 Cache 的工作原理，须要答复 4 个问题：
- 数据如何搁置
- 数据如何查问
- 数据如何被替换
- 如果产生了写操作，Cache 如何解决
2.1 数据如何搁置
这个问题也好解决。咱们举个简略的栗子来阐明问题。
假如咱们主存中有 32 个块，而咱们的 Cache 一共有 8 个 Cache 行 (一个 Cache 行放一行数据）。
假如咱们要把主存中的块 12 放到 Cache 里。
那么应该放到 Cache 里什么地位呢？
三种办法：
- 全相连（Fully associative）。能够放在 Cache 的任何地位。
- 间接映射（Direct mapped）。只容许放在 Cache 的某一行。比方 12 mod 8
- 组相连（set associative）。能够放在 Cache 的某几行。例如 2 路组相连，一共有 4 组，所以能够放在 0,1 地位中的一个。
能够看到，全相连和间接映射是 Cache 组相连的两种极其状况。
不同的搁置形式次要影响有两点：
1、组相连组数越大，比拟电路就越大，但 Cache 利用率更高，Cache miss 产生的概率小。
2、组相连数目变小，Cache 常常产生替换，然而比拟电路比拟小。
这也好了解，内存中的块在 Cache 中可搁置的地位多，天然找起来就麻烦。
2.2 如何在 Cache 中找数据
其实找数据就是一个比对过程，如下图所示。
咱们地址都以 Byte 为单位的。
但主存于 Cache 之间的数据交换单位都是块（block，古代 Cache 个别一个 block 大概 64Byte)。所以地址对最初几位是 block offset。
因为咱们采纳了组相连，则还有几个比特代表的是存储到了哪个组。
组内放着若干数据，咱们须要比拟 Tag, 如果组内有 Tag 呈现，则阐明咱们拜访的数据在缓存中，能够开心的应用了。
比方举个 2 路组相连的例子，如下图所示。
T 示意 Tag。间接比拟 Tag，就能得悉是不是命中了。如果命中了，则依据 index(组号）将对应的块取出来即可。
如上图所示。用 index 选出位于组相连的哪个组。而后并行的比拟 Tag, 判断最初是不是在 Cache 中。上图是 2 路组相连，也就是说两组并行比拟。
那如果不在缓存中呢？这就波及到另一个问题。
不在缓存中如何替换 Cache？
2.3 如何替换 Cache 中的数据
Cache 中的数据如何被替换的？这个就比较简单间接。
- 随机替换。如果产生 Cache miss 里随机替换掉一块。
- Least recently used. LRU。最近应用的块最初替换。
- First in, first out (FIFO), 先进先出。
实际上第一个不怎么应用，LRU 和 FIFO 依据理论状况抉择即可。
Cache 在什么时候数据会被替换内？也有几种策略。
- 不在本 Cache 替换。如果 Cache miss 了，间接转发拜访地址到主存，取到的数据不会写到 Cache.
- 在读 MISS 时替换。如果读的时候 Cache 里没有该数据，则从主存读取该数据后写入 Cache。
- 在写 MISS 时替换。如果写的时候 Cache 里没有该数据，则将本数据调入 Cache 再写。
2.4 如果产生了写操作怎么办
Cache 毕竟是个长期缓存。
如果产生了写操作，会造成 Cache 和主存中的数据不统一。如何保障写数据操作正确呢？
也有三种策略。
- 通写：间接把数据写回 Cache 的同时写回主存。极其影响写速度。
- 回写：先把数据写回 Cache, 而后当 Cache 的数据被替换时再写回主存。
- 通写队列：通写与回写的联合。先写回一个队列，而后缓缓往主存储写。如果屡次写同一个数据，间接写这个队列。防止频繁写主存。
Cache 一致性
Cache 一致性是 Cache 中遇到的比拟坑的一个问题。
什么起因须要 Cache 解决一致性呢？
次要是多核零碎中，如果 core 0 读了主存储的数据，写了数据。core 1 也读了主从的数据。这个时候 core 1 并不知道数据曾经被改变了，也就是说，core 1 Cache 中的数据过期了，会产生谬误。
Cache 一致性的保障就是让多核拜访不出错。
Cache 一致性次要有两种策略。
策略一：基于监听的一致性策略
这种策略是所有 Cache 均监听各 Cache 的写操作，如果一个 Cache 中的数据被写了，有两种解决方法。
写更新协定：某个 Cache 产生写了，就索性把所有 Cache 都给更新了。
写生效协定：某个 Cache 产生写了，就把其余 Cache 中的该数据块置为有效。
策略 1 因为监听起来老本比拟大，所以只利用于极简略的零碎中。
策略二：基于目录的一致性策略
这种策略是在主存处保护一张表。记录各数据块都被写到了哪些 Cache, 从而更新相应的状态。一般来讲这种策略采纳的比拟多。又分为上面几个罕用的策略。
- SI: 对于一个数据块来讲，有 share 和 invalid 两种状态。如果是 share 状态，间接告诉其余 Cache, 将对应的块置为有效。
- MSI：对于一个数据块来讲，有 share 和 invalid，modified 三种状态。其中 modified 状态表示意该数据只属于这个 Cache, 被批改过了。当这个数据被逐出 Cache 时更新主存。这么做的益处是防止了大量的主从写入。同时，如果是 invalid 时写该数据，就要保障其余所有 Cache 里该数据的标记位不为 M，负责要先写回主存储。
- MESI：对于一个数据来讲，有 4 个状态。modified, invalid, shared, exclusive。其中 exclusive 状态用于标识该数据与其余 Cache 不依赖。要写的时候间接将该 Cache 状态改成 M 即可。
咱们着重讲讲 MESI。图中黑线：CPU 的拜访。红线：总线的拜访，其余 Cache 的拜访。
以后状态时 I 状态时，如果产生处理器读操作 prrd。
- 如果其余 Cache 里有这份数据，如果其余 Cache 里是 M 态，先 把 M 态写回主存再读。否则间接读。最终状态变为 S。
- 其余 Cache 里没这个数据，间接变到 E 状态。
以后状态为 S 态
- 如果产生了处理器读操作，依然在 S 态。
- 如果产生了处理器写操作，则跳转到 M 状态。
- 如果其余 Cache 产生了写操作，跳到 I 态。
以后状态 E 态
- 产生了处理器读操作还是 E。
- 产生了处理器写操作变成 M。
- 如果其余 Cache 产生了读操作，变到 S 状态。
以后状态 M 态
- 产生了读操作仍旧是 M 态。
- 产生了写操作仍旧是 M 态。
- 如果其余 Cache 产生了读操作，则将数据写回主存储，变换到 S 态。
总结
Cache 在计算机体系架构中有十分重要的位置，本文讲了 Cache 中最次要的内容，具体细节能够再依据某个点深入研究。
近期热文举荐：
1.1,000+ 道 Java 面试题及答案整顿 (2022 最新版)
2. 劲爆！Java 协程要来了。。。
3.Spring Boot 2.x 教程，太全了！
4. 别再写满屏的爆爆爆炸类了，试试装璜器模式，这才是优雅的形式！！
5.《Java 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！
