# 3.3 高速缓冲存储器Cache

## 一、Cache概述

### 1.1 为什么需要Cache

**问题**：
- CPU速度远快于主存
- CPU等待主存，效率低

**解决**：
- 在CPU和主存之间增加高速小容量存储器
- 存放最近使用的数据
- 缓解速度差异

### 1.2 Cache的工作原理

**局部性原理**：
- 时间局部性：最近访问的数据可能再次被访问
- 空间局部性：邻近数据可能被访问

**工作过程**：
1. CPU访问Cache
2. Cache命中：直接访问Cache
3. Cache未命中：访问主存，同时调入Cache

**命中率**：
```
命中率 = Cache命中次数 / 总访问次数
```

**平均访问时间**：
```
T_avg = H × T_c + (1-H) × T_m
```
- H：命中率
- T_c：Cache访问时间
- T_m：主存访问时间

---

## 二、Cache的地址映射

### 2.1 直接映射

**方式**：
- 每个主存块只能映射到固定的Cache行
- Cache行号 = 主存块号 mod Cache行数

**地址划分**：
```
| 标记 | Cache行号 | 块内地址 |
|------|-----------|----------|
```

**优点**：
- 实现简单
- 查找速度快

**缺点**：
- 冲突率高
- 利用率低

### 2.2 全相联映射

**方式**：
- 每个主存块可以映射到任意Cache行

**地址划分**：
```
| 标记 | 块内地址 |
|------|----------|
```

**优点**：
- 冲突率低
- 利用率高

**缺点**：
- 查找慢（需要遍历）
- 硬件复杂

### 2.3 组相联映射

**方式**：
- Cache分成若干组
- 每个主存块映射到固定组，组内任意行
- 组号 = 主存块号 mod 组数

**地址划分**：
```
| 标记 | 组号 | 块内地址 |
|------|------|----------|
```

**优点**：
- 兼顾直接映射和全相联映射的优点
- 冲突率适中
- 查找速度较快

**常用**：
- 2路组相联
- 4路组相联
- 8路组相联

---

## 三、Cache的替换算法

### 3.1 随机算法（RAND）

**方法**：
- 随机选择替换块

**优点**：
- 实现简单

**缺点**：
- 命中率低

### 3.2 先进先出算法（FIFO）

**方法**：
- 替换最早调入的块

**优点**：
- 实现简单

**缺点**：
- 可能替换常用块

### 3.3 最近最少使用算法（LRU）

**方法**：
- 替换最近最少使用的块

**实现**：
- 计数器法
- 栈法

**优点**：
- 命中率高

**缺点**：
- 实现复杂

### 3.4 最不经常使用算法（LFU）

**方法**：
- 替换访问次数最少的块

---

## 四、Cache的写策略

### 4.1 写命中时的策略

**写直达（Write Through）**：
- 同时写Cache和主存
- 优点：数据一致
- 缺点：写速度慢

**写回（Write Back）**：
- 只写Cache，替换时写回主存
- 优点：写速度快
- 缺点：数据不一致，需要脏位

### 4.2 写未命中时的策略

**写分配（Write Allocate）**：
- 先调入块到Cache，再写
- 配合写回使用

**非写分配（No Write Allocate）**：
- 直接写主存，不调入Cache
- 配合写直达使用

---

## 五、Cache的性能

### 5.1 影响Cache性能的因素

**Cache容量**：
- 容量越大，命中率越高
- 但成本增加，访问时间增加

**块大小**：
- 块太小：空间局部性利用不足
- 块太大：块数减少，冲突增加
- 典型：32-128字节

**相联度**：
- 相联度越高，冲突越少
- 但查找越慢，成本越高

**替换算法**：
- LRU优于FIFO

**写策略**：
- 写回优于写直达

### 5.2 Cache的优化技术

**多级Cache**：
- L1 Cache：最快，最小
- L2 Cache：较大，较慢
- L3 Cache：更大，更慢

**预取技术**：
- 预测访问的数据，提前调入

**非阻塞Cache**：
- 未命中时不阻塞，继续服务其他请求

---

## 六、考研重点

1. **Cache概述**：
   - 为什么需要Cache
   - 局部性原理
   - 命中率和平均访问时间

2. **Cache的地址映射**：
   - 直接映射
   - 全相联映射
   - 组相联映射

3. **Cache的替换算法**：
   - 随机
   - FIFO
   - LRU
   - LFU

4. **Cache的写策略**：
   - 写直达
   - 写回
   - 写分配
   - 非写分配

5. **Cache的性能**：
   - 影响因素
   - 优化技术

---

*下一节：3.4 虚拟存储器*