【总结笔记】Cache-TLB-虚拟内存

【总结笔记】存储器层次结构：Cache / TLB / 虚拟内存

本部分涵盖：存储层次关系图、虚拟地址与物理地址划分、TLB与Cache结构辨识、Cache三种映射方式与地址切分、Cache容量计算、LRU替换算法、Cache命中率与AMAT、缺页异常次数、虚存-Cache-TLB联合寻址完整流程。

---

一、存储层次关系与访问链路

访问链路总图（必背）：

CPU产生虚拟地址
    │
    ▼ 第一阶段：地址翻译（虚 → 实）
   查 TLB（快表）
    ├─ 命中 → 直接得到物理地址
    └─ 缺失 → 查主存页表
              ├─ 命中 → 得物理地址 + 更新TLB
              └─ 缺失 → 缺页中断，OS从磁盘调入
    │
    ▼ 第二阶段：数据获取（查Cache → 访主存）
   查 Cache（物理地址索引）
    ├─ 命中 → 直接把数据送CPU（最快）
    └─ 缺失 → 访主存，把整块数据装入Cache，送CPU

存储介质速查：

• TLB / Cache：在CPU片内 → SRAM（极速，无需刷新）
• 主存（内存）/ 页表：在CPU片外 → DRAM（容量大，需动态刷新）

四种状态组合

组合	是否可能	说明
TLB命中 + Cache命中	✅	最理想状态
TLB命中 + Cache缺失	✅	数据还未调入Cache
TLB缺失 + Cache命中	✅	TLB项被替换，但数据还在Cache
TLB命中 + 缺页异常	❌ 不可能	TLB命中说明页在主存，绝不缺页
缺页异常 + Cache命中	❌ 不可能	页没进内存，Cache不可能有该页数据

---

二、地址划分（两大视角）

2.1 虚存视角（由页面大小决定）

$\text{虚拟地址}=[\underset{V-p\text{ 位}}{\underbrace{\text{虚页号 (VPN)}}}]+[\underset{p\text{ 位}}{\underbrace{\text{页内偏移}}}]$

$\text{物理地址}=[\underset{P-p\text{ 位}}{\underbrace{\text{页框号 (PPN)}}}]+[\underset{p\text{ 位}}{\underbrace{\text{页内偏移}}}]$

其中：$p={\log }_2(\text{页面大小})$，$V={\log }_2(\text{虚拟地址空间})$，$P={\log }_2(\text{主存大小})$

关键：虚拟地址和物理地址的页内偏移完全相同（位数和值），直接下传！

2.2 Cache视角（物理地址的进一步切分）

Cache映射方式	物理地址切分结构	字段位数
直接映射	[Tag] + [行号] + [块内地址]	行号 = ${\log }_2(\text{总行数})$
K路组相联	[Tag] + [组号] + [块内地址]	组号 = ${\log }_2(\text{总行数}/K)$
全相联	[Tag] + [块内地址]	无行号/组号

块内地址（任何方式）：$b={\log }_2(\text{主存块大小})$

Tag位数 = 物理地址总位数 - 组号位数 - 块内地址位数

2.3 TLB视角（虚页号的切分）

TLB映射方式	切分结构	Tag位数
全相联（最常考）	[TLB Tag] = 完整虚页号	= 虚页号位数
K路组相联	[TLB Tag] + [TLB组号]	= 虚页号位数 - 组号位数
直接映射	[TLB Tag] + [TLB行号]	= 虚页号位数 - 行号位数

---

三、Cache结构辨识（考图题）

看TLB映射方式

特征	映射方式
每行都有比较器，虚页号完整送入所有比较器	全相联
虚页号被切成Tag + 组号，组内K行并行比对	K路组相联
虚页号被切成Tag + 行号，1个比较器	直接映射

看Cache映射方式

特征	映射方式
每行只有1个Data槽位，由行号索引	直接映射
一个组号下并排K个Data槽位+K个比较器	K路组相联
无组号/行号，Tag直接并行送所有行	全相联

---

四、Cache容量计算

$\text{Cache总容量}=\text{行数}\times \text{块大小(B)}+\text{行数}\times \text{单行标记开销(bit)}$

单行标记开销：

$=\text{Tag位数}+\underset{\text{任何情况必有}}{\underbrace{\text{有效位(1 bit)}}}+\underset{\text{写回法=1，直写法=0}}{\underbrace{\text{脏位(0或1 bit)}}}+\underset{\text{直接映射=0，K路LRU}={\log }_{2}K}{\underbrace{\text{LRU替换位}}}$

速查表：

映射方式	写策略	替换算法	脏位	LRU位
直接映射	任何	无	视策略	0
K路组相联	回写法	LRU	1	${\log }_{2}K$
K路组相联	直写法	LRU	0	${\log }_{2}K$
K路组相联	任何	RAND	视策略	0

---

五、Cache行号/组号定位（数组题）

两步定位法：

$\text{主存块号}=\lfloor \frac{\text{字节物理地址}}{\text{块大小}}\rfloor$

$\text{Cache行号（直接映射）}=\text{主存块号}\mathrm{mod}\text{Cache总行数}$

$\text{Cache组号（组相联）}=\text{主存块号}\mathrm{mod}\text{Cache总组数}$

数组元素地址（二维数组 $a[M][N]$，按行存储）：

$\text{字节地址}=\text{Base}+(i\times N+j)\times \text{sizeof}(T)$

---

六、Cache命中率与AMAT

6.1 数组占用块数（必用首尾地址法）

1. 首地址 $A_{start}$，末地址 = $A_{start}+N\times S-1$（必须减1！）
2. 首块号 = $\lfloor \text{首地址}/B\rfloor$，末块号 = $\lfloor \text{末地址}/B\rfloor$
3. 总块数 = 末块号 - 首块号 + 1（必须加1！）
4. 缺失次数 = 总块数

快速规律（仅当数组总大小是块大小整数倍时）：

• 首地址对齐 → 块数 = 总字节 / 块大小
• 首地址不对齐 → 块数 = 总字节 / 块大小 + 1

6.2 总访问次数计算

• 纯读（sum += a[i]）：每次循环 1次 Cache访问
• 读写复合（a[i] = a[i]/x）：先读后写 = 2次 Cache访问
• 寄存器变量（i、k）：不计入 Cache访问

6.3 性能指标

$\text{缺失率}M=\frac{\text{总缺失次数}}{\text{总访问次数}}\times 100\%$

$\text{AMAT}=t_c+M\times t_{\text{penalty}}$

其中 $t_c$ 为Cache命中时间，$t_{\text{penalty}}$ 为缺失损失（访主存时间）

6.4 CPU执行时间

$T_{\text{total}}=T_{\text{base}}+T_{\text{miss}}$

$T_{\text{base}}=\text{指令条数}\times \text{CPI}\times \text{时钟周期}$

$T_{\text{miss}}=\text{指令条数}\times \text{每条指令平均访存次数}\times \text{缺失率}\times \text{缺失损失}$

6.5 按行遍历 vs 按列遍历

遍历方式	命中率	原因
按行	$(E-1)/E$（$E$=块内元素数）	顺序访问，空间局部性极好
按列（能装下）	同按行	首轮调入后不被置换，后续全命中
按列（装不下/冲突）	0%	每次访问都导致替换（抖动效应）

---

七、LRU替换算法

核心规则：淘汰最久未被访问的表项

1. 算组号：$\text{组号}=\text{虚页号/块号}\mathrm{mod}\text{组数}$（各组独立，互不影响）
2. 新加入/命中的项 → 移到最新位置
3. 缺失且组满 → 淘汰队尾（最旧的），放入新项

关键易错：命中时也必须更新LRU顺序！被访问到的项新鲜度立刻刷新。

---

八、虚存跨页与缺页异常

8.1 计算跨越页数

1. 末地址 = 首地址 + 总字节数 - 1（减1防溢出）
2. 起始页号 = 截掉物理地址低 $p$ 位（十六进制截掉低 $p/4$ 个十六进制字符）
3. 末尾页号 = 同理
4. 跨越页数 = 末页号 - 首页号 + 1（加1闭区间计数）

口诀：算末地址”减1”，算页数”加1”。

8.2 缺页异常次数

在顺序遍历且无页面置换的条件下：

$\text{缺页次数}=\text{跨越的不同页面总数}$

（每个新页面首次访问时触发1次缺页，之后同页内的元素全部命中）

---

九、虚存-Cache-TLB联合寻址（完整字段计算）

综合题字段对照（以32位虚址、24位物理址、8KB页、64B块、2路组相联Cache为例）：

虚拟地址(32位) = [虚页号(19位)] + [页内偏移(13位)]
                      ↓（TLB翻译）
物理地址(24位) = [页框号(11位)] + [页内偏移(13位)]
                      ↓（Cache索引）
物理地址(24位) = [Cache Tag(9位)] + [Cache组号(9位)] + [块内地址(6位)]

解题顺序：

1. 由页面大小算 $p$（页内偏移位数）
2. 由虚拟地址空间算虚页号位数；由主存大小算物理地址总位数、页框号位数
3. 由主存块大小算块内地址位数 $b$
4. 由Cache容量和路数算组数 → 组号位数 $c$
5. Cache Tag = 物理地址总位数 - $c$ - $b$
6. TLB Tag = 虚页号位数（全相联）或虚页号位数 - TLB组号位数（组相联）

---

十、高频易错汇总

错误	正确做法
Cache总容量只算数据区	必须加上标记阵列（Tag+有效位+脏位+LRU位）
直写法加脏位	直写法无脏位（0bit）；只有回写法才有1bit脏位
LRU位数按总行数算	LRU位 = ${\log }_{2}K$（K为路数，不是总行数）
TLB介质答DRAM	TLB在CPU片内，必须是SRAM
TLB命中会缺页	TLB命中 → 页必在主存 → 绝不缺页
末地址不减1	末地址 = 首地址 + 总字节 -1（否则多算1页/块）
跨页/块数不加1	总数 = 末编号 - 首编号 +1（闭区间计数）
a[i]=a[i]/x 算1次访问	先读后写 = 2次 Cache访问
命中时不更新LRU顺序	命中也必须刷新新鲜度，否则LRU模拟结果错误
按列遍历一定命中率为0%	数组能装入Cache且无冲突时，按列遍历命中率与按行相同