本文已收录到 GitHub · AndroidFamily，有 Android 进阶常识体系，欢送 Star。技术和职场问题，请关注公众号 [彭旭锐] 进 Android 面试交换群。
前言
大家好，我是小彭。
在上一篇文章里，咱们聊到了计算机存储器零碎的金字塔构造，其中在 CPU 和内存之间有一层高速缓存，就是咱们明天要聊的 CPU 三级缓存。
那么，CPU Cache 的构造是怎么的，背地隐含着哪些设计思维，CPU Cache 和内存数据是如何关联起来的，明天咱们将围绕这些问题开展。
学习路线图：
1. 意识 CPU 高速缓存
1.1 存储器的金字塔构造
古代计算机系统为了寻求容量、速度和价格最大的性价比会采纳分层架构，从“CPU 寄存器 – CPU 高速缓存 – 内存 – 硬盘”自上而下容量逐步增大，速度逐步减慢，单位价格也逐步升高。
- 1、CPU 寄存器： 存储 CPU 正在应用的数据或指令；
- 2、CPU 高速缓存： 存储 CPU 近期要用到的数据和指令；
- 3、内存： 存储正在运行或者将要运行的程序和数据；
- 4、硬盘： 存储临时不应用或者不能间接应用的程序和数据。
存储器金字塔
1.2 为什么在 CPU 和内存之间减少高速缓存？
我认为有 2 个起因：
- 起因 1 – 补救 CPU 和内存的速度差（次要）： 因为 CPU 和内存的速度差距太大，为了拉平两者的速度差，古代计算机会在两者之间插入一块速度比内存更快的高速缓存。只有将近期 CPU 要用的信息调入缓存，CPU 便能够间接从缓存中获取信息，从而进步访问速度；
- 起因 2 – 缩小 CPU 与 I/O 设施争抢访存： 因为 CPU 和 I/O 设施会竞争同一条内存总线，有可能呈现 CPU 期待 I/O 设施访存的状况。而如果 CPU 能间接从缓存中获取数据，就能够缩小竞争，进步 CPU 的效率。
1.3 CPU 的三级缓存构造
在 CPU Cache 的概念刚呈现时，CPU 和内存之间只有一个缓存，随着芯片集成密度的进步，古代的 CPU Cache 曾经广泛采纳 L1/L2/L3 多级缓存的构造来改善性能。自顶向下容量逐步增大，访问速度也逐步升高。当缓存未命中时，缓存零碎会向更底层的档次搜寻。
- L1 Cache： 在 CPU 外围外部，分为指令缓存和数据缓存，离开寄存 CPU 应用的指令和数据；
- L2 Cache： 在 CPU 外围外部，尺寸比 L1 更大；
- L3 Cache： 在 CPU 外围内部，所有 CPU 外围共享同一个 L3 缓存。
CPU 三级缓存
2. 了解 CPU 三级缓存的设计思维
2.1 为什么 L1 要将指令缓存和数据缓存离开？
这个策略叫拆散缓存，与之绝对应的叫对立缓存：
-
拆散缓存： 指令和数据别离寄存在不同缓存中：
- 指令缓存（Instruction Cache，I-Cache）
- 数据缓存（Data Cache，D-Cache）
- 对立缓存： 指令和数据对立寄存在一个缓存中。
那么，为什么 L1 缓存要把指令和数据离开呢？我认为有 2 个起因：
- 起因 1 – 防止取指令单元和取数据单元抢夺访缓存（次要）： 在 CPU 内核中，取指令和取数据指令是由两个不同的单元实现的。如果应用对立缓存，当 CPU 应用超前管制或流水线管制（并行执行）的管制形式时，会存在取指令操作和取数据操作同时争用同一个缓存的状况，升高 CPU 运行效率；
- 起因 2 – 内存中数据和指令是绝对聚簇的，拆散缓存能进步命中率： 在古代计算机系统中，内存中的指令和数据并不是随机散布的，而是绝对聚集地离开存储的。因而，CPU Cache 中也采纳拆散缓存的策略更合乎内存数据的现状；
2.2 为什么 L1 采纳拆散缓存而 L2 采纳对立缓存？
我认为起因有 2 个：
- 起因 1： L1 采纳拆散缓存后曾经解决了取指令单元和取数据单元的抢夺访缓存问题，所以 L2 是否应用拆散缓存没有影响；
- 起因 2： 当缓存容量较大时，拆散缓存无奈动静调节拆散比例，不能最大化施展缓存容量的利用率。例如数据缓存满了，然而指令缓存还有闲暇，而 L2 应用对立缓存则可能保障最大化利用缓存空间。
2.3 L3 缓存是多外围共享的，放在芯片外有区别吗？
集成在芯片外部的缓存称为片内缓存，集成在芯片内部（主板）的缓存称为片外缓存。最后，因为受到芯片集成工艺的限度，片内缓存不可能很大，因而 L2 / L3 缓存都是设计在主板上，而不是在芯片内的。
起初，L2 / L3 才逐步集成到 CPU 芯片外部后的。片内缓冲和片外缓存是有区别的，次要体现在 2 个方面：
- 区别 1 – 片内缓存物理间隔更短： 片内缓存与取指令单元和取数据单元的物理间隔更短，速度更快；
- 区别 2 – 片内缓存不占用系统总线： 片内缓存应用独立的 CPU 片内总线，能够加重系统总线的累赘。
3. CPU Cache 的根本单位 —— Cache Line
CPU Cache 在读取内存数据时，每次不会只读一个字或一个字节，而是一块块地读取，这每一小块数据也叫 CPU 缓存行（CPU Cache Line）。这也是对局部性原理的利用，当一个指令或数据被拜访过之后，与它相邻地址的数据有很大概率也会被拜访，将更多可能被拜访的数据存入缓存，能够进步缓存命中率。
当然，块长也不是越大越好（个别是取 4 到 8 个字长，即 64 位）：
- 后期：当块长由小到大增长时，随着局部性原理的影响使得命中率逐步进步；
- 前期：但随着块长持续增大，导致缓存中承载的块个数缩小，很可能内存块刚刚装入缓存就被新的内存块笼罩，命中率反而降落。而且，块长越长，追加的局部间隔被拜访的字越远，近期被拜访的可能性也更低，杯水车薪。
辨别几种容量单位：
- 字节（Byte）： 字节是计算机数据存储的根本单位，即便存储 1 个位也须要按 1 个字节存储；
- 字（Word）： 字长是 CPU 在单位工夫内可能同时解决的二进制数据位数。多少位 CPU 就是指 CPU 的字长是多少位（比方 64 位 CPU 的字长就是 64 位）；
- 块（Block）： 块是 CPU Cache 治理数据的根本单位，也叫 CPU 缓存行；
- 段（Segmentation）/ 页（Page）： 段 / 页是操作系统治理虚拟内存的根本单位。
事实上，CPU 在拜访内存数据的时候，与计算机中对于“缓存设计”的一般性法则是雷同的： 对于基于 Cache 的零碎，对数据的读取和写入总会先拜访 Cache，查看要拜访的数据是否在 Cache 中。如果命中则间接应用 Cache 上的数据，否则先将底层的数据源加载到 Cache 中，再从 Cache 读取数据。
那么，CPU 怎么晓得要拜访的内存数据是否在 CPU Cache 中，在 CPU 中的哪个地位，以及是不是无效的呢？这就是下一节要讲的内存地址与 Cache 地址的映射问题。
4. 内存地址与 Cache 地址的映射
无论对 Cache 数据查看、读取还是写入，CPU 都须要晓得拜访的内存数据对应于 Cache 上的哪个地位，这就是内存地址与 Cache 地址的映射问题。
事实上，因为内存块和缓存块的大小是雷同的，所以在映射的过程中，咱们只须要思考 “内存块索引 – 缓存块索引” 之间的映射关系，而具体拜访的是块内的哪一个字，则应用雷同的偏移在块中寻找。举个例子：假如内存有 32 个内存块，CPU Cache 有 8 个缓存块，咱们只须要思考 紫色 局部标识的索引如何匹配即可。
目前，次要有 3 种映射计划：
- 1、间接映射（Direct Mapped Cache）： 固定的映射关系；
- 2、全相联映射（Fully Associative Cache）： 灵便的映射关系；
- 3、组相联映射（N-way Set Associative Cache）： 前两种计划的折中办法。
内存块索引 - 缓存块索
4.1 间接映射
间接映射是三种形式中最简略的映射形式，间接映射的策略是： 在内存块和缓存块之间建设起固定的映射关系，一个内存块总是映射到同一个缓存块上。
具体形式：
- 1、将内存块索引对 Cache 块个数取模，失去固定的映射地位。例如 13 号内存块映射的地位就是 13 % 8 = 5，对应 5 号 Cache 块；
- 2、因为取模后多个内存块会映射到同一个缓存块上，产生块抵触，所以须要在 Cache 块上减少一个 组标记（TAG），标记以后缓存块存储的是哪一个内存块的数据。其实，组标记就是内存块索引的高位，而 Cache 块索引就是内存块索引的低 4 位（8 个字块须要 4 位）；
- 3、因为初始状态 Cache 块中的数据是空的，也是有效的。为了标识 Cache 块中的数据是否曾经从内存中读取，须要在 Cache 块上减少一个 无效位（Valid bit）。如果无效位为 0，则 CPU 能够间接读取 Cache 块上的内容，否则须要先从内存读取内存块填入 Cache 块，再将无效位改为 1。
间接映射
4.2 全相联映射
了解了间接映射的形式后，咱们发现间接映射存在 2 个问题：
- 问题 1 – 缓存利用不充沛： 每个内存块只能映射到固定的地位上，即便 Cache 上有闲暇地位也不会应用；
- 问题 2 – 块抵触率高： 间接映射会频繁呈现块抵触，影响缓存命中率。
基于间接映射的毛病，全相联映射的策略是： 容许内存块映射到任何一个 Cache 块上。 这种形式可能充分利用 Cache 的空间，块抵触率也更低，然而所须要的电路构造物更简单，老本更高。
具体形式：
- 1、当 Cache 块上有闲暇地位时，应用闲暇地位；
- 2、当 Cache 被占满时则替换出一个旧的块腾出闲暇地位；
- 3、因为一个 Cache 块会映射所有内存块，因而组标记 TAG 须要扩充到与主内存块索引雷同的位数，而且映射的过程须要沿着 Cache 从头到尾匹配 Cache 块的 TAG 标记。
全相联映射
4.3 组相联映射
组相联映射是间接映射和全相联映射的折中计划，组相联映射的策略是：将 Cache 分为多组，每个内存块固定映射到一个分组中，又容许映射到组内的任意 Cache 块。显然，组相联的分组为 1 时就等于全相联映射，而分组等于 Cache 块个数时就等于间接映射。
组相联映射
5. Cache 块的替换策略
在应用间接映射的 Cache 中，因为每个主内存块都与某个 Cache 块有间接映射关系，因而不存在替换策略。而应用全相联映射或组相联映射的 Cache 中，主内存块与 Cache 块没有固定的映射关系，当新的内存块须要加载到 Cache 中时（且 Cache 块没有闲暇地位），则须要替换到 Cache 块上的数据。此时就存在替换策略的问题。
常见替换策略：
- 1、随机法： 应用一个随机数生成器随机地抉择要被替换的 Cache 块，实现简略，毛病是没有利用“局部性原理”，无奈进步缓存命中率；
- 2、FIFO 先进先出法： 记录各个 Cache 块的加载事件，最早调入的块最先被替换，毛病同样是没有利用“局部性原理”，无奈进步缓存命中率；
- 3、LRU 最近起码应用法： 记录各个 Cache 块的应用状况，最近起码应用的块最先被替换。这种办法绝对比较复杂，也有相似的简化办法，即记录各个块最近一次应用工夫，最久未拜访的最先被替换。与前 2 种策略相比，LRU 策略利用了“局部性原理”，均匀缓存命中率更高。
6. 总结
- 1、为了补救 CPU 和内存的速度差和缩小 CPU 与 I/O 设施争抢访存，计算机在 CPU 和内存之间减少高速缓存，个别存在 L1/L2/L3 多级缓存的构造；
- 2、对于基于 Cache 的存储系统，对数据的读取和写入总会先拜访 Cache，查看要拜访的数据是否在 Cache 中。如果命中则间接应用 Cache 上的数据，否则先将底层的数据源加载到 Cache 中，再从 Cache 读取数据；
- 3、CPU Cache 是一块块地从内存读取数据，一块数据就是缓存行；
- 4、内存地址与 Cache 地址的映射有间接映射、全相联映射和组相联映射；
- 5、应用全相联映射或组相联映射的 Cache 中，当新的内存块须要加载到 Cache 中时且 Cache 块没有闲暇地位，则须要替换到 Cache 块上的数据。
明天，咱们次要探讨了 CPU Cache 的根本设计思维以及 Cache 与内存的映射关系。具体 CPU Cache 是如何读取和写入的还没讲，另外有一个 CPU 缓存一致性问题 说的又是什么呢？下一篇文章咱们具体展开讨论，请关注。
参考资料
- 深入浅出计算机组成原理（第 37、38 讲）—— 徐文浩 著，极客工夫 出品
- 计算机组成原理教程（第 7 章）—— 尹艳辉 王海文 邢军 著
- 面试官：如何写出让 CPU 跑得更快的代码？—— 小林 Coding 著
- CPU cache —— Wikipedia
- CPU caches —— LWN.net