Cache命中率一算就错？从局部性原理到替换算法

Cache的概念与存储层次

计算机系统中存在一个根本矛盾：CPU处理速度极快，而主存访问速度相对缓慢。典型现代计算机的CPU时钟周期已进入纳秒级别，DRAM主存的访问延迟却在数十到上百纳秒之间。这种速度落差被称为"存储墙"，严重制约计算机整体性能的发挥。

Cache（高速缓冲存储器）正是为解决这一矛盾而设计的关键部件。它是一种容量小但速度极快的存储器，位于CPU和主存之间，临时存放CPU近期可能频繁访问的指令和数据。Cache通常由SRAM（静态随机存取存储器）构成，SRAM存取速度远优于DRAM，但集成度低、功耗大、成本高，这直接约束了Cache的容量上限。典型的一级Cache容量在三十二KB到六十四KB之间，二级Cache在二百五十六KB到五百一十二KB之间，三级Cache可达数MB。

从存储层次的整体视角来看，现代计算机采用金字塔式的存储体系：最顶层是CPU内部寄存器，速度最快、容量最小；向下一层是Cache，再往下是主存，然后才是固态硬盘或机械硬盘等外部存储。每一层都充当下一层的"高速缓存"，越靠近CPU的层次速度越快、容量越小、单位成本越高。整个存储层次有效运作的根基是局部性原理：大部分访问在高层命中，少量缺失到低层补齐。在软考体系架构设计师和系统分析师考试中，Cache几乎年年必考，涉及命中率计算、映射方式识别、替换算法选择和写策略判断等多个维度，融合了计算、判断和推理多种考查形式，区分度较高。

存储层次的核心参数

评估存储层次性能有三个关键指标：命中时间、缺失代价和命中率。命中时间是CPU访问Cache且命中时的耗时，通常为一到两个时钟周期。缺失代价是Cache未命中时从下一级存储读取并传输数据到CPU的总耗时，可达数十到数百个时钟周期。命中率是CPU访问Cache时命中的概率。

三者的数学关系为：平均访问时间等于命中时间加上缺失率乘以缺失代价。这个公式揭示了一个关键洞察：即使命中率高达百分之九十九，如果缺失代价极大，平均访问时间仍然可能很高。软考命题频繁围绕此公式设计计算题——给定命中时间、缺失代价和命中率求平均访问时间，或给定目标平均访问时间反推所需最小命中率。

局部性原理：Cache为什么能提速

局部性原理是Cache能够显著提升性能的理论根基。如果程序完全随机访问存储空间，Cache中预取的数据将毫无用处，命中率趋近于零。局部性原理分为时间局部性和空间局部性两个维度，二者共同决定了Cache的块大小、关联度和替换策略等核心参数。

时间局部性指：如果某个存储单元被访问，不久的将来它很可能被再次访问。最典型的例子是循环结构——循环体代码被反复执行，循环控制变量被反复读写。Cache利用时间局部性将最近访问过的数据保留在SRAM单元中，CPU再次访问时直接从Cache获取，避免等待缓慢的主存。从硬件视角看，时间局部性的价值在于只需将热数据保持在Cache中，即可在多个时钟周期内不断命中，大幅摊薄初次访问的缺失代价。

空间局部性指：如果某个存储单元被访问，它附近的存储单元也很可能在近期被访问。这源于程序的顺序执行特性——指令顺序存放，数据常以数组或结构体形式连续存储。例如遍历整型数组时，访问a[i]后通常会接着访问a[i+1]，二者在内存中恰好相邻。Cache利用空间局部性，在读取某个地址的数据时，将其附近一整个块的数据一并读入。

两种局部性在不同程序中表现各异。科学计算程序具有较强的空间局部性，因为大量处理连续存储的数组和矩阵。数据库事务处理程序则表现出更强的时间局部性，因为频繁访问索引结构中的热数据页。软考命题偶尔要求判断代码片段的局部性类型，或分析访问模式对命中率的影响。

块大小的设计权衡

Cache将存储空间划分为固定大小的块，每块通常为三十二字节或六十四字节。当CPU访问的地址不在Cache中时，Cache控制器从主存读取包含该地址的整个块——这种"多读一点"的策略正是利用空间局部性。块太小，空间局部性利用不充分，相邻数据未被预取，后续访问容易再次缺失。块太大，会引入不必要的数据占用宝贵的Cache空间，挤压热数据的生存空间，同时单次缺失的延迟惩罚也更大。一级Cache的块通常较小以控制缺失时间，最后一级Cache的块可以较大以充分挖掘空间局部性收益。软考偶尔涉及块大小与命中率关系的定性判断，核心思想是"过犹不及"。

三种地址映射方式深度对比

CPU发出访存请求时给出的是主存地址，Cache控制器需要将主存地址映射到Cache中的某个位置——这就是地址映射要解决的核心问题。根据映射的灵活程度，Cache分为三种基本组织方式：直接映射、全相联映射和组相联映射。三种方式的本质区别在于：主存中的一个块可以放入Cache中的哪些位置。这一区别直接决定了硬件复杂度、访问延迟和冲突缺失率。

直接映射是最简单的方式。主存地址空间按Cache容量划分为若干区，每个区内相同偏移位置的块只能映射到Cache中唯一对应的行。主存地址被划分为标记、行号和块内偏移三个字段——行号直接决定块在Cache中的位置，标记用于区分不同区的同名块。直接映射的硬件实现最简洁，比较器只需一个，但冲突缺失率极高：如果程序频繁交替访问映射到同一Cache行的两个不同地址，就会发生"抖动"，每次访问都把对方替换出去，命中率剧烈下降。

全相联映射是另一个极端。主存中任意一个块可以放入Cache中任意一个位置，地址仅包含标记和块内偏移两个字段。访问时需要将标记与Cache中所有行的标记同时进行并行比较，需要一个大规模比较器阵列。全相联映射的冲突缺失率最低，但硬件成本极高且比较延迟大，通常仅用于TLB或极小容量的一级指令Cache。

组相联映射是前两者的折中，也是实际处理器中最常用的组织方式。Cache被划分为若干组，每组内包含若干行——通常为两路、四路或八路，分别称为两路组相联、四路组相联等。地址被划分为标记、组索引和块内偏移三个字段。组索引决定属于哪一组（直接映射逻辑），组内位置则采用全相联方式（可放入组内任意一行）。组相联用较小的并行比较器阵列换取了接近全相联的灵活性——组内路数越多，冲突缺失率越低，硬件也越复杂。

地址字段的位宽计算

理解三种映射的关键是看懂地址字段划分。在直接映射中，地址分为标记、行号、块内偏移，行号位数等于以二为底Cache行数的对数。在全相联映射中，地址分为标记和块内偏移，标记位数等于以二为底主存总块数的对数。组相联映射中，行号替换为组索引，组索引位数等于以二为底组数的对数，组数等于Cache总行数除以每组路数。

软考中常见题型：给定主存地址位数、Cache容量和块大小，求三种映射方式下标记、索引和偏移各占多少位。解题关键是块内偏移位数由块大小决定，与映射方式无关；行号或组索引位数由Cache的槽位数量决定；标记位数用地址总位数减去其余部分。例如主存地址三十二位，Cache六十四KB，块大小十六字节（偏移需四位），直接映射共四千零九十六行（索引需十二位），标记为三十二减十二减四得十六位。同一Cache改为四路组相联，组数为一千零二十四组，组索引需十位，标记变为十八位。

替换算法与写策略

当Cache已满需调入新块时，必须选择一个现有块替换出去。替换算法的选择直接影响命中率，软考主要考查三种：随机替换、先进先出和最近最少使用。

随机替换最为简单，用伪随机数发生器选取替换目标，硬件成本极低但无法利用局部性信息，命中率不理想。先进先出记录每个块的进入顺序，替换最早进入的块。它比随机替换略好，但存在致命缺陷：一个块即使被频繁访问，只要"资历够老"就会被替换，无视实际使用热度。最近最少使用（LRU）跟踪每个块的访问历史，替换最长时间未被访问的块——这完美契合时间局部性原理：最近被访问的块很快可能再次被访问，最久未用的块未来被访问概率最低。LRU命中率在多数场景下优于另两种算法，但硬件成本较高，需为每行维护计数器记录访问顺序。两路组相联时LRU可简化为每行一个使用位——访问某行时将其置一，替换时选择使用位为零的行。

写直达与写回的策略

本篇完！