虚拟内存与分页

虚拟地址与访问权限

进程执行普通访存指令时使用虚拟地址，硬件按照当前地址空间的映射把它转换为物理地址。不同进程中的同一虚拟地址可以对应不同物理位置，多个虚拟地址也可以在明确授权下映射同一块共享内存。地址转换使进程获得连续的地址视图，同时让内核控制内存隔离、共享和访问权限。

一个地址具有映射还不够，访问类型也必须得到许可。例如，只读代码页允许取指或读取，却应拒绝普通写入；用户态代码不能访问仅供内核使用的页面。硬件检查失败时产生异常，内核再根据原因决定补充映射、执行写时复制或报告非法访问。把所有内存异常都归结为物理内存不足，会忽略越界和权限错误。

页与页框

分页把虚拟地址空间分成固定大小的页，把物理内存按相同大小分成页框。页表记录虚拟页到物理页框的映射及权限等状态。页内偏移在普通分页转换中保持不变，转换只改变页号对应的位置。

页大小通常取二的整数次幂，便于用地址位分解页号和偏移。大页减少页表项数量，提高地址转换缓存的覆盖范围，却可能增加内部碎片，并改变内存分配与回收的粒度。选择页大小时，需要结合数据布局、访问跨度、内存压力和硬件支持，不能只根据页表占用做决定。

页号与页内偏移

设页大小为 $P=2^p$ 字节，虚拟地址为非负整数 $v$。虚拟页号与页内偏移分别为

$\operatorname{VPN}=\left\lfloor\frac{v}{P}\right\rfloor,\qquad d=v\bmod P.$

若该页映射到物理页框号 $f$，访问权限也满足要求，物理地址为 $fP+d$。偏移满足 $0\le d<P$，因此不会越过所选页框。跨页读取需要分别处理每一页的映射和权限，第一字节合法并不保证整个访问范围合法。

分页地址转换

这里采用精确的 $4\,\mathrm{KiB}=4096$ 字节页面。虚拟地址为十六进制 0x3456，页表把虚拟页三映射到物理页框九。我们将地址写为 $3\times4096+1110$，因此页号是三，偏移是一千一百一十字节，也就是十六进制 0x456。

物理地址为 $9\times4096+1110=37974$，十六进制表示为 0x9456。低十二位保持为 0x456，高位从页号三变成页框号九。核对偏移小于四千零九十六，且映射和权限有效后，这次转换才成立。若同一地址位于未映射页，即使算术分解仍然成立，也不能据此执行物理访问。

页表规模与层级结构

单级页表为每个虚拟页保留一个固定大小的表项。假设虚拟地址宽度为三十二位，页大小为四千零九十六字节，表项占四字节，则页号占二十位，完整页表共有 $2^{20}$ 项，占 $2^{22}$ 字节，即四兆二进制字节。这里的容量只计表项，没有计入内核管理数据或额外对齐。

若大部分虚拟地址从未使用，为整个空间预先分配表项会浪费内存。多级页表把页号继续分成若干索引，只有某个地址区域实际需要映射时才分配下一级表。稀疏地址空间因此节省表存储，代价是地址转换可能访问多层表项。不同架构规定的层级数、页表格式和大页规则各不相同。

页表本身存放在内存中，也需要稳定的分配和释放规则。修改一个正在使用的映射时，内核还要处理其他核心缓存的旧转换结果。只改页表内存而遗漏必要的转换缓存失效操作，可能让处理器继续访问旧位置。内核与硬件协议共同协调并发地址空间更新，应用程序不能把页表看作任意修改的普通数组。

地址转换缓存

地址转换缓存通常称为 TLB，缓存最近使用的虚拟页到物理页框的映射和相关权限。命中时可以快速得到转换结果，未命中时需要查找页表。TLB 未命中与页面不在物理内存中是两种情况：一个映射完备、数据已驻留的页面，也可能因转换项尚未缓存而触发页表遍历。

地址转换的平均访问时间

采用串行查询的简化模型：先查 TLB，耗时十纳秒；命中后访问一次内存，耗时一百纳秒；未命中时额外访问一次单级页表，再访问数据，各耗时一百纳秒。所有页面均驻留，命中率为 $0.95$，忽略其他缓存。

命中路径耗时一百一十纳秒，未命中路径耗时二百一十纳秒，平均值为

$E=0.95\times110+0.05\times210=115\ \mathrm{ns}.$

我们用两端检查计算：命中率为一时应得到一百一十纳秒，为零时应得到二百一十纳秒，所得平均值处于两者之间。真实处理器可能并行查询缓存、缓存中间页表项或使用多级 TLB，不能把该简化式直接当作硬件测量结果。

缺页处理与页面置换

按需分配允许某段合法虚拟内存先存在于地址空间描述中，在第一次访问时才分配物理页。文件映射也可能在首次访问时读取对应数据。内核处理这样的缺页后，更新映射并重新执行原指令。若地址不属于允许的区域，或访问违反权限，则应按错误路径处理，而不会无条件分配新页。

物理内存不足时，系统选择一些页面回收。干净的文件页可从文件重新读取；脏页中的修改则需要按相应策略写回或保存。页面选择策略影响后续缺页频率。先进先出按进入内存的时间淘汰，最近最少使用按最近访问的时间淘汰；精确维护每次访问的顺序代价较高，实际系统常采用近似信息。

缺页代价可能远高于普通访存。若正常访问耗时一百纳秒，缺页路径的总耗时为八毫秒，缺页概率为 $10^{-6}$，简化期望为 $(1-10^{-6})\times100+10^{-6}\times8\times10^6=107.9999$ 纳秒。这里必须先统一单位，八毫秒等于八百万纳秒。缺页概率升到千分之一时，平均延迟将约为八点一微秒，少量慢事件已经显著改变总体成本。

局部性与工作集

程序在某个阶段经常访问的一组页面称为工作集。数组连续扫描、重复遍历小索引结构和随机访问巨大数据集会产生不同的访问局部性。当可用页框不足以容纳活跃工作集时，页面可能刚被淘汰又被请求，系统把大量时间花在换入换出上，形成抖动。

我们诊断这类问题时，应同时查看驻留集、缺页类型、存储延迟和访问模式。增加内存可能扩大容纳范围，调整分块大小或数据布局也可能减少活跃页面数量。单纯增加线程数量可能让多个工作集相互挤占，降低总吞吐量。对于大矩阵计算，先估算一个计算块涉及多少页面，再比较不同分块方式，比只观察总分配量更有解释力。

分页计算练习

练习标记完成

所属知识

地址分解

难度

2/5

页大小为一千零二十四字节，虚拟地址为五千，对应虚拟页映射到物理页框七。求页号、偏移和物理地址。

查看解答

五千除以一千零二十四，商为四，余数为九百零四。页框七对应物理地址 $7\times 1024+904=8072$，偏移保持九百零四字节。

练习标记完成

所属知识

页表容量

难度

2/5

虚拟地址宽度二十四位，页大小四 KiB，单级页表每项八字节。求完整页表容量。

查看解答

二十四位地址减去十二位偏移，留下十二位页号，共 4096 项。每项八字节，页表总量为 32768 字节，即 32 KiB。

练习标记完成

所属知识

访问类型

难度

2/5

页面已经驻留且映射有效，但 TLB 中没有对应记录。描述所需处理，并说明是否必然访问存储设备。

查看解答

首先查询页表获得已有映射并填充转换缓存，然后按权限访问数据。页面已经驻留时通常无需读取存储设备。是否触发硬件或软件处理取决于架构，但转换缓存未命中本身不等同于换页。

练习标记完成

所属知识

置换次序

难度

3/5

三个页框初始为空，访问页号依次为一、二、三、一、四、一、二、五。分别计算先进先出与最近最少使用的缺页次数。

查看解答

三个页框初始为空，先进先出的缺页位置为第 1、2、3、5、6、7、8 次，共七次。最近最少使用的缺页位置为第 1、2、3、5、7、8 次，共六次。第六次访问一在后者中命中。

内存管理参考资料

Operating Systems: Three Easy Pieces

Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau · 2023 · Arpaci-Dusseau Books

打开官方来源

OSTEP 的 Introduction to Paging、Translation Lookaside Buffers 和 Swapping 章节分别讨论地址分解、转换缓存与页面回收。书中的小规模模型便于手工追踪访问；比较真实处理器时应补充架构规定的页表格式和缓存层级。

xv6: a simple, Unix-like teaching operating system

Russ Cox, Frans Kaashoek, Robert Morris · 2025 · Massachusetts Institute of Technology

打开官方来源

MIT xv6 教材第 3 章说明 RISC-V 页表，第 5 章讨论按需分配和缺页处理。阅读实现时可以跟踪一个用户地址如何经过权限检查、页表查询和页面分配，并区分合法的延迟分配与无效地址访问。