Cache技术

Cache 技术

1. Cache 的基本原理

局部性原理

时间局部性：

• 程序倾向于重复访问相同的数据
• 近期访问的数据很可能再次被访问
• 利用时间局部性提高命中率

空间局部性：

• 程序倾向于访问相邻的数据
• 访问某个数据后，相邻数据很可能被访问
• 利用空间局部性提高命中率

Cache 工作原理

基本概念：

• 在 CPU 和主存之间设置高速缓存
• 存储近期访问的数据
• 减少访问主存的次数

工作过程：

1. CPU 发出访问请求
2. 首先在 Cache 中查找
3. 如果命中，直接返回数据
4. 如果未命中，从主存调入数据

Cache 性能指标

命中率：

• 命中次数 / 总访问次数
• 反映 Cache 的效果
• 目标：提高命中率

访问时间：

• 命中时：Cache 访问时间
• 未命中时：主存访问时间
• 目标：减少平均访问时间

Cache 效率：

• 平均访问时间 = 命中率 × Cache 时间 + (1-命中率) × 主存时间
• 反映整体性能提升

2. Cache 的映射方式

直接映射

基本原理：

• 主存地址按 Cache 大小分块
• 每个主存块只能映射到 Cache 的固定位置
• 映射关系：Cache 行号 = 主存块号 mod Cache 行数

地址结构：

• 标记位：标识主存块
• 行号：Cache 行地址
• 块内偏移：块内字节地址

特点：

• 优点：实现简单，访问速度快
• 缺点：冲突率高，命中率低
• 应用：小容量 Cache

全相联映射

基本原理：

• 主存块可以映射到 Cache 的任意位置
• 需要比较所有 Cache 行的标记
• 完全自由的映射关系

地址结构：

• 标记位：完整的主存地址
• 块内偏移：块内字节地址

特点：

• 优点：冲突率低，命中率高
• 缺点：实现复杂，访问速度慢
• 应用：小容量 Cache

组相联映射

基本原理：

• 将 Cache 分成若干组
• 主存块映射到固定组内的任意行
• 结合直接映射和全相联的优点

地址结构：

• 标记位：标识主存块
• 组号：Cache 组地址
• 块内偏移：块内字节地址

特点：

• 优点：冲突率适中，命中率较高
• 缺点：实现复杂度适中
• 应用：大多数 Cache

3. Cache 的替换算法

FIFO（先进先出）

基本原理：

• 最先进入 Cache 的块最先被替换
• 按时间顺序管理 Cache 行
• 不考虑访问频率

实现方法：

• 使用队列记录进入顺序
• 替换时选择队列头部
• 新数据进入队列尾部

特点：

• 优点：实现简单
• 缺点：不考虑访问模式
• 适用：访问模式均匀的情况

LRU（最近最少使用）

基本原理：

• 最久未被访问的块最先被替换
• 记录每个块的访问时间
• 优先保留最近访问的块

实现方法：

• 使用计数器记录访问时间
• 每次访问更新计数器
• 替换时选择计数器最小的块

特点：

• 优点：命中率较高
• 缺点：实现复杂
• 适用：大多数应用

LFU（最不经常使用）

基本原理：

• 访问次数最少的块最先被替换
• 记录每个块的访问次数
• 优先保留经常访问的块

实现方法：

• 使用计数器记录访问次数
• 每次访问增加计数器
• 替换时选择计数器最小的块

特点：

• 优点：适合访问频率差异大的情况
• 缺点：不能反映最近的访问情况
• 适用：访问模式稳定的情况

CLOCK 算法

基本原理：

• 结合 LRU 和 FIFO 的优点
• 使用引用位标记访问状态
• 循环扫描选择替换块

实现方法：

• 每个 Cache 行设置引用位
• 访问时设置引用位为 1
• 替换时扫描，清除引用位，选择引用位为 0 的块

特点：

• 优点：实现相对简单，效果较好
• 缺点：不如 LRU 精确
• 适用：中等规模 Cache

4. Cache 的写策略

写直达（Write-Through）

基本原理：

• 写 Cache 的同时写主存
• 保证数据一致性
• 主存始终是最新数据

特点：

• 优点：数据一致性好
• 缺点：写操作速度慢
• 适用：对一致性要求高的场合

写回（Write-Back）

基本原理：

• 只写 Cache，不立即写主存
• 使用脏位标记修改状态
• 替换时才写回主存

特点：

• 优点：写操作速度快
• 缺点：数据一致性复杂
• 适用：大多数现代 Cache

写分配（Write-Allocate）

基本原理：

• 写未命中时，先调入数据块
• 然后修改 Cache 中的数据
• 配合写回策略使用

特点：

• 优点：提高后续访问命中率
• 缺点：增加写未命中的开销
• 适用：空间局部性好的情况

写不分配（Write-No-Allocate）

基本原理：

• 写未命中时，直接写主存
• 不调入数据块到 Cache
• 配合写直达策略使用

特点：

• 优点：减少 Cache 污染
• 缺点：可能降低命中率
• 适用：随机写访问的情况

5. 多级 Cache

两级 Cache 结构

L1 Cache：

• 容量小，速度快
• 与 CPU 集成
• 分离指令 Cache 和数据 Cache

L2 Cache：

• 容量较大，速度较慢
• 统一 Cache
• 弥补 L1 Cache 的不足

多级 Cache 优势

性能提升：

• 减少平均访问时间
• 提高整体命中率
• 降低主存访问频率

成本控制：

• 合理分配存储资源
• 降低总体成本
• 满足性能需求

练习题

练习 1

Cache 的三种映射方式分别是什么？

练习 2

虚拟存储器的基本原理是什么？常见的页面置换算法有哪些？