存储系统

1. 存储层次原理

1.1 局部性原理

时间局部性：最近访问的数据很可能在不久后再次被访问。

空间局部性：最近访问数据附近的数据很可能即将被访问。

局部性是存储层次有效性的理论基础。

1.2 存储层次设计目标

$\text{目标：以最低成本获得接近最快存储的访问速度}$

$t_{effective} = \sum_{i=1}^{n} h_i \times t_i$

其中 $h_i$ 为第 $i$ 层的命中率，$t_i$ 为第 $i$ 层的访问时间。

2. Cache 优化技术

2.1 降低缺失率

更大块大小：利用空间局部性，但块过大会增加缺失代价。

更大 Cache 容量：直接降低缺失率，但增加命中时间和功耗。

更高相联度：降低冲突缺失，但增加命中时间。

3C 模型：

$\text{缺失率} = \text{强制缺失} + \text{容量缺失} + \text{冲突缺失}$

2.2 降低缺失代价

多级 Cache：

$t_{miss} = t_{L2\_hit} + (1-h_{L2}) \times t_{L2\_miss}$

关键字优先（Critical Word First）：缺失时优先加载所需字，其余部分后台加载。

读缺失优先于写：写缓冲可能导致读缺失读到过时数据。

2.3 降低命中时间

小而简单的 Cache：L1 Cache 保持小容量、低相联度。

流水线化 Cache 访问：将 Cache 访问拆分为多个流水线级。

路预测：预测可能命中的路，只访问该路。

2.4 Cache 替换策略

LRU（最近最少使用）：替换最久未访问的行。

• 2路：1 bit 计数器
• 4路：需要更复杂的计数器
• 相联度高时开销大

伪 LRU（PLRU）：近似 LRU，用树形结构记录访问信息。

随机替换：简单，在某些情况下性能接近 LRU。

2.5 Cache 预取

硬件预取：

• 顺序预取：检测到顺序访问模式时预取下一行
• 跨步预取：检测固定跨步访问模式

软件预取：

// 使用预取指令
__builtin_prefetch(addr, rw, locality);

预取有效性条件：

$t_{prefetch} < t_{miss} \quad \text{且} \quad \text{预取准确率足够高}$

3. 虚拟存储

3.1 虚拟地址与物理地址

虚拟地址空间由 CPU 生成，物理地址空间对应实际内存：

$\text{物理地址} = f(\text{虚拟地址}, \text{页表})$

32 位系统：虚拟地址空间 4GB 64 位系统：虚拟地址空间 $2^{48}$ 或 $2^{57}$（实际实现）

3.2 页式存储

页表映射：

$\text{物理页号} = \text{页表}[\text{虚拟页号}]$

$\text{物理地址} = \text{物理页号} \times \text{页大小} + \text{页内偏移}$

页表项（PTE）结构：

┌──────┬──────┬──────┬──────┬──────┬──────┐
│ 有效位│ 读写位│ 用户位│ 脏位  │ 访问位│ 物理页号│
└──────┴──────┴──────┴──────┴──────┴──────┘

3.3 多级页表

32 位地址，4KB 页，4B PTE：

• 单级页表：$2^{20}$ 项 × 4B = 4MB（每个进程）
• 二级页表：仅映射已使用的虚拟地址范围

64 位系统通常使用四级页表：

虚拟地址：[PGD索引 | PUD索引 | PMD索引 | PTE索引 | 偏移]

Linux 的四级页表：PGD → PUD → PMD → PTE → 物理页

3.4 反置页表

按物理页号索引而非虚拟页号：

$\text{哈希表}[\text{虚拟页号} \oplus \text{PID}] \to \text{物理页号}$

优势：页表大小与物理内存成正比，与虚拟地址空间无关。

4. TLB

4.1 TLB 原理

TLB（Translation Lookaside Buffer）是页表的高速缓存：

虚拟地址 → TLB 查找 → 命中 → 物理地址
                  → 缺失 → 页表查找 → 填充 TLB → 物理地址

4.2 TLB 结构

典型 TLB 参数：

4.3 TLB 与 Cache 的交互

物理索引物理标记（PIPT）：

• Cache 使用物理地址索引和标记
• TLB 必须先完成翻译
• 命中时间较长

虚拟索引物理标记（VIPT）：

• Cache 索引使用虚拟地址低位（与物理地址相同）
• Cache 标记使用物理地址
• TLB 翻译和 Cache 索引可并行

$\text{索引位数} \leq \log_2(\text{页大小}) - \log_2(\text{块大小})$

4.4 超大页（Huge Pages）

标准 4KB 页导致 TLB 覆盖范围有限：

$\text{TLB 覆盖} = \text{TLB 项数} \times \text{页大小}$

64 项 × 4KB = 256KB，远不够大工作集。

解决方案：使用 2MB 或 1GB 大页。

$64 \times 2\text{MB} = 128\text{MB}$

Linux 透明大页（THP）自动将连续的 4KB 页合并为 2MB 大页。

5. 内存管理

5.1 页面置换算法

最优置换（OPT）：置换未来最久不被访问的页，理论最优但不可实现。

FIFO：置换最早进入内存的页，简单但性能差，存在 Belady 异常。

LRU：置换最近最久未访问的页，性能好但实现开销大。

Clock 算法：LRU 的近似实现，使用访问位和循环指针。

改进型 Clock 算法：同时考虑访问位和脏位：

5.2 工作集模型

进程的工作集 $W(t, \Delta)$ 是在时刻 $t$ 之前的 $\Delta$ 个时间单位内被访问的页面集合。

$\text{工作集大小} = |W(t, \Delta)|$

抖动（Thrashing）：当分配给进程的物理页数小于工作集大小时，频繁发生页面置换。

5.3 页面分配策略

• 全局置换：所有进程共享物理页池，可从其他进程夺取页面
• 局部置换：每个进程有固定数量的物理页

6. 存储一致性

6.1 Cache 一致性问题

多核系统中，每个核心有自己的私有 Cache，同一内存块可能在不同 Cache 中有不同副本。

6.2 监听协议（Snooping）

MSI 协议：

MESI 协议（Intel 使用）：

E 状态优化：当只有一个 Cache 拥有该行且未修改时，无需总线广播即可写入。

MOESI 协议（AMD 使用）：增加 O（Owner）状态，允许共享脏行。

6.3 目录协议（Directory）

适用于大规模多核系统，用目录记录每个缓存行的共享信息：

$\text{目录项} = \text{脏位} + \text{共享向量}[N]$

其中 $N$ 为处理器数量。

目录协议的扩展性：

• 全映射目录：$O(N)$ 空间/行
• 有限目录：$O(\log N)$ 空间/行
• 链式目录：动态分配空间