#内存管理

#考点定位

• 大纲章节：内存管理（内存管理基础：程序装入与链接、连续分配、分页、分段、段页式；虚拟内存：请求分页、页框分配与置换算法、抖动与工作集）
• 常见题型：选择题（装入方式辨析、分配算法选择、分页/分段地址结构、置换算法性质、Belady 异常）+ 综合大题高频（地址翻译全流程推演、页面置换算法手推表、有效访问时间计算——常与 TLB/Cache 组合出题，横跨计组）
• 考查频率：极高（与进程管理并列的 OS 大题主要出处；地址翻译 + 置换手推几乎每年在选择题或大题中出现）
• 工程师读者注意：你天天跟虚拟地址、页错误、mmap 打交道，但考试考的是地址二进制拆分的精确计算、变换机构每一步的访存次数、置换算法逐格手推的表格纪律——工程直觉帮你理解"为什么"，答题必须按机器步骤推
• 前置知识：操作系统概述（中断、内核态/用户态是缺页中断的基础）；进程与线程（进程映像与内存分配的关系）；硬件基础见存储器层次结构（TLB 与 Cache 的工作原理，地址翻译组合题必用）

#一、内存管理概念

#1.1 内存管理的功能

内存管理是操作系统对内存的划分、分配、保护与扩充，考点口径为四大功能：

1. 内存空间的分配与回收：为进程分配运行所需内存，进程结束后回收（对应地址分配的数据结构与算法）
2. 地址转换：将程序中的逻辑地址转换为内存中的物理地址（重定位机制，见 1.3）
3. 内存保护：各进程在自己的内存空间内运行，互不干扰。两种经典实现：
   • 设置上下限寄存器：判断 逻辑地址 ∈ [下限, 上限]
   • 利用重定位寄存器（基址寄存器）+ 界地址寄存器（限长寄存器）：判断 逻辑地址 < 界地址寄存器的值，再加上重定位寄存器的值得到物理地址。这两个寄存器只能由操作系统（内核态）修改（选择题高频）
4. 内存空间的扩充：利用覆盖、交换、虚拟存储技术"扩充"逻辑上的内存容量（见第五节）

#1.2 程序的装入与链接（三阶段 → 三种装入方式）

从源程序到在内存中执行，经历三个阶段：

链接的三种方式：静态链接（运行前一次性链接成完整装入模块，以后不再拆开）、装入时动态链接（边装入边链接，便于修改和共享目标模块）、运行时动态链接（执行到未链接模块时才链接，未用到的模块不链接，加快装入、节省内存）。

装入的三种方式（选择题高频，考"允许移动与否/何时形成物理地址"）：

判断窍门：题目出现"程序装入后允许在内存中移动/换出再换入"→ 必须是动态重定位；出现"无需硬件地址变换机构支持"→ 静态重定位。

#1.3 逻辑地址与物理地址

• 逻辑地址（虚拟地址）：程序视角的地址，从 0 开始编址，CPU 地址机构给出的都是逻辑地址
• 物理地址：内存单元的真实编号
• 重定位（地址变换）：逻辑地址 → 物理地址 的过程，三种实现见 1.2 表格

工程师映射：你调 GDB 看到的 0x400000、mmap 返回的指针都是逻辑地址；分页/分段就是用硬件把二者解耦——这正是"进程拥有独立地址空间"幻觉的物理基础。

#二、连续分配管理方式

"连续分配"：为一个用户程序划分一块连续的内存空间。

#2.1 单一连续分配

内存分为系统区 + 用户区，用户区一次只装一道程序、独占整个用户区。无外部碎片、有内部碎片（程序比用户区小则浪费），无需硬件保护也可（就一道程序）。仅适合单用户单任务（早期 CP/M、DOS 思路）。

#2.2 固定分区分配

用户区预先划分为若干固定大小的分区（分区可以不等大），每个分区装一道程序；需建立分区说明表记录分区大小、起始地址、状态。

• 有内部碎片（程序小于分区则浪费），无外部碎片
• 缺点：分区总数固定 → 限制并发进程数；程序与分区大小难匹配 → 内存利用率低
• "固定分区 + 分区说明表"是判断题常客：分区大小可以不相等，但运行期间不可改变

#2.3 动态分区分配

进程装入时才创建分区，分区大小 = 进程请求的大小。

数据结构：空闲分区表 / 空闲分区链（每个空闲分区记录大小、起始地址、前后向指针）。

#四种分配算法（必考，规则 + 对比表）

设当前空闲分区按地址递增排列如下（经典示例，进程请求 100 KB）：

（注：首次/最佳/最坏/邻近适应都在按地址递增的空闲分区链上扫描；"最佳适应"另需按容量组织空闲链的口径在本表推演中不采用，以扫描顺序为准。）

考点提醒：上例中 100KB 请求恰好与 F1 等大，首次/最佳/邻近都选中 F1；若请求改为 150KB，则首次适应选 F2（500KB）、最佳适应选 F3（200KB，剩余 50KB）、最坏适应选 F5（600KB）、邻近适应从上次结束处起选第一个 ≥150KB 的。"请求大小不同时四种算法结果不同"是选择题的设计点。

#动态分区的分配与回收（分裂与合并）

• 分配（分裂）：找到的空闲分区大于请求 → 一分为二：低地址部分分配给进程，剩余部分留在空闲链中（更新大小与起始地址）
• 回收（合并）：进程释放分区，按相邻情况四种处理：
  1. 回收区前邻空闲分区 → 合并成一个大空闲分区（起始地址 = 前邻起始，大小相加）
  2. 回收区后邻空闲分区 → 合并（起始地址 = 回收区起始，大小相加）
  3. 前后都邻空闲分区 → 三块合并成一个（起始地址 = 前邻起始，大小三块相加，空闲链上删一个结点）
  4. 前后都不邻 → 新建空闲分区结点插入链中（按地址有序插入）

#碎片总结（高频判断）

紧凑（Compaction）：将内存中进程整体移动，把外部碎片拼接成一个大分区。前提是动态重定位（程序可移动，见 1.2）；代价是移动开销大，且需在进程不运行时进行。分页不需要紧凑（无外部碎片），分段才可能需要——高频选择题。

#三、基本分页存储管理

#3.1 页框、页面与页表

• 页面（page）：进程逻辑地址空间划分为大小相等的块
• 页框（页帧，frame/物理块）：内存划分为与页面大小相等的块
• 进程的任一页面可装入任一页框；页面大小 = 页框大小，且是 2 的整数次幂（408 默认）
• 页表：每个进程一张，记录页号 → 页框号的映射。页表项按页号顺序存放，故页表中不存页号本身（隐含为下标），只存页框号 + 状态位（该页是否在内存）

地址结构（页面大小 $2^k$，按字节编址）：

$$\underbrace{31 \cdots k}_{\text{页号 } P \text{（高位）}} \; \underbrace{k-1 \cdots 0}_{\text{页内偏移 } W \text{（低位，} k \text{ 位）}}$$

• 逻辑地址 $A$：$P = \lfloor A / 2^k \rfloor$（即二进制右移 $k$ 位 / 取高位），$W = A \bmod 2^k$
• 物理地址 $= \text{页框号} \times 2^k + W$（即页框号二进制拼接 $k$ 位偏移）

页内碎片：进程最后一页平均浪费半页——分页有内部碎片、无外部碎片。

页表大小计算（选择题高频）：页表长度（页数）= 逻辑地址空间 / 页面大小；页表占用内存 = 页数 × 每项大小。例：32 位逻辑地址、4KB 页、每项 4B → 页数 $2^{20}$，页表共 $2^{20} \times 4\text{B} = 4\text{MB}$——这正是需要多级页表的原因（见 3.3）。

#3.2 基本地址变换机构（完整过程 + TLB 两条路径）

基本机构（无 TLB）：页表基址寄存器（PTBR，进程切换时更新）指向页表起始地址。

1. CPU 给出逻辑地址，硬件拆成页号 $P$ 与偏移 $W$
2. 比较 $P$ 与页表长度寄存器（PTLR）：$P \geq$ 页表长度 → 越界中断（考点：先查越界再查页表）
3. 物理地址 = $P \times \text{页表项大小} + \text{PTBR}$，访问内存读页表项，得页框号 $F$（第一次访存）
4. 若页表项状态位 = 不在内存 → 缺页中断（基本分页无此情况，请求分页见第五节）
5. 物理地址 = $F \times 2^k + W$，访问内存取数据（第二次访存）

快表 TLB（Translation Lookaside Buffer）：页表项的高速缓存（相联存储器/Cache 结构，原理见存储器层次结构），按内容（页号）并行查找，访问速度远快于内存。

引入 TLB 后的完整流程（两条路径，必考）：

表格化分步推演（待动画化；读者可按此表逐步核对每一步访存）。

设定：页面 4KB（偏移 12 位），内存按字节编址，$t_{\text{访存}} = 100\text{ns}$，$t_{\text{TLB}} = 10\text{ns}$；页表（页号 → 页框号）：0→5，1→3，2→7，3→1；TLB 中当前缓存：页 1→帧 3、页 3→帧 1。

情形 A：逻辑地址 0x1A2C（TLB 命中路径）

情形 B：逻辑地址 0x2B5D（TLB 未命中路径）

访存次数口诀：无 TLB 的基本分页，一次数据访问 = 2 次访存（页表 1 + 数据 1）；TLB 命中 = 1 次访存；二级页表未命中 TLB = 3 次访存。

TLB 命中率的条件：基于局部性原理——同一页内的连续访问只需一次页表查询。快表深度通常 16～1024 项，命中率可达 90% 以上。

#3.3 两级页表

为什么需要（简答题背诵口径）：

1. 32 位系统 4KB 页 → 页表 $2^{20}$ 项 × 4B = 4MB 连续内存——页表本身要求连续存放（因为按页号索引），与分页"离散分配"初衷矛盾
2. 页表必须常驻内存才不至于每次翻译多一次缺页，但一次 4MB 常驻太浪费
3. 局部性原理：一段时间内只用到少数几个页面对应的页表项——不必让整个页表都在内存

结构：把页表再分页（每页放 $2^{10}$ 个页表项），建立页目录（外层页表/一级页表）：页目录项 → 二级页表所在页框。

地址结构（32 位、4KB 页、页表项 4B → 每页放 $2^{10}$ 项 → 每级各 10 位）：

$$\underbrace{31 \cdots 22}_{\text{一级页号（10 位）}} \; \underbrace{21 \cdots 12}_{\text{二级页号（10 位）}} \; \underbrace{11 \cdots 0}_{\text{页内偏移（12 位）}}$$

翻译步骤（TLB 未命中时）：

1. 拆出一级页号 → 访问内存查页目录得二级页表所在页框（第 1 次访存）
2. 用二级页号在二级页表中查 → 得数据页框号（第 2 次访存）
3. 拼装物理地址访问数据（第 3 次访存）

访存分析（必考）：两级页表 + TLB，命中率 $\alpha$，$t_{\text{TLB}}$、$t_{\text{访存}}$：

$$EAT = \alpha (t_{\text{TLB}} + t_{\text{访存}}) + (1-\alpha)(t_{\text{TLB}} + 3 t_{\text{访存}})$$

（x86-64 的 4 级页表是同一思想的推广；408 计算一般到两级为止。）

各级页表都要离散：页目录、二级页表、数据页都可放任意页框——这是"页表也分页"的完整含义。

#3.4 页式管理的碎片分析

• 只有内部碎片：最后一页装不满（平均半页），页面越大内部碎片越大
• 无外部碎片：任意页框可分配 → 不需要紧凑
• 页面大小权衡：页大 → 页表短、碎片大；页小 → 碎片小、页表长、TLB 覆盖率低（工程上 4KB 是权衡结果）

#四、基本分段与段页式存储管理

#4.1 分段

按程序逻辑结构（主程序、子程序、数据段、栈段）划分，各段长度不等、内部连续、段间离散。逻辑地址二维：(段号 S, 段内偏移 W)。

段表：段号（隐含）→ 段长、该段在内存的起始地址。段表项中必须存段长——用于越界检查（与页表的关键区别：页内偏移不越界天然成立，因为页面等长；段长不等，必须显式检查 $W <$ 段长）。

地址变换过程（无 TLB，每次数据访问 2 次访存，流程与分页对偶）：

1. 拆出段号 $S$ 与偏移 $W$；检查 $S \geq$ 段表长度 → 越界中断
2. 访问内存查段表（第 1 次访存），得段长 $L$ 与基址 $B$
3. 检查 $W \geq L$ → 越界中断（分段特有，分页无此步）
4. 物理地址 $= B + W$，访问内存取数据（第 2 次访存）

分段同样可引入快表（按段号并行查找）。

#4.2 段页式

先分段，段内再分页：逻辑地址 = (段号 S，段内页号 P，页内偏移 W)。每段一张页表，一张段表（段表项含：页表长度、页表起始地址）。

翻译（TLB 未命中）：查段表（1 次访存）→ 查页表（2 次）→ 访数据（3 次），共 3 次访存；TLB 命中则 1 次。逻辑地址是三维的；物理地址一维。段页式兼具两者优点：段共享/保护方便 + 页无外部碎片；代价是硬件与访存开销更大。

#4.3 分页 vs 分段对比（必背表）

易错：说"分段一维、分页二维"正好说反；说"分页有外部碎片"错；页面大小由硬件确定、程序员不可见是判断题点。

#五、虚拟内存

#5.1 局部性原理与虚拟内存的定义

局部性原理（虚拟内存可行性的理论基础）：

• 时间局部性：刚被访问的指令/数据不久后很可能再被访问（循环、反复使用的变量）
• 空间局部性：刚被访问的存储单元附近的不久后很可能被访问（顺序执行、数组遍历）

虚拟内存定义（考点口径）：基于局部性原理，程序装入时只装部分页面即可开始运行，运行中访问到不在内存的信息时由 OS 调入（请求调入）或按算法预先调入（预调入），并把暂时不用的换出——从逻辑上扩充内存容量。请求分页 = 基本分页 + 请求调页功能 + 页面置换功能。

虚拟内存的三大特征：多次性（作业分多次调入内存）、对换性（运行过程中可换入换出）、虚拟性（逻辑容量远大于物理内存）。实现方式：请求分页 / 请求分段 / 请求段页式。所需支撑：一定内存 + 大容量外存 + 页表机制 + 缺页中断机构 + 地址变换机构。

#5.2 请求分页的页表与缺页中断

页表项扩展（对比基本分页多了 4 个字段，选择题必考）：

缺页中断处理流程（完整展开，大题/选择题高频）：

1. CPU 翻译地址，查页表发现状态位 = 不在内存 → 产生缺页中断（内中断中的故障 fault），陷入内核态
2. OS 保存现场，执行缺页中断处理程序：
   1. 按页表中的外存地址找到缺页
   2. 分配内存：
      • 若内存有足够空闲页框：分配一个空闲页框
      • 若无空闲页框：执行页面置换算法选择淘汰页；
        • 淘汰页修改位 = 1 → 写回外存（慢速 I/O）
        • 淘汰页修改位 = 0 → 直接淘汰，不必写回
   3. 从外存读入缺页到分配的页框（慢速 I/O）
   4. 更新页表：页框号、状态位 = 1、访问位置 1；更新 TLB
3. 重新执行被中断的指令（缺页返回后 PC 仍指向该指令——这是"故障"类中断的语义）

缺页中断与普通 I/O 中断的区别（必背对比表）：

#5.3 页框分配与调页策略

• 驻留集：OS 分给进程的物理页框集合。大小确定两种策略：固定分配（运行中不变）/可变分配（运行中可增减）
• 最小物理块数：保证进程正常运行所需的最少页框数（与指令格式有关：单地址指令直接寻址至少 2 块，间接寻址至少 3 块——取指 1 块 + 操作数间接寻址 2 块）
• 置换策略（固定/可变分配 × 局部/全局置换，选择题高频）：
  • 固定分配局部置换：页框数不变，缺页只能从自己进程的页中淘汰
  • 可变分配全局置换：缺页时可淘汰任何进程的页（只要被淘汰页不是别的进程正在用的临界页——实际上会"偷"别的进程的页框，可能引发连锁缺页）
  • 可变分配局部置换：先在自己进程内置换，频繁缺页则 OS 增加该进程页框，缺页率过低则回收
• 调页时机：请求调页（缺页才调，及时但 I/O 次数多）/预调页（预测即将使用，一次调入若干相邻页，利用率约 50%，常用于首次调入）
• 从何处调入：系统有足够对换区 → 全部从对换区调（快）；对换区不足 → 不会被修改的文件从文件区调、可能修改的换出到对换区再调入；UNIX 方式：首次从文件区、被淘汰过的从对换区

#5.4 页面置换算法（统一引用串手推）

统一引用串（下文各置换算法全部使用，页框数 = 3；四算法单步对照动画见交互演示）：

$$7,\; 0,\; 1,\; 2,\; 0,\; 3,\; 0,\; 4,\; 2,\; 3,\; 0,\; 3,\; 2,\; 1,\; 2,\; 0,\; 1,\; 7,\; 0,\; 1$$

约定符号：F = 缺页（Fault），带框 = 淘汰替换，— = 命中。

#OPT 最佳置换（淘汰"以后最久不再使用"的页，理论最优、不可实现）

推演规则：缺页时，比较内存中各页下一次被访问的位置（再不访问视为 $\infty$），淘汰"下一次访问最远"的页。

关键步骤说明：第 4 步访问 2 时，7/0/1 的下次访问位置分别为 18/5/14，淘汰 7；第 8 步访问 4 时，2/0/3 的下次为 9/11/10，淘汰 0；第 14 步访问 1 时，2/0/3 的下次为 15/16/∞，淘汰 3；第 18 步访问 7 时，2/0/1 的下次为 ∞/19/20，淘汰 2。共 9 次缺页。

#FIFO 先进先出（淘汰最早进入内存的页）

推演规则：按进入内存的先后排队，缺页时淘汰队头。Belady 异常的载体。

淘汰次序（步号按 1 起计）：第 4 步淘 7 → 第 6 步淘 0 → 第 7 步淘 1 → 第 8 步淘 2 → 第 9 步淘 3 → 第 10 步淘 0 → 第 11 步淘 4 → 第 14 步淘 2 → 第 15 步淘 3 → 第 18 步淘 0 → 第 19 步淘 1 → 第 20 步淘 2；3 次初始装入 + 12 次淘汰 = 共 15 次缺页。注意第 7 步访问 0 又缺页——0 在第 2 步装入、虽在第 5 步刚被命中，仍因"最早装入"被淘汰：命中不改变 FIFO 队列次序，这正是它性能差的根源。

#LRU 最近最久未使用（淘汰最长时间未被访问的页）

推演规则：缺页时淘汰上次访问时间最早的页。性能接近 OPT，但硬件开销大。

关键步骤（步号按 1 起计，@n = 最近一次访问在第 n 步）：第 4 步淘 7（7@1、0@2、1@3）；第 6 步淘 1（2@4、0@5、1@3）；第 8 步淘 2（2@4、0@7、3@6）；第 9 步淘 3（4@8、0@7、3@6）；第 10 步淘 0（4@8、0@7、2@9）；第 11 步淘 4（4@8、2@9、3@10）；第 14 步淘 0（0@11、3@12、2@13）；第 16 步淘 3（1@14、3@12、2@15）；第 18 步淘 2（1@17、0@16、2@15）。每次淘汰"上次访问最久远者"。共 12 次缺页。

（提示：FIFO 与 LRU 的表格容易看串——FIFO 看"装入时间"，LRU 看"最近访问时间"；命中会刷新 LRU 的时钟、但不会改变 FIFO 的队列位置。）

#Clock 简单时钟置换（NRU 近似）

规则：所有页框组成循环队列，每项一个访问位 A。装入时 A=1，被访问（命中）时 A=1。

1. 缺页时从指针当前位置顺序扫描：
2. A=1 → 置 0，指针前移；A=0 → 淘汰该页框，装入新页（A=1），指针指向下一位置

完整手推（同一引用串，P = 指针指向的帧，括号内为 A 位）：

Clock 共 14 次缺页，介于 FIFO(15) 与 LRU(12) 之间。

#改进型 Clock（考虑修改位，考试常考"优先淘汰谁"）

每项 (访问位 A, 修改位 M)。淘汰优先级（从最优先到最后）：(0,0) → (0,1) → (1,0) → (1,1)——优先淘汰"没访问过且没修改过"的页（省一次写回外存）。

算法三步：

1. 第一轮：从指针处扫描找 (A=0, M=0)，不修改任何标志；找到即淘汰
2. 第二轮：找 (A=0, M=1)，路过时将 A 清 0；找到即淘汰
3. 若二轮失败，重复第 1 步（此时所有 A 均已为 0，必能找到）

完整手推约定：引用串同上，且第 5、10、15、19 步（访问页 0、3、2、0）为写访问（M 置 1），其余为读访问；每帧记录 (页(A,M))：

改进型 Clock 共 12 次缺页（本串下缺页数与 LRU 持平；其典型收益是缺页时优先选中未修改页，省一次写回磁盘的 I/O）。

#四算法对照总表（同一引用串，页框 3）

Belady 异常完整实例（FIFO 独有；LRU/OPT 是栈式算法，页框增加缺页必不增，不会异常）：引用串 $1,2,3,4,1,2,5,1,2,3,4,5$：

3 个页框（缺页序列逐步推演）：

3 页框 = 9 次缺页。

4 个页框：

4 页框 = 10 次缺页 > 9 次缺页——页框更多、缺页反而更多，即 Belady 异常。原因是 FIFO 的淘汰决策与访问历史无关（只看装入顺序），不是栈式算法。

#页面缓冲算法 PBA（Page Buffering）

已淘汰页先挂入空闲页链（未修改）/ 修改页链（已修改），物理页框暂不立即让出：修改页成批写回外存（合并 I/O），若短期内又被访问则直接"救回"（从链上取回，省一次磁盘读）。是 VAX/VMS 采用的实用算法，考试考概念：降低缺页处理的开销与频繁写盘。

#5.5 抖动与工作集

• 抖动（颠簸，thrashing）：刚换出的页马上又要访问（频繁缺页），进程把时间耗在页面调度上，CPU 利用率骤降。成因：驻留集太小 / 全局置换下多进程互相抢占页框 / 并发进程数过多。注意：CPU 调度器看到利用率低会误以为缺 CPU 而引入更多进程，形成恶性循环
• 工作集 $W(t, \Delta)$：时刻 $t$、窗口长度 $\Delta$ 内进程实际访问页面的集合（去重）。工作集策略：OS 跟踪各进程工作集，缺页且驻留集 < 工作集大小时才增加页框；总需求超过物理内存时挂起（换出）部分进程而不是硬挤——从根源上避免抖动
• 定性考点：工作集大小随驻留集窗口 $\Delta$ 增大而单调不减；驻留集 < 工作集 → 缺页率飙升（进入抖动区）

#5.6 缺页率与有效访问时间 EAT（多口径计算，大题高频）

缺页率：$f = \dfrac{\text{缺页次数}}{\text{页面访问总次数}}$。

口径一：基本分页、无 TLB——每次数据访问 = 2 次访存：

$EAT = 2 \times t_{\text{访存}}$

口径二：单级页表 + TLB（命中率 $\alpha$，TLB 时间 $t_T$）：

$EAT = \alpha (t_T + t_{\text{访存}}) + (1-\alpha)(t_T + 2 t_{\text{访存}})$

口径三：二级页表 + TLB（未命中时查两级页表 + 数据 = 3 次访存）：

$EAT = \alpha (t_T + t_{\text{访存}}) + (1-\alpha)(t_T + 3 t_{\text{访存}})$

口径四：含缺页（缺页率 $f$，缺页平均处理时间 $t_{\text{缺页}}$，先按口径三算出无缺页 EAT）：

$EAT = (1-f) \cdot EAT_{\text{口径三}} + f \cdot t_{\text{缺页}}$

（另一种常见简化式：$EAT = t_{\text{访存}} + f \cdot t_{\text{缺页}}$，即"命中时间 + 缺页率 × 缺页开销"，审题看题目口径。）

例题（模拟题，多口径递进）：内存访问 100ns，TLB 访问 10ns，TLB 命中率 90%，二级页表，缺页率 2%，缺页平均处理（含磁盘 I/O）5ms。求 EAT。

• 无缺页：$EAT_3 = 0.9 \times (10+100) + 0.1 \times (10+300) = 99 + 31 = 130$ ns
• 含缺页：$EAT = 0.98 \times 130 + 0.02 \times 5{,}000{,}000 = 127.4 + 100{,}000 \approx 100{,}127$ ns

结论（论述题要点）：缺页率是主导项——1 次磁盘 I/O ≈ 十万次访存；TLB 命中率提升 1% 只省几纳秒，缺页率降低 1% 却省约百万纳秒。这就是为什么置换算法追求"少缺页"重于一切。

#例题精选

例 1（模拟题） 某系统按字节编址，页面大小 1KB，进程页表：页 0→帧 5、页 1→帧 3、页 2→帧 7、页 3→帧 1。求逻辑地址 2500 的物理地址。

解：$2500 = 2 \times 1024 + 452$ → 页号 2、偏移 452（不越界）。帧号 7。物理地址 $= 7 \times 1024 + 452 = 7620$。

例 2（模拟题，真题同型） 系统采用一级页表，TLB 访问 10ns，内存访问 100ns，TLB 命中率 90%。求一次数据访问的平均时间。

解：$EAT = 0.9 \times (10 + 100) + 0.1 \times (10 + 200) = 99 + 21 = 120$ ns（单级页表未命中 = 页表 1 次 + 数据 1 次 = 2 次访存）。

例 3（模拟题） 引用串 $4,3,2,1,4,3,5,4,3,2,1,5$，页框 3。OPT 约定并列时淘汰最先装入者。求 OPT/FIFO/LRU 缺页数，并问 FIFO 在 4 页框时是否出现 Belady 异常。

解：手推得 OPT = 7（第 4 步淘汰 2，第 7 步淘汰 1，第 10 步淘汰 4，第 11 步淘汰 3）、FIFO = 9、LRU = 10；FIFO 4 页框时缺页 10 > 9，出现 Belady 异常。注意本串下 FIFO 缺页反而比 LRU 少——LRU 并非在任意引用串上都优于 FIFO，只是长期统计上更接近 OPT。完整手推见内存管理章节测第 28 题解析。

#常见坑

1. 先越界检查，后查页表/TLB：页号 ≥ 页表长度直接越界中断，不会去查 TLB
2. 页表项不存页号（页号是下标）；段表必须存段长（越界检查需要）
3. 访存次数：基本分页无 TLB 2 次；TLB 命中 1 次；二级页表未命中 3 次；段页式未命中 3 次（段表 + 页表 + 数据）。缺页时另算（还多外存 I/O）
4. FIFO 的"命中"不改变队列次序；LRU 的命中刷新访问时间——两者表格手推时最容易混
5. Belady 异常只有 FIFO（及 Clock 等非栈式算法）有；OPT/LRU 是栈式算法，页框增多缺页单调不增
6. 改进型 Clock 优先淘汰 (0,0) 不是 (1,0)，第一轮扫描不清任何位，第二轮才清 A
7. 换出时只写回修改位=1 的页；置换次数 ≠ 写回次数（计算题设陷）
8. 缺页中断是内中断（故障），重新执行当前指令；一条指令可能产生多次缺页
9. 最佳适应产生最多外部碎片（不是最坏适应）；紧凑需要动态重定位，分页无外部碎片故不需要紧凑
10. EAT 计算先看清：单级/二级、TLB 是否并行查找、缺页开销是否含"重新访问内存"——按题目给定口径列式，别背单一公式

#自测

1. （选择）动态分区分配中，产生外部碎片最多、通常需配合紧凑技术的分配算法是（最佳/首次/最坏/邻近 适应）中的哪个？
2. （选择）页面大小 4KB，逻辑地址（十六进制）0x2AF7 的页号与页内偏移分别是多少？
3. （判断）FIFO 置换算法在页框数增加时缺页次数一定减少。
4. （计算）两级页表，$t_{\text{访存}}=100$ns，$t_{\text{TLB}}=20$ns，命中率 80%，求 EAT；若缺页率 1%、缺页处理 8ms，再求 EAT。
5. （简答）缺页中断处理中，为什么淘汰"修改位 = 0"的页比"修改位 = 1"的页开销小？

#自测答案与简析

1. 最佳适应——每次切出最小满足的分区，残余碎片多而小；最坏适应反而碎片少但耗尽大分区。紧凑的前提是动态重定位（非分页连续分配才需要）。
2. 4KB = $2^{12}$ → 低 12 位为偏移：0x2AF7 → 页号 = 0x2 = 2，偏移 = 0xAF7。
3. 错。FIFO 存在 Belady 异常（见 5.4 完整实例：3 页框 9 次 → 4 页框 10 次）。OPT/LRU 无此现象（栈式算法）。
4. $EAT = 0.8 \times (20+100) + 0.2 \times (20+300) = 96 + 64 = 160$ ns；含缺页：$0.99 \times 160 + 0.01 \times 8{,}000{,}000 = 158.4 + 80{,}000 \approx 80{,}158$ ns——缺页项完全主导。
5. 修改位 = 1 的页换出时必须写回外存（一次慢速磁盘写 I/O）；修改位 = 0 的页外存中副本与内存一致，直接丢弃页框即可，零写回开销。这也是改进型 Clock 优先淘汰 (A=0,M=0) 的原因。

#小结与后续

内存管理三大主线：连续分配（简单但碎片）→ 离散化（分页消灭外部碎片、分段保留语义）→ 虚拟化（请求分页 + 置换算法，用缺页中断把内存扩充到外存）。地址翻译（页表 + TLB）与置换算法手推是本章两大题源，计算纪律（拆位、数访存、逐格填表）比理解更重要。