考研笔记

基本分页存储管理

连续分配的死结是外部碎片：内存里明明还有很多空间，却因为不连续而放不下作业。紧凑能缓解，但移动作业的开销很大。

分页的思路很直接：既然”必须连续”是问题的根源，那就不要求连续。 把内存切成固定大小的小块，进程需要多少块给多少块，放在哪儿无所谓。

机制

三个基本概念

页框（页帧、物理块）：把物理内存等分成的固定大小的块，从 0 开始编号。

页（页面）：把进程的逻辑地址空间按同样的大小分成的块，也从 0 开始编号。

页表：记录每个页放在哪个页框里的对照表。每个进程一张。

页和页框大小必须相同——正因如此，任意一页都能装进任意一个页框，摆放才彻底自由。

页表项通常只需要记录页框号：页号是隐含的（第 个表项对应第 页），不必存储。这一点在计算页表大小时很重要。

地址结构

逻辑地址被拆成两段：

逻辑地址页号高位页内偏移低位

页内偏移的位数由页面大小决定：页面大小为 字节，则页内偏移占 位。剩下的高位全是页号。

这个拆分不需要做除法——页面大小是 2 的幂，所以只要按位截断即可，硬件做起来极快。这正是页面大小必须取 2 的幂的原因。

地址变换过程

flowchart LR
    LA["逻辑地址<br/><b>页号 P</b> | 页内偏移 W"]:::la
    PTR["页表寄存器<br/>（存页表始址+长度）"]:::reg
    CHK{"P ≥ 页表长度？"}:::chk
    ERR["越界中断"]:::err
    PT["查页表<br/>得页框号 F"]:::pt
    PA["物理地址<br/><b>页框号 F</b> | 页内偏移 W"]:::pa

    LA --> CHK
    PTR --> CHK
    CHK -->|"是"| ERR
    CHK -->|"否"| PT
    PT --> PA
    LA -.->|"W 原样拼接"| PA

    classDef la fill:#dbeafe,stroke:#2563eb,color:#1e3a5f
    classDef pa fill:#dcfce7,stroke:#16a34a,color:#14532d
    classDef reg fill:#fef3c7,stroke:#d97706,color:#78350f
    classDef pt fill:#fef3c7,stroke:#d97706,color:#78350f
    classDef chk fill:#f1f5f9,stroke:#94a3b8,color:#334155
    classDef err fill:#fee2e2,stroke:#dc2626,color:#7f1d1d

有两个细节必须记牢：

① 页内偏移 W 原样照抄，不参与任何计算。 因为页和页框大小相同，某个字节在页内是第几个，在页框内也是第几个。只有页号需要被翻译。

② 这个过程要访问两次内存：一次读页表（页表在内存里），一次读真正的数据。这就是分页的性能代价，也是引入快表的动机。

疑问点：页表始址存放在何处，查页表由谁完成

  1. 在页式存储管理中，页表的始地址存放在（ ）中。 A. 物理内存　B. 页表　C. 快表（TLB）　D. 页表寄存器

  2. 在页式存储管理中，当 CPU 形成一个有效地址时，查找页表的工作是由（ ）实现的。 A. 操作系统　B. 页表查询程序　C. 硬件　D. 存储管理进程

第 31 题答案 D：页表寄存器。

要区分两件事：页表本身存放在内存中（这是 A 的迷惑之处），但页表的起始地址存放在 CPU 的页表寄存器里。

道理很简单：如果连”页表在哪儿”都要去内存里查，那就成了先有鸡还是先有蛋。必须有一个 CPU 能直接读到的地方来存这个入口，那就是寄存器。

页表寄存器通常同时存放页表始址和页表长度，后者用于越界检查（见上图）。

进程切换时，页表寄存器的内容要作为进程上下文的一部分被保存和恢复——这正是进程切换比模式切换昂贵的原因之一。

第 32 题答案 C：硬件。

关键在于频率：每一次访存都要做一次地址变换。如果由操作系统的软件来做，意味着每取一个数就要陷入内核跑一段程序，开销将高到无法接受。

因此地址变换必须由硬件（地址变换机构 / MMU）完成，全程不需要操作系统介入。操作系统只负责在进程切换时设置好页表寄存器，剩下的交给硬件。

排除 B、D 也是同样的道理：任何”程序”或”进程”级别的实现都太慢了。

快表（TLB）

为了消除”访存两次”的代价，引入快表——一个高速缓存，存放最近用过的页表项。

TLB 由相联存储器实现，可以并行比较所有表项，一次查找就知道命中与否。

有 TLB 之后的流程：

  • TLB 命中：直接得到页框号 → 访存 1 次（只取数据）
  • TLB 未命中：查内存中的页表得页框号 → 再取数据 → 访存 2 次，同时把该表项装入 TLB

TLB 之所以有效，靠的是程序访问的局部性原理——程序倾向于在一段时间内反复访问相邻的地址，因此命中率通常能达到 90% 以上。

注意 TLB 中存的是”页号→页框号”的完整映射，这一点在多级页表下极其重要（见下方边界段）。

多级页表

单级页表有个致命问题：页表本身太大，而且要求连续存放。

以 32 位系统、4KB 页面为例：页号占 20 位，共 = 1M 个页表项，每项 4B，一张页表就要 4MB 连续内存。一个进程 4MB，几十个进程就把内存吃光了。

解决办法是把页表本身也分页，再用一张”页表的页表”来索引它——这就是二级页表。逻辑地址随之拆成三段：逻辑地址一级页号二级页号页内偏移多级页表带来两个好处：

  • 页表不必连续存放，各级页表自己也按页存储，散落在内存各处
  • 可以只装入需要的部分，进程没用到的地址区域，对应的下级页表根本不必建立

代价是访存次数增加： 级页表意味着查表要访存 次，加上取数据一次，共 次。这正是 TLB 变得更加不可或缺的原因。

计算题模板一：需要几级页表

疑问点：多级页表级数的计算方法

  1. 在采用页式存储管理的系统中，逻辑地址空间大小为 256TB，页表项大小为 8B，页面大小为 4KB， 则该系统中的页表应该采用（ ）级页表。 A. 2　B. 3　C. 4　D. 5

这类题应当如何着手？

答案 C：4 级。

这类题的唯一原理是：每一级页表必须恰好装进一个页面（这是多级页表的设计目标——让页表本身也能按页管理）。因此每一级能覆盖的位数是固定的，用总页号位数除一下即可。

四步法：

第一步：算页内偏移位数。 页面大小 → 偏移占 12 位。

第二步：算页号总位数。 逻辑地址空间 → 地址共 48 位。页号位数位第三步：算一个页面能装多少个页表项——这决定了每一级能”吃掉”多少位页号。每级消化位第四步：向上取整相除。级注意第四步必须向上取整：若算出 36/9 = 4 恰好整除，就是 4 级；若是 37 位则需 5 级（最高级那张表用不满一整页，但仍要单独一级）。

计算题模板二：平均访存次数

疑问点：带 TLB 的多级页表平均访存次数计算

  1. 在配置了 TLB 的页式虚拟存储管理的系统中，假设 TLB 的命中率约为 75%， 忽略访问 TLB 的时间，并且使用二级页表，则每次存取的平均访问次数是（ ）。 A. 1.25　B. 1.5　C. 1.75　D. 2

答案 B：1.5。

三步法：

第一步：分别算出”命中”和”未命中”两条路径各要访存几次。

  • TLB 命中：直接拿到页框号，不需要查任何一级页表 → 只需 1 次访存去取数据
  • TLB 未命中：要查完 2 级页表（2 次访存），再取数据（1 次）→ 共 3 次

第二步：按概率加权。第三步：检查合理性。 结果必然落在 1（全命中）与 （全不命中）之间。这里 ✓

通用公式（ 级页表、TLB 命中率 ）：

平均访存次数

边界

TLB 缓存的是最终映射，不是某一级

疑问点：多级页表下 TLB 命中率是否需要按级数相乘

在二级页表下，TLB 是否可能”只命中某一级”？两级都命中的概率是否应为 ？

不需要相乘，也不存在”只命中某一级”。这是理解 TLB 最关键的一点。

原因在于 TLB 中存放的是”页号 → 页框号”的完整映射，而不是各级页表的中间项。

换句话说，TLB 的查找以完整的页号为键，一次查询要么直接给出最终的页框号，要么什么都没有。它把整个多级查表过程当作一个黑盒缓存了起来。

所以：

  • 命中：整条路径被跳过，无论有几级页表都不必查 → 1 次访存
  • 未命中：整条路径都得走一遍 → 次查表 + 1 次取数

“两级都命中”这个概念本身不成立——不存在”第一级命中而第二级未命中”的中间状态。75% 就是拿到完整翻译结果的概率，不需要再做任何复合运算。

这也解释了为什么多级页表下 TLB 的价值更大：级数越多，未命中的代价越高（ 次），命中带来的节省也就越可观。

分页有内部碎片，没有外部碎片

外部碎片消失了，因为任何一个空闲页框都能被使用——不存在”太小以致用不上”的空闲块。这正是分页取代连续分配的根本理由。

但引入了内部碎片：进程的最后一页通常装不满。平均而言每个进程浪费半个页面。

由此可推出页面大小的权衡：

  • 页面太大 → 内部碎片大
  • 页面太小 → 页表项数量剧增，页表本身太大

页表项里存的是页框号，不是物理地址

页表项存的是页框号（块号），不是完整的物理地址。物理地址要由页框号拼接页内偏移得到。

计算页表项大小时常犯的错是按物理地址位数去算。正确做法是按页框号位数（= 物理内存大小的位数 − 页内偏移位数）向上取整到字节。

分页提供的物理地址空间

疑问点：采用分页或分段后用户可用的物理地址空间

  1. 采用分页或分段管理后，提供给用户的物理地址空间（ ）。 A. 分页支持更大的物理地址空间　B. 分段支持更大的物理地址空间 C. 不能确定　D. 一样大

答案 C：不能确定。

命题人的意图是：页表和段表本身也要占用内存。因此用户可用物理空间总物理空间页表段表所占空间而页表和段表的长度取决于地址空间大小、页面大小、段的数目等因素，题目未给出这些条件，故无法确定。

这道题的措辞确实偏松——严格说”提供给用户的物理地址空间”应指物理内存的寻址范围，那是由地址总线宽度决定的，与采用分页还是分段无关。命题人想问的其实是”可供用户程序使用的物理内存量”。

遇到这类题的稳妥做法：先看选项。当出现”不能确定”且题干确实缺少关键条件时，命题人多半就是想考”管理机构本身也要占空间”这个点。答题按命题意图走，但心里要清楚它问得不严谨。

对照速查

概念属于说明
页框（物理块）物理内存内存被等分成的固定大小块
页（页面）逻辑地址空间进程被等分成的块，与页框等大
页表每进程一张，存于内存记录页 → 页框的映射
页表寄存器CPU 中存页表始址和长度
快表 TLB相联存储器缓存完整的页号→页框号映射
情形访存次数
无 TLB，单级页表2
无 TLB， 级页表
TLB 命中1
TLB 未命中， 级
平均（命中率 ）
计算模板步骤
几级页表① 页内偏移位数 ② 页号总位数 ③ 一页装几个表项 = 每级消化位数 ④ 向上取整相除
平均访存① 命中路径 1 次、未命中 次 ② 按概率加权 ③ 检查落在

考点

  • 页内偏移原样照抄，只有页号需要翻译
  • 页表始址存于页表寄存器（页表本身在内存）
  • 地址变换由硬件完成，操作系统不介入
  • TLB 缓存完整映射，不存在”只命中某一级”，命中率不需相乘
  • 多级页表的设计目标：每级页表恰好装进一个页面
  • 分页有内部碎片、无外部碎片；页面大小是碎片与页表大小的权衡
  • 页表项存页框号，不是物理地址

链接

反向链接