作者丨 smcdef
起源丨 http://www.wowotech.net/memory_management/458.html
明天探索的主题是 cache。咱们围绕几个问题开展。为什么须要 cache？如何判断一个数据在 cache 中是否命中？cache 的品种有哪些，区别是什么？
对于没有接触过底层技术的敌人来说，或者从未据说过 cache。毕竟 cache 的存在对程序员来说是通明的。在接触 cache 之前，先为你筹备段 code 剖析。
int arr[10][128];
for (i = 0; i < 10; i++)
for (j = 0; j < 128; j++);
arr[i][j] = 1;
如果你已经学习过 C /C++ 语言，这段 code 天然不会生疏。如此简略的将 arr 数组所有元素置 1。你有没有想过这段 code 还有上面的一种写法。
int arr[10][128];
for (i = 0; i < 128; i++)
for (j = 0; j < 10; j++);
arr[j][i] = 1;
性能齐全一样，然而咱们始终在反复着第一种写法（或者很多的书中也是倡议这么编码），你是否想过这其中的原因？文章的配角是 cache，所以你肯定猜到了答案。那么 cache 是如何影响这 2 段 code 的呢？
为什么须要 cache memory
在思考 cache 是什么之前咱们首先先来思考第一个问题：咱们的程序是如何运行起来的？
咱们应该晓得程序是运行在 RAM 之中，RAM 就是咱们常说的 DDR（例如 DDR3、DDR4 等）。咱们称之为 main memory（主存）当咱们须要运行一个过程的时候，首先会从 Flash 设施（例如，eMMC、UFS 等）中将可执行程序 load 到 main memory 中，而后开始执行。在 CPU 外部存在一堆的通用寄存器（register）。如果 CPU 须要将一个变量（假如地址是 A）加 1，个别分为以下 3 个步骤：
- CPU 从主存中读取地址 A 的数据到外部通用寄存器 x0（ARM64 架构的通用寄存器之一）。
- 通用寄存器 x0 加 1。
- CPU 将通用寄存器 x0 的值写入主存。
咱们将这个过程能够示意如下：
其实事实中，CPU 通用寄存器的速度和主存之间存在着太大的差别。两者之间的速度大抵如下关系：
CPU register 的速度个别小于 1ns，主存的速度个别是 65ns 左右。速度差别近百倍。因而，下面举例的 3 个步骤中，步骤 1 和步骤 3 实际上速度很慢。当 CPU 试图从主存中 load/store 操作时，因为主存的速度限制，CPU 不得不期待这漫长的 65ns 工夫。如果咱们能够晋升主存的速度，那么零碎将会取得很大的性能晋升。
现在的 DDR 存储设备，动不动就是几个 GB，容量很大。如果咱们采纳更快资料制作更快速度的主存，并且领有简直差不多的容量。其老本将会大幅度回升。
咱们试图晋升主存的速度和容量，又冀望其老本很低，这就有点难为人了。因而，咱们有一种折中的办法，那就是制作一块速度极快然而容量极小的存储设备。那么其老本也不会太高。这块存储设备咱们称之为 cache memory。
在硬件上，咱们将 cache 搁置在 CPU 和主存之间，作为主存数据的缓存。当 CPU 试图从主存中 load/store 数据的时候，CPU 会首先从 cache 中查找对应地址的数据是否缓存在 cache 中。如果其数据缓存在 cache 中，间接从 cache 中拿到数据并返回给 CPU。当存在 cache 的时候，以上程序如何运行的例子的流程将会变成如下：
CPU 和主存之间间接数据传输的形式转变成 CPU 和 cache 之间间接数据传输。cache 负责和主存之间数据传输。
多级 cache memory
cahe 的速度在肯定水平上同样影响着零碎的性能。个别状况 cache 的速度能够达到 1ns，简直能够和 CPU 寄存器速度媲美。然而，这就满足人们对性能的谋求了吗？并没有。当 cache 中没有缓存咱们想要的数据的时候，仍然须要漫长的期待从主存中 load 数据。
为了进一步晋升性能，引入多级 cache。后面提到的 cache，称之为 L1 cache（第一级 cache）。咱们在 L1 cache 前面连贯 L2 cache，在 L2 cache 和主存之间连贯 L3 cache。等级越高，速度越慢，容量越大。然而速度相比拟主存而言，仍然很快。不同等级 cache 速度之间关系如下：
通过 3 级 cache 的缓冲，各级 cache 和主存之间的速度最萌差也逐级减小。在一个实在的零碎上，各级 cache 之间硬件上是如何关联的呢？咱们看下 Cortex-A53 架构上各级 cache 之间的硬件形象框图如下：
在 Cortex-A53 架构上，L1 cache 分为独自的 instruction cache（ICache）和 data cache（DCache）。L1 cache 是 CPU 公有的，每个 CPU 都有一个 L1 cache。一个 cluster 内的所有 CPU 共享一个 L2 cache，L2 cache 不辨别指令和数据，都能够缓存。所有 cluster 之间共享 L3 cache。L3 cache 通过总线和主存相连。
多级 cache 之间的配合工作
首先引入两个名词概念，命中和缺失。CPU 要拜访的数据在 cache 中有缓存，称为“命中”(hit)，反之则称为“缺失”(miss)。多级 cache 之间是如何配合工作的呢？咱们假如当初思考的零碎只有两级 cache。
当 CPU 试图从某地址 load 数据时，首先从 L1 cache 中查问是否命中，如果命中则把数据返回给 CPU。如果 L1 cache 缺失，则持续从 L2 cache 中查找。当 L2 cache 命中时，数据会返回给 L1 cache 以及 CPU。如果 L2 cache 也缺失，很可怜，咱们须要从主存中 load 数据，将数据返回给 L2 cache、L1 cache 及 CPU。
这种多级 cache 的工作形式称之为 inclusive cache。某一地址的数据可能存在多级缓存中。与 inclusive cache 对应的是 exclusive cache，这种 cache 保障某一地址的数据缓存只会存在于多级 cache 其中一级。也就是说，任意地址的数据不可能同时在 L1 和 L2 cache 中缓存。
间接映射缓存（Direct mapped cache）
咱们持续引入一些 cache 相干的名词。cache 的大小称之为 cahe size，代表 cache 能够缓存最大数据的大小。咱们将 cache 均匀分成相等的很多块，每一个块大小称之为 cache line，其大小是 cache line size。
例如一个 64 Bytes 大小的 cache。如果咱们将 64 Bytes 均匀分成 64 块，那么 cache line 就是 1 字节，总共 64 行 cache line。如果咱们将 64 Bytes 均匀分成 8 块，那么 cache line 就是 8 字节，总共 8 行 cache line。当初的硬件设计中，个别 cache line 的大小是 4 -128 Byts。为什么没有 1 byte 呢？起因咱们前面探讨。
这里有一点须要留神，cache line 是 cache 和主存之间数据传输的最小单位。什么意思呢？当 CPU 试图 load 一个字节数据的时候，如果 cache 缺失，那么 cache 控制器会从主存中一次性的 load cache line 大小的数据到 cache 中。例如，cache line 大小是 8 字节。CPU 即便读取一个 byte，在 cache 缺失后，cache 会从主存中 load 8 字节填充整个 cache line。又是因为什么呢？前面说完就懂了。
咱们假如上面的解说都是针对 64 Bytes 大小的 cache，并且 cache line 大小是 8 字节。咱们能够相似把这块 cache 想想成一个数组，数组总共 8 个元素，每个元素大小是 8 字节。就像下图这样：
当初咱们思考一个问题，CPU 从 0x0654 地址读取一个字节，cache 控制器是如何判断数据是否在 cache 中命中呢？cache 大小绝对于主存来说，堪称是小巫见大巫。所以 cache 必定是只能缓存主存中极小一部分数据。咱们如何依据地址在无限大小的 cache 中查找数据呢？当初硬件采取的做法是对地址进行散列（能够了解成地址取模操作）。咱们接下来看看是如何做到的？
咱们一共有 8 行 cache line，cache line 大小是 8 Bytes。所以咱们能够利用地址低 3 bits（如上图地址蓝色局部）用来寻址 8 bytes 中某一字节，咱们称这部分 bit 组合为 offset。同理，8 行 cache line，为了笼罩所有行。咱们须要 3 bits（如上图地址黄色局部）查找某一行，这部分地址局部称之为 index。
当初咱们晓得，如果两个不同的地址，其地址的 bit3-bit5 如果齐全一样的话，那么这两个地址通过硬件散列之后都会找到同一个 cache line。所以，当咱们找到 cache line 之后，只代表咱们拜访的地址对应的数据可能存在这个 cache line 中，然而也有可能是其余地址对应的数据。所以，咱们又引入 tag array 区域，tag array 和 data array 一一对应。
每一个 cache line 都对应惟一一个 tag，tag 中保留的是整个地址位宽去除 index 和 offset 应用的 bit 残余局部（如上图地址绿色局部）。tag、index 和 offset 三者组合就能够惟一确定一个地址了。
因而，当咱们依据地址中 index 位找到 cache line 后，取出以后 cache line 对应的 tag，而后和地址中的 tag 进行比拟，如果相等，这阐明 cache 命中。如果不相等，阐明以后 cache line 存储的是其余地址的数据，这就是 cache 缺失。
在上述图中，咱们看到 tag 的值是 0x19，和地址中的 tag 局部相等，因而在本次拜访会命中。因为 tag 的引入，因而解答了咱们之前的一个疑难“为什么硬件 cache line 不做成一个字节？”。这样会导致硬件老本的回升，因为本来 8 个字节对应一个 tag，当初须要 8 个 tag，占用了很多内存。
咱们能够从图中看到 tag 旁边还有一个 valid bit，这个 bit 用来示意 cache line 中数据是否无效（例如：1 代表无效；0 代表有效）。当零碎刚启动时，cache 中的数据都应该是有效的，因为还没有缓存任何数据。cache 控制器能够依据 valid bit 确认以后 cache line 数据是否无效。所以，上述比拟 tag 确认 cache line 是否命中之前还会查看 valid bit 是否无效。只有在无效的状况下，比拟 tag 才有意义。如果有效，间接断定 cache 缺失。
下面的例子中，cache size 是 64 Bytes 并且 cache line size 是 8 bytes。offset、index 和 tag 别离应用 3 bits、3 bits 和 42 bits（假如地址宽度是 48 bits）。咱们当初再看一个例子：512 Bytes cache size，64 Bytes cache line size。依据之前的地址划分办法，offset、index 和 tag 别离应用 6 bits、3 bits 和 39 bits。如下图所示：
间接映射缓存的优缺点
间接映射缓存在硬件设计上会更加简略，因而老本上也会较低。依据间接映射缓存的工作形式，咱们能够画出主存地址 0x00-0x88 地址对应的 cache 分布图：
咱们能够看到，地址 0x00-0x3f 地址处对应的数据能够笼罩整个 cache。0x40-0x7f 地址的数据也同样是笼罩整个 cache。咱们当初思考一个问题，如果一个程序试图顺次拜访地址 0x00、0x40、0x80，cache 中的数据会产生什么呢？首先咱们应该明确 0x00、0x40、0x80 地址中 index 局部是一样的。因而，这 3 个地址对应的 cache line 是同一个。
所以，当咱们拜访 0x00 地址时，cache 会缺失，而后数据会从主存中加载到 cache 中第 0 行 cache line。当咱们拜访 0x40 地址时，仍然索引到 cache 中第 0 行 cache line，因为此时 cache line 中存储的是地址 0x00 地址对应的数据，所以此时仍然会 cache 缺失。而后从主存中加载 0x40 地址数据到第一行 cache line 中。
同理，持续拜访 0x80 地址，仍然会 cache 缺失。这就相当于每次拜访数据都要从主存中读取，所以 cache 的存在并没有对性能有什么晋升。拜访 0x40 地址时，就会把 0x00 地址缓存的数据替换。这种景象叫做 cache 平稳（cache thrashing）。
针对这个问题，咱们引入多路组相连缓存。咱们首先钻研下最简略的两路组相连缓存的工作原理。
两路组相连缓存
咱们仍然假如 64 Bytes cache size，cache line size 是 8 Bytes。什么是路（way）的概念。咱们将 cache 均匀分成多份，每一份就是一路。因而，两路组相连缓存（Two-way set associative cache）就是将 cache 均匀分成 2 份，每份 32 Bytes。如下图所示：
cache 被分成 2 路，每路蕴含 4 行 cache line。咱们将所有索引一样的 cache line 组合在一起称之为组。例如，上图中一个组有两个 cache line，总共 4 个组。咱们仍然假如从地址 0x0654 地址读取一个字节数据。因为 cache line size 是 8 Bytes，因而 offset 须要 3 bits，这和之前间接映射缓存一样。
不一样的中央是 index，在两路组相连缓存中，index 只须要 2 bits，因为一路只有 4 行 cache line。下面的例子依据 index 找到第 2 行 cache line（从 0 开始计算），第 2 行对应 2 个 cache line，别离对应 way 0 和 way 1。因而 index 也能够称作 set index（组索引）。先依据 index 找到 set，而后将组内的所有 cache line 对应的 tag 取出来和地址中的 tag 局部比照，如果其中一个相等就意味着命中。
因而，两路组相连缓存较间接映射缓存最大的差别就是：第一个地址对应的数据能够对应 2 个 cache line，而间接映射缓存一个地址只对应一个 cache line。那么这到底有什么益处呢？
两路组相连缓存优缺点
两路组相连缓存的硬件老本绝对于间接映射缓存更高。因为其每次比拟 tag 的时候须要比拟多个 cache line 对应的 tag（某些硬件可能还会做并行比拟，减少比拟速度，这就减少了硬件设计复杂度）。
为什么咱们还须要两路组相连缓存呢？因为其能够有助于升高 cache 平稳可能性。那么是如何升高的呢？依据两路组相连缓存的工作形式，咱们能够画出主存地址 0x00-0x4f 地址对应的 cache 分布图：
咱们仍然思考间接映射缓存一节的问题“如果一个程序试图顺次拜访地址 0x00、0x40、0x80，cache 中的数据会产生什么呢？”。当初 0x00 地址的数据能够被加载到 way 1，0x40 能够被加载到 way 0。这样是不是就在肯定水平上防止了间接映射缓存的难堪地步呢？在两路组相连缓存的状况下，0x00 和 0x40 地址的数据都缓存在 cache 中。试想一下，如果咱们是 4 路组相连缓存，前面持续拜访 0x80，也可能被被缓存。
因而，当 cache size 肯定的状况下，组相连缓存对性能的晋升最差状况下也和间接映射缓存一样，在大部分状况下组相连缓存成果比间接映射缓存好。同时，其升高了 cache 平稳的频率。从某种程度上来说，间接映射缓存是组相连缓存的一种非凡状况，每个组只有一个 cache line 而已。因而，间接映射缓存也能够称作单路组相连缓存。
全相连缓存（Full associative cache）
既然组相连缓存那么好，如果所有的 cache line 都在一个组内。岂不是性能更好。是的，这种缓存就是全相连缓存。咱们仍然以 64 Byts 大小 cache 为例阐明。
因为所有的 cache line 都在一个组内，因而地址中不须要 set index 局部。因为，只有一个组让你抉择，间接来说就是你没得选。咱们依据地址中的 tag 局部和所有的 cache line 对应的 tag 进行比拟（硬件上可能并行比拟也可能串行比拟）。哪个 tag 比拟相等，就意味着命中某个 cache line。因而，在全相连缓存中，任意地址的数据能够缓存在任意的 cache line 中。所以，这能够最大水平的升高 cache 平稳的频率。然而硬件老本上也是更高。
一个四路组相连缓存实例问题
思考这么一个问题，32 KB 大小 4 路组相连 cache，cache line 大小是 32 Bytes。请思考一下问题：
- 多少个组？
- 假如地址宽度是 48 bits，index、offset 以及 tag 别离占用几个 bit？
总共 4 路，因而每路大小是 8 KB。cache line size 是 32 Bytes，因而一共有 256 组（8 KB / 32 Bytes）。因为 cache line size 是 32 Bytes，所以 offset 须要 5 位。一共 256 组，所以 index 须要 8 位，剩下的就是 tag 局部，占用 35 位。这个 cache 能够绘制下图示意：
Cache 调配策略
cache 的调配策略（Cache allocation policy）是指咱们什么状况下应该为数据调配 cache line。cache 调配策略分为读和写两种状况。
读调配（read allocation）
当 CPU 读数据时，产生 cache 缺失，这种状况下都会调配一个 cache line 缓存从主存读取的数据。默认状况下，cache 都反对读调配。
写调配（write allocation）
当 CPU 写数据产生 cache 缺失时，才会思考写调配策略。当咱们不反对写调配的状况下，写指令只会更新主存数据，而后就完结了。当反对写调配的时候，咱们首先从主存中加载数据到 cache line 中（相当于先做个读调配动作），而后会更新 cache line 中的数据。
Cache 更新策略
cache 更新策略（Cache update policy）是指当产生 cache 命中时，写操作应该如何更新数据。cache 更新策略分成两种：写直通和回写。
写直通（write through）
当 CPU 执行 store 指令并在 cache 命中时，咱们更新 cache 中的数据并且更新主存中的数据。cache 和主存的数据始终保持统一。
写回（write back）
当 CPU 执行 store 指令并在 cache 命中时，咱们只更新 cache 中的数据。并且每个 cache line 中会有一个 bit 位记录数据是否被批改过，称之为 dirty bit（翻翻后面的图片，cache line 旁边有一个 D 就是 dirty bit）。咱们会将 dirty bit 置位。主存中的数据只会在 cache line 被替换或者显示 clean 操作时更新。因而，主存中的数据可能是未修改的数据，而批改的数据躺在 cache line 中。cache 和主存的数据可能不统一。
同时思考个问题，为什么 cache line 大小是 cache 控制器和主存之间数据传输的最小单位呢？这也是因为每个 cache line 只有一个 dirty bit。这一个 dirty bit 代表着整个 cache line 是否被批改的状态。
实例
假如咱们有一个 64 Bytes 大小间接映射缓存，cache line 大小是 8 Bytes，采纳写调配和写回机制。当 CPU 从地址 0x2a 读取一个字节，cache 中的数据将会如何变动呢？假如以后 cache 状态如下图所示：
依据 index 找到对应的 cache line，对应的 tag 局部 valid bit 是非法的，然而 tag 的值不相等，因而产生缺失。此时咱们须要从地址 0x28 地址加载 8 字节数据到该 cache line 中。然而，咱们发现以后 cache line 的 dirty bit 置位。因而，cache line 外面的数据不能被简略的抛弃，因为采纳写回机制，所以咱们须要将 cache 中的数据 0x11223344 写到地址 0x0128 地址（这个地址依据 tag 中的值及所处的 cache line 行计算失去）。这个过程如下图所示：
当写回操作实现，咱们将主存中 0x28 地址开始的 8 个字节加载到该 cache line 中，并革除 dirty bit。而后依据 offset 找到 0x52 返回给 CPU。