操作系统章节测 02:内存管理
覆盖《内存管理》一章(教材:内存管理),共 30 题(第 1-25 题为单项选择,第 26-30 题为综合计算大题),全部为模拟题。限时 90 分钟,先做后看答案。做错的题请登记到 错题本。地址翻译与 TLB/Cache 相关背景可对照存储器层次结构复习。
选择题
第 1 题 程序装入内存后,若要求它在内存中可以被整体移动(例如紧凑时),还可以被换出到外存、之后换入到另一个内存位置继续运行,则该程序必须采用( )。 A. 绝对装入 B. 可重定位装入 C. 动态运行时装入 D. 静态链接
第 2 题 某系统采用重定位寄存器与界地址寄存器实现内存保护,下列说法正确的是( )。 A. 两个寄存器均可由用户进程直接读写 B. 界地址寄存器存放进程物理地址上界,用物理地址与其比较判断越界 C. 界地址寄存器存放进程逻辑地址空间长度,逻辑地址先与其比较;重定位寄存器存放进程在内存的物理起始地址;二者只能由操作系统在内核态修改 D. 重定位寄存器存放页表长度,用于页号越界检查
第 3 题 关于覆盖与交换技术,下列说法正确的是( )。 A. 交换以进程为单位,将暂时不能运行的进程整体换出到外存对换区 B. 覆盖技术由操作系统自动管理,对程序员完全透明 C. 交换技术只能与固定分区分配配合使用 D. 被交换出内存的进程必须等其终止后才能重新换入
第 4 题 关于固定分区分配与动态分区分配的碎片,下列说法正确的是( )。 A. 固定分区有外部碎片、无内部碎片;动态分区相反 B. 固定分区有内部碎片;动态分区有外部碎片 C. 两者都既有内部碎片又有外部碎片 D. 两者都只有内部碎片
第 5 题 动态分区分配,空闲分区按地址递增排列依次为 100KB、500KB、200KB、300KB、600KB,进程请求 130KB。采用首次适应算法,选中( )。 A. 100KB 分区 B. 500KB 分区 C. 200KB 分区 D. 600KB 分区
第 6 题 沿用第 5 题的空闲分区表。最佳适应算法先处理 130KB 请求(选中 200KB 分区、剩余 70KB),随后又来一个 90KB 请求。关于最佳适应算法,下列评价正确的是( )。 A. 每次都使用最大分区,大分区被迅速耗尽 B. 优先选最小满足分区,会不断残留过小的空闲分区,外部碎片最多 C. 从链头顺序查找,查找开销是四种算法中最大的 D. 必须按容量排序空闲链,因此无法进行分区回收
第 7 题 关于紧凑(拼接)技术,下列说法正确的是( )。 A. 紧凑可以消除分页存储管理的内部碎片 B. 紧凑要求程序采用动态重定位(动态运行时装入)方式装入 C. 紧凑可以在进程正在运行时随时进行 D. 紧凑将各进程已分配分区内部的空间拼接为一个大分区
第 8 题 某分页系统页面大小为 2KB,按字节编址。逻辑地址 4116 的页号与页内偏移分别是( )。 A. 1,2012 B. 2,20 C. 2,1020 D. 1,4116
第 9 题 关于请求分页存储管理的页表项,下列说法正确的是( )。 A. 页表项中必须显式存放本项对应的页号 B. 页表项在页框号之外还包含状态位、访问字段、修改位、外存地址 C. 修改位为 1 表示该页必须常驻内存、不可淘汰 D. 访问字段用于地址变换时的越界检查
第 10 题 某基本分页存储管理系统未引入快表,CPU 从内存取一个操作数,共需访问内存( )次。 A. 1 B. 2 C. 3 D. 4
第 11 题 单级页表系统引入 TLB,TLB 访问 10ns,内存访问 100ns,TLB 命中率 90%。一次数据访问的平均有效访问时间为( )。 A. 110ns B. 120ns C. 140ns D. 210ns
第 12 题 逻辑地址 32 位、页面 4KB、页表项 4B、采用二级页表。一级页号(页目录索引)占( )位。 A. 8 B. 10 C. 12 D. 20
第 13 题 采用两级页表的原因,不正确的是( )。 A. 单级页表过大且要求连续存放,与离散分配思想矛盾 B. 依据局部性原理,暂时用不到的页表项所在页表页可不安置在内存 C. 两级页表减少了地址变换的访存次数 D. 使页表本身也能离散地存放在不连续的页框中
第 14 题 分段系统中,某逻辑地址的段号为 2、段内偏移为 500,段表中段 2 的段长为 400。地址变换机构将( )。 A. 直接用段 2 的基址加 500 形成物理地址 B. 产生越界中断 C. 动态扩展段 2 的长度后继续访问 D. 陷入缺页中断,从外存调入该段
第 15 题 关于分页与分段的对比,错误的是( )。 A. 分页地址空间是一维的,分段地址空间是二维的 B. 页面大小固定由硬件决定,段的长度不定由程序逻辑决定 C. 分页便于实现信息共享与保护,分段反而不便于共享 D. 分页有内部碎片无外部碎片,分段有外部碎片无内部碎片
第 16 题 段页式存储管理系统中,快表未命中时,访问内存中的一个数据共需访问内存( )次。 A. 1 B. 2 C. 3 D. 4
第 17 题 关于虚拟内存,下列说法正确的是( )。 A. 虚拟内存的最大容量只受外存容量限制,可以无限大 B. 虚拟内存基于局部性原理,允许作业分多次调入内存运行 C. 虚拟内存要求作业运行前一次性全部装入内存 D. 虚拟性是指物理内存条真实容量被扩大了
第 18 题 请求分页的缺页中断处理中,若按置换算法选中的淘汰页修改位为 1,正确的处理是( )。 A. 直接用缺页覆盖该页框,无需其他操作 B. 先将该页写回外存,再从外存读入缺页到该页框 C. 不写回外存,直接丢弃后读入缺页 D. 挂起当前进程,等待外存空闲
第 19 题 缺页中断与普通 I/O 中断的区别,错误的是( )。 A. 缺页中断在指令执行期间产生,普通外中断在指令执行结束后响应 B. 一条指令的执行过程中可能产生多次缺页中断 C. 缺页中断处理完成后重新执行被中断的那条指令 D. 缺页中断处理完成后返回执行被中断指令的下一条指令
第 20 题 缺页中断属于( )。 A. 外中断 B. 内中断中的故障(fault) C. 内中断中的自愿陷入(trap) D. 内中断中的终止(abort)
第 21 题 进程运行期间页框数固定不变,缺页时只能从该进程自己的页面中选择淘汰页,这种策略是( )。 A. 固定分配局部置换 B. 可变分配全局置换 C. 可变分配局部置换 D. 固定分配全局置换
第 22 题 关于 Belady 异常,下列说法正确的是( )。 A. OPT 与 LRU 都可能出现 Belady 异常 B. 只有 LRU 会出现 Belady 异常 C. FIFO 可能出现 Belady 异常,原因是它不是栈式算法 D. 只要增加页框数,任何算法的缺页次数都必然减少
第 23 题 改进型 Clock 置换算法中,第一轮扫描寻找的页面及对标志位的处理是( )。 A. 寻找 (访问位=0, 修改位=0) 的页面,且扫描过程中不修改任何标志位 B. 寻找 (访问位=0, 修改位=1) 的页面,并将路过页面的访问位清 0 C. 寻找 (访问位=1, 修改位=0) 的页面,并清 0 访问位 D. 寻找 (访问位=0, 修改位=0) 的页面,同时将修改位清 0
第 24 题 关于抖动(颠簸),下列说法正确的是( )。 A. 抖动由驻留集过大引起 B. 抖动指页面频繁换入换出,进程把时间耗在页面调度上、CPU 利用率骤降 C. 出现抖动时应引入更多并发进程以提高利用率 D. 抖动与页面置换算法和内存分配量无关
第 25 题 工作集 的准确定义是( )。 A. 进程当前已调入内存的全部页面集合 B. 在时刻 之前的 次页面访问所涉及页面的集合(去重) C. 进程页表中登记的全部页面集合 D. 操作系统分配给进程的全部页框集合
综合计算大题
第 26 题(动态分区分配与回收) 某系统采用动态分区分配,某一时刻空闲分区按地址递增排列为:F1=100KB、F2=500KB、F3=200KB、F4=300KB、F5=600KB。
(1) 进程 P1 请求 130KB,分别给出首次适应、最佳适应、最坏适应算法选中的分区及分配后该分区的剩余量; (2) 在最佳适应完成 (1) 的分配后,进程 P2 请求 90KB,最佳适应选中哪个分区?分配后剩余多少?这暴露了最佳适应的什么问题? (3) 在 (1)(2) 完成后,P1 结束并释放其 130KB 分区。该回收区与其空闲前邻分区如何合并?合并后空闲分区的大小与起始地址如何表述(设 P1 分区起始地址为 S)?
第 27 题(地址翻译全流程) 某请求分页系统按字节编址,页面大小 4KB,采用单级页表。某进程页表长度为 5 页(页 0~4),页表内容:页 0→帧 2、页 1→帧 5、页 2→帧 3、页 3→帧 7、页 4→帧 1;TLB 中当前缓存两条:页 1→帧 5、页 4→帧 1。TLB 与页表均按页号精确匹配。对下列逻辑地址(十六进制),逐个给出:页号与页内偏移的拆分、查 TLB 命中与否、最终物理地址(或异常)、访问数据所需的内存访问次数(TLB 查询不计入内存访问次数)。
(1) 0x2AF8;(2) 0x1FFF;(3) 0x4123;(4) 0x5234
(5) 若该系统改为二级页表且 TLB 未命中、无缺页,访问一次数据需几次内存访问?若 TLB 命中呢?
第 28 题(页面置换算法手推) 引用串为 ,分配 3 个页框,初始为空。OPT 约定:多个页面并列"最久不再使用"时淘汰最先装入者。
(1) 给出 LRU 的完整逐格手推表(每步给出驻留页与是否缺页),统计缺页次数; (2) 直接给出 OPT 与 FIFO 的缺页次数,并给出两者的淘汰页序列; (3) 改为 4 个页框,FIFO 的缺页次数是多少?与 3 个页框比较说明什么现象?该现象为什么只发生在 FIFO(及 Clock 类)而不发生在 LRU/OPT 上? (4) 本串下 FIFO(3 页框)与 LRU 谁缺页更少?这说明什么?
第 29 题(有效访问时间多口径) 某页式系统:内存访问一次 100ns,TLB 访问一次 20ns,TLB 命中率 90%,先查 TLB 后访存。
(1) 单级页表、无缺页时,一次数据访问的 EAT; (2) 二级页表、无缺页时,一次数据访问的 EAT; (3) 在 (2) 的基础上,缺页率 5%,每次缺页平均处理时间 10ms(含磁盘 I/O 与现场处理,处理完重新执行指令),EAT 是多少? (4) 仍基于 (2),若要求 EAT 不超过 200ns,缺页率 f 至少要控制在多少以下?由此说明工程上最优先优化什么。
第 30 题(二级页表结构计算) 某系统逻辑地址 32 位、按字节编址、页面大小 4KB、每个页表项 4B,采用二级页表(页目录 + 页表页)。
(1) 页内偏移占多少位?进程最大页数是多少? (2) 若用单级页表,一个进程的页表共多少字节?为什么不可接受? (3) 一页能容纳多少个页表项?由此二级页号占多少位、一级页号占多少位? (4) 页目录本身最多多少项、共占多少内存?
参考答案与解析
第 1 题:C 考点标签:程序装入与链接|难度:易|错因提醒:误选 B"可重定位装入"——它只在装入时一次性完成地址变换,装入后不能再移动。
第 2 题:C 考点标签:内存保护|难度:中|错因提醒:保护检查用的是逻辑地址与界地址寄存器比较,不是物理地址;两寄存器只能内核态修改(A 违反特权指令规则)。
第 3 题:A 考点标签:内存扩充(覆盖/交换)|难度:易|错因提醒:覆盖由程序员声明固定区与覆盖区、对程序员不透明(B 反);换出的进程在内存空闲时可重新换入(D 反)。
第 4 题:B 考点标签:连续分配碎片|难度:易|错因提醒:固定分区"分区内用不满"是内部碎片;动态分区"分区都分得刚好,但小空隙无人能用"是外部碎片。注意分页同属"有内部碎片"阵营。
第 5 题:B 考点标签:动态分区分配算法|难度:易|错因提醒:首次适应从地址最小端起找第一个满足者:100KB < 130KB 不满足,选中 500KB。别与最佳适应(选 200KB)混淆。
第 6 题:B 考点标签:最佳适应与外部碎片|难度:中|错因提醒:90KB 请求会切分 100KB 分区、剩 10KB 的"无用小分区"——最佳适应每次都留最小残余,外部碎片最多。选 A 是最坏适应的特征。
第 7 题:B 考点标签:紧凑技术|难度:易|错因提醒:紧凑拼接的是空闲分区(外部碎片),与内部碎片无关(A、D 错);能移动的前提是地址变换在运行时进行,即动态重定位。
第 8 题:B 考点标签:地址拆分|难度:易|错因提醒:,。做此题别用"除以页数",是除以页面大小取商与余数。
第 9 题:B 考点标签:请求分页页表机制|难度:中|错因提醒:页号是页表项的下标、不显式存放(A 错);访问字段供置换算法参考而非越界检查(D 错);修改位只影响淘汰时是否写回(C 错)。
第 10 题:B 考点标签:基本地址变换机构|难度:易|错因提醒:1 次查页表 + 1 次取数据 = 2 次访存。这是引入 TLB 与多级页表后所有访存计数题的基准。
第 11 题:B 考点标签:有效访问时间|难度:中|错因提醒:ns。未命中路径是"TLB + 页表 + 数据"三段时间;误把未命中算成 会得 110ns。
第 12 题:B 考点标签:二级页表地址结构|难度:中|错因提醒:偏移 12 位;每页容纳 项 → 二级页号 10 位;一级页号 位。常见错误是拿 再对半分前忘了"每页项数"这一步的依据。
第 13 题:C 考点标签:多级页表动机|难度:中|错因提醒:两级页表在 TLB 未命中时增加一次访存(页目录 + 页表 + 数据 = 3 次)。多级页表省的是"页表连续存放的内存",不是访存时间。
第 14 题:B 考点标签:分段越界检查|难度:易|错因提醒:分段特有"段内偏移 ≥ 段长 → 越界中断"这一步(分页因页面等长无需此检查)。缺页中断的前提是该段已在段表登记但不在内存,与越界是两类事件。
第 15 题:C 考点标签:分页 vs 分段对比|难度:中|错因提醒:说反了——分段的段是完整逻辑单位(代码段/数据段),按段共享与保护才方便;分页共享要以页集合为单位,粒度不自然。
第 16 题:C 考点标签:段页式地址变换|难度:中|错因提醒:查段表(1)→ 查页表(2)→ 取数据(3)= 3 次;快表命中则 1 次。注意"段表 + 页表"不要漏算其中一级。
第 17 题:B 考点标签:虚拟内存概念|难度:易|错因提醒:虚拟内存最大容量同时受外存容量与逻辑地址位数限制,不是无限大(A 错);"一次性全部装入"恰是传统管理的特征(C 错)。
第 18 题:B 考点标签:缺页中断处理流程|难度:易|错因提醒:修改位=1 → 内存与外存副本不一致 → 必须先写回。换出脏页与干净页的开销差一次磁盘写 I/O,这是计算题设陷点(置换次数 ≠ 写回次数)。
第 19 题:D 考点标签:缺页中断与普通中断区别|难度:中|错因提醒:缺页属"故障",处理完重新执行本条指令(读写操作数尚未完成);普通中断返回的是下一条指令。"重新执行"正是 fault 类中断的语义。
第 20 题:B 考点标签:中断分类(与概述章交叉)|难度:易|错因提醒:缺页由指令执行引发、与 CPU 外部事件无关,属内中断中的故障;自愿陷入是 trap(系统调用),终止是 abort(如非法指令)。
第 21 题:A 考点标签:页框分配与置换策略|难度:中|错因提醒:三种组合按"页框数变不变 × 淘汰范围是自己还是全局"两维记忆。"可变分配全局置换"会偷别的进程的页框、可能引发连锁缺页。
第 22 题:C 考点标签:Belady 异常|难度:中|错因提醒:LRU/OPT 是栈式算法(k 页框的驻留页集合恒为 k+1 页框的子集),页框增多缺页单调不增;FIFO 的淘汰只看装入顺序、与访问历史无关,故可能出现异常。
第 23 题:A 考点标签:改进型 Clock|难度:中|错因提醒:三轮规则——①找 (0,0) 且不动任何标志位;②找 (0,1) 且路过清 A;③重复①。第一轮就清 A 是 Clock 与改进型最常被混的细节。
第 24 题:B 考点标签:抖动|难度:易|错因提醒:抖动 = 驻留集太小(小于工作集)导致频繁缺页;调度器看到 CPU 利用率低反而引入更多进程会加剧抖动(C 恰是恶性循环);对策是降低多道度/按工作集分配页框。
第 25 题:B 考点标签:工作集|难度:中|错因提醒:工作集是窗口内实际访问过的页面集合(去重),不是"已分配的页框"(D)也不是"页表登记的页"(C)。驻留集 < 工作集是缺页率飙升的先兆。
第 26 题解析 考点标签:动态分区分配与回收|难度:中|错因提醒:三个算法结果必须分别推,别凭印象写同一个。
(1) 130KB 请求:
- 首次适应:F1(100KB) 不满足 → 选中 F2(500KB),剩余 370KB
- 最佳适应:最小满足者是 F3(200KB),剩余 70KB
- 最坏适应:最大者 F5(600KB),剩余 470KB
(2) 此时空闲为 F1=100KB、F2=370KB、F3'=70KB、F4=300KB、F5=470KB(按地址递增)。最佳适应选最小满足者 F1(100KB),剩余 10KB——暴露的问题:最佳适应优先选最小满足分区,会不断产生 10KB 这类难以再利用的小空闲分区,外部碎片最多。
(3) P1 的 130KB 回收区与低地址侧的空闲前邻 70KB 合并为一个 200KB 空闲分区:起始地址不变(仍为该 70KB 空闲分区的起始地址,即 S−70KB),大小 = 70+130 = 200KB;空闲链上不新增结点,只更新大小。(若后邻也空闲则三块合一并删一个结点;本题只有前邻。)
第 27 题解析 考点标签:地址翻译全流程(TLB/页表)|难度:难|错因提醒:拆分必须按 12 位二进制低位取偏移;越界判断在查 TLB 之前。
(5) 二级页表、TLB 未命中:页目录 1 次 + 页表页 1 次 + 数据 1 次 = 3 次;TLB 命中:1 次。这正是教材 EAT 公式中 的来源。
第 28 题解析 考点标签:页面置换算法手推|难度:难|错因提醒:LRU 命中会刷新时间、FIFO 命中不改变队列次序;OPT 要逐页看"下一次访问位置"而不是"上次"。
(1) LRU 手推表(F=缺页,括号内为最近一次访问的步号):
关键淘汰:第 4 步淘 4(1@1 最久);第 5 步淘 3;第 6 步淘 2;第 7 步淘 1;第 10 步淘 5(5@7 早于 4@8、3@9);第 11 步淘 4;第 12 步淘 3。LRU 缺页 = 10 次。
(2) OPT:淘汰序列为 第 4 步淘 2(4/3/2 的下次为 5/6/10)、第 7 步淘 1(4/3/1 的下次为 8/9/11)、第 10 步淘 4(4、3 并列不再使用,淘汰最先装入的 4)、第 11 步淘 3(2、3 并列,3 更早装入),OPT = 7 次。FIFO:淘汰序列为 4→3→2→1→4→3(第 4、5、6、7、10、11 步),第 12 步访问 5 命中,FIFO = 9 次。
(3) 4 个页框的 FIFO:初始装入 4、3、2、1(4 次缺页,第 5、6 步命中),此后第 7 步淘 4、第 8 步淘 3、第 9 步淘 2、第 10 步淘 1、第 11 步淘 5、第 12 步淘 4,共 4+6 = 10 次缺页 > 9 次——Belady 异常:页框更多缺页反而更多。LRU/OPT 是栈式算法(k 页框驻留集恒含于 k+1 页框驻留集),缺页次数随页框数单调不增,故不会出现该异常;FIFO 的淘汰只看装入顺序、与访问历史无关,不是栈式算法。
(4) 本串下 FIFO(9 次)反而少于 LRU(10 次)。说明 LRU 并非在任意引用串上都最优,它只在长期统计意义上更接近 OPT;单串比较不能推翻算法的平均性能排序。
第 29 题解析 考点标签:有效访问时间计算|难度:难|错因提醒:先分清单级/二级决定未命中路径的访存次数(2 次还是 3 次);含缺页时用"无缺页 EAT + 缺页项"加权。
(1) 单级:
(2) 二级(未命中 3 次访存):
(3)
(4) (百万分之五量级)。结论:EAT 的主导项是缺页率——TLB 命中率再提高几个百分点只省几纳秒,而缺页率从 5% 降到百万分之五才能把 EAT 拉回 200ns 以内。工程上最优先优化的是减少缺页(更大的驻留集、更好的局部性/置换算法),其次才是 TLB。
第 30 题解析 考点标签:二级页表结构计算|难度:中|错因提醒:页大小 4KB → 偏移 12 位这一步是所有后续位的来源;"每页容纳多少页表项"用页大小除以页表项大小。
(1) 偏移 位;最大页数 页(1M 页)。
(2) 单级页表: 项 × 4B = 4MB,且因按页号索引而要求连续存放——每个进程都要 4MB 连续内存常驻,与分页"离散分配"的初衷矛盾。
(3) 一页容纳 项 → 二级页号 10 位;一级页号 位。
(4) 页目录 项 × 4B = 4KB,恰好占一页——页目录自身只需一个页框,这正是两级页表"用一页管一千页表页、再由一千页表页管全部数据页"的杠杆结构。