网硕互联帮助中心一 真题2009-46
2009-46题.（8分）请求分页管理系统中，假设某进程的页表内容如下表所示：
| 0 | 101H | 1 |
| 1 | – | 0 |
| 2 | 254H | 1 |
页面大小为 4KB，一次内存的访问时间为 100ns，一次快表（TLB）的访问时间为 10ns，处理一次缺页的平均时间为 10810^8108ns（已含更新 TLB 和页表的时间），进程的驻留集大小固定为 2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设 ① TLB初始为空；② 地址转换时先访问 TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）；③ 有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列 2362H、1565H、25A5H，请问：
1.依次访问上述三个虚地址，各需多少时间？给出计算过程。
2.基于上述访问序列，虚地址 1565H 的物理地址是多少？请说明理由。
二 题目要素解析
核心前提
关键概念
- 有效位：1 = 页面在内存，0 = 页面不在内存（缺页）；
- TLB 初始为空：第一次访问任意页号都不会命中 TLB；
- 缺页处理后需重新执行：缺页时的时间需包含 “缺页处理时间 + 重新地址转换 + 访存时间”。
| 页面大小 | 4KB = 2122^{12}212 B → 虚地址低 12 位为页内偏移，高 4 位为页号（因地址为 16 位十六进制，共 16 位） |
| 虚地址结构 | 16 位地址：高 4 位 = 页号，低 12 位 = 页内偏移 |
| 页表状态 | – 页 0：在内存，页框 101H – 页 1：不在内存（有效位=0） – 页 2：在内存，页框 254H |
| 驻留集 = 2 | 内存中最多只能有 2 个该进程的页面 |
| 当前内存页面 | 初始时：页 0 和页 2 在内存（共 2 个），符合驻留集限制 |
| TLB 初始为空 | 每次首次访问某页，TLB 必未命中 |
| 缺页处理后重试 | 缺页中断处理完，重新执行导致缺页的那条访存指令 |
三 哔哔详解
步骤 1：解析每个虚地址的页号和偏移
- 2362H → 二进制：0010 0011 0110 0010
- 高 4 位：0010 = 2 → 页号 = 2
- 低 12 位：0011 0110 0010 = 362H → 偏移
- 1565H → 0001 0101 0110 0101
- 高 4 位：0001 = 1 → 页号 = 1
- 偏移 = 565H
- 25A5H → 0010 0101 1010 0101
- 高 4 位：0010 = 2 → 页号 = 2
- 偏移 = 5A5H
✅ 页号：2 → 1 → 2
步骤 2：模拟访问过程（含 TLB、页表、缺页、LRU）
🟢 初始状态：
- 内存页面：{页0, 页2}（驻留集满）
- LRU 队列（最近使用在右）：[页0, 页2]（假设初始顺序，但第一次访问会更新）
- TLB：空
🔹 访问 1：2362H（页号 = 2）
✅ 总时间 =10ns(访问TLB) + 100ns(访问页表) + 100 ns（访问内存单元）= 210 ns
📌 注意：即使 TLB 未命中，只要页在内存，就只需一次额外内存访问（查页表）
🔹 访问 2：1565H（页号 = 1）
- 驻留集已满（2 个页面），需 LRU 淘汰
- 当前页面使用历史：页2 刚被访问（最新），页0 较旧 → 淘汰页0
- 调入页1，分配新页框（假设为 XH），更新页表：页1 → XH，有效位=1
- 更新 TLB（页1 条目）
- 查 TLB：命中（10 ns）→ 得到页框 XH
- 访问物理内存：100 ns
✅ 总时间 = 第一次：10ns(访问TLB) + 100ns(访问页表) + 10810^8108ns(调页) + 重试：10 ns（访问TLB） + 100 ns（访问内存单元）
= 10810^8108+220 ns = 100,000,220 ns
⚠️ 关键：缺页后必须重试原指令，因此有两次地址转换过程！
🔹 访问 3：25A5H（页号 = 2）
- 此时内存页面：{页1, 页2}（页0 已被淘汰）
- TLB 中已有页2（第一次访问后加入），也可能有页1（缺页后加入）
✅ 总时间 = 10ns(访问TLB) + 100 ns（访问内存单元） = 110 ns
📌 无需查页表，因 TLB 命中
步骤 3：回答问题 2 —— 1565H 的物理地址
步骤 1：分解虚地址 1565H
- 1565H = 0001 0101 0110 0101（16 位）
- 页面大小 4KB = 212212 → 低 12 位为偏移，高 4 位为页号
- 页号 = 0001 = 1
- 页内偏移 = 0101 0110 0101 = 565H
步骤 2：确定页1 的页框号
- 缺页时，LRU 淘汰页0（因其在页2 之后未被访问）；
- 页0 原占页框 101H，被淘汰后该页框空闲；
- OS 将页1 装入此空闲页框 → 页1 的页框号 = 101H
📌 注：虽然题目未明说“分配哪个页框”，但在驻留集固定、局部置换下，回收被淘汰页面的页框是标准做法。因此，101H 是页1 最可能的页框号。
步骤 3：拼接物理地址
- 物理地址 = (页框号 << 12) | 页内偏移
- = (101H << 12) | 565H
- = 101000H + 565H
- = 101565H
四 参考答案
-
2362H（页号=2）：
TLB 未命中（10 ns）→ 访问页表（100 ns）→ 访问内存（100 ns）总时间 =10ns(访问TLB) + 100ns(访问页表) + 100 ns（访问内存单元）= 210 ns
总计：210 ns
-
1565H（页号=1）：
总时间 = 第一次：10ns(访问TLB) + 100ns(访问页表) + 10810^8108ns(调页) + 重试：10 ns（访问TLB） + 100 ns（访问内存单元）
= 10810^8108+220 ns = 100,000,220 ns总计： 100,000,220 ns
-
25A5H（页号=2）：
TLB 命中（10 ns）→ 访问内存（100 ns）总时间 = 10ns(访问TLB) + 100 ns（访问内存单元） = 110 ns
总计：110 ns
-
1565H 的物理地址 是101565H；因为2号页面刚被访问，不会被置换，因此用101H页框；
五 考点精析
5.1 页式管理与请求页式管理
5.1.1 基本概念与性质
1.页式管理（Paging）—— 传统内存管理
定义：将物理内存划分为大小相等的块（页框 / 帧，Frame），将逻辑地址空间划分为与块大小相同的页（Page）。通过页表（Page Table）建立页号到页框号的映射。
核心性质：
- 连续性：物理内存可以不连续，但逻辑地址空间是连续的。
- 一次性：作业运行前，必须将全部页面装入内存（除非使用覆盖技术）。
- 驻留性：作业运行期间，全部页面一直驻留在内存中，直到作业结束。
优点：解决了内存碎片问题（外部碎片），提高了内存利用率。
缺点：存在内部碎片（最后一页可能没装满）；要求作业一次性装入，限制了大作业的运行。
2. 请求页式管理（Demand Paging）—— 虚拟内存管理
- 定义：建立在页式管理基础上的虚拟存储管理方式。它打破了 “一次性” 和 “驻留性” 的限制。
- 核心性质：
- 按需调入（Lazy Loading）：只装入当前需要的页面，作业开始运行时不需要全部装入。
- 部分装入：内存中只保留当前活跃的页面集合（工作集）。
- 虚拟性：逻辑地址空间可以远大于物理内存空间。
- 核心机制：缺页中断（Page Fault）。当访问的页面不在内存时，由操作系统将其从外存调入内存。
5.1.2 工作流程对比
1. 页式管理的地址转换流程
- 注：若页号越界，则产生越界中断。
2. 请求页式管理的地址转换流程（含缺页中断）
- 情况 A（存在位 = 1）：页面在内存。
- 将物理块号与偏移拼接，访问内存。
- （可选）更新 TLB。
- 情况 B（存在位 = 0）：页面不在内存 → 缺页中断。
- 步骤 B1（中断处理）：保存现场，转缺页中断处理程序。
- 步骤 B2（申请内存）：检查内存是否有空块。
- 若无空块，执行页面置换算法（如 LRU, FIFO, OPT），选择一个牺牲页。
- 若牺牲页被修改过（脏位 = 1），需写回外存（Swap Out）。
- 步骤 B3（调页）：从外存（Swap 区）将所需页面调入内存（Swap In）。
- 步骤 B4（更新页表）：修改页表项（物理块号、存在位 = 1、脏位 = 0）。
- 步骤 B5（重启指令）：恢复现场，重新执行导致缺页的指令。
5.1.3 区别和联系
| 所属范畴 | 传统内存管理（实存管理） | 虚拟内存管理 |
| 核心思想 | 静态离散分配 | 动态按需分配 |
| 核心目标 | 解决外部碎片，提高内存利用率 | 实现虚拟性，支持大作业在小内存中运行 |
| 页面装入方式 | 进程创建时一次性全部装入内存 | 按需调入，首次访问时才装入 |
| 驻留性 | 所有页面必须全程驻留内存 | 页面可动态换入/换出，非活跃页可调出 |
| 内存需求 | ≥ 进程总大小 | 可 < 进程总大小（仅需驻留集） |
| 是否支持虚拟存储 | ❌ 不支持 | ✅ 支持 |
| 硬件支持 | MMU、页表、地址映射机构 | 页表（含有效位/存在位、修改位、访问位）、缺页中断机制、TLB |
| 中断类型 | 仅越界中断（地址非法） | 越界中断 + 缺页中断（页面不在内存） |
| 系统开销 | 较低（仅地址转换，无磁盘 I/O） | 较高（缺页时需磁盘 I/O，可能引发抖动） |
| 内存利用率 | 较高（无外部碎片） | 极高（内存中仅保留活跃页面） |
| 碎片问题 | 存在内部碎片（页内未用空间） | 同样存在内部碎片 |
| 是否需要置换算法 | ❌ 不需要 | ✅ 需要（如 FIFO、LRU、Clock） |
| 关系 | 基础模型 | 请求页式 = 页式 + 虚拟存储 + 缺页机制 + 页面置换 |
5.2 常见页面置换算法
5.2.1 基本概念
| OPT | 最佳置换算法（Optimal） | 淘汰未来最久不会被使用的页面 | 需预知未来访问序列（理论算法） | ❌（不可实现） |
| FIFO | 先进先出算法（First-In-First-Out） | 淘汰最早装入内存的页面 | 队列记录页面装入顺序 | ❌ |
| LRU | 最近最少使用算法（Least Recently Used） | 淘汰最近最久未使用的页面 | 链表/栈/计数器记录访问时间 | ✅（需访问位或时间戳） |
| Clock | 时钟置换算法（Clock / NRU） | FIFO 的改进，引入使用位（Reference Bit）避免淘汰活跃页 | 循环链表 + 使用位（R 位） | ✅（需 R 位） |
5.2.2 综合对比
| 核心依据 | 未来使用时间（淘汰最久不用的） | 页面装入内存的时间 | 最近一次使用的时间 | 使用位（R 位）+ 循环扫描顺序 |
| 预见性 | 预知未来（“上帝视角”） | 仅记录进入顺序 | 基于历史访问行为 | 近似历史行为（1 位使用信息） |
| 是否可实现 | ❌ 不可实现（理论模型） | ✅ 可实现 | ✅ 可实现（精确 LRU 需硬件；常用近似） | ✅ 可实现 |
| 缺页率 | 最低（理论下限） | 较高（可能严重） | 接近 OPT | 介于 FIFO 与 LRU 之间 |
| Belady 异常 | 无 | ✅ 存在（主要缺陷） | 无 | 无 |
| 硬件支持需求 | —— | 无 | 需访问时间记录或栈结构（通常需 MMU 支持） | 需 使用位（Reference Bit, R 位） |
| 实现难度 | 不可能 | 最简单（队列即可） | 较难（维护访问顺序开销大） | 简单（循环指针 + R 位） |
| 系统开销 | —— | 极低 | 高（每次访问需更新时间/栈） | 低（仅缺页时扫描并清 R 位） |
| 典型应用场景 | 性能评估基准 | 早期简单系统 | 高性能系统目标（如 Linux 尝试近似） | 现代操作系统广泛采用（如 Clock、Enhanced Clock） |
六 考点跟踪
| 2009 | 第46题 | 请求页式管理 | |||
| 2010 | 第46题 | 页面置换算法 | |||
| 2011 | 第28题 | 请求页式管理 | |||
| 2012 | 第45题 | 请求页式管理 | |||
| 2013 | 第30题 | 请求页式管理 | |||
| 2017 | 第45题 | 请求页式管理 | |||
| 2018 | 第45题 | 请求页式管理、页面置换算法 | |||
| 2020 | 第46题 | 请求页式管理 | |||
| 2021 | 第28题 | 页面置换算法 | |||
| 2022 | 第29题 | 请求页式管理 | |||
| 2024 | 第45题 | 请求页式管理 |
说明：本文内容基于公开资料整理，参考了包括但不限于《数据结构》（严蔚敏）、《计算机操作系统》（汤小丹）、《计算机网络》（谢希仁）、《计算机组成原理》（唐朔飞）等国内高校经典教材，以及其他国际权威著作。同时，借鉴了王道、天勤、启航等机构出版的计算机专业考研辅导系列丛书中的知识体系框架与典型题型分析思路。文中所有观点、例题解析及文字表述均为作者结合自身理解进行的归纳与重述，未直接复制任何出版物原文。内容仅用于学习交流，若有引用不当或疏漏之处，敬请指正。
评论前必须登录！
注册