作者丨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。