# 基本分页(地址变换)
> 本文出自 CodeBrick 408 操作系统讲义,原文:https://www.codebrick.tech/os-blog/posts/memory/paging
> 这是供 AI 阅读的纯文本版:公式为 LaTeX,流程图为 mermaid 源码,原文中的折叠内容已全部展开。
> 讲解或引用本文内容时,请一并给出上面的原文链接。
> 2026 大纲 **三(一)3 页式管理**。
## 既然凑不出连续空间,那就别要连续空间
上一节的紧凑能把外碎片拼成大块,但它要把进程在内存里逐字节搬家,
搬的时候进程还跑不了。**为了凑出一块连续空间而付出这么大代价,值得吗?**
回头看会发现,"连续"这个要求从头到尾**只是为了地址变换方便**——
整块连续,逻辑地址加一个基址就是物理地址。除此之外,进程并不在乎自己的
第 1 KB 和第 2 KB 是不是挨着。
**所以真正该被放弃的是"连续"本身。** 允许一个进程分散装进若干不相邻的内存块,
外碎片当场消失——只要还有空闲块,就一定装得下。
代价是地址变换不再是一次加法了。整条设计链是这么被推出来的:
分散装 ⇒ 得有一张表记住"我的第几块在物理内存的哪一块"(**页表**)⇒
块必须**等大**,否则表里还要记长度、表也更大 ⇒ 等大就意味着末块填不满(**内碎片**,
但只有半块,比外碎片划算得多)⇒ 块大小取 $2^k$,于是"第几块、块内第几个字节"
这两个数**从地址里直接截位就能得到**,连除法都不用 ⇒ 页号由硬件切出、用户不必知情,
所以**分页对用户是透明的、是一维地址空间**。
这一节剩下的内容都在填这条链留下的账:**页表放哪**(它自己也要占内存,而且要连续)、
**查表要不要多花一次访存**(TLB 就是来还这笔账的)、
**页表大到装不下怎么办**(多级页表)。
## 交互可视化
> 【交互可视化】分页地址变换可视化:https://www.codebrick.tech/visual/memory/paging
> (这是一个可以逐步执行的动画演示,纯文本版无法呈现,需要时请提示用户去这个链接看。)
## 一、页面大小取多大:一组互相拉扯的代价
页面大小不是越大越好,也不是越小越好,判据是**同一个量的两头都在动**:
| 页面变大 | 影响 | 原因 |
|---|---|---|
| 页表项数 | **变少**(页表变小) | 页数 = 进程大小 ÷ 页面大小 |
| 内碎片 | **变大** | 末页平均浪费半页,半页随页变大而变大 |
| 一次缺页调入的数据量 | **变大** | 换页的 I/O 效率高,但可能调入用不上的内容 |
| TLB 覆盖的地址范围 | **变大** | 同样多的 TLB 项能罩住更多内存,命中率上升 |
所以页面大小是"页表开销"与"内碎片开销"之间的折中,现代系统典型取 **4KB**($2^{12}$B)。
## 二、页表项里除页框号还有什么
基本分页的页表项即使不做虚拟内存,也常设一个**存取控制字段(保护位)**:1 位可表达读/写与只读,2 位可再加只执行;试图写只读块会引发中断,交由操作系统处理。
若要用分页实现[虚拟内存](/posts/memory/virtual-memory-concept),页表项还要再扩几个字段——它们在[请求分页](/posts/memory/demand-paging)里才真正发挥作用,这里只需建立"页表项是可以扩展的"这个概念:
| 字段 | 含义 | 谁来置位 |
|---|---|---|
| 状态位(存在位)P | 该页是否已调入内存 | 调入时由操作系统置 1,换出时置 0 |
| 访问字段 A | 本页近期被访问过没有/访问了多少次 | 硬件访问时自动置位,供置换算法参考 |
| 修改位 M | 调入内存后是否被写过 | 硬件写操作时自动置 1 |
| 外存地址 | 该页在磁盘上的位置 | 操作系统建立映射时填写 |
页表项长度要对齐到 2 的幂,是因为"页表始址 + $P\times$ 页表项长度"这个乘法只有在长度为 2 的幂时才退化成移位。
## 三、地址变换过程
下面这张流程图第一步就要拿"页表长度"去比大小。**这个量不是常数,也不凭空存在——它和页表始址一起存在页表寄存器 PTBR 里,平时保存在进程的 PCB 中,调度到该进程时才装入。** 所以它随进程切换而变:越界判断比的始终是"当前正在运行的那个进程"的合法页号上界。
```mermaid
flowchart TD
A["CPU 发出逻辑地址 A"] --> B["硬件按页面大小 2^k 截位:
高位 = 页号 P,低 k 位 = 偏移 W"]
B --> C{"P < 页表寄存器中的
页表长度?"}
C -->|否| D["越界中断"]
C -->|是| E["页表项地址 = 页表始址 + P × 页表项长度
(第 1 次访存:读页表项)"]
E --> F{"存取控制位
允许本次操作?"}
F -->|否| D2["越权,引发中断"]
F -->|是| G["取出页框号 b"]
G --> H["物理地址 = b × 2^k + W
(第 2 次访存:读/写数据)"]
```
两次访存里第一次纯属为了查表——这是分页为"离散分配"付出的直接代价,也是引入 TLB 的全部动机。
**〔原文中此段为可折叠内容〕一个逻辑地址逐位变成物理地址的走查(想看截位、查表、拼接三步具体怎么落到数上时展开)**
```
逻辑地址 = 页号 P + 页内偏移 W
|← ── 页号 P ── →|← 页内偏移 W →|
高位部分 低位部分
```
页面大小 4KB $=2^{12}$B,逻辑地址 0x00002A1F:
1. 页内偏移占 12 位,正好是十六进制的低 3 位:**0xA1F**;
2. 剩下的高位就是页号:**0x2**(第 2 页);
3. 查页表得第 2 页对应的页框号,设为 **8**;
4. 物理地址 $=8\times4096+\text{0xA1F}=\text{0x8A1F}$。
第 4 步里"页框号乘页面大小"等价于把页框号**左移 12 位**再与偏移拼接,所以物理地址的合成也没有真正的乘法。整个过程里硬件只做了截位、一次查表寻址、一次拼接。
## 四、快表 TLB
**快表(TLB,Translation Lookaside Buffer)**存放当前正在用的那些页表项。它不是按地址索引的存储器,而是**相联存储器**:把页号同时送给所有表项并行比对,一拍就知道命中与否。相联比较的硬件代价随表项数急剧上升,所以 TLB 容量通常只有 16~512 项。
TLB 项 = **页号 + 页框号 + 控制位**,比页表项多一个页号字段。TLB 里存的是**当前进程**的映射,进程切换后旧映射全部失效,因此切换时要么清空 TLB,要么给每项打上进程标识——这也是[上下文切换](/posts/process/context-switch)开销的一部分。
```mermaid
flowchart TD
A["CPU 发出逻辑地址"] --> B["截位得到 P 和 W"]
B --> C{"TLB 中有页号 P?"}
C -->|命中| D["直接得到页框号"]
C -->|未命中| E["按第四节流程查内存中的页表(1 次访存)"]
E --> F["把该页表项装入 TLB
TLB 满则按替换算法淘汰一项"]
F --> D
D --> G["物理地址 = 页框号 × 页面大小 + W
(访问数据)"]
```
### EAT 两个口径的来历
符号:$\lambda$ 查一次快表的时间,$t$ 访问一次内存的时间,$a$ 快表命中率。
**串行**(先查快表,未命中再查页表):命中支花"查快表 + 取数据" $=\lambda+t$;未命中支多一次查页表,$=\lambda+t+t$。加权展开即 $2t+\lambda-ta$。
**并行**(快表与页表同时启动):未命中支的 $\lambda$ 被查页表的时间**盖住**,不再累加,故为 $2t$。
**两个公式都不适用的场合**:页面不在内存(缺页)要另加缺页处理时间,那属于[请求分页](/posts/memory/demand-paging);多级页表时未命中支的 $t$ 要换成 $n\times t$。
**〔原文中此段为可折叠内容〕EAT 四种口径的完整算例:无快表 / 串行 / 并行 / 二级页表(想看数值怎么代、简式怎么复核时展开)**
某系统访问一次内存需 100ns,查一次快表需 10ns,快表命中率 95%。
**① 无快表**:每次访问数据必须先查页表再取数,恒为两次访存,没有随机性、不需要加权。
$$EAT = 2t = 2 \times 100 = 200\text{ns}$$
**② 有快表,串行**:命中支 $\lambda + t = 110$ns,未命中支 $\lambda + 2t = 210$ns。先把两支各自的耗时算清楚再加权,比直接套简式不容易错:
$$EAT = 0.95 \times 110 + 0.05 \times 210 = 104.5 + 10.5 = 115\text{ns}$$
用简式复核:$2t + \lambda - ta = 200 + 10 - 100 \times 0.95 = 115$ns,一致。
**③ 有快表,并行**:命中支不变,未命中支去掉 $\lambda$,为 $2t = 200$ns。并行只影响未命中那一支——命中时本来就没访问页表,无从"并行"。
$$EAT = 0.95 \times 110 + 0.05 \times 200 = 104.5 + 10 = 114.5\text{ns}$$
两口径差 $(1-a)\lambda = 0.05 \times 10 = 0.5$ns,与直接相减一致。
**④ 二级页表,串行**:未命中时要查两级页表再取数据,共 3 次访存。
$$EAT = 0.95 \times 110 + 0.05 \times (10 + 3 \times 100) = 104.5 + 15.5 = 120\text{ns}$$
多级页表只让**未命中支**变长,命中支仍是 1 次访存——快表直接给出最终页框号,中间各级都被跳过了。这也是多级页表能被接受的根本原因:绝大多数访问根本不走完整路径。
## 五、多级页表
先算清楚单级页表有多大:32 位逻辑地址、4KB 页面、4B 页表项 ⇒ 页号 20 位 ⇒ 页表项数 $2^{20}=1\text{M}$ 个 ⇒ 页表占 $2^{20}\times 4\text{B}=4\text{MB}$,而且必须**连续**、**每个进程一份**。一个可能只用了几十 KB 内存的进程要为此付出 4MB 连续内存,这才是多级页表要解决的问题。
把页表本身再分页,建立**外层页表(页目录)**指向各个页表分页:4MB 被切成 1024 个 4KB 的分页各自装进任意空闲页框,只有页目录需要连续,而页目录只占一页;同时在外层页表项里增设**状态位 S**,S=0 表示这张页表分页尚未调入,运行时查到 S=0 就产生中断请求调入。
**只讲"离散存放"是不够的**
仅仅离散存放并**没有减少**页表占用的总内存——1024 个分页加起来还是 4MB。真正省内存的是状态位 S:只把当前需要的那几张页表分页留在内存里。这两条经常被合并成一句"多级页表省内存",但它们解决的是两个不同的问题。
### 多级页表省的是空间,代价是时间
这一条要单独钉住,因为它常被顺手记反:**多级页表不会让地址变换变快,只会变慢。**
单级页表未命中 TLB 时查一次表就够(1 次访存),$n$ 级页表要顺着查 $n$ 次
($n$ 次访存),再加上取数据那一次,一共 $n+1$ 次。级数越多,未命中时越慢。
所以问"多级页表的优点是什么"时,答案只能落在**空间**上——
**减少页表所占的连续内存空间**。它既不加快地址变换(反而变慢),
也不减少页表项的字节数(每项还是那么宽),更不会减少缺页中断次数。
反过来,真正能压低平均访存时间的是另外几样:
| 措施 | 作用在哪一环 | 能否降低平均访存时间 |
|---|---|---|
| **增大 TLB 容量** | 提高命中率,命中时地址变换降到 0 次访存 | **能** |
| **让页表常驻内存** | TLB 未命中后查页表不再触发"把页表本身调进来"的额外磁盘 I/O | **能** |
| **工作集** | 让驻留集贴合实际需要,压低缺页率 | **能**(见[页框分配与回收](/posts/memory/page-allocation)) |
| **页缓冲队列** | 被换出的页先进队列而不立即写盘,再次访问可直接取回 | **能**(同上) |
| **多级页表** | 把 1 次查表变成 $n$ 次 | **不能,反而变慢** |
| **增大交换区** | 只影响能换出多少,不在地址变换路径上 | **不能** |
判据统一成一句:**看它作用在"地址变换"还是"缺页处理"这两段路径上**——
两段都不沾的(交换区大小),以及只优化空间的(多级页表),都不降低访存时间。
```mermaid
flowchart LR
subgraph LA["逻辑地址(二级)"]
direction LR
L1["一级页号 P1"]
L2["二级页号 P2"]
L3["页内偏移 W"]
end
PTBR["页表寄存器
存页目录始址 + 长度
(随进程切换而装载)"]
DIR["页目录(外层页表)
必须连续,仅占 1 页
每项:状态位 S + 页表分页所在页框号"]
PT1["页表分页 0 号
常驻"]
PT2["页表分页 k 号
常驻"]
PT3["页表分页 m 号
S=0,尚未调入"]
FR["页框号 b"]
PA["物理地址 = b × 页面大小 + W"]
PTBR --> DIR
L1 -->|"索引"| DIR
DIR --> PT1
DIR --> PT2
DIR -.->|"S=0 → 缺页中断,先调入这张页表分页"| PT3
L2 -->|"索引"| PT1
PT1 --> FR
L3 --> PA
FR --> PA
```
分级不能随便分:**每一级页表都必须恰好放得进一个页框**,否则这一级自己又需要连续大块,等于没解决问题。由这句话直接推出每级页号该占几位——一个页框能装 $\dfrac{\text{页面大小}}{\text{页表项大小}}$ 个表项,能寻址这么多表项需要的位数就是每级页号的位数:
$$
\text{每级页号位数}=\log_2\frac{\text{页面大小}}{\text{页表项大小}}
$$
**〔原文中此段为可折叠内容〕给定参数把多级页表划分出来的完整走查(想看判据怎么逐级试、驻留量怎么算时展开)**
某系统逻辑地址 32 位,页面大小 1KB,页表项大小 4B。
**① 划分位数**:偏移位数只由页面大小决定,与地址总长无关,剩下的全是页号。$1\text{KB}=2^{10}$B ⇒ 页内偏移 **10 位**;页号 $32-10=$ **22 位**。
**② 单级页表大小**:页表项数 = 页数 = $2^{\text{页号位数}}$,与进程实际用了多少页无关——单级页表必须为每个可能的页号预留一项,这正是它浪费的根源。
$$2^{22} \times 4\text{B} = 4\text{M} \times 4\text{B} = 16\text{MB}$$
而且这 16MB 必须连续。
**③ 分几级**:一个页框能放多少个页表项:$1\text{KB}/4\text{B}=256=2^8$ ⇒ 每级页号占 8 位。判据不是"分得越多越好",而是"最高一级必须装得下一页",所以从低位往高位按 8 位一刀切,切到剩余位数 ≤ 8 就停:
- 试二级:末级 8 位,剩 $22-8=14$ 位给顶级 ⇒ 顶级页表 $2^{14}\times4\text{B}=64\text{KB}=64$ 页,**放不进一个页框,不合格**;
- 试三级:$22-8-8=6$ 位给顶级 ⇒ 顶级页表 $2^{6}\times4\text{B}=256\text{B}\le1\text{KB}$,**合格**。
所以要 **3 级**,地址划分为:
```
| 一级页号 6 位 | 二级页号 8 位 | 三级页号 8 位 | 页内偏移 10 位 |
```
**④ 实际驻留量**:若某进程只访问了 2 个页面且这 2 页的表项落在同一张末级页表分页内,则驻留的是顶级页表 1 页 + 二级分页 1 页 + 三级分页 1 页 $=3\times1\text{KB}=3\text{KB}$。顶级只有 256B,但内存按页框分配,不足一页也占一页。这一问才是多级页表的价值所在:**从必须连续的 16MB,降到离散的 3KB**。
## 考点速记
1. 整条设计链由一句话推出:允许分散装 ⇒ 要**页表** ⇒ 块必须**等大** ⇒ 末块填不满产生**内碎片**(无外碎片)⇒ 块大小取 $2^k$ 让除法退化成**截位** ⇒ 页号由硬件切出、用户不必知情 ⇒ **分页是一维地址空间、对用户透明**。
2. **地址拆分**:页面大小 $L=2^k$ ⇒ **页内偏移占低 $k$ 位**,其余高位全是页号。**物理地址合成** $=$ 页框号 $\times L + W$,等价于把页框号**左移 $k$ 位再拼上偏移**,没有乘法。
3. **越界判断比的是 $P <$ 页表长度**,上界来自**页表寄存器**,单位是**表项个数不是字节数**;页面大小只决定偏移占几位,与越界判断无关。
4. **页表项不存页号,TLB 项必须存**。判据是"这一项能不能靠位置认出自己是谁"——页表按页号连续排布,第 $P$ 项就是第 $P$ 页;TLB 只装任意子集,位置说明不了身份。
5. **页表项地址** $=$ 页表始址 $+ P\times$ 页表项长度,所以**每个进程的页表必须占连续内存**——这正是多级页表要解决的问题。PTBR 存**页表始址 + 页表长度**,平时在 PCB 里,单处理机只需一个。
6. **访存次数**:TLB 命中 **1 次**;未命中(单级)**2 次**;未命中 + $n$ 级页表 **$n+1$ 次**。**命中恒为 1 次,与级数无关**;查 TLB 不走内存总线,**不计作访存**。
7. **EAT 串行口径**(默认)$=a(\lambda+t)+(1-a)(\lambda+2t)=2t+\lambda-ta$;**并行口径** $=a(\lambda+t)+(1-a)\cdot 2t$,两者差 $(1-a)\lambda$。⚠️ $\lambda$ 与 $t$ **必须分开累加**;"快表具有并行查寻能力"指**表内各项并行比较**,不等于快表与页表并行,没写明并行就按串行。
8. **多级页表省下的是两样东西**:① **离散存放**(解决"连续大块难找",但**不减少总占用**);② **外层页表项的状态位 S** 允许某些页表分页不驻留内存(这条才真正省内存)。只说一条等于只答一半。
9. **多级页表不加快地址变换,反而变慢**。它的优点只能落在空间上——**减少页表所占的连续内存空间**。
10. **分级判据**:每级页号位数 $=\log_2\dfrac{\text{页面大小}}{\text{页表项大小}}$,从低位往高位按这个位数切,切到剩余位数 $\le$ 它为止,剩下的全给最高一级——**最高一级必须放得进一个页框**。
**这一节在真题里被考过的形式**:
分页是内存章出题最密的一节,**近乎年年一道选择题外加一道大题的若干分问**。
但十几道题的问法只有五类,按类准备比按题准备省得多。
- **① 由地址结构拆位段**(2019-31、2026-28)。做法固定:**先从最低位切走页内偏移**($\log_2$ 页面大小位),剩下的位数再按"每级页号位数 $=\log_2\frac{\text{页面大小}}{\text{页表项大小}}$"从低往高切。2019-31 给了 10+10+12 的结构,把虚拟地址 `20501225H` 展开成二进制按位段切即得页目录号 `081H`、页号 `101H`。⚠️ 一处会让整题全错的手滑是**从高位往低位切**——必须从低位起,因为偏移在低位。
- **② 算某一级页表的项数、或页表要占几个页框**(2010-29、2013-46)。判据是"这一级要覆盖多少个下一级对象"。2010-29:逻辑空间 $2^{16}$ 页 ⇒ 共需 $2^{16}$ 个页表项;页大小 $2^{10}$ B、页表项 2 B ⇒ 一个页框装 $2^{10}/2=2^9$ 个页表项 ⇒ 二级页表共 $2^{16}/2^9=2^7=\mathbf{128}$ 张 ⇒ 页目录至少 **128** 项。⚠️ 单位换算是唯一的坑,"页数"和"字节数"要分清。
- **③ 给出页表内容做一次完整地址转换**(2015-46、2021-29、2024-45、2017-45、2018-45,全是大题分问)。流程恒定:**拆位段 → 查越界 → 逐级查表得页框号 → 页框号左移拼偏移**。⚠️ 两处必错点:合成物理地址时**页框号要左移而不是直接相加**;以及题目给的页表项里通常还有存在位,**存在位为 0 要答"产生缺页"而不是硬算出一个地址**。
- **④ 判断某项措施的作用**(2014-32、2014-28、2026-29)。这一类全靠速记第九条。2014-32 答**减少页表所占的连续内存空间**(不是加快变换、不是减少页表项字节数、不是减少缺页)。2014-28 答**增大 TLB + 页表常驻内存**,增大交换区不在地址变换路径上。2026-29 答 **TLB + 工作集 + 页缓冲队列**,⚠️**多级页表是唯一的错项,它反而使访存变慢**。
- **⑤ 访问顺序与局部性**(2020-46)。给一个二维数组和按行/按列的遍历方式,问缺页次数。判据是 **C 语言按行优先存储**,所以逐行访问时一页里的数据会被连续用完(局部性好),逐列访问则每访问一个元素就可能换一页。
**复习优先级**:**本节必须拿满,且要练熟手算。** 五类问法里 ①②③ 是纯技术动作,
练到不看步骤也能走完;④ 靠速记第九条一条判据;⑤ 只考过一次,理解"按行优先"即可。
EAT 的两个口径要都会,但**没写明并行就按串行**这条默认口径不能忘。
> **易错**:拆位段时从高位往低位切。**必须先从最低位切走页内偏移**。
> **易错**:合成物理地址时把页框号和偏移直接相加。要**页框号 × 页面大小 + 偏移**,即左移 $k$ 位再拼。
> **易错**:认为多级页表能加快地址变换。它把 1 次查表变成 $n$ 次,**反而变慢**;它的优点只在空间。
> **易错**:说"多级页表省内存"时只讲离散存放。离散存放**不减少总占用**,真正省内存的是**状态位 S 允许分页不驻留**。
> **易错**:越界判断时拿页号和"页表字节数"比。上界的单位是**表项个数**。
> **易错**:认为 TLB 项和页表项内容一样。**TLB 项必须多存一个页号**,因为它不是按页号连续排布的。
> **易错**:算 EAT 时把查快表的 $\lambda$ 并进访存时间里。两者要分开累加,否则两支都偏大。
> **易错**:把"快表具有并行查寻能力"理解成快表与页表并行查。它指的是**表内各项并行比较**。
> **易错**:认为 TLB 未命中时访存次数与页表级数无关。**命中才恒为 1 次**;未命中是 $n+1$ 次。
> **易错**:查到页表项后不看存在位就算物理地址。**存在位为 0 应答"缺页"**。
**〔原文中此段为可折叠内容〕教材出处**
- 汤小丹《计算机操作系统》4.5.1 分页存储管理的基本方法(地址结构、页表、存取控制字段),p139
- 同上 4.5.2 地址变换机构(页表寄存器 PTR 存放页表始址与长度、平时存于 PCB;快表与联想寄存器),p140–p141
- 同上 4.5.3 访问内存的有效时间(EAT 公式与命中率对照表),p142
- 同上 4.5.4 两级和多级页表(32 位地址 4KB 页面下页表项数达 1M;外层页表项增设状态位 S),p142–p144
## 相关知识
[连续分配](/posts/memory/contiguous-allocation)|[基本分段](/posts/memory/segmentation)|[内存管理基本概念](/posts/memory/memory-concept)|[请求页式管理](/posts/memory/demand-paging)
## 真题练习
## 本节对应的历年 408 真题
- 2010 年第 29 题:https://www.codebrick.tech/practice/q/os-2010-29
- 2011 年第 28 题:https://www.codebrick.tech/practice/q/os-2011-28
- 2013 年第 46 题:https://www.codebrick.tech/practice/q/os-2013-46
- 2014 年第 28 题:https://www.codebrick.tech/practice/q/os-2014-28
- 2014 年第 32 题:https://www.codebrick.tech/practice/q/os-2014-32
- 2015 年第 46 题:https://www.codebrick.tech/practice/q/os-2015-46
- 2017 年第 45 题:https://www.codebrick.tech/practice/q/os-2017-45
- 2018 年第 45 题:https://www.codebrick.tech/practice/q/os-2018-45
- 2019 年第 31 题:https://www.codebrick.tech/practice/q/os-2019-31
- 2020 年第 46 题:https://www.codebrick.tech/practice/q/os-2020-46
- 2021 年第 29 题:https://www.codebrick.tech/practice/q/os-2021-29
- 2024 年第 45 题:https://www.codebrick.tech/practice/q/os-2024-45
- 2026 年第 28 题:https://www.codebrick.tech/practice/q/os-2026-28
- 2026 年第 29 题:https://www.codebrick.tech/practice/q/os-2026-29
- 2026 年第 30 题:https://www.codebrick.tech/practice/q/os-2026-30