408 计算机组成原理高频考点精讲:Cache基本概念与局部性原理¶
- 模块归属:存储系统(Storage System)/ 高速缓冲存储器(Cache)
- 考点层级:核心必考点(考频星级:5星)
- 适用对象:全国硕士研究生统一考试 计算机学科专业基础综合(408)备考考生
一、考情档案¶
1. 考频统计与出题形式¶
在 408 计算机学科专业基础综合统考中,Cache 既是计算机组成原理考查的绝对重心,也是连接操作系统、计算机系统结构的核心纽带。 近十年(2016~2025年)在“Cache基本概念”子考点上直接命题 5 次;自 2009 年统考设立以来,累计直接考查达 12 次。
出题形式覆盖两类题型: 1. 单项选择题(每题 2 分):侧重考查程序局部性判断、Cache 命中率计算、Cache/TLB 介质与硬件机制辨析。 2. 综合应用题(43 题或 45 题,单题分值 2~8 分):常将 Cache 与虚拟存储系统(TLB、页表、物理内存)、指令流水线、C 语言多层嵌套循环数组访问深度融合,考查系统级访存性能评估与软硬件协同设计。
2. 命题特点提炼¶
- 软件语义与硬件机制强联动:考题常给出一段 C 语言数组遍历循环,要求考生从底层物理存储映射、Cache 块大小、按行/列展开等细节出发,精准判定其时间局部性与空间局部性,并精确计算访问缺失率。
- 层次结构指标建模严谨:深度考查平均访存时间(AMAT)、加速比、命中率的数学推导,尤其注重区分串行层次访问模型与并行访问模型的物理实现差异。
- 写策略与硬件开销对比考查:深入考查写直达法(Write-Through)与写回法(Write-Back)、写分配法(Write-Allocate)与非写分配法(Not-Write-Allocate)的时序性能、总线负载差异,以及脏位(Dirty Bit)的硬件开销。
- 跨层次存储机制辨析:对比 Cache 缺失(纯硬件响应、微秒/纳秒级延迟)与缺页异常(操作系统软硬件协同中断处理、毫秒级磁盘 I/O 延迟),揭示计算机分层存储体系的设计精髓。
3. 2016~2025 年近十年考查年份分布图¶
========================================================================================================
年份 题号及分值 考查题型 核心考查内容
--------------------------------------------------------------------------------------------------------
2016 年 第 15 题 (2分) 单项选择题 数组循环累加中的连续读写访问时序与 Cache 缺失率计算
2016 年 第 45 题 (4分) 综合应用题 Cache 缺失与缺页异常时间开销对比;写直达与写回策略选用机理
2017 年 第 14 题 (2分) 单项选择题 双重嵌套循环展开下数组访问的时间局部性与空间局部性判定
2020 年 第 15 题 (2分) 单项选择题 TLB 与 Cache 的硬件介质构成(SRAM/DRAM)及缺失处理机制辨析
2023 年 第 43 题 (6分) 综合应用题 循环遍历维度调换对工作集 Cache 局部性与命中率的影响深度解析
========================================================================================================
二、具体考察内容¶
1. Cache 工作原理与硬件架构¶
(1) 存储体系面临的核心矛盾:存储墙(Memory Wall)¶
现代计算机系统中,CPU 运算器与寄存器的访问延迟通常小于 1 个时钟周期(亚纳秒级,Sub-nanosecond),而主存(动态随机存储器 DRAM)的访问延迟通常在数十至数百纳秒(50~100 ns)。CPU 运算速度与 DRAM 访存延迟之间存在数个数量级的性能差距,此现象被称为“存储墙”。 为了缓解 CPU 的高速运算能力与主存的慢速访问之间的速度脱节,在 CPU 与主存之间引入了高速缓冲存储器(Cache)。
(2) Cache 的透明性原则¶
Cache 处于存储体系的 CPU-主存层级之间。在软硬件界面划分上: - Cache 对程序员(包含系统级程序员与应用程序员)完全透明:无论是编写操作系统内核还是编写用户态应用程序,程序员在逻辑上均面向统一的线性编址物理空间(或虚拟地址空间),无法通过专门的汇编指令对 Cache 行进行直接寻址读写。 - 数据在 Cache 与主存之间的调度、替换、标记比对与内容同步,全部由专门的硬件控制器(Cache Controller)自主完成。
(3) Cache 行(Cache Line / Block)物理构成¶
Cache 内部被划分为若干大小相等的存储单元,称为 Cache 行(Cache Line)或 Cache 块(Cache Block)。每个 Cache 行由控制字段与数据区组成: 1. 有效位(Valid Bit, 1 位):用于标记该行内的数据是否有效。计算机开机冷启动或进程切换上下文刷新 Cache 时,所有有效位被置为 0;当对应主存块被调入该行后,有效位置为 1。 2. 脏位 / 修改位(Dirty Bit / Modified Bit, 1 位):仅在采用写回法(Write-Back)策略的 Cache 中存在。若为 1,表示该 Cache 行被 CPU 写入修改过,其内容已与对应主存块不一致,被替换时必须写回主存;若为 0,表示该行未被修改,与主存内容完全一致,替换时直接覆盖即可。 3. 标记位(Tag Bit, \(t\) 位):保存主存物理地址的高位标记,用于与 CPU 访存请求的地址标记进行比对,以判定是否命中。 4. 替换控制位(Replacement Bits):在组相联或全相联 Cache 中,用于记录行使用历史(如 LRU 计数器)。 5. 数据区(Data Field, \(B = 2^b\) 字节):存放从主存整块载入的有效指令或数据内容,大小通常为 16B、32B、64B 或 128B。
+----------+------------+--------------------+------------------------+-------------------------------+
| 有效位(1b)| 脏位(0/1b) | 替换控制位(如LRU) | 标记字段 Tag ($t$$ \text{位) | 数据块区 Data Block (} $$B$ 字节) |
+----------+------------+--------------------+------------------------+-------------------------------+
2. 程序局部性原理(Principle of Locality)¶
程序局部性是 Cache 能够以极小容量(数 KB 至数十 MB)支撑整个系统获得接近 SRAM 高速特性的理论基石。局部性分为时间局部性与空间局部性。
(1) 时间局部性(Temporal Locality)¶
- 定义:程序中某一条指令或某一数据单元一旦被访问,在不久的将来极可能再次被访问。
- 产生机理:程序代码中存在大量的循环迭代结构、递归调用、公共子函数以及循环控制计数器(如
for(i=0;...)中的变量i)、累加求和变量等。 - 硬件映射与利用:利用 Cache 存储近期被访问的数据或指令副本;当 Cache 空间不足时,采用替换算法(如近期最少使用算法 LRU)淘汰最久未被访问的行,最大限度保留处于活跃复用期的数据。
(2) 空间局部性(Spatial Locality)¶
- 定义:一旦程序访问了某一存储单元,在不久的将来,与其物理地址相邻或临近的存储单元极可能被访问。
- 产生机理:
- 指令流按顺序依次执行,存储在连续的代码段地址中。
- 数组、结构体、向量等聚合数据结构在物理内存中呈线性连续存放,程序常以步长(Stride)为 1 的方式顺序遍历访问。
- 硬件映射与利用:Cache 与主存之间以“数据块(Cache Block)”为基本传输粒度,而非单字节或单字。当 CPU 访问某一字发生缺失时,硬件控制器一次性将包含该字的整个主存块批量调入 Cache,使得随后对其相邻单元的顺序访问均能直接命中。
(3) 局部性劣化典型场景剖析¶
- 跨大步长访问:当数组遍历步长 \(S\)$ \text{明显大于 Cache 块大小} $\(B\)$ \text{(如以步长} $\(S = 4096\text{ B}\) 访问),每次访问都会落在全新的主存块内,导致空间局部性完全失效。
- 指针链表无序离散跳跃:在堆空间频繁动态分配节点构成的链表,逻辑上连续而物理地址分散,无法获得空间局部性红利。
- 随机哈希探测与超大工作集乱序读写:工作集规模超出 Cache 物理容量,引发严重的抖动(Thrashing)。
3. Cache 命中率与平均访存时间(AMAT)数学模型¶
(1) 命中率与缺失率定义¶
设系统在某段时间内的总访存请求次数为 \(N\)$ \text{,其中在 Cache 中成功命中的次数为} $\(N_c\)$ \text{,缺失并转由主存处理的次数为} $\(N_m\)(\(N = N_c + N_m\))。 - 命中率(Hit Rate, \(h\)): $\(h = \frac{N_c}{N_c + N_m} = \frac{N_c}{N}\)$ - 缺失率(Miss Rate, \(M\)): $\(M = 1 - h = \frac{N_m}{N_c + N_m} = \frac{N_m}{N}\)$
(2) 平均访存时间(AMAT, Average Memory Access Time)推导¶
设 Cache 单次存取时间为 \(t_c\)$ \text{,主存单次存取时间为} $\(t_m\)。根据 CPU 与 Cache/主存控制器的硬件连接与访问流水架构,AMAT 分为两种理论模型:
模型一:并行访问模型(Parallel Access Architecture)¶
CPU 发出访存地址的同时,向 Cache 和主存控制器同时启动访问请求。 - 若 Cache 命中(概率为 \(h\)$ \text{),主存访问流程被硬件中止,访存开销为} $\(t_c\)。 - 若 Cache 缺失(概率为 \(1 - h\)$ \text{),主存继续完成数据读取并送达 CPU,访存开销为} $\(t_m\)。 - 平均访存时间公式: $\(\text{AMAT}_{\text{parallel}} = h \cdot t_c + (1 - h) \cdot t_m\)$
模型二:串行层次访问模型(Serial / Hierarchical Architecture)¶
CPU 发出访存请求后,先由 Cache 进行地址匹配。 - 若 Cache 命中(概率为 \(h\)$ \text{),耗时为} $\(t_c\)。 - 若 Cache 缺失(概率为 \(1 - h\)$ \text{),判定缺失耗时} $\(t_c\)$ \text{,随后启动主存访问,产生额外的缺失损失(Miss Penalty)} $\(t_m\)$ \text{,总耗时为} $\(t_c + t_m\)。 - 平均访存时间公式: $\(\text{AMAT}_{\text{serial}} = h \cdot t_c + (1 - h) \cdot (t_c + t_m) = t_c + (1 - h) \cdot t_m\)$
408 考场研判准则: 在 408 试题中,若题干明确指明“同时访问 Cache 和主存”或给出“Cache 命中耗时 \(t_c\)$ \text{,缺失耗时} $\(t_m\)$ \text{”,采用并行模型公式;若题干明确指明“先访问 Cache,缺失后再访问主存”或给出“缺失损失 Miss Penalty 为} $\(t_m\)”,则严格采用串行模型公式。若无特殊说明且两者并存,应结合选项数值进行反向检验或注明前提。
(3) 性能加速比与效率¶
- 访存加速比(Speedup, \(S\)):引入 Cache 后访存系统相对纯主存系统的加速倍数: $\(S = \frac{t_m}{\text{AMAT}}\)$
- 存储系统效率(Efficiency, \(e\)): $\(e = \frac{t_c}{\text{AMAT}} \times 100\%\)$ 当命中率 \(h \to 1\)$ \text{时,} $\(\text{AMAT} \to t_c\),\(e \to 100\%\),系统整体性能逼近 SRAM 的极致速度。
4. Cache 写策略(Write Policy)深度解剖¶
由于写操作会改变存储单元的内容,如何保证 Cache 与主存数据的一致性,是存储系统控制器的核心挑战。
(1) 写命中时的处理策略¶
写直达法 / 全写法(Write-Through)¶
- 工作机制:当写操作在 Cache 中命中时,CPU 同时将数据写入 Cache 和主存。
- 优点:实现简单,Cache 与主存的内容在任何时刻均保持严格一致。无需设置脏位(Dirty Bit)。某一行被替换时直接丢弃,无须写回主存。
- 缺点:由于每次写命中都必须访问慢速主存,写操作的整体执行时间受制于主存周期,大幅增加了存储总线上的写流量。
- 硬件优化:写缓冲(Write Buffer)。 CPU 将数据写入 Cache 和一个容量较小的 FIFO 写缓冲寄存器队列后,立即继续执行后续指令;写缓冲在后台自主将数据写入主存。仅当写缓冲满时,CPU 才被迫停顿等待。
写回法(Write-Back)¶
- 工作机制:当写操作在 Cache 中命中时,仅将数据写入 Cache,并不立即写入主存;同时将该 Cache 行的“脏位(Dirty Bit)”置为 1。仅当该行后续因为冲突或容量不足被替换算法驱逐时,硬件才检查脏位:若脏位为 1,则将其整块内容写回主存;若脏位为 0,则直接丢弃。
- 优点:极大降低了总线写事务频率。在某一 Cache 块被频繁读写修改(如循环局部变量)的场景下,数千次写操作仅需在被替换时产生 1 次主存写回,性能显著高于写直达法。
- 缺点:主存数据存在滞后性,Cache 与主存之间存在瞬时数据不一致,系统掉电或支持 DMA 访问时需严格的一致性维护逻辑;每个 Cache 行必须额外配置 1 位脏位。
(2) 写缺失时的处理策略¶
写分配法(Write-Allocate)¶
- 工作机制:当写操作发生 Cache 缺失时,硬件控制器先将主存中包含目标字的整个数据块调入 Cache,然后在 Cache 中对目标字执行写操作。
- 适用搭配:通常与写回法(Write-Back)结合使用。因为被调入的数据块很可能会被后续连续写入,调入后即可在 Cache 中享受写回法的高速读写优势。
非写分配法(Not-Write-Allocate)¶
- 工作机制:当写操作发生 Cache 缺失时,直接将数据写入主存,并不把对应的主存块调入 Cache。
- 适用搭配:通常与写直达法(Write-Through)结合使用。避免了在写缺失时为了写入极少数字节而耗费昂贵总线周期去载入整个主存块。
(3) 四大写策略组合对比矩阵¶
| 特性维度 | 写回法 + 写分配法 (Write-Back + Write-Allocate) | 写直达法 + 非写分配法 (Write-Through + Not-Write-Allocate) |
|---|---|---|
| 写命中行为 | 仅写入 Cache,脏位置 1 | 同时写入 Cache 和主存(或写缓冲) |
| 写缺失行为 | 从主存调块入 Cache,再写入 Cache | 直接写入主存,不调块入 Cache |
| 脏位(Dirty Bit) | 必须配置(每行 1 位) | 不需要配置 |
| 总线写带宽占用 | 极低(仅替换脏行时产生总线块写传输) | 极高(每次写指令均产生总线写事务) |
| 数据一致性 | 存在暂态不一致,依赖脏位写回同步 | Cache 与主存数据始终保持强一致 |
| 典型应用场景 | 现代主流高性能处理器的 L1/L2/L3 数据 Cache | 对电路面积敏感的简易嵌入式核心、显存写透体系 |
(4) 为什么虚拟存储器(主存-外存层次)必须采用写回法?¶
在虚拟页式存储系统中,主存相当于外存(磁盘/SSD)的“Cache”。 - Cache-主存层级中,主存读写耗时约 50~100 ns,Cache 约 1~5 ns,速度差距约为 10~100 倍。若采用写直达法,借助写缓冲仍可勉强维系系统运转。 - 主存-外存层级中,主存访问耗时约为数十纳秒,而机械磁盘寻道及数据传输耗时在毫秒(ms)级别,固态硬盘在微秒(\(\mu\text{s}\)$ \text{)级别,速度差距高达} $\(10^5 \sim 10^6\) 倍。 若虚拟存储器采用写直达法,CPU 每次执行内存写指令都必须同步等待磁盘 I/O 完成,系统吞吐量将产生毁灭性下跌。因此,虚拟存储器在修改页面时只能且必须采用写回法(Write-Back),并在页表项中配置修改位(Dirty Bit),仅在页面被置换算法淘汰出内存时才写回外存交换区。
5. 多级 Cache 层次结构与局部/全局缺失率¶
现代高性能处理器普遍采用分层的多级 Cache 架构(通常为 L1、L2、L3 三级): 1. L1 Cache:片内核心私有。通常划分为独立的指令 Cache(I-Cache)与数据 Cache(D-Cache)。物理容量较小(如 32KB~64KB),访问周期仅 1~4 个时钟周期。哈佛结构的物理隔离有效避免了流水线在取指(IF)与访存(MEM)阶段的结构冲突(Structural Hazard)。 2. L2 Cache:片内核心私有或局部共享,容量适中(如 512KB~2MB),统一存放指令和数据,访问周期约 10~20 个时钟周期。 3. L3 Cache:片内多核共享(LLC, Last Level Cache),容量庞大(如 16MB~64MB),统一存放指令和数据,访问周期约 40~80 个时钟周期。
(1) 局部缺失率与全局缺失率¶
- 局部缺失率(Local Miss Rate):某一级 Cache 的未命中次数占输入到该级 Cache 的总请求次数的比例。 $\(M_{L1} = 1 - h_1, \quad M_{L2} = 1 - h_2\)$
- 全局缺失率(Global Miss Rate):某一级 Cache 的未命中次数占 CPU 发出的总体访存请求总次数的比例。 $\(\text{Global Miss Rate}_{L1} = M_{L1} = 1 - h_1\)$ $\(\text{Global Miss Rate}_{L2} = M_{L1} \times M_{L2} = (1 - h_1)(1 - h_2)\)$
(2) 两级 Cache 的 AMAT 计算公式¶
$$\text{AMAT} = t_{L1} + M_{L1} \times \left( t_{L2} + M_{L2} \times t_m \right) = t_{L1} + (1
-
h_1) \cdot t_{L2} + (1
-
h_1)(1
-
h_2) \cdot t_m$$
6. 常见陷阱与易错辨析¶
辨析 1:指令 Cache 为什么通常不需要脏位(Dirty Bit)?¶
指令代码段在程序执行过程中通常是只读的(自修改代码在现代操作系统与硬件架构下受到严格保护并引发异常),CPU 执行指令只涉及读操作,绝不会写入修改指令 Cache,因此指令 Cache 行不需要脏位,其写策略逻辑大幅简化。
辨析 2:Cache 行三类缺失(3C 模型)的成因与消除手段¶
- 强制缺失(Compulsory Miss / Cold Miss):该数据块从未被访问过,初次装入 Cache 时必然发生的冷启动缺失。
- 缓解手段:适当增大主存块大小(利用空间局部性提前预取相邻字),或采用硬件预取技术。
- 容量缺失(Capacity Miss):Cache 总容量有限,无法完整容纳程序在某一时段内的工作集(Working Set),淘汰后再被访问引发的缺失。
- 缓解手段:直接增大 Cache 总容量。
- 冲突缺失(Conflict Miss):在直接映射或组相联映射中,多个主存块争夺同一个组(Set)中的有效行导致的缺失。
- 缓解手段:提高组相联度(Way-associativity),极端情况下采用全相联映射可彻底消除冲突缺失。
辨析 3:TLB 与 Cache 的硬件物理介质本质¶
- Cache 由高速度、双稳态触发器构成的静态随机存储器(SRAM)实现,集成在 CPU 芯片内部。
- TLB(翻译后备缓冲器/快表)存储虚拟页号到物理页框号的映射表项,对查询延迟要求极高,通常由相联存储器(CAM, Content Addressable Memory)或高速 SRAM 构成。
- 动态随机存储器(DRAM)利用电容存储电荷,读取具有破坏性且电荷随时间泄漏,必须持续进行动态刷新,速度较慢,仅用作大容量物理主存,绝不可能用于制造 Cache 或 TLB。
三、近十年真题精讲(2016~2025)¶
1. 2016 年 408 统考真题第 15 题¶
【考查方向】¶
循环累加中的连续读写访问时序与 Cache 缺失率计算。
【题干与选项】¶
有如下 C 语言程序段:
若数组a 以及变量 k 均为 int 型,int 型数据占 4B,数据 Cache 采用直接映射方式,数据区大小是 1KB,块大小是 16B,该程序段执行前 Cache 为空,则该程序段执行过程中,访问数组 a 的 Cache 的缺失率是( )。
A. 1.25%B. 2.5%
C. 12.5%
D. 25%
【详细解析】¶
- 程序访存行为分解:
分析赋值语句
a[k] = a[k] + 32。在每一次循环迭代中,CPU 针对数组元素a[k]包含两次内存访问操作: - 第一次操作:读取
a[k]的值,属于读操作; -
第二次操作:将加 32 后的计算结果写回
a[k],属于写操作。 因此,循环 1000 次,CPU 针对数组a共发起 \(1000 \times 2 = 2000\) 次访存请求。 -
数据块容量与元素分布: Cache 块大小为 16B,数组元素为 4B 的
int型。 因此,每个 Cache 块恰好容纳: $$ \text{\frac{16\text{ B}}{4\text{ B}} = 4\text{ 个数组元素}} $$ 例如,第 0 块容纳a[0], a[1], a[2], a[3];第 1 块容纳a[4], a[5], a[6], a[7],以此类推。 -
Cache 命中与缺失详细轨迹追踪: 以第 0 个数据块(存放
a[0] ~ a[3])为例: - \(k=0\) 时:
- 读
a[0]:初始 Cache 为空,发生冷缺失(Miss)。硬件控制器从主存将包含a[0] ~ a[3]的整个 16B 主存块调入 Cache 对应行。 - 写
a[0]:由于该块已在读操作中调入 Cache,写操作直接命中(Hit)。
- 读
- \(k=1\) 时:
- 读
a[1]:a[1]已经在当前 Cache 块中,命中(Hit)。 - 写
a[1]:命中(Hit)。
- 读
- \(k=2\) 时:
- 读
a[2]:命中(Hit)。 - 写
a[2]:命中(Hit)。
- 读
-
\(k=3\) 时:
- 读
a[3]:命中(Hit)。 - 写
a[3]:命中(Hit)。
- 读
-
缺失率量化推导: 对于每个数据块中的 4 个连续整型元素,CPU 总共产生 4 次读和 4 次写,合计 8 次访存请求。 在这 8 次访问中,仅在第一次读取第一个元素时发生 1 次 Cache 缺失,其余 7 次访问全部命中! 由于数组
a在单重循环中是严格线性单向顺序访问,后续元素不会回头映射冲突驱逐刚刚访问完的块(虽然 Cache 数据区为 1KB 容纳 64 块,数组需 250 块,循环覆盖但由于无复用,不影响前向遍历的缺失模式)。 因此,访问数组a的整体 Cache 缺失率为: $\(\text{Miss Rate} = \frac{1}{8} = 12.5\%\)$
【干扰项剖析】¶
- 误选 D(25%):忽略了赋值语句先读后写的两次访存特性,误以为每个元素只访问 1 次(每个块 4 次访问,缺失 1 次,即 \(1/4 = 25\%\))。
- 误选 B(2.5%)或 A(1.25%):混淆了总块数与命中率计算,算错块内元素容量。
【正确答案】¶
C
2. 2016 年 408 统考真题第 45 题¶
【考查方向】¶
虚拟存储系统与 Cache 的联合架构、缺失处理开销对比、写策略选择机理。
【题干与设问】¶
某计算机采用页式虚拟存储管理方式,按字节编址,虚拟地址为 32 位,物理地址为 24 位,页大小为 8KB;TLB 采用全相联映射;Cache 数据区大小为 64KB,按 2 路组相联方式组织,主存块大小为 64B。存储访问过程的示意图如下。
虚拟地址 [ A 位 ] [ D 位 ]
| 虚页号 | 页内偏移 |
|
+-----+-----+
| |
v v
[ TLB查询 ] [ 页表查询 ]
标记B|页框号C
|
+---> 拼接形成物理地址: [ 页框号 C (11位) ] [ 页内偏移 D (13位) ]
\_________________________/
|
v
物理地址划分为: [ Cache Tag E ] [ Cache 组号 F ] [ 块内地址 G ]
| | |
v v v
[ Tag 比较器 ] [ 组索引解码 ] [ 数据区定位 ]
请回答下列问题。 (1) 图中字段 A~G 的位数各是多少?TLB 标记字段 B 中存放的是什么信息? (2) 将块号为 4099 的主存块装入到 Cache 中时,所映射的 Cache 组号是多少?对应的 H 字段内容是什么? (3) Cache 缺失处理的时间开销大还是缺页处理的时间开销大?为什么? (4) 为什么 Cache 可以采用直写(Write Through)策略,而修改页面内容时总是采用回写(Write Back)策略?
【详细解析】¶
针对第 (1) 问:¶
- 页大小为 8KB = \(2^{13}\text{ B}\)$ \text{,故页内偏移字段} $\(D = 13\) 位。
- 虚拟地址为 32 位,虚页号字段 \(A = 32 - 13 = 19\) 位。
- TLB 采用全相联映射,TLB 标记必须保存完整的虚页号用于并发检索,故 \(B = A = 19\) 位。
- 物理地址为 24 位,物理页框号字段 \(C = 24 - 13 = 11\) 位。
- 主存块大小为 64B = \(2^6\text{ B}\)$ \text{,故 Cache 块内地址字段} $\(G = 6\) 位。
- Cache 数据区大小为 64KB,按 2 路组相联组织,每组容量为 \(2 \times 64\text{ B} = 128\text{ B}\)。
- Cache 组数 \(= \frac{64\text{ KB}}{128\text{ B}} = 512\)$ \text{组} $\(= 2^9\)$ \text{,故 Cache 组号字段} $\(F = 9\) 位。
-
物理地址高位为 Cache 标记 Tag,字段 $E = 24
-
F
-
G = 24
-
9
-
6 = 9$ 位。
- TLB 标记字段 B 中存放的是虚拟页号(虚页号),用于标识该 TLB 项对应哪一个虚拟页的物理映射信息。
针对第 (2) 问:¶
主存块号为 4099。将十进制数 4099 转换为二进制: $\(4099 = 4096 + 2 + 1 = 2^{12} + 2^1 + 2^0 = 0001\_0000\_0000\_0011_B\)$ 物理地址中,块号由 Tag(高 9 位)与 Cache 组号(低 9 位)拼接而成。 提取主存块号的低 9 位作为 Cache 组号: $$ \text{组号} = 4099 \pmod{512} = 3 = 000000011_B $$ 提取主存块号的高 9 位(即右移 9 位:\(4099 \gg 9\))作为 Tag 字段(即 H 字段内容): $\(H = \lfloor 4099 / 512 \rfloor = 8 = 000001000_B\)$
针对第 (3) 问(考点核心):¶
缺页处理的时间开销远大于 Cache 缺失处理的时间开销。 - 原因一(存储介质与访问延迟差异): Cache 缺失时,访问的目标介质是主存(DRAM),延迟通常在几十纳秒到上百纳秒(\(\sim 10^{-7}\text{ s}\)$ \text{)量级;而缺页异常发生时,目标页面存放在辅助存储器(机械硬盘或固态硬盘)中,磁盘 I/O 涉及机械寻道、旋转等待或闪存块擦写,延迟在毫秒或微秒量级(} $\(\sim 10^{-3}\text{ s}\))。两者延迟差距高达数万至数十万倍。 - 原因二(处理主体与实现层次差异): Cache 缺失完全由纯硬件控制器自动完成主存块的读取与装载,CPU 不需要中断流水线上下文;而缺页处理属于操作系统的缺页异常中断,需要保护现场、由内核陷入(Trap)处理程序执行 I/O 调度、进程挂起置换,开销极其庞大。
针对第 (4) 问(考点核心):¶
- Cache 可以采用直写(Write-Through)策略的原因: Cache 的下一级存储层次是主存。写直达法虽然每次都需要写主存,但主存访问速度较快(纳秒级),且硬件上可以引入写缓冲(Write Buffer)来解耦 CPU 与主存写周期,系统性能损失在可控范围内。
- 虚拟存储器必须采用回写(Write-Back)策略的原因: 虚拟存储系统的下一级存储介质是外存(磁盘/SSD)。外存的写速度极慢(毫秒级)。如果虚拟存储器采用写直达法,CPU 每次执行内存写操作都必须同步进行磁盘写 I/O,整个计算机系统的吞吐量将被极其缓慢的磁盘写操作锁死,系统性能将发生灾难性劣化。因此,对页面的写修改只能留在主存中,仅在页面被置换算法淘汰出主存且被修改过时,才执行一次性回写磁盘。
【官方采分点归纳】¶
- 位数计算及 TLB 标记定义准确无误。
- 组号计算为 3,H 字段为 8。
- 明确指明缺页开销大,核心原因为“缺页需访问磁盘而 Cache 缺失只需访问主存”(或“缺页由软件操作系统中断处理而 Cache 缺失由硬件完成”)。
- 对比主存与磁盘写操作的巨大速度差异,指出直写磁盘会导致严重性能瓶颈。
3. 2017 年 408 统考真题第 14 题¶
【考查方向】¶
双重嵌套循环下数组访问的时间局部性与空间局部性判断。
【题干与选项】¶
某 C 语言程序段如下:
下列关于数组a 的访问局部性的描述中,正确的是( )。
A. 时间局部性和空间局部性皆有B. 无时间局部性,有空间局部性
C. 有时间局部性,无空间局部性
D. 时间局部性和空间局部性皆无
【详细解析】¶
-
空间局部性剖析: 考查内层循环
for (j = 0; j <= i; j++) temp *= a[j];。 在每一次外层循环固定时,内层循环的下标变量 \(j\) 均以步长 1 连续递增,依次访问数组元素: $\(a[0], a[1], a[2], \dots, a[i]\)$ 在 C 语言中,一维数组在内存中占据连续的物理地址空间。由于访问的存储单元在物理地址上严格相邻连续,故对数组a的访问具有显著的空间局部性。 -
时间局部性剖析: 考查外层循环
for (i = 0; i <= 9; i++)对内层循环的影响: - 当 \(i=0\)$ \text{时,内层循环访问} $\(a[0]\);
- 当 \(i=1\)$ \text{时,内层循环再次访问} $\(a[0]\)$ \text{,接着访问} $\(a[1]\);
- 当 \(i=2\)$ \text{时,内层循环第三次访问} $\(a[0]\)$ \text{,接着再次访问} $\(a[1]\)$ \text{,随后访问} $\(a[2]\);
-
……以此类推,随着外层循环推进,\(a[0]\)$ \text{被重复访问了 10 次,} $\(a[1]\) 被重复访问了 9 次…… 同一存储单元在较短的时间间隔内被系统反复读取使用,完全满足时间局部性的定义。因此,对数组
a的访问具有显著的时间局部性。 -
结论: 该程序段对数组
a的访问既具有时间局部性,又具有空间局部性。
【干扰项剖析】¶
- 误选 B:仅看到内层循环中下标 \(j\) 单调递增,忽略了外层循环导致内层数组元素被反复重用这一关键事实。
- 误选 C 或 D:概念混淆,未能理解连续地址访问即构成空间局部性。
【正确答案】¶
A
4. 2020 年 408 统考真题第 15 题¶
【考查方向】¶
TLB 与 Cache 的硬件介质构成、局部性原理、缺失处理机制综合辨析。
【题干与选项】¶
下列关于 TLB 和 Cache 的叙述中,错误的是( )。
A. 命中率都与程序局部性有关
B. 缺失后都需要去访问主存
C. 缺失处理都可以由硬件实现
D. 都由 DRAM 存储器组成
【详细解析】¶
- 选项 A 正确: Cache 缓存主存的数据块与指令块,依靠程序的时间局部性和空间局部性来保障高命中率;TLB(快表)缓存页表项(虚拟页号到物理页框号的映射关系),程序在执行过程中对指令与数据页面的访问同样具备极强的时间局部性(同一页内反复访问)与空间局部性(连续顺序跨页),因此两者的命中率均直接取决于程序的局部性优劣。
- 选项 B 正确: Cache 缺失意味着目标数据不在 Cache 中,硬件必须访问主存(DRAM)将对应的主存块加载到 Cache;TLB 缺失意味着快表中没有该虚页的物理映射,必须访问存放在主存中的慢表(Page Table,多级页表)进行地址转换查询。两者缺失后最终都必须访问主存。
- 选项 C 正确: Cache 缺失的行分配、替换与数据调入完全由纯硬件控制器(Cache Controller)自动实现,对软件完全透明;TLB 缺失处理在现代主流体系结构中(如 x86 架构)由 CPU 内部集成的硬件页表遍历器(Hardware Page Table Walker / MMU)全自动遍历内存页表完成装载,虽然部分早期或特定 RISC 架构(如 MIPS、SPARC)支持软件异常陷入处理 TLB 缺失,但题干表述为“都可以由硬件实现”,命题完全准确。
- 选项 D 错误: TLB 与 Cache 均集成在 CPU 芯片内部,处于纳秒级的极速访存通路上。
- Cache 必须采用读写速度极快、无需动态刷新的静态随机存储器(SRAM)构成;
- TLB 需要对多个页表项的标记字段进行并发比对,通常采用相联存储器(CAM, Content Addressable Memory)或高速 SRAM 实现;
- 动态随机存储器(DRAM)需要周期性充电刷新,读写延迟高,仅用于制造大容量物理主存,绝不可能用来制作 TLB 或 Cache。
【正确答案】¶
D
5. 2023 年 408 统考真题第 43 题¶
【考查方向】¶
虚拟存储管理、数据 Cache 组相联映射机制、嵌套循环次序调换对局部性与命中率的影响。
【题干与设问】¶
已知计算机 M 字长为 32 位,按字节编址,采用请求调页策略的虚拟存储管理方式,虚拟地址为 32 位,页面大小为 4KB;数据 Cache 采用 4 路组相联映射,数据区大小为 8KB,主存块大小为 32B。现有 C 语言程序段如下:
已知二维数组a 按行优先存放,在虚拟地址空间中分配的起始地址为 0042 2000H,sizeof(int) = 4,假定在 M 上执行上述程序段之前数组 a 不在主存,且在该程序段执行过程中不会发生页面置换。请回答下列问题。
(1) 数组 a 分为几个页面存储?对于数组 a 的访问,会发生几次缺页异常?页故障地址各是什么?
(2) 不考虑变量 i 和 j,该程序段的数据访问是否具有时间局部性?为什么?
(3) 计算机 M 的虚拟地址(A31~A0)中哪几位用作块内地址?哪几位用作 Cache 组号?a[1][0] 的虚拟地址是多少?其所在主存块对应的 Cache 组号是多少?
(4) 数组 a 占用多少主存块?假设上述程序段执行过程中数组 a 的访问不会和其他数据发生 Cache 访问冲突,则数组 a 的 Cache 命中率是多少?若将循环中 i 和 j 的次序按如下方式调换:
则数组 a 的 Cache 命中率又是多少?
【详细解析】¶
针对第 (1) 问:¶
- 数组元素总数 \(= 24 \times 64 = 1536\) 个。
- 数组占用总字节数 \(= 1536 \times 4\text{ B} = 6144\text{ B}\)。
- 页面大小为 4KB = 4096B。
因为 \(4096 < 6144 \le 8192\),且起始地址为
0042 2000H(页面低 12 位偏移量为000H,恰好从页面起始边界对齐),所以数组a分布在 2 个连续页面中。 - 执行前数组
a不在主存,访问第一页发生 1 次缺页异常,跨到第二页(偏移 4096B = 1000H 处)发生第 2 次缺页异常。缺页异常共 2 次。 - 页故障地址即首次触发缺页的访存地址,分别为:
0042 2000H和0042 3000H。
针对第 (2) 问(考点核心):¶
该程序段的数据访问没有时间局部性。 - 原因:在嵌套循环的执行过程中,每个数组元素 \(a[i][j]\) 仅被赋值写入 1 次,在后续整个程序段的执行过程中从未被再次重复读取或写入,因此不存在时间局部性。
针对第 (3) 问:¶
- 主存块大小为 32B = \(2^5\text{ B}\),因此低 5 位(A4~A0)用作块内地址。
- Cache 数据区 8KB,4 路组相联,每组容量 \(= 4 \times 32\text{ B} = 128\text{ B} = 2^7\text{ B}\)。
- Cache 组数 \(= \frac{8\text{ KB}}{128\text{ B}} = 64\)$ \text{组} $\(= 2^6\)。
- 组号占用 6 位。虚拟地址中块内地址之后的高 6 位,即 A10~A5 用作 Cache 组号。
a[1][0]之前有 1 行元素,共 \(1 \times 64 = 64\)$ \text{个int元素,物理偏移字节数} $\(= 64 \times 4\text{ B} = 256\text{ B} = 100\text{H}\)。a[1][0]的虚拟地址 \(= 0042\ 2000\text{H} + 100\text{H} = 0042\ 2100\text{H}\)。- 将地址低位转换为二进制分解:
... 0001 0000 0000B(低 12 位) - 低 5 位(A4~A0)为块内地址:
00000B; - 接着的 6 位(A10~A5)为 Cache 组号:虚拟地址第 8 位为 1,第 5 位为 0,即
001000B= 8。 故a[1][0]所在主存块对应的 Cache 组号为 8。
针对第 (4) 问(考点核心——极致深度解析):¶
- 占用主存块数: $$ \text{块数} = \frac{6144\text{ B}}{32\text{ B}} = 192\text{ 个主存块} $$
- 原始行优先遍历的命中率:
每个主存块为 32B,存放 \(\frac{32\text{ B}}{4\text{ B}} = 8\) 个
int型元素。 按行优先顺序遍历写入时,每 8 个连续元素恰好位于同一个主存块中。 访问第一个元素时发生 Cache 缺失(Cold Miss),调入对应块;后续 7 个元素的访问均直接命中。 因此,行优先遍历的 Cache 命中率为: $\(\text{Hit Rate} = \frac{8 - 1}{8} = \frac{7}{8} = 87.5\%\)$ - 调换次序为列优先遍历后的命中率: 代码变更为: 考查突破口:Cache 容量与组相联度是否能完全容纳列遍历工作集?
- 数组每一行包含 64 个元素,占用字节数 \(= 64 \times 4\text{ B} = 256\text{ B}\)。
- 每一行占用主存块数 \(= \frac{256\text{ B}}{32\text{ B}} = 8\) 个主存块。
- Cache 总共有 64 组。连续 8 行数组包含的主存块总数 \(= 8 \times 8 = 64\) 块,这 64 个连续主存块恰好依次一一对应映射到 Cache 的 0~63 号组!
- 数组总共有 24 行。因此,对于同一个 Cache 组,整个数组 24 行中映射到该组的主存块数量为: $$ \text{\frac{24\text{ 行}}{8\text{ 行/周期}} = 3\text{ 块}} $$
- 关键硬件边界比对: 该 Cache 是 4 路组相联!这意味着每一个 Cache 组拥有 4 个 Cache 行,最多可以同时容纳 4 个冲突的主存块! 而在遍历列的过程中,映射到同一个 Cache 组的最大块数仅为 3 块(\(3 \le 4\))。
- 执行过程物理推演:
- 当 \(j=0\)$ \text{(遍历第 0 列)时:访问} $\(a[0][0], a[1][0], \dots, a[23][0]\)。虽然跨行访问,但因为每组有 4 路空间,调入的块在组内并不会互相驱逐替换!当第 0 列访问结束时,整个数组涉及的所有主存块(按列涉及的所有块)均安然常驻在 Cache 对应的组内!
- 当 \(j=1\)$ \text{(遍历第 1 列)时:访问} $\(a[0][1], a[1][1], \dots, a[23][1]\)。这些元素恰好与其同行第 0 列的元素位于完全相同的主存块内(每个块装 8 个元素)!由于这些块全都在第 0 列遍历时被加载进 Cache 且未被替换,所以第 1 列的访问全部命中!
- 类似地,\(j=2, 3, 4, 5, 6, 7\) 的遍历访问全部直接命中!
- 直到 \(j=8\) 时,才会进入下一批主存块,重新经历上述过程。
- 结论: 在整个列优先遍历过程中,总访存次数仍然为 1536 次,发生缺失的次数依然仅仅是每个块首次访问时的 1 次(共 192 次缺失),没有任何主存块发生冲突替换驱逐! 因此,Cache 命中率仍然为: $\(\text{Hit Rate} = \frac{7}{8} = 87.5\%\)$
【官方采分点归纳】¶
- 页面数 2,缺页异常 2 次,页故障地址正确。
- 明确回答无时间局部性,理由为“每个数组元素仅访问 1 次”。
- 虚拟地址字段划分正确,组号为 8。
- 占用主存块数 192;行优先命中率为 87.5%;列优先命中率推导严密并正确得出 87.5%(若回答因列访问冲突导致命中率为 0 则判定未掌握组相联冲突容限机制,不得分)。
四、综合大题应用与考查拓展¶
在 408 统考的综合大题(第 43 题、44 题或 45 题)中,Cache 概念从不孤立出现,而是与操作系统虚拟页式存储、CPU 内部数据通路、总线事务进行三维立体交织。考生必须建立以下三大跨模块系统性思维框架:
1. 数组访问步长与 Cache 冲突抖动的数学建模¶
在综合大题中,若对数组进行多重循环操作,必须采用“步长-块-组”三级映射分析法: 1. 单块覆盖步长判定: 设数组元素大小为 \(E\)$ \text{字节,Cache 块大小为} $\(B\)$ \text{字节,则单块容纳元素个数为} $\(K = B / E\)。 - 若内层循环以步长 \(S=1\)$ \text{顺序访问连续元素,只要不发生 Cache 组内冲突驱逐,其缺失率理论下界必然为} $\(1/K\)。 - 若内层循环以大步长 \(S \ge K\) 跨行/跨步访问,每个元素的访问均映射到不同主存块,空间局部性彻底丧失。 2. 工作集与组相联度容量判定(2023#43 变式推演): 判断大步长列访问是否会导致命中率断崖式下跌,核心在于计算“映射到同一个 Cache 组的最大活跃块数 \(M_{\text{conflict}}\)$ \text{”与“Cache 组相联路数} $\(W\)”的大小关系: - 若 \(M_{\text{conflict}} \le W\)$ \text{:Cache 组内有足够的路数同时容纳这些冲突块,不会发生冲突替换。后续列访问仍能享受先前调入块的命中红利,命中率保持为} $\(1 - 1/K\)。 - 若 \(M_{\text{conflict}} > W\):发生致命的“Cache 颠簸/抖动(Thrashing)”。先调入的块在同一列还没遍历完就被后续行驱逐出 Cache,导致下一列访问时又必须重新从主存载入,此时 Cache 命中率将跌落至 0%!
2. 虚拟地址到 Cache 访问的跨层次时序机制(TLB + Page + Cache)¶
综合大题常要求画出或计算从 CPU 发出虚拟地址(VA)到最终从 Cache/主存读取数据的完整路径:
CPU 发出虚拟地址 (VA)
|
+---> [ 步骤 1: TLB 检索 (快表) ]
| |-- 命中 (TLB Hit): 立即输出物理页框号 (PPN)
| \-- 缺失 (TLB Miss): 启动步骤 2
|
+---> [ 步骤 2: 页表检索 (慢表) ]
| |-- 命中 (Page Hit): 从内存页表中读取 PPN 并更新 TLB
| \-- 缺页 (Page Fault): 触发操作系统缺页异常,从外存调入页面
|
v (获得完整物理地址 PA = PPN + 页内偏移)
[ 步骤 3: Cache 检索 ]
|-- 命中 (Cache Hit): 直接将数据高速送往 CPU 寄存器 (耗时仅 1~5 ns)
\-- 缺失 (Cache Miss): 向内存总线发起读事务,将对应主存块装入 Cache (耗时 50~100 ns)
3. 写策略与总线写流量(Bus Write Traffic)定量评估¶
在综合系统性能分析题中,常要求定量计算采用不同写策略时系统主存总线的吞吐开销: - 场景模型: 设某程序共执行 \(I\)$ \text{条指令,其中访存指令占比为} $\(f_{\text{mem}}\)$ \text{,访存指令中写操作占比为} $\(w\)$ \text{(读操作占比} $\(1-w\)$ \text{)。Cache 读缺失率为} $\(M_r\)$ \text{,写缺失率为} $\(M_w\)$ \text{,写回法下被替换的 Cache 行中脏块占比为} $\(D_{\text{dirty}}\)。 - 写直达法 + 非写分配法下的总线写事务数: 由于每一次写操作都必须直接写入主存,总线写事务数直接正比于程序总写次数: $\(\text{Bus Writes} = I \times f_{\text{mem}} \times w\)$ - 写回法 + 写分配法下的总线写事务数: 写命中时不引发总线写事务,仅在发生缺失且替换脏块时,向总线发起整块写回事务: $\(\text{Bus Writes} = I \times f_{\text{mem}} \times \left( (1-w)M_r + w M_w \right) \times D_{\text{dirty}}\)$ 在典型应用程序中,\(D_{\text{dirty}} \approx 30\% \sim 50\%\),且缺失率通常低于 5%,因此写回法能将总线写流量削减 90% 以上,是多核共享总线系统的主流标配。
五、考点速记清单¶
1. 局部性快速判别法则¶
- 时间局部性判断口诀:“找循环复用”。
- 凡是在循环体中被多次重复读写的同一个标量变量(如计数器、累加器)、在多重嵌套循环中被内层循环反复访问的外层数组元素,均具备时间局部性。
- 数组元素若在遍历中只被访问一次且再无后续引用,绝无时间局部性。
- 空间局部性判断口诀:“看地址连续”。
- 沿物理内存连续地址顺序遍历数组(行优先存储下的行遍历、按步长 1 访问),具备强空间局部性。
- 跨大步长访问(步长大于块大小)、乱序链表指针随机跳转,空间局部性差或丧失。
2. Cache 核心性能指标与公式汇总表¶
| 指标名称 | 数学计算公式 | 核心说明 |
|---|---|---|
| 命中率 | \(h = \frac{N_c}{N_c + N_m}\) | \(N_c\)$ \text{为 Cache 命中次数,} $\(N_m\) 为主存访问次数 |
| 缺失率 | \(M = 1 - h = \frac{N_m}{N_c + N_m}\)$ \text{ | 满足} $\(h + M = 1\) |
| AMAT(并行访问) | \(\text{AMAT} = h \cdot t_c + (1 - h) \cdot t_m\) | Cache 与主存并发启动查询,命中则中断主存 |
| AMAT(串行访问) | \(\text{AMAT} = t_c + (1 - h) \cdot t_m\)$ \text{ | 先查 Cache,缺失后再启动主存(} $\(t_m\) 为缺失损失) |
| 两级 Cache AMAT | \(\text{AMAT} = t_{L1} + M_{L1}(t_{L2} + M_{L2} \cdot t_m)\) | \(M_{L1}, M_{L2}\) 为各级局部缺失率 |
| 全局缺失率 | \(\text{Global Miss Rate}_{L2} = M_{L1} \times M_{L2}\) | 穿透两级最终落入主存的缺失率 |
| 加速比 | \(S = \frac{t_m}{\text{AMAT}}\) | 相比纯主存系统的性能提升倍数 |
3. 四大写策略组合必背对照表¶
| 对比维度 | 写回法 + 写分配法 (Write-Back + Write-Allocate) | 写直达法 + 非写分配法 (Write-Through + Not-Write-Allocate) |
|---|---|---|
| 写命中动作 | 只写 Cache,置脏位为 1 | 同时写 Cache 与主存(或进入写缓冲) |
| 写缺失动作 | 将主存块调入 Cache,再修改 Cache | 直接写主存,不调块入 Cache |
| 脏位(Dirty Bit) | 必须具备(每行 1 位) | 不需要 |
| 总线写开销 | 极小(仅被替换的脏行写回主存) | 极大(每次写指令均写主存) |
| 一致性状态 | 主存数据存在暂态陈旧 | 主存与 Cache 严格一致 |
| 虚存采用原因 | 虚拟存储器必须采用写回法,因为磁盘写入延迟比主存慢数十万倍,直写磁盘系统将崩溃 | 绝不适用于虚拟存储系统 |
4. 408 核心避坑指南¶
- 赋值语句访存次数陷阱:在计算循环访问数组的 Cache 缺失率时,务必看清语句是单纯读取(如
sum += a[k],访存 1 次),还是读写组合(如a[k] = a[k] + 32,先读后写共 2 次访存)。 - 写策略与脏位硬件开销陷阱:计算 Cache 标记阵列总容量时,只有在题干指明“采用写回法(Write-Back)”时,每个 Cache 行才需要加 1 位脏位;若为写直达法,绝无脏位。
- 介质构成陷阱:Cache 与 TLB 均由高速 SRAM/CAM 组成,绝不含 DRAM;主存由 DRAM 组成。
- 缺失处理开销陷阱:Cache 缺失由纯硬件处理,耗时纳秒级;缺页异常由操作系统软硬件协同中断处理,耗时毫秒级,二者存在数十万倍量级差距。
- 列优先访问命中率陷阱:不要形成“列优先遍历命中率必然为 0”的思维定势!若数组映射到同组的块数小于等于组相联路数(如 2023 年第 43 题),4 路组相联能够完全容纳冲突行,命中率仍然可高达 87.5%!