2.1 - 内存基础 | QuetzalSidera 的个人博客

一篇围绕 Unix 内存管理展开的总览笔记。

进程基础中已介绍地址空间是进程的核心资源。本篇聚焦操作系统如何将有限、离散的物理内存组织为进程看到的地址空间。

本篇是内存一章的入口，建立后续反复出现的主线：地址转换、连续与非连续分配、分页与页表、交换与请求调页、写时复制以及 mmap 的映射模型。不展开内核分配器实现和具体平台细节。

导览

1. 核心问题

内核要在进程视图和物理布局之间维持映射、保护和复用，本章的主干可以展示如下：

内存虚拟化：逻辑地址与物理地址的区分。
内存管理：

分配：连续分配/分段/分页与碎片的消除，以及带来的页表和地址转换成本。
交换：物理内存不足时的交换、请求调页与页置换。

内存映射：文件和设备进入地址空间的映射模型。
内存保护：多进程共享物理内存时的隔离与保护。

2. 路线图

部分	核心问题
地址转换	CPU 产生的地址如何落到物理内存
连续分配	一段连续物理内存如何分给一个进程
非连续分配	分段、分页如何把逻辑视图和物理布局分开
内存优化	物理内存不足时如何维持执行
内存映射	文件和设备如何进入地址空间

地址转换

1. 地址绑定

程序里的地址最终都要绑定到物理内存，但绑定时机并不相同：

绑定时机	含义	特点
编译时绑定	编译器直接生成绝对地址	只有装入位置固定时才成立
装入时绑定	装入内存时再决定起始位置	装入后位置固定
运行时绑定	指令执行时再做地址转换	最灵活，也是现代系统主流

现代系统几乎都依赖运行时绑定，因为进程既不知道自己会被装到哪段物理内存，也不能要求整个生命周期都固定不动。

2. 逻辑地址、物理地址与 MMU

运行时绑定意味着要区分两类地址：

A_{L} \overset{MMU}{\to} A_{P}

对象	含义
逻辑地址 $A_{L}$	CPU 执行指令时产生的地址，也常叫虚拟地址
物理地址 $A_{P}$	最终送到内存总线上的地址

MMU（Memory Management Unit）负责把 $A_{L}$ 翻译成 $A_{P}$ ，并做越界和权限检查。地址转换至少包含两件事：

按当前内存管理方案完成映射。
在映射过程中拒绝非法访问。

3. 虚拟地址空间

地址转换对于进程而言是透明的，进程看到的是一个只有自身使用的连续的虚拟地址空间；它在物理内存中是否连续，由内核和 MMU 决定。后面的分段、分页、交换，本质上都在维护这层连续视图。

连续分配

1. 基址寄存器与界限寄存器

最直接的方案，是给每个进程分配一段连续物理内存，并用两类寄存器完成重定位和保护：

硬件对象	作用
基址寄存器 `base`	该进程对应物理区间的起始地址
界限寄存器 `limit`	该进程允许访问的区间长度

若逻辑地址为 $a_{L}$ ，则

0 \leq a_{L} < l i m i t, a_{P} = b a s e + a_{L}

否则触发越界异常。

这一方案简单，但要求整个进程占用连续物理内存，进程增长时很容易和周围空闲区冲突。

2. 空闲空间管理

连续分配需要维护一组空闲孔洞（hole），并决定把哪块空闲区分给新进程或扩展请求。

策略	核心思路	典型问题
首次适应 `first-fit`	找到第一块足够大的空闲区就分配	前部区域容易碎
最优适应 `best-fit`	找到最接近请求大小的空闲区	容易留下很多小碎片
最差适应 `worst-fit`	优先使用最大的空闲区	实际效果通常不好
下次适应 `next-fit`	从上次结束处继续查找	效果依赖内存分布

这些分配方法大同小异，只是减少但并没有消除连续分配本身的碎片问题。

3. 碎片

类型	含义	常见来源
内部碎片	已分配但未使用	固定粒度分配，如分页
外部碎片	未分配但因不连续而难以分配	连续分配、可变分区

连续分配最典型的问题是外部碎片。解决方向有两类：

方向	核心做法
紧凑 `compaction`	搬移进程，把零散空闲区压成连续大块
非连续分配	允许一个进程分散放在多个物理位置

前者的代价太高，而且对动态分配不友好，后者就是分段和分页。

非连续分配

1. 分段

分段按程序的逻辑模块组织内存，例如代码段、数据段、堆、栈。逻辑地址写成

L A = (s, d)

其中 $s$ 是段号， $d$ 是段内偏移。若段表给出该段基址 $b a s e_{s}$ 和界限 $l i m i t_{s}$ ，则

0 \leq d < l i m i t_{s}, P A = b a s e_{s} + d

分段的优点是符合程序结构，也便于按段设置权限和共享；缺点是每一段仍要求连续，因此外部碎片仍然存在。

2. 分页

分页把逻辑地址空间切成固定大小的页，把物理内存切成 同样大小 的页框( 在有的教材中，也将“页”称为“虚拟页”，“页框”称为“物理页”)。

对象	含义
页 `page`	逻辑地址空间中的固定大小块
页框 `frame`	物理内存中的固定大小块

逻辑地址与物理地址可写成：

L A = (p, d), P A = (f, d)

其中 $p$ 是页号， $d$ 是页内偏移， $f$ 是页框号。若页表为 $P T$ ，则

f = P T [p], P A = f \times p a g e_s i z e + d

页表项通常包含：

字段	作用
页框号	该页当前所在物理页框
有效位	该页当前是否可访问 / 是否在内存中
保护位	读写执行权限
修改位 `dirty bit`	该页是否被写过
引用位 `reference bit`	该页近期是否被访问过

分页的关键收益是：进程地址空间仍然保持线性视图，但底层物理页框可以离散放置。它基本消除了外部碎片，但会引入页内未用空间，也就是内部碎片。

这也意味着，操作系统分配内存的单位从“字节”变成了“页”。这也是为什么在一些程序中越界访问内存并没有陷入操作系统，因为虽然越界，但并没有超出所在的页。

3. TLB

分页引入了一个直接成本：页表本身在内存里，所以一次内存访问至少会变成两步：

先查页表，拿到页框号。
再访问目标地址。

TLB（Translation Lookaside Buffer）是页表项缓存，用来降低这部分开销。

情况	路径
`TLB hit`	`page -> TLB -> frame -> memory`
`TLB miss`	`page -> page table -> frame -> memory`

在忽略 TLB 查找时间时，若主存访问时间为 $t_{M}$ ，TLB 命中率为 $h$ ，则有效访问时间可近似写成：

E A T \approx h \cdot t_{M} + (1 - h) \cdot 2 t_{M}

由于页表通常是进程独立的，TLB 里的地址转换结果也天然带有进程语义。若硬件不区分地址空间，那么每次上下文切换后，旧进程留下的 TLB 项都可能失效，因此需要刷新 TLB。ASID（Address Space Identifier）就是为这个问题引入的标签：它把 TLB 项和某个地址空间绑定，使不同进程的 TLB 项可以共存，从而减少上下文切换时的刷新开销。

TLB 只优化地址转换成本，不改变分页模型本身。

4. 页表组织

分页继续往下走，会遇到第二个问题：虚拟地址空间越大，线性页表越大。于是便衍生了多种页表结构。

a. 线性页表

最直接的方案是一张连续数组：

f = P T [p]

优点是简单；问题是空间开销与虚拟页数线性相关。地址空间很大时，页表本身就会变成负担。

b. 多级页表

多级页表把页号拆成多段：

p = (p_{1}, p_{2}, \dots, p_{k})

地址转换变成逐级索引，每一级都是线性页表：

P T^{(1)} [p_{1}] \to P T^{(2)} [p_{2}] \to \dots \to P T^{(k)} [p_{k}] \to f

在访问内存时，使用 $p_{1}$ 索引 $P T^{(1)}$ ，得到下一级页表 $P T^{(2)}$ 的指针。再使用 $p_{2}$ 索引 $P T^{(2)}$ ，以此类推，最后一级得到页框号。

这样的优点在于可以将相似的页表项合并，例如[0x00010000,0x00020000)可以在顶级页表中用一项 0x0001表示。

而缺点在于多级索引导致的多次内存访问，这也是“时间换空间”的一个典型例子。

c. 哈希页表

哈希页表适合很大的地址空间。它用虚拟页号做哈希：

h = H (p i d, p)

然后在桶中查找匹配项 $< p i d, p, f >$ 。它不要求维护一张完整的线性表，但查找成本受哈希分布影响。

d. 反向页表

反向页表不再使用“虚拟页号”作为索引，而是使用“物理页框号”作为索引。每个物理页框对应一个表项，记录当前页框的分配状态：

E n t r y [f] = (p i d, p)

这等于把“每个进程一张页表”压成了“整个系统围绕物理页框维护一张表”。它的空间开销与物理页框数相关，而不与虚拟地址空间线性增长；代价是从 $< p i d, p >$ 反查 $f$ 的查询路径更长，通常需要额外的哈希或搜索结构来控制查找开销。

从这里也可以看出，虽然内存被称为RAM (Random Access Memory)，但是访问每一个目标的开销并不是相等的，受到缓存与页表结构的多方面影响。

内存优化

1. 交换与请求调页

物理内存不足时，系统必须把一部分内容移到磁盘，或在从磁盘加载时选择性读取，分别对应以下：

概念	单位	含义
交换 `swapping`	传统上以整个进程为单位	把进程整体换出，再在需要时换回
请求调页 `demand paging`	以页为单位	访问到某页时，才把它调入内存

当需要访问某虚拟页，但此页并没有在物理内存上（被换出或未加载）时，操作系统将触发缺页异常。

缺页异常的处理流程可以表述如下：

CPU 访问某页，发现页表项标记为“不在内存”。
触发缺页异常，转入内核。
找到该页在后备存储中的位置。
若没有空闲页框，先选一个牺牲页。
牺牲页若为脏页，则先写回磁盘。
把目标页读入页框，更新页表和 TLB，再恢复执行。

与此同时，若在初次加载时，加载的页面数目过少，会导致程序运行初期频繁触发缺页异常（抖动）。因此操作系统总是在空间与时间中进行折中。

页置换

在交换时若物理内存不足，将不得不把一些页面移到磁盘。页置换回答的便是：没有空闲页框时，淘汰谁。

算法	淘汰依据	特点
`OPT`	未来最久不会再用的页	理论最优，只能作为比较基线
`FIFO`	最早进入内存的页	实现简单，但可能淘汰热点页，甚至出现 Belady 异常
`LRU`	最近最久未使用的页	更贴近局部性，但精确实现成本高
`Clock`	用引用位近似 `LRU`	工程上常见，成本和效果折中

设物理内存有3个页框，考虑如下顺序访问序列：

1, 2, 3, 4, 1, 2, 3, 4

下表展示了不同算法的累计缺页次数与当前页框 (累计缺页次数 - 当前页框)

序列	访问目标	`OPT`	`FIFO`	`LRU`
1	1	1次 - 001	1次 - 001	1次 - 001
2	2	2次 - 012	2次 - 012	2次 - 012
3	3	3次 - 123	3次 - 123	3次 - 123
4	4	4次 - 124	4次 - 234	4次 - 423
5	1	4次 - 124	5次 - 341	5次 - 413
6	2	4次 - 124	6次 - 412	6次 - 412
7	3	5次 - 134	7次 - 123	7次 - 312
8	4	5次 - 134	8次 - 234	8次 - 342
对比	-	理论最优	顺序访问极差	顺序访问极差

在顺序访问（如多次遍历数组）的情况下，FIFO与LRU表现得几乎一样糟，每次内存访问都出现了缺页错误。

再看另一个例子，设物理内存有3个页框，考虑如下随机访问序列：

1, 2, 3, 4, 2, 1, 5, 2, 1, 6, 2, 1, 7

下表展示了不同算法的累计缺页次数与当前页框 (累计缺页次数 - 当前页框)

序列	访问目标	`OPT`	`FIFO`	`LRU`
1	1	1次 - 001	1次 - 001	1次 - 001
2	2	2次 - 012	2次 - 012	2次 - 012
3	3	3次 - 123	3次 - 123	3次 - 123
4	4	4次 - 124	4次 - 234	4次 - 423
5	2	4次 - 124	4次 - 234	4次 - 423
6	1	4次 - 124	5次 - 341	5次 - 421
7	5	5次 - 125	6次 - 415	6次 - 521
8	2	5次 - 125	7次 - 152	6次 - 521
9	1	5次 - 125	7次 - 152	6次 - 521
10	6	6次 - 126	8次 - 526	7次 - 621
11	2	6次 - 126	8次 - 526	7次 - 621
12	1	6次 - 126	9次 - 261	7次 - 621
13	7	7次 - 127	10次 - 617	8次 - 721
对比	-	理论最优	只看进入时间，无法利用局部性	通常比 `FIFO` 更接近实际局部性

也就是说，页置换算法的核心在于如何估计“下一页谁最不可能被访问”，以减少缺页错误的发生频率。 LRU利用了内存访问的时间局部性，因此随机访问表现比FIFO更好。

2. 写时复制与只读共享

写时复制（COW, copy on write）和只读共享的作用，都在于减少物理页占用和不必要的复制。

机制	做法	典型场景
写时复制	初始共享同一物理页，真正写入时再复制	`fork` 之后的地址空间复制
只读共享	多个进程长期共享同一份只读页面	代码页、共享库

二者的区别在于：前者允许后续写入，但写入时会复制物理页；后者根本不允许写入。

3. 抖动与控制

抖动（thrashing）是指进程分到的页框太少，导致系统大部分时间都在缺页、换页，而导致CPU利用率下降的现象。

它常表现为一条恶性循环：

页框不足，缺页率上升。
调页I/O增多，CPU利用率下降。
调度器可能会在此时提高多道程度，以提高CPU利用率。
进程数变多后，每个进程可用页框更少。
缺页率进一步上升，抖动加重。

控制抖动常用两类方法。

a. 工作集模型

设进程 $i$ 在时刻 $t$ 的工作集窗口为 $Δ$ ，则

W_{i} (t, Δ) = {p ∣ p 在 (t - Δ, t] 内被访问过}

工作集大小记为

W S S_{i} = | W_{i} (t, Δ) |

系统总需求为

D = \sum_{i} W S S_{i}

若系统总页框数为 $m$ ，当

D > m

时，说明所有进程当前活跃页的总需求已经超过物理内存，抖动风险很高。

工作集模型的实现通常不是精确记录每次访问，而是用引用位 + 定时中断 做近似，周期性地判断“哪些页在最近一段窗口内被用过”，从而将这些页加入工作集，并从工作集剔除未使用的页。

b. 缺页率控制 `PFF`

另一种更直接的方法是监控缺页率 $P F F_{i}$ ，并设置上下界 $α < β$ ：

α \leq P F F_{i} \leq β

若

P F F_{i} > β

则说明当前页框太少，应增加页框，或在没有空闲页框时换出别的进程；若

P F F_{i} < α

则说明页框可能分多了，可以回收一部分。

工作集模型直接估计“当前需要多少页”，PFF 直接观察“当前缺页是否过多”。二者的目标一致，都是避免进程在局部尚未装入时被迫反复换页。

内存映射

1. 内存映射文件

内存映射文件把文件页纳入进程地址空间。第一次访问映射区时，仍可能因为页不在内存而触发缺页；一旦映射建立，后续读写就按普通内存访问处理。

它的价值主要有三点：

把文件访问统一到地址空间模型里。
支持按页调入，而不是整文件读入。
便于多个进程共享同一份文件页。

2. 内存映射 I/O

内存映射 I/O 不是把文件映射进地址空间，而是把设备寄存器或设备缓冲区映射进地址空间，让 CPU 通过读写特定地址访问设备。

类型	背后对象	典型用途
内存映射文件	文件页	文件访问、共享库、共享数据
内存映射 I/O	设备寄存器、显存、控制缓冲区	驱动、显卡、设备控制

二者共同点是“都通过地址空间访问”，区别只在于背后的对象是文件还是设备。

小结

本篇介绍了内存一章的主干：

主线	结论
地址转换	`MMU` 负责把逻辑地址翻译成物理地址
分配方式	连续分配简单但易碎片，分页更适合现代系统
页表与 `TLB`	一个解决映射存储，一个解决映射开销
内存优化	请求调页、页置换、`COW` 让有限物理内存可被复用
内存映射	文件和设备都可以进入地址空间

2.1 - 内存基础

导览 ​

1. 核心问题 ​

2. 路线图 ​

地址转换 ​

1. 地址绑定 ​

2. 逻辑地址、物理地址与 MMU ​

3. 虚拟地址空间 ​

连续分配 ​

1. 基址寄存器与界限寄存器 ​

2. 空闲空间管理 ​

3. 碎片 ​

非连续分配 ​

1. 分段 ​

2. 分页 ​

3. TLB ​

4. 页表组织 ​

a. 线性页表 ​

b. 多级页表 ​

c. 哈希页表 ​

d. 反向页表 ​

内存优化 ​

1. 交换与请求调页 ​

页置换 ​

2. 写时复制与只读共享 ​

3. 抖动与控制 ​

a. 工作集模型 ​

b. 缺页率控制 PFF ​

内存映射 ​

1. 内存映射文件 ​

2. 内存映射 I/O ​

小结 ​

导览