内存管理

1. 地址空间

1.1 逻辑地址 vs 物理地址

概念	含义	产生者
逻辑地址（虚拟地址）	CPU 程序视角的地址	CPU 生成
物理地址	实际内存硬件中的地址	经 MMU 转换后

MMU（Memory Management Unit）负责运行时将逻辑地址转换为物理地址，对程序完全透明。

1.2 进程地址空间布局

典型 Linux 进程虚拟地址空间（64-bit）：

高地址 ┌─────────────────┐
       │  内核空间         │  用户不可访问
       ├─────────────────┤  0xFFFF800000000000
       │  栈 (Stack) ↓    │  向下增长
       │                  │
       │  （空闲区域）      │
       │                  │
       │  mmap 区域        │  共享库、mmap 文件
       │                  │
       │  堆 (Heap) ↑     │  向上增长（malloc/new）
       ├─────────────────┤
       │  BSS（未初始化）   │
       │  Data（已初始化）  │
       │  Text（代码段）    │  只读+可执行
低地址 └─────────────────┘  0x0000000000400000

2. 分页（Paging）

2.1 基本概念

将虚拟地址空间和物理内存都划分为固定大小的页（Page） / 帧（Frame）：

\[ \text{虚拟地址} = \underbrace{\text{VPN (Virtual Page Number)}}_{p} \;\|\; \underbrace{\text{Offset}}_{d} \]

\[ \text{物理地址} = \underbrace{\text{PFN (Physical Frame Number)}}_{f} \;\|\; \underbrace{\text{Offset}}_{d} \]

页表完成 VPN → PFN 的映射。偏移量不变。

常见页大小：4 KB（$2^{12}$ bytes），大页 2 MB / 1 GB。

2.2 单级页表

问题——页表太大：

32-bit 地址空间 + 4 KB 页 → $2^{20}$ 个 PTE → 若每项 4 字节 → 4 MB/进程
64-bit 地址空间 → 不可接受

2.3 多级页表

按需分配页表页，未使用的虚拟地址范围不分配页表。

以 x86-64 四级页表（48-bit 虚拟地址）为例：

虚拟地址 (48 bits):
┌──────┬──────┬──────┬──────┬────────┐
│ PML4 │ PDPT │  PD  │  PT  │ Offset │
│ 9bit │ 9bit │ 9bit │ 9bit │ 12bit  │
└──┬───┴──┬───┴──┬───┴──┬───┴────────┘
   │      │      │      │
   ▼      ▼      ▼      ▼
 PML4表 → PDPT表 → PD表 → PT表 → 物理帧

优势：

空间高效——仅为已使用的地址区间分配页表页
实际 48-bit 虚拟地址空间，大部分进程只用极小部分

代价：

一次地址转换需要 4 次内存访问（每级查一次）
TLB 的重要性更加突出

2.4 反向页表（Inverted Page Table）

以物理帧号为索引（而非虚拟页号）
全系统仅一张表，大小 = 物理帧数
查找需要哈希或线性搜索
用于 IA-64、PowerPC

2.5 TLB（Translation Lookaside Buffer）

页表翻译的硬件缓存（详见存储层次设计）。

\[ \text{EAT} = h \cdot (t_{\text{TLB}} + t_{\text{mem}}) + (1-h) \cdot (t_{\text{TLB}} + k \cdot t_{\text{mem}} + t_{\text{mem}}) \]

其中 $h$ 为 TLB 命中率，$k$ 为页表级数，$t_{\text{mem}}$ 为内存访问时间。

数值示例

TLB 命中率 = 99%，TLB 访问 = 1 ns，内存访问 = 100 ns，4 级页表：

\[\text{EAT} = 0.99 \times (1 + 100) + 0.01 \times (1 + 4 \times 100 + 100)$$ $$= 0.99 \times 101 + 0.01 \times 501 = 99.99 + 5.01 = 105 \text{ ns}\]

若无 TLB：每次访存都需 $5 \times 100 = 500$ ns——TLB 将访存时间降低了 4.7 倍。

3. 分段（Segmentation）

将地址空间划分为语义有意义的段（代码段、数据段、栈段等），每段有独立的基址和长度。

\[ \text{物理地址} = \text{Base}[\text{segment}] + \text{Offset} \]

分页 vs 分段	分页	分段
单位大小	固定	可变
外部碎片	无	有
内部碎片	有（最后一页）	无
对程序员可见	透明	可见（逻辑划分）

现代做法：分段 + 分页结合（x86 保留分段机制但段基址设为 0，实质纯分页）。

4. 页面置换算法

当物理内存不足时，需要选择页面换出到磁盘（swap）。

4.1 最优算法（OPT / Belady's MIN）

替换未来最久不会被使用的页面。

理论最优，作为其他算法的性能上界
不可实现（需要未来知识）

4.2 FIFO

替换最早进入内存的页面。

Belady 异常

FIFO 可能出现增加页面数反而缺页率上升的反直觉现象。

例：引用序列 1,2,3,4,1,2,5,1,2,3,4,5 - 3 个页面：9 次缺页 - 4 个页面：10 次缺页（更多！）

4.3 LRU（Least Recently Used）

替换最近最久未使用的页面。

基于时间局部性假设：过去访问模式预测未来
精确实现需要维护访问时间戳或栈 → 硬件开销大
属于栈算法，不会出现 Belady 异常

4.4 Clock 算法（近似 LRU）

实际操作系统最常用的替换算法：

环形链表，指针（时钟指针）扫描页面：

  检查 reference bit：
    1 → 清零，指针前进（给第二次机会）
    0 → 替换该页，指针前进

Enhanced Clock（考虑 dirty bit）：

(reference, dirty)	优先级	含义
(0, 0)	最优替换	未使用且未修改
(0, 1)	次优	未使用但已修改（需写回）
(1, 0)	较差	最近使用但未修改
(1, 1)	最差	最近使用且已修改

4.5 算法比较

算法	缺页率	开销	Belady 异常	实用性
OPT	最低	—	无	不可实现
LRU	接近 OPT	高	无	精确实现代价大
Clock	接近 LRU	低	无	最常用
FIFO	较高	最低	有	简单场景

5. 抖动（Thrashing）

5.1 定义

当进程的工作集超过可用物理内存时，频繁缺页导致系统大部分时间在做页面换入换出，CPU 利用率急剧下降。

5.2 工作集模型（Working Set Model）

工作集 $W(t, \Delta)$：在时间窗口 $\Delta$ 内进程引用的页面集合。

\[ \text{总需求} = \sum_{i} |W_i(t, \Delta)| \]

若总需求 > 物理内存 → 发生抖动。

操作系统策略：

监控每个进程的工作集大小
若总需求超出内存，挂起部分进程（中期调度）
恢复条件满足后重新激活

5.3 PFF（Page Fault Frequency）

更实用的抖动检测方法：

监控每个进程的缺页率
缺页率 > 上阈值 → 分配更多帧
缺页率 < 下阈值 → 回收部分帧
无帧可分配 → 挂起进程

6. 内存分配

6.1 内核级内存分配

连续内存分配

算法	策略	特点
First Fit	找到第一个足够大的空闲块	速度快，低地址碎片化
Best Fit	找最小的足够大的空闲块	减少浪费，但搜索慢、产生微小碎片
Worst Fit	找最大的空闲块	减少微小碎片，但大块很快用尽
Next Fit	从上次分配位置继续搜索	分布更均匀

伙伴系统（Buddy System）

Linux 物理内存分配的基础：

内存块大小为 $2^k$ 页（$0 \leq k \leq \text{MAX\_ORDER}-1$）
分配：找最小的满足需求的 $2^k$ 块；若过大则对半拆分
释放：检查伙伴块是否空闲，若空闲则合并为 $2^{k+1}$ 块

\[ \text{内部碎片} \leq 50\% \quad (\text{最坏情况：请求 } 2^{k-1}+1\text{，分配 }2^k) \]

优势：合并操作简单高效（伙伴地址仅一位不同）

Slab 分配器

Linux 内核对象（task_struct、inode 等）频繁分配释放，Slab 在 Buddy 之上提供对象级缓存：

预分配特定大小的对象池
释放的对象不归还，保留在缓存中复用
消除内部碎片，减少初始化开销

6.2 用户级内存分配

malloc / free 的实现（如 glibc ptmalloc、jemalloc、tcmalloc）：

分配器	特点
ptmalloc（glibc）	分 arena 减少锁竞争；bins 按大小分类
jemalloc（FreeBSD/Firefox）	线程本地缓存、更好的多线程扩展性
tcmalloc（Google）	小对象线程本地分配、大对象集中管理
mimalloc（Microsoft）	极致的小对象性能

7. 内存映射（Memory-Mapped I/O）

mmap 将文件或设备映射到进程地址空间：

用途	说明
文件映射	将文件内容映射为内存，按需加载（lazy loading）
匿名映射	分配不与文件关联的内存（大块 malloc）
共享映射	多进程共享同一物理页（IPC、共享库）
私有映射	COW（Copy-on-Write），写时复制

Copy-on-Write（COW）

fork() 时父子进程共享物理页面（标记为只读）：

父或子尝试写入 → 触发页面保护异常
内核复制该页 → 各自拥有独立副本
若子进程立即 exec() → 大部分页面从未复制（极高效）

8. 内存保护与安全

机制	功能
页表权限位	读/写/执行权限控制
NX bit	标记页面不可执行（防代码注入）
ASLR	地址空间布局随机化（防 ROP 攻击）
Guard Page	栈溢出检测（不可访问的哨兵页）
SMEP/SMAP	内核模式下禁止执行/访问用户空间内存

9. 性能优化实践

问题	优化
TLB miss 过多	使用大页（Huge Page）、减少地址空间碎片
缺页率高	增加物理内存、优化数据局部性
内存碎片	内存规整（compaction）、Slab 分配器
NUMA 延迟	NUMA 感知的内存分配（`numactl`、`mbind`）
Swap 过多	增加内存、调整 `swappiness`、使用 zswap 压缩

导航

上一节：进程与线程
下一节：文件系统与IO
相关：存储层次设计