# 基本分页(地址变换) > 本文出自 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