内存管理：堆
本文本文参考OSDev Wiki上关于CPU缓存的介绍，原文地址：https://wiki.osdev.org/CPU_Caches
Introduction（介绍）
最初，内存的速度和 CPU 一样快。随着时间推移，CPU 的速度越来越快。内存速度也在提升，但无法跟上 CPU 提升的速度，这意味着 CPU 需要花越来越多的时间等待来自 RAM 的数据（这会对性能造成严重影响）。
作为应对 CPU 与 RAM 速度差异的折中方法，CPU 厂商开始加入缓存。其基本思想是在 CPU 可以非常快速访问的一小块 RAM 中存储 RAM 数据的副本（以减少 CPU 访问较慢 RAM 所花费的时间）。
随着时间推移，CPU 与 RAM 的速度差距进一步扩大，因此 CPU 厂商增大了缓存的容量；但由于半导体设计的限制，缓存越大速度越慢（或延迟越高）。为了进一步提高性能，CPU 厂商开始在更大的缓存之上加入更小但更快的缓存。
在当前/现代 CPU 中，缓存可能有最多 3 层 —— 靠近 CPU 的、极快但相对较小的一级缓存（L1），中等容量且较快的二级缓存（L2），以及靠近系统总线或 RAM 的、较大的三级缓存（L3）。
当然，计算机使用的 RAM 数量也在增长；即使是非常大的 L3 缓存也无法缓存所有内容。例如，一台有 4 GiB RAM 的电脑可能只有 12 MiB 的 L3 缓存。为了提升性能，CPU 厂商希望缓存未来最有可能使用到的数据。然而，预测未来非常困难，因此 CPU 厂商通常为缓存使用“最近最少使用”（LRU）算法，因为最近使用过的数据通常更可能再次被使用。
幸运的是，除了极少数情况（如 RAM 故障测试、RAM 带宽基准测试）外，程序员不需要担心缓存。然而，缓存对系统整体性能起着重要作用，程序员可以通过关注缓存效率获得显著的性能提升。
总体而言，“最近最少使用”算法通常能很好地工作，但有些情况下会导致效率低下。其中一个例子称为“缓存污染”，即 CPU 访问大量未来不会再次使用的数据；这些数据因为被“最近使用”而挤出了本来应该保留的更有可能再次使用的数据。另一个例子称为“缓存抖动”（cache thrashing），即你重复访问一块比缓存容量更大的数据（例如 CPU 缓存只有 8 MiB，但你反复访问一个 10 MiB 的数组）。在这种情况下，即使某些数据会再次被使用，它们也会在被再次访问之前被更新的数据挤出缓存。
有多种技术可以用于管理这些缓存效率问题。CPU 厂商的一种技巧是将缓存分离。例如，一个 CPU 可能有一个用于指令的 L1 缓存和一个用于数据的 L1 缓存，这样 L1 数据缓存效率的问题就不会影响 L1 指令缓存效率。这也有助于缓解“大缓存延迟更高”的问题。
现代 CPU 还包含一些指令，程序员可以用来避免“最近最少使用”的缓存效率问题；包括用于将数据预取到缓存中的指令（当你知道数据即将被使用时很有用）、用于显式从缓存移除/刷新数据的指令（当你知道最近使用的数据不会再次使用时很有用），以及用于将数据直接写入 RAM 并绕过缓存的指令（类似于正常写入后再从缓存中刷新该数据）。
在某些情况下，软件需要处理大量数据，但可以分块处理（例如解压缩通常属于此类）。在这些情况下，为避免“缓存抖动”，检测缓存大小并确保每个数据块都能放入缓存中可能是有益的。例如，如果 CPU 的缓存是 4 MiB，而你要处理 100 MiB 数据，那么处理 50 个 2 MiB 的块可以比处理 20 个 5 MiB 的块获得更好的性能。因此，操作系统检测 CPU 缓存大小并为软件（例如应用程序）提供获取该信息的方式会很有帮助。
Caches In Systems With Multiple CPUs（多 CPU 系统中的缓存）
当多个 CPU 直接连接到内存（没有缓存）时，一切能够正常工作（但很慢）。当多个 CPU 带有各自的缓存并连接到内存时，存储在 RAM 中的数据可能是过时的，因为数据的当前版本仍可能在某个 CPU 的缓存中。大多数系统中缓存是透明的（例如，软件应该可以安全地忽略缓存的存在），而每个 CPU 拥有自己的缓存会造成问题，因为程序员不再能安全地忽略缓存。大多数计算机的硬件使用特殊协议确保这些问题不会发生 —— 例如，当某个 CPU 访问内存时，它访问的是数据的最新版本，而不管最新版本是在 RAM 中还是另一个 CPU 的缓存中。这称为“缓存一致性”（cache coherency）。
有些计算系统不是缓存一致的；程序员必须自行避免访问过期数据。通常这类系统编写程序非常麻烦，把每个 CPU 视为独立系统（例如把拥有 2 GiB RAM 和 2 个 CPU 的计算机看作两个每个带 1 GiB RAM 及 1 个 CPU 的计算机）会更简单一些。幸运的是，非缓存一致的系统很少见，尤其是在桌面/服务器计算机中。
在具有多个 CPU（尤其是多核 CPU）的系统中，多个 CPU 可能会共享同一个缓存。例如，一台拥有一对四核 CPU 的计算机，可能总共有 8 个 CPU，每个 CPU 具有自己的 L1 缓存，每两个 CPU 共享 L2 缓存，每 4 个 CPU 共享每个 L3 缓存。这会使操作系统软件（例如调度器和内存管理）以及应用程序的“缓存效率”优化变得复杂。
Cache Organization（缓存组织）
通常，缓存被拆分为许多“缓存行”（cache line），缓存行是可以存储到缓存中的最小数据单位。例如，一个 4 MiB 的缓存可能有 65536 个条目，用来容纳最多 65536 个缓存行，其中每个缓存行为 64 字节。当数据在缓存与 RAM 之间传输（或在不同层级缓存之间传输）时，所有 64 字节都会被传输。对于给定的缓存行大小，更大的缓存包含更多的条目。
CPU 需要能够在缓存中找到与特定地址对应的条目。为此，每个条目都有一个“标签”（tag），用于说明该条目中存的是什么（例如条目是否被使用，如果被使用，它对应的是哪个地址的数据）。对于非常简单的缓存，这意味着 CPU 需要查看每一个标签才能找到某个数据。这显然会带来问题（很慢）。
为了加快缓存速度，CPU 厂商通常使用“缓存行集合”（sets of cache lines），某个地址的数据只能在每个集合中的一个位置。集合的数量称为“相联度”（associativity），这种设计的缓存称为“N 路相联缓存”（N-way set associative cache）。例如，一个 4 MiB 的缓存如果是 4 路相联，那么它每个集合有 1 MiB，某个地址的数据只能在 4 个位置之一，CPU 只需要查看 4 个标签就能找到数据。
为了确定在每个缓存行集合中应该查看哪些标签，CPU 会使用地址的部分位。例如，对于地址 0x12345678，如果每个缓存行是 64 字节，那么最低 6 位无关紧要；（如果每个集合是 1 MiB），再往上的 14 位决定数据在每个集合中的可能位置。这也意味着对于 32 位地址，标签只需要存储最高的 12 位地址（这有助于减小标签大小）。
补充理解：每个缓存行有 64 字节是从内存取来的连续 64=2^6 字节，最低 6 bits 是 offset，表示块内偏移，无论低 6 bits是什么，都指向着同一个缓存块。如果每个集合是 1 MiB = 2^20 bytes，所以再往上的 14 位决定数据在每个集合中的可能位置。 CPU将需要的数据地址给到缓存控制器，控制器根据tag判断数据是否在缓存中。缓存中包含标签阵列（Tag Array）和数据阵列（Data Array），标签阵列存储tag（地址高位，用于匹配命中）、valid bit（这一行是否有效）、dirty bit（是否修改过）、coherence state（MESI/MOESI 状态）。CPU 查询缓存命中时，控制器用地址的 tag 部分 去 Tag Array 查找对应行的 tag 是否匹配。
一个地址的数据可以放在缓存中任何位置的缓存（上面提到的简单/较慢的缓存）称为“全相联”（fully associative），实际上等价于无限相联度。一个地址的数据在缓存中只能放在唯一一个位置的缓存称为“直接映射缓存”（direct mapped），等价于“1 路相联”。
对于直接映射缓存和相联度较低的缓存，缓存中的数据查找更快，因为数据只能位于较少的几个位置；但由于可能位置有限，也增加了缓存缺失（cache miss）的概率。例如，对于 1 MiB 的直接映射缓存，来自地址 0x00000000、0x00100000、0x00200000、0x00300000 等的数据必须共享缓存中的同一个位置；从 0x00000000 访问的数据会驱逐 0x00100000 的数据，即使缓存中其他条目空闲，即使 0x00100000 的数据被频繁使用。这会导致过多的缓存缺失。因此，缓存的设计是在低相联度（查找快）与高相联度（减少缓存缺失）之间寻求折中。
在大多数现代 CPU 中，缓存通常是 2 路、4 路或 8 路相联的。再更高的相联度，查找条目的开销会超过减少缓存缺失带来的微小收益。
Optimizing Cache Efficiency（优化缓存效率）
在现代计算机中，CPU 非常快，而 RAM 仅仅是“够快”。如果软件能够高效使用缓存，缓存可以显著提升性能；但如果软件不能高效利用缓存，那么缓存对性能的帮助就不大。下面是提高缓存效率时可以使用的几种技术。
Cache Blocking（缓存分块）
第一种技术在介绍部分已经提到 —— 如果可能，将大量数据拆分为能够放入缓存的小块，以避免缓存抖动。要做到这一点，你需要知道缓存的大小，以及有多少 CPU 在共享这些缓存。
Page Colouring（页面着色）
下一种技术称为“页面着色”（page colouring）或“缓存着色”（cache colouring）。使用分页的系统可以选择物理页，以最小化低相联度导致的缓存缺失概率。
考虑一个 4 MiB、4 路相联的缓存，假设某进程特别倒霉，它使用的每个页面恰好对应缓存中每个集合的相同位置。在这种情况下，该进程只能使用缓存中的 16 KiB，而其余 99.6% 的缓存都被浪费。当然，这是用于说明问题的极端不太可能的情况 —— 实际上，这类问题通常只会导致缓存效率略微下降。关键在于，没有页面着色时，操作系统只能依赖概率，希望缓存效率不会太差。另外，这还可能导致非确定性性能（例如软件运行速度取决于运气），这是不可取的（特别是在实时系统中）。
页面着色的思想是确保页面被分配时，尽可能降低缓存效率受影响的概率。为此，操作系统会确定物理地址中哪些位会影响缓存行在各集合中的位置；然后确保虚拟地址中的对应位与物理地址中的这些位一致。然而，这可能带来额外问题：通常某些虚拟地址比其他地址更常用（例如某操作系统可能将所有进程加载到虚拟地址 0x00001000）；这意味着操作系统可能会耗尽与这些虚拟地址匹配的物理页。为避免这个问题，OS 可以在给不同进程分配物理页前，为进程的虚拟地址添加不同的偏移量。
要使页面着色工作，你需要知道缓存中每个集合的大小。这可以通过用缓存总大小除以缓存的相联度得到。
Preventing Unnecessary Caching（避免不必要的缓存）
在某些情况下，软件可能要访问大量数据，而程序员知道这些数据要么不会再被使用，要么不会很快再次被使用。在这种情况下，你可以通过显式刷新缓存行（例如 x86 的 “CLFLUSH” 指令）来提升缓存效率，为更重要的数据释放缓存条目。
一些 CPU 允许基于页面禁用缓存。在某些情况下，这个特性可以避免软件手动刷新缓存行。
Prefetching（预取）
在某些情况下，很容易预测哪些缓存行即将被使用。在这种情况下，一些 CPU 允许程序员明确请求将数据加载到缓存中（预取），以避免缓存缺失。
此外，一些 CPU 会自动检测某些访问模式（例如连续递增或连续递减的地址访问），并自动执行缓存预取。
Scheduling With Multiple CPUs（多 CPU 调度）
对于拥有多个 CPU 的计算机，当一个任务运行时，它的代码和数据会进入其运行所在 CPU 的缓存中。下次调度器再次为该任务分配 CPU 时间时，该任务的一些代码和数据可能仍在某个 CPU 的缓存中；通过让任务运行在它上次运行的同一 CPU 上，可以避免一些缓存缺失。由于操作系统的调度器还需要考虑许多其他因素（如性能、电源管理等），所以不应始终强制这样做 —— 更合理的方式是将其视为一种调度“提示”。
对于多层缓存、不同缓存被不同 CPU 共享的复杂系统，如果调度器无法将任务安排在其上次使用的 CPU 上，那么选择与之前使用的 CPU 共享缓存的 CPU，会比选择不共享缓存的 CPU 更佳。