计算机系统基础-06：虚拟内存

虚拟内存

物理寻址

主存可视为一个连续字节数组，每个字节有唯一物理地址，从 0 开始编号。

物理寻址中，CPU 直接用物理地址访问主存。早期 PC、DSP 和部分嵌入式微控制器可采用这种方式。

1	CPU --{PA}--> Main Memory

虚拟寻址

虚拟内存是操作系统和硬件共同提供的内存抽象。CPU 使用虚拟地址访问内存，MMU 将虚拟地址翻译为物理地址。

虚拟内存的主要作用：

作为缓存工具：把 DRAM 作为虚拟地址空间中活跃页面的缓存。

简化内存管理：每个进程看到相同形式的线性虚拟地址空间。

隔离地址空间：一个进程不能直接访问另一个进程的内存。

提供内存保护：用户程序不能直接访问内核数据，页面可按读、写、执行权限保护。

虚拟寻址中，CPU 产生虚拟地址（Virtual Address, VA），再由 MMU 翻译为物理地址。

1	CPU --{VA}--> MMU --{PA}--> Main Memory

地址翻译需要硬件和操作系统协作：

MMU：CPU 芯片上的硬件，动态执行地址翻译。
页表：存放在主存中的查找表，由操作系统维护。

现代服务器、桌面和笔记本系统都使用虚拟寻址。

硬件地址翻译必须足够简单。课堂中多次强调：CPU 适合执行固定、快速、规则的查表逻辑，因此页表、异常表、物理内存和虚拟内存都被组织成类似数组的结构。MMU 不能在每次访存时执行复杂数据结构搜索，否则会直接限制 CPU 主频和访存流水线性能。

只使用物理地址会有什么问题？

物理内存容量有限，多个进程和大程序无法都完整常驻主存。

程序直接使用物理地址会互相冲突，链接器和加载器必须关心其他程序占用了哪些地址。

进程缺少隔离，一个程序可能直接读写另一个程序或内核的数据。

共享库、按需加载、页面换入换出等机制难以统一实现。

地址空间

地址空间是非负整数地址的有序集合。线性地址空间是连续非负整数地址集合：

1	{0, 1, 2, 3, ...}

若虚拟地址有 $n$ 位，则虚拟地址空间大小为 $N = 2^n$ ；若物理地址有 $m$ 位，则物理地址空间大小为 $M = 2^m$ 。

每个对象可同时具有：一个物理地址；一个或多个虚拟地址。

一个物理对象为什么可以有多个虚拟地址？

解析：

虚拟地址属于进程私有地址空间，同一物理页可被多个进程的不同 VA 映射。

共享库代码是典型例子：库文件内容最初在磁盘上，加载后可在物理内存中只保留一份。

不同进程的页表项可指向同一物理页，从而共享只读代码或共享映射区域。

每个进程看到的是自己的虚拟地址；真正的数据位置由 PTE 中的物理页号决定。

常见虚拟地址位数：

虚拟地址位数	虚拟地址数量	最大虚拟地址
8	256	255
16	64K	64K - 1
32	4G	4G - 1
48	256T	256T - 1
64	16E	16E - 1

$K=2^{10}$ ， $M=2^{20}$ ， $G=2^{30}$ ， $T=2^{40}$ ， $P=2^{50}$ ， $E=2^{60}$ 。

页与页表

页

虚拟内存和物理内存都按页面组织。页面大小通常为 $2^p$ bytes，常见为 4KB。

名称	含义
Virtual Page, VP	虚拟页
Physical Page, PP	物理页，也称 page frame

页面是磁盘和主存之间的传输单位。

虚拟页有三种状态：

状态	含义
Unallocated	尚未由 VM 系统分配或创建，没有关联数据
Cached	已分配，当前缓存在物理内存中
Uncached	已分配，但当前不在物理内存中

未缓存在 DRAM 中的已分配页面通常位于磁盘上的可执行文件、映射文件或 swap space 中。

页表

页表记录虚拟页到物理页的映射。每个已分配虚拟页有一个页表项（Page Table Entry, PTE）。

PTE 可能表示：

页面在内存中：PTE 给出物理页号。
页面不在内存中：PTE 给出磁盘位置或由 OS 维护的相关信息。
页面非法或未分配：访问会触发异常。

页表由操作系统管理，由 MMU 查询。

为什么页表适合设计成数组式查表？

硬件需要在极短时间内完成地址翻译，数组索引可以由基地址加偏移直接计算。

页表项大小固定，VPN 可直接作为索引或被拆成多级索引。

CPU 只需实现简单的加法、位切分和内存读取逻辑。

若采用复杂树或哈希结构，硬件实现和最坏情况延迟都更难控制。

虚拟内存作为缓存

DRAM 可视为虚拟页的缓存。虚拟内存系统按需把页面从磁盘加载到 DRAM。

Page Hit

若访问的虚拟页已经缓存在物理内存中：

CPU 产生虚拟地址。
MMU 查询页表。
PTE 有效并给出 PPN。
MMU 形成物理地址。
Cache 或主存返回数据。

Page Fault

若 PTE 表示页面不在物理内存中，则发生 page fault。

处理流程：

CPU 产生虚拟地址并交给 MMU。
MMU 查询页表，发现 valid bit 为 0。
MMU 触发 page fault exception。
CPU 转入内核态，将控制流切换到 OS 的 page fault handler。
handler 判断 faulting address 是否可恢复：若页面已分配但未缓存，则准备调入；若地址或权限非法，则发送信号。
若需要空闲物理页，handler 选择 victim page；若 victim 为 dirty，则写回磁盘。
handler 从磁盘或匿名零页来源准备目标页，更新 PTE。
handler 返回原进程，重新执行 faulting instruction。

页面调入过程使用 DMA：

处理器通知 I/O 控制器从磁盘地址 X 读取长度为 P 的块，写入内存地址 Y。
I/O 控制器通过 DMA 把磁盘数据写入内存。
进程在 I/O 完成前通常被阻塞，CPU 可调度其他进程执行。
I/O 完成后，控制器通过 interrupt 通知处理器。
OS 根据中断来源找到等待该 I/O 的 page fault 请求，更新页表并恢复被挂起进程。

换入页面时找不到空闲物理页怎么办？

OS 必须先选择一个当前不适合继续保留在主存中的 victim page。

若 victim page 为 dirty，需要先写回磁盘或 swap space。

写回或丢弃后，该物理页变为空闲页。

OS 再把目标虚拟页从磁盘、映射文件或匿名零页来源调入该物理页。

最后更新 faulting page 的 PTE，并恢复 faulting instruction。

DMA 完成后为什么需要 interrupt？

DMA 由 I/O 控制器直接把数据搬到主存，CPU 不需要逐字节参与复制。

CPU 在 DMA 期间可以运行其他任务，不能一直等待设备完成。

I/O 控制器完成数据搬运后，通过 interrupt 通知 CPU。

OS 在中断处理路径中识别对应的 I/O 请求，再恢复等待该页面的进程。

Page Fault 的三类情况

情况	说明
Swapped / paged in	页面之前被换出，需要从 swap 或文件调回
Demand paging	页面首次访问时才分配和载入，例如文件映射页或匿名零页
Segmentation fault	地址非法或权限不合法，内核向进程发送 `SIGSEGV`

其中 demand paging 包括两类常见场景：

文件支持的页面：execve、动态链接库或 mmap 文件区域只先建立 VMA 与文件的映射关系；真正访问某页时，page fault handler 才把该页内容读入内存。
匿名页面：堆、栈、MAP_ANON 映射没有实际文件来源。OS 可先只分配虚拟地址范围；首次写入时再分配全 0 物理页并填入 PTE。

malloc 申请大块堆空间时，为什么 OS 不立即分配所有物理页？

malloc 可能通过 C 库一次性向 OS 申请较大的虚拟堆区域，但应用实际只使用其中一部分。

若 OS 立即为整段区域分配物理页，会把未访问区域也占入主存，形成浪费。

对匿名堆页，OS 可以先建立 VMA 或扩展堆边界，不填实际 PTE。

当程序执行 memset、memcpy 或普通读写并首次触碰某页时，再通过 demand-zero page fault 分配全 0 物理页。

Segmentation fault 和普通 page fault 的关系是什么？

从 CPU/MMU 角度看，二者都先表现为 page fault exception。

CPU 不判断该 fault 是否可恢复，只负责转入内核异常处理流程。

OS 检查 VMA 与权限后，如果发现地址合法且可按需调入，就恢复执行。

如果地址未分配、权限不允许，或访问类型非法，OS 才向进程发送 SIGSEGV。

虚拟内存依赖局部性。任意时刻，程序倾向于访问一组活跃虚拟页，称为 working set。

时间局部性越好，working set 越小。
若 working set 小于主存容量，程序在强制缺页（首次访问没有装入过）后可获得较好性能。
若所有进程 working set 总和大于主存容量，系统会不断换入换出页面，称为 thrashing。

虚拟内存作为内存管理工具

链接与加载

每个进程有自己的虚拟地址空间。进程把内存看成从 0 到 $N-1$ 的线性数组。

因为每个进程看到相似的虚拟地址空间，链接器和加载器可以使用固定布局：

498

execve 运行新程序时：

释放旧程序的 vm_area_struct 和页表。
为新程序创建新的 VM areas 和页表，包括 stack、bss、data、text、shared libraries。
.text 和 .data 由 ELF 可执行文件支持。
.bss 和 stack 初始为 0。
设置 PC 为 .text 入口。
代码和数据页面按需调入。

execve 按需分页的收益是什么？

程序启动时不需要立即把所有代码和数据读入内存。

只访问过的页面才触发 page fault 并调入。

可减少启动时间和初始内存占用。

对大型程序和共享库尤其有效。

物理页分配

一个虚拟页可以映射到任意物理页。同一虚拟页在不同时间也可映射到不同物理页。

这使操作系统可以：

灵活分配物理内存。
移动或换出页面。
让不同进程使用相同虚拟地址但映射到不同物理页。

同一虚拟页能否先后映射到不同物理页？

可以。假设某个虚拟页最初映射到 PP2，之后该页被换出，PP2 被其他用途占用。下一次该虚拟页触发 page fault 时，OS 只需选择新的空闲物理页，例如 PP8，把磁盘或文件中的页面内容调入 PP8，再把 PTE 改为指向 PP8。

对用户进程而言，虚拟地址不变；变化只发生在 OS 维护的 VA 到 PA 映射中。这是分页管理提供灵活性的核心。

不同进程可把各自虚拟页映射到同一物理页。例如只读共享库代码可由多个进程共享。

共享时，虚拟地址可以不同，但 PTE 指向同一物理页。

虚拟内存作为保护工具

PTE 可扩展权限位，例如：

read permission。
write permission。
execute permission。
user/supervisor permission。

同一物理页可在不同进程中具有不同权限。page fault handler 会检查：

虚拟地址是否属于某个合法 VMA。
访问类型是否符合该 VMA 权限。
PTE 权限是否允许该访问。

若违反权限，内核向进程发送 SIGSEGV。

地址翻译

地址翻译可定义为 $MAP: V \rightarrow P \cup \{\emptyset\}$ 。若 $MAP(a)=a'$ ，表示虚拟地址 $a$ 对应物理地址 $a'$ ；若 $MAP(a)=\emptyset$ ，表示该虚拟地址对应数据当前不在物理内存，或地址非法。

基本参数：

参数	含义
$N=2^n$	虚拟地址空间大小
$M=2^m$	物理地址空间大小
$P=2^p$	页面大小

虚拟地址分为：

1	\| VPN \| VPO \|

物理地址分为：

1	\| PPN \| PPO \|

其中：

VPN：Virtual Page Number。
VPO：Virtual Page Offset。
PPN：Physical Page Number。
PPO：Physical Page Offset。
由于页内偏移不变，PPO = VPO。

MMU 如何从 VA 找到 PTE？

MMU 先把 VA 拆成 VPN 和 VPO。

页表基地址由控制寄存器提供，x86 中典型为 CR3。

在单级页表中，PTEA = PTBR + VPN * sizeof(PTE)。

在多级页表中，VPN 被拆成多段索引，每一级索引都在当前页表页中选择一个 PTE。

页表本身也存放在物理内存中，因此读取 PTE 可能命中 cache，也可能继续访问主存。

PTE 中的 PPN 如何变成 PA？

PTE 保存的是物理页号 PPN，不需要保存完整物理地址。

VA 的页内偏移 VPO 在翻译后保持不变，直接作为 PPO。

最终物理地址由 PPN 与 VPO 拼接得到，即 PA = (PPN << p) | VPO。

这里是按位拼接，不是把完整物理地址和 offset 简单相加。

地址翻译示例：

14-bit virtual address。

12-bit physical address。

page size = 64 bytes，因此 $p=6$ 。

页表只展示前 16 项。

页表：

问题：翻译虚拟地址 0x03D4。

解析：

页面大小为 $2^6=64$ bytes，所以低 6 位是 VPO。

0x03D4 = 980_{10}。

VPN 为 0x03D4 >> 6 = 0x0F。

VPO 为 0x03D4 & 0x3F = 0x14。

查询页表 PTE[0x0F]，valid bit 为 1，PPN 为 0x0D，无 page fault。

物理地址为 (PPN << 6) | VPO = (0x0D << 6) | 0x14 = 0x354。

结论：

TLB 加速

多数 cache 使用物理地址访问。这样可以：

允许多个进程的 cache block 同时存在。
允许多个进程共享同一物理页。
将保护检查放在地址翻译阶段完成。
进程切换时不必清空 cache，因为物理地址不会因进程不同而产生歧义。

问题是：cache lookup 前需要先完成地址翻译，而地址翻译本身可能访问内存中的 PTE。

TLB（Translation Lookaside Buffer）是 MMU 内的小型硬件缓存，用于缓存 VPN 到 PPN 的映射。MMU 通过 PTEA 访问映射表的时候，返回的 PTE 可以缓存在 TLB 中，进行地址翻译的时候如果 hit 则可以直接传递 PA 访问物理内存，而不是到 PTE 重复取映射关系。

TLB hit 可避免访问内存中的 PTE。
TLB miss 需要额外访问页表。

TLB miss 不等于 page fault：

TLB miss：TLB 中没有该 VPN 的缓存映射。MMU 继续查页表；若 PTE present 且权限合法，可把映射填入 TLB 并继续访问。
Page fault：页表检查失败，常见原因是 PTE 不 present、地址未分配或权限不合法，需要进入 OS handler。

在多级页表下，TLB miss 的代价更高。若 x86-64 四级页表全部需要访问内存，地址翻译本身最多需要读取 4 个页表项；再加上最终数据访问，本来一次访存可能变为多次内存访问。因此 TLB 是多级页表可接受的关键条件。

加入 TLB 的 VPN 被切分成 TLBT 和 TLBI 两部分，物理地址则保持不变。翻译流程如下：

为什么 cache 通常不直接按虚拟地址访问？

虚拟地址属于进程私有地址空间，不同进程的同一 VA 可映射到不同 PA。

如果 cache 直接以 VA 标识数据，进程切换时可能需要 flush cache，代价远高于 flush TLB。

TLB 只缓存地址翻译项，容量较小；cache 保存真实数据，容量大得多，频繁 flush 会严重影响性能。

使用物理地址可让不同进程的 cache line 同时存在，也可自然支持共享物理页。

为什么 TLB miss 通常不频繁？

程序具有时间局部性，会反复访问同一批虚拟页。

程序具有空间局部性，一个页面包含多个相邻字节，一次 TLB entry 可覆盖整个页。

常用页面集中在 working set 中，TLB 可缓存其中的热页映射。

多级页表

单级页表在大地址空间下占用过大：

x86 32-bit，4KB page，4-byte PTE：VPN 为 20 位，需要 $2^{20}$ 个 PTE，总大小为 $2^{20}\times4=4$ MB。
x86-64 48-bit effective VA，4KB page，8-byte PTE：VPN 为 36 位，需要 $2^{36}$ 个 PTE，总大小为 $2^{36}\times8=512$ GB。

通用解决方案是多级页表。

多级页表解决两个问题：

按需分配页表页：只有已分配虚拟区域对应的下级页表页需要存在；未分配区域不需要二级或更低级页表。
避免大块连续物理内存：单级页表必须是一段连续数组；多级页表只要求每个页表页自身连续，不同页表页可放在任意物理页中。

多级页表为什么既能覆盖完整地址空间，又能节省空间？

若所有下级页表页都存在，多级页表的索引组合仍可覆盖完整虚拟地址空间。

以 32-bit 10-10-12 为例，一级 10 位、二级 10 位、页内偏移 12 位，总计 32 位。

节省空间不是因为覆盖能力变小，而是因为未分配虚拟区域的下级页表页可以不创建。

若地址空间被密集使用，多级页表需要大量下级页表页，还会额外引入中间层开销。

x86-32 两级页表

32-bit 地址，4KB page，4-byte PTE 时，地址可按 10-10-12 划分：

1	\| Level-1 index: 10 \| Level-2 index: 10 \| Offset: 12 \|

一级页表有 1024 项，每项指向一个二级页表。
每个二级页表有 1024 项，每项指向一个 4KB 页面。
若某段虚拟空间未分配，对应二级页表可不创建。

这里的字段宽度来自页表页大小和 PTE 大小的匹配：一个页表页为 4KB，32-bit PTE 为 4 bytes，因此一个页表页可容纳 $4096/4=1024=2^{10}$ 个 entry，需要 10 位索引。4KB page 的页内偏移为 12 位，所以 32-bit VA 剩余 20 位可拆成两级 10+10。

两级页表仍保持数组式查表：CR3 或页表基址寄存器给出一级页表页的物理基地址，一级索引找到 PDE，PDE 给出二级页表页地址，二级索引找到最终 PTE。

为什么 10-10-12 中两个索引都是 10 位？

32-bit 机器中 PTE 可用 4 bytes 表示。

一个页表页大小为 4KB，因此可存放 $4\text{KB}/4\text{B}=1024$ 个 PTE。

索引 1024 个 entry 正好需要 10 位。

offset 为 12 位来自 4KB page size，剩余 20 位自然拆成两个 10 位索引。

x86-64 四级页表

x86-64 当前常用 48-bit effective virtual address。64-bit 虚拟地址需满足 canonical address 规则：高 16 位必须复制第 47 位。

48-bit 地址划分：

1 2	\| 63:48 \| 47:39 \| 38:30 \| 29:21 \| 20:12 \| 11:0 \| \| sign \| L1 \| L2 \| L3 \| L4 \| offset \|

每级索引 9 位，每个页表页大小为 4KB，每个 PTE 为 8 bytes，因此每个页表页有 512 项。

CR3 寄存器保存一级页表页的物理基地址。页表项中保存下一级页表页或最终物理页的物理地址。

9 位索引同样来自页表页容量： $4096/8=512=2^9$ 。因此一个 48-bit effective VA 可拆成 4 级索引和 12 位 offset，即 9-9-9-9-12。高 16 位不参与普通 48-bit 地址翻译，只用于 canonical address 检查。

四级页表中每一级最多有多少个页表页？

顶级页表页只有 1 个，其物理基地址由 CR3 保存。

第二级最多有 $512$ 个页表页，因为顶级页表页最多有 512 个 entry。

第三级最多有 $512^2$ 个页表页。

第四级最多有 $512^3$ 个页表页。

每个页表页内有 512 个 PTE，这是“页表页数量”和“页表项数量”的区别。

页表项中保存的是物理地址还是虚拟地址？

物理地址。硬件页表遍历发生在地址翻译过程中，不能依赖尚未翻译的虚拟地址。

每个 L4 页表页可映射 $512 \times 4\text{KB} = 2\text{MB}$ 。每个 L3 entry 覆盖一个 L4 页表页可映射的范围，即 2MB。

若只分配一条完整页表路径：L1、L2、L3、L4 各一个页表页，总页表大小为 16KB。此时若 L4 表中 512 项都填写，可以翻译一个 2MB 连续虚拟地址范围。

稀疏虚拟页的页表开销：

如果进程只用到虚拟页 0、1、2^36-1。

单级页表：

48-bit VA，4KB page，因此 VPN 为 36 位。

由于页表视为一个连续的大数组，因此中间的全部 PTE 不能跳过，需要 $2^{36}$ 个 PTE。

每个 PTE 为 8 bytes。

总大小为 $2^{36}\times8=2^{39}\text{ bytes}=512\text{GB}$ 。

四级页表：

虚拟页 0 和 1 在同一路径下，共享 L1、L2、L3、L4 页表页。

虚拟页 $2^{36}-1$ 对应全 1 索引，需要另一条 L2、L3、L4 路径。

根 L1 页表只有一个。

所需页表页：
1
2
3
4
5
1 个 L1
2 个 L2
2 个 L3
2 个 L4
共 7 个页表页
总大小为 $7\times4\text{KB}=28\text{KB}$ 。

多级页表一定比单级页表省内存吗？

不一定。

解析：

多级页表适合稀疏地址空间，因为未使用区域不需要分配下级页表。

若虚拟地址空间被密集使用，多级页表仍需分配较多下级页表。

多级页表还需要中间层页表页，因此可能不比单级页表更小。

拆分虚拟地址 0xFFF8080604FFF

按 x86-64 低 48 位字段拆分：
1
2
3
4
5
L1 index = (VA >> 39) & 0x1FF = 0x1FF
L2 index = (VA >> 30) & 0x1FF = 0x002
L3 index = (VA >> 21) & 0x1FF = 0x003
L4 index = (VA >> 12) & 0x1FF = 0x004
offset   = VA & 0xFFF        = 0xFFF
因此：

字段值

L1 index 0x1FF

L2 index 0x002

L3 index 0x003

L4 index 0x004

offset 0xFFF

若将其视为完整 64-bit canonical address，需要保证高 16 位等于第 47 位的复制。该地址第 47 位为 1，所以完整 canonical 形式应补高位 1。

字段	值
L1 index	`0x1FF`
L2 index	`0x002`
L3 index	`0x003`
L4 index	`0x004`
offset	`0xFFF`

映射虚拟地址 0 ~ 16MB 需要多少页表空间？

按 4KB page， $16\text{MB}/4\text{KB}=4096\text{ pages}$ 。

一个 L4 页表页有 512 个 PTE，可映射 $512\times4\text{KB}=2\text{MB}$ 。映射 16MB 需要 $16\text{MB}/2\text{MB}=8\text{ 个 L4 页表页}$ 。

这些 L4 页表页由同一个 L3 页表页的 8 个 entry 指向。更高层只需要一个 L2 页表页和一个 L1 页表页。

页表页总数：
1
1 个 L1 + 1 个 L2 + 1 个 L3 + 8 个 L4 = 11 个页表页
总大小为 $11\times4\text{KB}=44\text{KB}$ 。

若题目把地址 16MB 所在页面也包含进去，则还需要第 9 个 L4 页表页，总计 48KB。通常区间 0 ~ 16MB 表示 [0,16MB)，答案为 44KB。

Core i7 内存系统

系统结构

Core i7 / Skylake 内存系统如下：

L1 cache 和 L1 TLB 都区分 instruction 与 data：

instruction fetch 使用 PC 作为虚拟地址，经过 i-TLB 与 i-cache。
load/store 使用指令中的有效地址，经过 d-TLB 与 d-cache。
两类访问模式不同，分离后可降低互相干扰，并提高取指和数据访问的并行度。

地址翻译如下：

为什么要区分 i-TLB / d-TLB 和 i-cache / d-cache？

取指和数据访问可以并行发生，分离结构可减少结构冲突。

instruction access 通常更顺序，data access 可能更随机，两者访问模式不同。

分离后，数据访问的局部性变化不容易污染取指缓存。

更低层可使用 unified TLB/cache，在容量和共享性上折中。

PTE 中常见位：

位	含义
`P`	present bit，页面或下级页表是否在内存中
`R/W`	只读或可写
`U/S`	用户态或内核态访问权限
`WT`	write-through / write-back cache policy
`CD`	cache disabled
`A`	accessed/reference bit，由 MMU 在读写时设置
`D`	dirty bit，由 MMU 在写时设置，最终级 PTE 常用
`PS`	page size，可表示 4KB、2MB 或 1GB page
`G`	global page，任务切换时不从 TLB 驱逐
`XD`	禁止或允许取指

当 P=0 时，PTE 中部分位可由 OS 用于记录页面在二级存储中的位置。

PTE 为什么保存 PPN 而不是完整 PA？

页面大小为 4KB 时，物理地址低 12 位是页内偏移 PPO。

PPO 与虚拟地址中的 VPO 相同，不需要保存在 PTE 中。

PTE 只需保存高位物理页号 PPN，再与 VPO 拼接即可形成 PA。

省下的低位和其他位可用于 present、permission、accessed、dirty 等控制信息。

VIPT 加速

L1 cache 可采用 Virtually Indexed, Physically Tagged（VIPT）：

cache index 所需位与虚拟地址和物理地址相同，因为这些位位于页内偏移或不受翻译影响的范围。
cache 可在地址翻译同时用 VA 取 index。
TLB 命中后得到 PPN，再用物理 tag 比较。

该设计可隐藏一部分翻译延迟，但要求 L1 cache 大小和相联度满足索引位不跨越页号变化范围。

以 4KB page 为例，VPO/PPO 为 12 位。若 L1 cache line 为 64 bytes，则 block offset 需要 6 位；若 cache 有 64 个 set，则 cache index 需要 6 位。CO + CI = 12，两者完全落在页内偏移中，因此 VA 与 PA 的这 12 位相同。

访问过程可以并行执行：

用 VA 的 VPN 查询 TLB，获得 PPN。
同时用 VA 的低位 CI 选中 L1 cache set。
TLB 返回 PPN 后组成物理 tag。
用物理 tag 与所选 set 中各 way 的 tag 比较。

若 CO + CI 超过 page offset 位数，cache index 会依赖 VPN 中的位，不同虚拟地址别名可能指向同一物理页但落入不同 cache set，设计会更复杂。

Linux 虚拟内存

Linux 将进程虚拟内存组织为一组 area。相关数据结构包括：

task_struct：进程描述符。
mm_struct：描述进程地址空间。
pgd：页目录地址，运行时加载到 CR3。
mmap：指向 vm_area_struct 链表。
vm_area_struct：描述一个连续虚拟内存区域。

vm_area_struct 主要字段：

字段	含义
`vm_start`	VMA 起始地址
`vm_end`	VMA 结束地址
`vm_prot`	区域读写执行权限
`vm_flags`	shared/private 等属性
`vm_next`	下一个 VMA

VMA 记录的是虚拟地址区间的合法性和来源，不表示所有页面已经有物理页。一个 VMA 可以已经存在，但其中大多数 PTE 仍为空；只有访问到具体虚拟页时，page fault handler 才根据 VMA 的文件对象、匿名映射属性和访问权限建立实际 PTE。

Linux Page Fault Handling

Linux page fault handler 的检查流程：

检查 VA 是否落在某个 vm_area_struct 定义的合法区域中。
若不在任何 VMA 中，发送 segmentation fault。
若在 VMA 中，检查访问操作是否合法，例如写只读区域。
若权限不合法，发送 protection violation。
若地址和权限合法，执行缺页处理，例如 demand paging 或 COW。

为什么 page fault handler 需要先查 VMA？

页表只回答“当前是否有有效映射”，不能单独说明该地址是否属于进程合法地址空间。

VMA 描述了已分配虚拟区域、权限和 backing object。

若 VA 不属于任何 VMA，说明该地址从未被合法分配，应触发 SIGSEGV。

若 VA 属于 VMA 但 PTE 不 present，则可能是 demand paging、file-backed mapping 或 COW，可由 OS 恢复。

Memory Mapping

文件映射

Linux 通过 memory mapping 将 VM area 与磁盘对象关联，区域初始内容来自被映射对象。

可映射对象：

regular file，例如 ELF executable object file，映射不等于立刻读入物理内存。它指示将来如果程序访问这段虚拟地址，内容应该从哪个文件位置取得。
anonymous file，表示没有实际文件，首次缺页时分配全 0 物理页。

dirty page 可在内存和 swap file 之间换入换出。swap file 由内核维护，存储栈、堆等结构对应的匿名页，也称 swap space 或 swap area。

虚拟页在被引用前不会复制到物理内存，这称为 demand paging。Linux 不会在程序刚启动时，把整个程序文件、所有库、所有堆栈空间都读进内存，而是等页面真正被访问时再调入。


进程虚拟地址空间
┌────────────────────┐
│ text VM area       │ → regular file: ELF text segment
├────────────────────┤
│ rodata VM area     │ → regular file: ELF rodata segment
├────────────────────┤
│ data VM area       │ → regular file: ELF data segment
├────────────────────┤
│ bss VM area        │ → anonymous file，初始全 0
├────────────────────┤
│ heap VM area       │ → anonymous file，初始全 0
├────────────────────┤
│ mmap file area     │ → regular file
├────────────────────┤
│ stack VM area      │ → anonymous file，初始全 0
└────────────────────┘

`mmap`

用户可通过 mmap 创建新的内存映射区域：

/* start 通常传 0 让内核选择映射地址；len 是映射长度。 */
/* prot 指定读写执行权限；flags 指定私有/共享等映射属性。 */
/* fd 与 offset 指定从哪个文件的哪个偏移开始建立映射。 */
void *mmap(void *start, int len, int prot,
           int flags, int fd, int offset);

含义：

从文件描述符 fd 指定的文件中，自 offset 开始映射 len bytes。
start 是期望虚拟地址，通常传 NULL 表示由内核选择。
prot 指定权限，例如 PROT_READ、PROT_WRITE。
flags 指定映射类型，例如 MAP_PRIVATE、MAP_SHARED。
返回映射区域指针。

`mmap` 快速文件复制

void mmapcopy(int fd, int size)
{
    char *bufp;

    /* 将文件 fd 的前 size 字节私有映射到当前进程虚拟地址空间。 */
    bufp = mmap(0, size, PROT_READ, MAP_PRIVATE, fd, 0);
    /* 对 bufp 的读取会由虚拟内存系统按需触发文件页调入。 */
    write(1, bufp, size);
}

主程序：

int main(int argc, char **argv)
{
    struct stat stat;
    int fd;

    /* 以只读方式打开输入文件。 */
    fd = open(argv[1], O_RDONLY, 0);
    /* 获取文件大小，用于确定 mmap 的映射长度。 */
    fstat(fd, &stat);
    mmapcopy(fd, stat.st_size);
}

为什么 mmapcopy 更快？

传统 read 需要把文件数据从内核缓冲复制到用户缓冲，再由 write 从用户缓冲复制回内核。

mmap 把文件页映射到进程虚拟地址空间，访问时由 page fault 按需读入。

write 可直接从映射区域读取数据，减少一次显式用户态缓冲复制。

对 Web server 等文件传输场景，减少数据复制和系统调用可降低开销。

mmap 后页表形态

程序运行在 32-bit Linux 系统上，page size 为 4KB。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define PAGE_SIZE (4 * 1024)

int main(void) {
    char *p = NULL;
    int i;

A:
    /* 建立 128 页匿名私有映射；此时通常只创建 VMA 和页表元数据。 */
    p = mmap(0, 128 * PAGE_SIZE, PROT_READ | PROT_WRITE,
             MAP_PRIVATE | MAP_ANON, -1, 0);
    printf("buffer start: %p\n", p);

    for (i = 0; i < 128 * PAGE_SIZE; i += PAGE_SIZE)
        /* 每隔一个页面写 1 字节，促使对应虚拟页按需分配物理页。 */
        p[i] = 1;

B:
    /* 取消映射，相关 PTE 和物理页可被内核回收。 */
    munmap(p, 128 * PAGE_SIZE);
    return 0;
}
已知 printf 输出：
1
buffer start: 0xb7bdf000
程序到达标号 B 时，新映射区域相关页表如何变化？

mmap 创建长度为 128 * 4KB = 512KB 的匿名私有 VMA。

起始地址为 0xb7bdf000。

到达 A 后，VMA 已建立，但物理页尚未按需分配。

循环中每隔 4KB 写一次，正好触碰 128 个虚拟页。

每次首次写某页时触发 demand-zero page fault，内核分配一个全 0 物理页，建立 PTE，并执行写入。

计算 32-bit 10-10-12 页表索引：
1
2
start = 0xb7bdf000
end   = start + 128 * 4096 - 1 = 0xb7c5efff
起始页：
1
2
PDE index = (0xb7bdf000 >> 22) & 0x3ff = 0x2de
PTE index = (0xb7bdf000 >> 12) & 0x3ff = 0x3df
结束页：
1
2
PDE index = (0xb7c5efff >> 22) & 0x3ff = 0x2df
PTE index = (0xb7c5efff >> 12) & 0x3ff = 0x05e
因此 128 个页面跨越两个二级页表：

PDE PTE 范围页数

0x2de 0x3df ~ 0x3ff 33

0x2df 0x000 ~ 0x05e 95

到达 B 前：

对应 VMA 存在。

这 128 个 PTE 都已因写访问变为 present。

每个 PTE 指向一个新分配的物理页。

这些页具有私有匿名映射的读写权限。

PDE	PTE 范围	页数
`0x2de`	`0x3df ~ 0x3ff`	33
`0x2df`	`0x000 ~ 0x05e`	95

`fork` 与 COW

fork 创建新进程时：

复制旧进程的 mm_struct、vm_area_struct 和页表。
父子进程初始共享所有物理页。
对可写私有区域，内核将 PTE 标记为只读，并将 VMA 标记为 private copy-on-write。

这种处理在 fork 时不立即创建父进程页面的完整复制，而是暂时共享相同的页面，避免了一次性分配暂时不会使用的内存。如果父进程或子进程写入 COW（Copy-On-Write）页：

写操作触发 protection fault。
page fault handler 识别这是 COW 区域。
handler 分配新的物理页。
handler 复制原页内容到新页。
handler 更新当前进程 PTE 指向新页。
handler 恢复写权限。
faulting instruction 重新执行并成功写入。

结果：只有在进程实际写入共享页时才复制页面。

fork 为什么不直接复制所有物理页？

直接复制可以保证父子进程之后互不影响，但会立即消耗大量时间和物理内存。

很多 fork 后会立刻 execve，直接复制旧地址空间会被马上丢弃。

COW 先让父子进程共享物理页，并把可写私有页暂时标为只读。

真正写入时才触发 protection fault，由 OS 复制对应物理页。

因此复制成本被推迟到“确实需要修改”的页面上。

COW 为什么要把可写页暂时设为只读？

OS 需要在第一次写入时获得控制权，否则写入会直接修改共享物理页。

将 PTE 标为只读后，父进程或子进程执行写操作会触发 page fault。

handler 检查 VMA/PTE 后识别这是 COW，不是非法写。

handler 分配新物理页、复制旧内容、更新当前进程 PTE 并恢复写权限。

faulting store 重新执行后，只写入当前进程的新页。

Shared Object 与 Private Object

类型	写入可见性	是否回写文件
Shared object	对映射同一对象的其他进程可见	会反映到原对象
Private object	对其他进程不可见	不回写原对象

shared area 可用于进程间通信。private area 常配合 COW 实现高效 fork。

MAP_SHARED 和 MAP_PRIVATE 的写入可见性有什么区别？

MAP_SHARED 映射同一对象的进程共享写入结果，一个进程写入后其他进程可见。

MAP_PRIVATE 初始可共享同一物理页，但写入是本地私有的。

private mapping 的写入通常通过 COW 实现，不回写原始文件对象。

shared mapping 可用于进程间通信，private mapping 常用于加载代码、数据段和 fork 后的地址空间。

页替换策略

页替换

当 OS 需要分配空闲物理页但没有可用页时，需要选择页面换出。页面置换体现了机制与策略分离：

机制：page swapping 提供把页面从 DRAM 换出到二级存储、再换入 DRAM 的能力。
策略：replacement policy 决定在内存紧张时换出哪一个页面。

置换可能发生在需要新物理页时，例如 demand paging、COW 分配新页、mmap 首次写匿名页，或内核主动回收内存时。

Linux 可提前回收页面，例如 kswapd 使用 low/high water mark：

可用页数低于 low water mark 时开始回收。
回收到 high water mark 后停止。

主动回收可避免每次物理页分配失败时只临时换出一个页。若系统总在分配路径上同步回收，会增加请求延迟；后台回收可提前准备空闲页池。

什么时候会触发页面置换？

当 OS 需要分配新物理页但空闲页不足时，需要选择页面换出。

典型场景包括 page fault 调入页面、COW 写入分配新页、mmap 匿名页首次写入、内核申请连续页等。

实际系统不一定等到完全没有空闲页才开始；后台线程可在低水位线触发回收。

回收到高水位线后停止，以减少分配路径上的同步等待。

AMAT

平均内存访问时间（Average Memory Access Time）：

$AMAT = P_{hit}\cdot T_M + P_{miss}\cdot T_D$

其中：

$T_M$ ：访问内存成本，约 100ns。
$T_D$ ：访问磁盘成本，约 10ms。
$P_{hit}$ ：命中率。
$P_{miss}$ ：未命中率。

示例：若 miss rate 为 0.1，则 $AMAT = 100ns\times0.9 + 10ms\times0.1 = 1.00009ms$ ；若 miss rate 为 0.001，则 $AMAT = 100ns\times0.999 + 10ms\times0.001 = 10.0999\mu s$ 。

结论：很小的 miss rate 变化也会影响 AMAT。

OPT

OPT 策略换出未来最长时间不会再被访问的页面。

理论最优。
需要知道未来访问序列，实际系统无法直接实现。
常用于评价其他置换策略的上界。

FIFO 与 Belady Anomaly

FIFO 维护一个队列，记录页面换入顺序。每次换入页面时加入队尾，换出时选择队头。

若访问序列：
1
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 个物理页和 4 个物理页时 FIFO 各产生几次缺页？

3 个物理页

访问内存状态结果

1 1 miss

2 1 2 miss

3 1 2 3 miss

4 2 3 4 miss，换出 1

1 3 4 1 miss，换出 2

2 4 1 2 miss，换出 3

5 1 2 5 miss，换出 4

1 1 2 5 hit

2 1 2 5 hit

3 2 5 3 miss，换出 1

4 5 3 4 miss，换出 2

5 5 3 4 hit

缺页次数：9。

4 个物理页

访问内存状态结果

1 1 miss

2 1 2 miss

3 1 2 3 miss

4 1 2 3 4 miss

1 1 2 3 4 hit

2 1 2 3 4 hit

5 2 3 4 5 miss，换出 1

1 3 4 5 1 miss，换出 2

2 4 5 1 2 miss，换出 3

3 5 1 2 3 miss，换出 4

4 1 2 3 4 miss，换出 5

5 2 3 4 5 miss，换出 1

缺页次数：10。

FIFO 中增加物理页数可能反而增加缺页次数，称为 Belady’s Anomaly。

访问	内存状态	结果
1	1	miss
2	1 2	miss
3	1 2 3	miss
4	2 3 4	miss，换出 1
1	3 4 1	miss，换出 2
2	4 1 2	miss，换出 3
5	1 2 5	miss，换出 4
1	1 2 5	hit
2	1 2 5	hit
3	2 5 3	miss，换出 1
4	5 3 4	miss，换出 2
5	5 3 4	hit

访问	内存状态	结果
1	1	miss
2	1 2	miss
3	1 2 3	miss
4	1 2 3 4	miss
1	1 2 3 4	hit
2	1 2 3 4	hit
5	2 3 4 5	miss，换出 1
1	3 4 5 1	miss，换出 2
2	4 5 1 2	miss，换出 3
3	5 1 2 3	miss，换出 4
4	1 2 3 4	miss，换出 5
5	2 3 4 5	miss，换出 1

Second Chance

Second Chance 是 FIFO 的改进。每个页维护一个访问位：

若访问页面已在内存中，设置访问位。
需要换页时检查队头。
若访问位为 0，换出该页。
若访问位为 1，清除访问位并放到队尾，继续查找。

它避免立即换出近期访问过的页。

LRU

LRU（Least Recently Used）换出最长时间未访问的页。

优点：

通常能保留热点页。
对 80-20 workload 表现较好：约 20% 热页贡献约 80% 访问。

缺点：

精确实现成本高，需要记录和排序所有页面访问时间。
对循环顺序访问可能表现差。

循环顺序访问示例：
1
访问 50 个页面：0,1,2,...,49，循环 10000 次
若 cache 大小为 49，LRU 和 FIFO 会不断换出即将再次使用的旧页，hit rate 可能为 0。随机置换反而可能避免这种特定最坏行为，因此一些硬件结构会使用随机置换。

Clock Algorithm

Clock 是近似 LRU 的策略。其数据结构：

物理页按环形排列。
每页有访问位。
指针指向候选位置。

算法：

需要换出时，从指针下一个位置开始扫描。
若访问位为 1，将其清 0，继续扫描。
若访问位为 0，选择该页换出。
新页换入该位置，指针更新。

指针更新规则是：换出某页并把新页放入该位置后，指针停在该位置或移动到该位置之后，下一次扫描从后继页开始。这样可避免每次都从同一位置重新扫描。

若考虑 dirty bit，置换策略可进一步区分 clean page 和 dirty page：

clean file-backed page 可直接丢弃，因为磁盘上已有相同内容。
dirty page 需要 write back，换出成本更高。
实际系统常结合 accessed bit 和 dirty bit 做多级优先级，而不是只看最近访问情况。

Clock 如何获得物理页访问位？

MMU 设置的是 PTE 中的 Accessed bit，它属于虚拟页映射（从虚拟页到物理页）。OS 做 swap 时需要知道某个物理页对应哪些 PTE。实现方式：

OS 在描述物理页的数据结构中记录对应 PTE 位置。

物理页被填入页表时，记录反向映射（reverse mapping）。

置换时通过反向映射检查并清除相关 PTE 的 accessed bit。

若页被多个进程共享，需要检查所有对应 PTE；只要任一映射近期被访问，该物理页就应被视为 recently used。

真正驱逐该物理页时，OS 需要更新所有相关 PTE，使它们不再指向被回收的物理页。

页表页和内核页能否被换出？

OS 能否换出页表页？

理论上除当前 CR3 指向的一级页表外，其余页表页可以设计为可换出，但实现复杂。硬件页表遍历需要页表页可访问，换出页表页需要额外元数据和异常处理。实际系统通常谨慎处理。

当前 CR3 指向的顶级页表页不能被换出。MMU 页表遍历的第一步就是读取 CR3 指向的物理页；如果该页已经被替换成普通数据，硬件无法知道真正的顶级页表在哪里，后续翻译会失去依据。

OS 能否换出自己的页面？

取决于页面用途，但通常关键内核代码、异常处理路径、页表管理数据和中断处理所需页面不能换出。否则处理缺页时可能再次缺页，导致无法恢复。

例如 page fault handler 所在代码页若被换出，处理 page fault 时又会因为取 handler 指令而 page fault，可能形成递归异常，严重时导致系统崩溃。因此关键内核路径通常必须常驻。

一条 mov 最多触发几次 page fault？

CPU 执行指令前要先 instruction fetch，PC 本身是虚拟地址。若指令所在代码页尚未调入，取指会触发 page fault。

mov 若访问内存操作数，该操作数地址也是虚拟地址。若对应数据页尚未调入，也会触发 page fault。

每次 page fault 处理后，faulting instruction 会重新执行，直到所需页面和权限都满足。

因此：

在常见不跨页情形下，一条访存 mov 最多可因取指页和数据页各触发一次 page fault，即最多 2 次。

若指令字节跨页，取指可能涉及两个代码页；若内存操作数跨页，也可能涉及两个数据页，此时次数可更多。

两条连续 mov 的第二条是否再次发生取指 page fault，取决于第二条指令是否仍在第一条已经调入的代码页中。若 PC 增量后仍在同一虚拟页，且中间没有调度、TLB flush 或页面换出，则通常不会因取指再次 fault；若第一条位于页尾，第二条跨入新代码页，则仍可能因取指 fault。

即使两条指令在同一虚拟页，中间也可能发生 timer interrupt 和进程切换。若该进程长时间后才继续执行，相关 TLB entry 可能已失效，甚至代码页可能被换出，因此下一条指令仍可能再次触发取指 page fault。

地址 0 是否可能合法访问？

原则上可以。虚拟地址 0 是否合法取决于页表映射和 VMA 权限。

实际用户程序中，操作系统通常故意不映射低地址区域，用于捕获空指针解引用。因此普通 Linux 进程访问地址 0 通常会触发 SIGSEGV。但从机制上看，只要 OS 允许在地址 0 建立 VMA 和页表映射，地址 0 就可以合法访问。用户态可尝试通过 mmap 指定起始地址，但该参数通常只是建议；是否允许映射低地址取决于 OS 配置和安全策略。

Segmentation Fault 的完整流程

应用执行 load、store 或 instruction fetch。

CPU/MMU 对虚拟地址进行翻译。

MMU 发现页表翻译失败或 PTE 权限检查失败，例如 PTE not present、用户态访问内核页、写只读页等。

CPU 触发 page fault exception，进入内核。

OS page fault handler 检查 faulting address 是否落在合法 VMA 中，并检查访问类型是否符合 VMA 权限。

若地址非法或权限非法，内核向当前进程发送 SIGSEGV。

若地址合法且可恢复，例如 demand paging 或 COW，则 handler 修复映射并重新执行 faulting instruction。

若进程没有自定义 signal handler，SIGSEGV 的默认动作是终止进程，shell 或父进程可观察到进程因 segmentation fault 退出。

动态内存分配

动态内存分配器管理运行时堆，将堆抽象为一组不同大小的 block。

内核和用户程序面对的分配粒度不同：

OS 管理虚拟页、物理页和 VMA，基本粒度通常是 4KB page 或连续若干页。
应用程序常请求更小且大小不固定的对象，例如 64-byte buffer、128-byte buffer。
C 库的 malloc/free 在用户态堆中管理小块；内核中的类似需求通常由 kmalloc/kfree 或 slab allocator 处理。

类型	特点	例子
Explicit allocator	应用显式分配和释放	C 的 `malloc` / `free`
Implicit allocator	应用分配，系统自动回收	Java/Python GC，Rust 编译器管理

`malloc` 与 `free`

#include <stdlib.h>

/* 从堆中分配至少 size 字节，返回满足对齐要求的块指针。 */
void *malloc(size_t size);
/* 释放先前由 malloc/calloc/realloc 返回的块。 */
void free(void *p);

malloc(size)：

成功返回至少 size bytes 的内存块指针。
返回地址按 8-byte 边界对齐。
返回内存内容不清零。
若 size == 0，可返回 NULL。
失败返回 NULL，并设置 errno=ENOMEM。

free(p)：

将 p 指向的块归还给可用内存池。
p 必须来自之前的 malloc、calloc 或 realloc。
否则行为未定义。

为什么释放非 malloc 指针是未定义行为？

分配器通常在 payload 前存放 header，记录 block size 和分配状态。

free(p) 会根据 p 回退到 header。

若 p 不是合法 payload 起始地址，分配器会读取错误 header。

后果可能是破坏堆结构、错误合并块或访问非法内存。

静态数组需要提前设置上限：

1
2
3

#define MAXN 15213
/* 静态数组大小固定，编译时决定存储空间。 */
int array[MAXN];

若输入规模超过 MAXN，必须修改代码并重新编译。动态分配可按运行时输入分配：

int *array, i, n;

scanf("%d", &n);
/* 根据运行时输入 n 动态分配数组空间。 */
array = (int *)Malloc(n * sizeof(int));
for (i = 0; i < n; i++)
    /* 将输入元素写入动态分配的连续内存。 */
    scanf("%d", &array[i]);

`sbrk`

堆空间来自内核。传统分配器可用 sbrk 调整堆顶 brk。

#include <unistd.h>

/* 将 program break 增加 incr 字节；常用于说明堆区扩展机制。 */
void *sbrk(int incr);

语义：

成功返回旧的 brk。
失败返回 -1，设置 errno=ENOMEM。
incr=0 返回当前 brk。
incr 可为负数，用于收缩堆。

分配器使用 sbrk 扩展堆，然后在堆内自行管理 blocks。

对齐要求

分配器通常要求 malloc 返回值按双字对齐。若一个 word 为 4 bytes，则双字对齐为 8 bytes。

为什么要求对齐？

某些数据类型和指令要求自然对齐。

对齐访问通常性能更好。

block 大小若总是 8 的倍数，则低 3 位恒为 0，可复用低位保存 allocated bit 等标志。

分配器要求与目标

分配器必须满足：

处理任意请求序列。
立即响应请求，不能批处理。
只使用堆区。
对齐 blocks。
不能修改已分配 blocks 中的 payload。

目标：

最大化吞吐。
最大化内存利用率。

二者通常冲突。

吞吐

吞吐是单位时间完成的请求数。

1 秒内完成 5000 次 malloc 和 5000 次 free，吞吐为 10000 operations/second。

内存利用率

给定请求序列：

1	R0, R1, ..., Rk, ..., Rn-1

若 malloc(m) 分配 payload 为 m bytes 的 block，则在请求 Rk 完成后，当前已分配 payload 总和为 $P_k$ 。

当前堆大小为 $H_k$ 。

内存利用率：

$U_k=\frac{P_k}{H_k}$

常用峰值利用率：

$U_k=\frac{\max_{i\le k}P_i}{H_k}$

内部碎片

内部碎片指一个 block 中 block size 与 payload size 的差。

原因：

header/footer 等元数据开销。
对齐 padding。
策略性选择，例如不拆分过小剩余块。

内部碎片只依赖已经发生的请求模式，容易测量。

外部碎片

外部碎片指总空闲内存足够，但没有单个 free block 足够大。

外部碎片依赖未来请求模式，难以精确测量。

隐式空闲链表

只给一个指针，如何知道释放多少内存？

标准方法是在 payload 前一个 word 保存 block size，该 word 称为 header。

free(p) 时，分配器通过 p 找到前面的 header，读取 block size。

如何记录 block 是否空闲？

如果 block size 总是 8 的倍数，则低 3 位为 0，可用低位保存 allocated bit。

读取 size 时屏蔽低位；读取 alloc bit 时检查低位。

如何选择 free block？

常见策略：

策略方法特点

First fit 从头搜索，选择第一个足够大的 free block 简单，但可能在链表前部产生小碎片

Next fit 从上次搜索结束处继续搜索可能更快，但碎片可能更差

Best fit 搜索所有 free block，选择最接近请求大小的块碎片通常较少，但搜索较慢

策略	方法	特点
First fit	从头搜索，选择第一个足够大的 free block	简单，但可能在链表前部产生小碎片
Next fit	从上次搜索结束处继续	搜索可能更快，但碎片可能更差
Best fit	搜索所有 free block，选择最接近请求大小的块	碎片通常较少，但搜索较慢

free block 大于请求时怎么办？

可拆分 block。若剩余部分太小，可能不拆分，以避免产生无法使用的小块。

释放 block 后如何重新插入？

最简单方法是清除 allocated bit，使该 block 变为空闲。但若相邻 free block 不合并，会产生 false fragmentation。

解决方法是 coalescing：若前后相邻 block 空闲，则合并。

边界标记与常数时间合并

为了向前合并，需要知道前一个 block 的大小和状态。边界标记（boundary tag）在 free block 底部复制 header 信息作为 footer。

释放 block 时有四种情况：

情况	前一块	后一块	操作
1	allocated	allocated	仅将当前块标为空闲
2	allocated	free	与后一块合并
3	free	allocated	与前一块合并
4	free	free	与前后两块合并

合并后更新新 free block 的 header 和 footer。

显式空闲链表

隐式链表搜索所有 blocks，包括 allocated blocks。显式空闲链表只把 free blocks 链接起来。

方法：

在 free block 的 payload 区域存放 predecessor 和 successor 指针。
通常使用双向链表。
仍可使用 boundary tag 做合并。

free list 中的链接顺序不一定等于 block 在堆中的地址顺序。

插入策略：

策略	方法	优点	缺点
LIFO（Last-In-First-Out）	新释放块插入链表头部	常数时间，简单	可能增加碎片
Address-ordered	按地址顺序插入	碎片通常较少	需要搜索插入位置

Simple Segregated Storage

分离存储（segregated storage）为不同 size class 维护不同 free list。

常见做法：

小尺寸为每个大小单独维护 list。
大尺寸按 2 的幂维护 size class。

无拆分版本：

分配大小为 n 的 block：

查找大小类 n 的 free list。
若非空，取第一个 block。
若为空，向堆申请新页，把该页切成大小为 n 的 blocks，并建立 free list。
返回第一个 block。

释放：将 block 加回对应 size class 的 free list。

特点：

分配和释放可为常数时间。
若 size class 不合适，内部碎片可能较大。

Segregated Fits

分配大小为 n 的 block：

查找合适 size class。
在该 list 中找大小 $m>n$ 的 block。
若找到，可选择拆分，剩余部分放入对应 list。
若找不到，继续查找更大 size class。
若所有 class 都找不到，扩展堆。

释放：

可选择合并相邻 free blocks。
将合并后的 block 放入对应 size class。

特点：

比顺序搜索更快。
对碎片控制较好。
合并会增加释放或搜索成本。
deferred coalescing 可降低部分开销。

Buddy System

Buddy system 是 segregated fits 的特例，每个 size class 都是 2 的幂。

在内核中，buddy system 常用于管理物理页。其 size class 通常表示 $2^n$ 个连续页面，因此最小块为 1 个 page，之后是 2、4、8 个连续 page。它适合满足页级分配需求，例如分配连续物理页、为页表或 DMA buffer 准备内存。

为什么 buddy system 适合内核页级分配？

内核经常需要 1 个或连续多个物理页，例如页表页、大页映射、DMA buffer。

buddy system 的 size class 是 $2^n$ 个 page，天然满足连续页分配。

分裂时把大块递归拆成两个同大小 buddy，释放时只尝试与自己的 buddy 合并。

这种规则让分配和合并逻辑简单，适合内核维护物理页池。

初始化：堆大小为 $2^m$ 。

分配大小为 $m$ 个物理页的 block：

找到满足 $2^{n-1}<m\le 2^n$ 的 size class。
查找大小为 $2^j$ 的空闲块，其中 $n\le j\le m$ 。
若块过大，递归二分，直到得到 $2^n$ 大小块。
剩余 buddy 块放入对应 free list。

释放：

找到被释放块的 buddy。
若 buddy 空闲且大小相同，则合并。
递归合并，直到 buddy 不空闲或达到最大块。

OS kernel 常用 buddy system 分配和释放物理页。

15KB 请求如何由 buddy system 分配？

假设最小页大小为 4KB，当前有一个 32KB 空闲块，请求分配 15KB。

15KB 不能按字节精确分配，需向上对齐到页级和 2 的幂 size class。

15KB 需要 4 个 4KB 页，即 16KB。

若 16KB free list 为空，则向上查找 32KB free list。

找到 32KB 块后，将其 split 为两个 16KB buddy。

一个 16KB 块返回给请求方，另一个 16KB 块插回 16KB free list。

释放该 16KB 块时，只能与自己的 16KB buddy 合并；若 buddy 也空闲，则合并回 32KB。

Buddy 地址计算示例：
1
2
3
4
Block A: 0 ~ 8KB
Block B: 8KB ~ 16KB
Addr(A) = 0x0
Addr(B) = 0x2000
8KB = $2^{13}$ ，两个 buddy block 的起始地址只在第 13 位不同。
1
0x0000 xor 0x2000 = 0x2000
因此大小为 $2^k$ 的 buddy 可通过翻转地址第 $k$ 位得到。

buddy system 为什么能快速找到伙伴块？

buddy 块大小相同，且来自同一个更大的父块二分。

两个 buddy 的起始地址只有表示当前块大小的那一位不同。

若块大小为 $2^k$ ，其伙伴地址可由 addr xor 2^k 得到。

是否可以合并还要检查伙伴块是否空闲且大小相同；空闲状态通常记录在内核维护的物理页元数据中。

Slab Allocator

系统中很多对象大小固定或可预知，例如内核对象。slab allocator 思路：

先从 OS 获取连续页，形成 slab。
将 slab 切成固定大小 slot。
为不同 slot size 建立不同 pool。
分配时从合适 pool 中取一个 slot。

slot 通常为 $2^n$ bytes，其中 $3\le n<12$ ；也可为特定数据结构设置专用大小，以减少内部碎片。

Resource Pool

每种固定大小维护一个 pool：

分配 N bytes：

选择 best-fit pool。
在该 pool 中选择一个可用 slab。
从 slab 的 free list 取第一个 slot。

释放：将 slot 插回对应 slab 的 free list。

一个 pool 内通常维护不同状态的 slab：

current slab：当前优先服务分配请求的 slab。
partial slabs：仍有空闲 slot 的 slab 集合。
full slabs：没有空闲 slot，不在快速分配路径中；当其中某个对象被释放后，可重新进入 partial 集合。

若 current slab 用尽，可从 partial slabs 中取一个作为新的 current；若没有 partial slab，则向 buddy system 申请新的连续页形成 slab。

Slab 内部 free list

free slot 本身可存放 next 指针：

1	Next_Free -> slot -> slot -> slot -> NULL

分配时取 Next_Free 指向的 slot，并更新 Next_Free。释放时把 slot 插回链表头。

如何选择 slot sizes？

通用场景可按 2 的幂设置。

对频繁分配的数据结构，可建立专用 cache，slot size 等于对象大小并满足对齐。

目标是在内部碎片和管理复杂度之间折中。

分配和释放的时间复杂度？

若已有可用 slab，定位 pool、读取 next_free、更新 free list 通常为 $O(1)$ 。

free(p) 也可为 $O(1)$ ：根据 slot 地址向下对齐到 slab 起始地址，找到该 slab 的元数据，再把 slot 插回 free list 头部。

若当前 slab 用尽，需要寻找 partial slab 或向 buddy system 申请新 slab，成本更高。

full slab 在哪里？

full slab 没有空闲 slot，不参与快速分配路径。

实现中可放在 full list，或只通过对象所属 slab 的元数据追踪。

为什么需要释放 empty slab？

empty slab 中所有 slot 都空闲。

若长期保留，会占用物理页并降低全局内存利用率。

释放 empty slab 可把页归还给 buddy system 或上层页分配器。