操作系统第三章:内存管理
依据所给 17 份讲义整理。记号约定:除特别说明外,按字节编址;页面大小记为 L,逻辑地址记为 A,页号为 P,页内偏移为 W,物理块号为 b。1 KiB=2^10 B、1 MiB=2^20 B;讲义中的 KB、MB 在计算题里通常按此二进制含义使用。
一、先建立全章框架
| 核心问题 | 对应知识 |
|---|---|
| 程序放哪里、地址怎么变 | 装入与链接、逻辑地址和物理地址、重定位、地址保护 |
| 内存如何分给进程 | 连续分配、动态分区算法、分页、分段、段页式 |
| 内存不够怎么办 | 覆盖、交换、虚拟内存、请求分页、页面置换、页面分配策略 |
| 怎样提高速度或方便共享 | 快表 TLB、多级页表、局部性、内存映射文件 |
主线:连续分配容易产生外部碎片;分页以固定大小的页框实现离散分配;分段按程序的逻辑模块划分;段页式兼顾逻辑模块和离散分配;请求分页进一步允许“部分页面在内存”,形成虚拟内存。
二、内存基础、地址与进程内存映像
1. 编址、地址空间与保护
- 内存由可编址的存储单元组成。按字节编址时,每个地址对应 1 B;按字编址时,对应 1 个字,必须结合字长换算容量。若有
N个可编址单元,至少需要ceil(log2 N)位地址。例如 4 GiB、按字节编址,需 32 位物理地址。 - 逻辑地址由程序使用,描述进程自身地址空间中的位置;物理地址是实际内存单元地址。地址转换或重定位将前者映射到后者。
- 内存管理的四项任务:内存空间分配与回收、从逻辑上扩充内存、地址转换、内存保护。
- 连续分配时可用上下限寄存器直接检查物理地址,也可用基址(重定位)寄存器 + 界限(限长)寄存器:先检验逻辑地址在合法范围内,再加基址。考试要留意题目把“界限”定义为长度还是最大合法偏移:若是长度,合法条件
0≤A<长度;若是最大偏移,合法条件0≤A≤最大偏移。
2. 从源程序到运行
源程序 → 编译成目标模块 → 链接成装入模块 → 装入内存运行。
| 装入方式 | 地址何时确定 | 特点 |
|---|---|---|
| 绝对装入 | 编译时形成绝对地址 | 适合已知固定装入位置的简单环境 |
| 可重定位装入/静态重定位 | 装入时一次性把逻辑地址改为物理地址 | 运行中一般不能移动;讲义所述模型要求装入时分配所需空间 |
| 动态运行时装入/动态重定位 | 执行指令、访问地址时转换 | 依赖重定位硬件;允许运行中移动,便于动态管理 |
链接方式:静态链接在运行前连接全部目标模块与所需库;装入时动态链接在装入时边装入边链接;运行时动态链接在执行中需要某模块时才链接。不要把“动态链接”和“动态重定位”混为一谈:前者解决模块何时组合,后者解决地址何时转换。
3. 进程内存映像
典型布局从低地址到高地址可理解为:代码/只读数据 → 可读写数据 → 堆 →(空闲虚拟地址区)→ 栈 → 内核地址区。代码段含指令和只读常量;数据段含全局变量、静态变量;堆用于动态分配;栈保存函数调用信息、参数与局部变量。堆通常向高地址增长,栈通常向低地址增长。

4. 覆盖与交换(选修)
- 覆盖:同一程序中不会同时使用的模块共享覆盖区;常用模块常驻固定区。需要程序员设计覆盖关系,历史意义较大。
- 交换:内存紧张时把整个进程暂时换出到外存,之后再换入;被换出的进程处于挂起态,可细分为就绪挂起、阻塞挂起。选择换入对象涉及中级调度。PCB 仍保留在内存供系统管理。
- 区分:覆盖针对同一进程的模块,交换针对进程,请求分页的换入换出针对页面。
三、连续分配与动态分区算法
1. 三种连续分配
| 方式 | 分配规则 | 碎片与局限 |
|---|---|---|
| 单一连续分配 | 内存分系统区、用户区;用户区只放一道程序 | 无外部碎片,可能有较多内部碎片;并发度低 |
| 固定分区分配 | 预先划分若干固定分区,每区最多一道作业 | 无外部碎片;进程小于分区时有内部碎片,大进程可能无可用分区 |
| 动态分区分配 | 进程到来时按其大小建立分区 | 在讲义模型中通常无内部碎片,但会形成外部碎片 |
内部碎片在已分配区域内部,不能再分给别的进程;外部碎片是各个已分配区域之间零散的空闲空间。动态分区回收时,必须和前、后相邻的空闲区合并。若总空闲空间足够但没有一块连续空间满足请求,可通过紧凑移动进程合并空闲空间;紧凑需要可用的动态重定位支持,并有移动开销。
2. 动态分区分配算法
假定空闲区依次为:(起始地址, 大小) = (0,10)、(20,30)、(60,20),请求 18 单位。
| 算法 | 查找规则 | 本例选中 | 常见影响 |
|---|---|---|---|
| 首次适应 FF | 按地址递增,从头找第一块够大的 | (20,30) | 实现简单,低地址易产生小空闲区;讲义综合评价较好 |
| 最佳适应 BF | 找满足需求的最小空闲块 | (60,20) | 保留大块,但常留下难以利用的小碎片 |
| 最坏/最大适应 WF | 找最大的空闲块 | (20,30) | 减少特别小的剩余块,但大块消耗较快 |
| 邻近适应 NF | 按地址循环,从上次查找结束处继续 | 取决于上次位置 | 减少从头扫描,但可能更快用掉高地址的大块 |
考试做题时先确定空闲分区的排序规则、起点、是否循环、并列时的选择规则,再逐次更新空闲分区表。分配后可能将一个空闲区拆成“已分配区 + 剩余空闲区”;回收时判断前邻、后邻、双邻或无邻四种情况。

四、基本分页存储管理
1. 页、页框与页表
- 将进程的逻辑地址空间分为大小相同的页;将物理内存分为同样大小的页框/页帧/物理块。进程各页可放在不相邻的页框里。
- 每个进程有自己的页表。页表项至少记录“该页所在的物理块号”;顺序存放的页表项,其页号可以由位置隐含,不一定需要单独存储。
- 分页不产生外部碎片,但进程最后一页往往未填满,会产生内部碎片。页越大,页表项数越少,但页内浪费可能越大;页越小则相反。
- 若物理内存
M字节,页大小L字节,则页框数M/L;物理块号至少需ceil(log2(M/L))位。页表项的实际字节数还要考虑状态位、权限、对齐等,不能机械地等同于块号位数向上取整。
2. 地址结构与换算
P = floor(A/L),W = A mod L;查页表得物理块号 b;物理地址 E=b×L+W。
若 L=2^k,低 k 位是页内偏移,高位是页号;物理地址也可视为“物理块号的二进制 + 页内偏移的二进制”。例如 32 位逻辑地址、4 KiB 页:页内偏移 12 位,页号 20 位;最多可表示 2^20 个虚拟页。若题目页大小不是 2 的幂,仍按整除和取余计算,不能强行按位切割。
计算例:页大小 1 KiB,逻辑地址 2500,页号 floor(2500/1024)=2,页内偏移 2500 mod 1024=452。若第 2 页映射到第 8 块,则物理地址 8×1024+452=8644。
3. 基本地址变换机构
页表寄存器 PTR 保存页表始址 F 和页表长度 m。对逻辑地址 A:
- 算
P、W;若P≥m,页号越界。 - 计算页表项位置
F+P×页表项长度,读出物理块号b。 - 计算
E=b×L+W,访问目标单元。

注意区分:页表长度是表项个数;页表项长度是每项占多少字节;页面大小是每页容量。若页表存放方式或表项对齐方式有特殊规定,计算表项位置须依题目条件。没有 TLB、也不计缺页时,查内存页表一次、访问数据一次,共 2 次访存。
4. 快表 TLB
TLB 是保存近期页表项副本的高速缓存。命中时直接得到块号,随后访问目标内存,通常按 1 次主存访问计;未命中时先查主存页表,再访问目标内存,通常按 2 次主存访问计。TLB 查找本身的时间要按题目是否计入处理。

设 TLB 查找时间 t、一次主存访问时间 T、命中率 h。若先查 TLB,未命中才查页表,平均时间为 h(t+T)+(1−h)(t+2T)。例如 t=1 μs、T=100 μs、h=0.9,结果 111 μs。若题目说明快表与慢表并行查找,则未命中路径可按 2T 计算,例中得到 110.9 μs。有数据 Cache、缺页开销或访存流水等条件时须重新建模。
5. 两级与多级页表
单级页表可能过大,且需要大量连续位置存放。把页表分成多个页,再用页目录表记录各二级页表的位置,可让页表离散存储,并按需建立/调入下级页表。
经典例:32 位逻辑地址、4 KiB 页、页表项 4 B。页内偏移 12 位,页号共 20 位;每页能放 4096/4=1024=2^10 项,因此地址划分为 10 位页目录号 + 10 位二级页号 + 12 位偏移。无 TLB 且所需页表均在内存时,访问页目录、二级页表、目标数据,共 3 次主存访问。一般 n 级页表需 n+1 次主存访问。

多级页表计算:页内偏移位数 k=log2 L;每页容纳的页表项数 q=L/页表项大小;每级最多索引 log2 q 位页号。40 位逻辑地址、4 KiB 页、4 B 表项:页号 28 位,每级最多 10 位,因此至少三级,可分成 8+10+10+12 位。
五、分段与段页式
1. 基本分段
按程序的逻辑模块划分长度可变的段,如主程序段、函数段、数据段。逻辑地址为**(段号 S,段内偏移 W);各段可离散放置,但每个段内部要连续。段表项记录段长 C和物理基址 B**。
地址转换:先检查 S<段表长度;再检查 W<C;最后计算物理地址 E=B+W。两个检查都是关键:页式通常检查页号是否合法,段式还要检查段内偏移是否越界。若段号、段内偏移分别占 s、w 位,则最多 2^s 段,每段可表示 2^w 个按编址单位计的地址;实际段长可以更短。

| 对比 | 分页 | 分段 |
|---|---|---|
| 划分依据 | 物理管理需要,页长固定 | 程序逻辑模块,段长可变 |
| 程序员视角 | 逻辑地址是一维的 | 段名/段号和段内地址,二维 |
| 碎片 | 可能有页内碎片,无外部碎片 | 可能有外部碎片 |
| 共享和保护 | 可做,但页边界未必对应逻辑模块 | 以逻辑段为单位较方便 |
共享代码一般要求纯代码/可重入代码,不能因某进程写入而破坏其他进程使用。无快表时,查段表一次、访问数据一次,通常共 2 次主存访问。
2. 段页式
先把进程按逻辑模块分段,再将每段分页;物理内存按页框分配。逻辑地址在硬件中可拆为段号 S + 段内页号 P + 页内偏移 W,但程序员仍以“段号 + 段内地址”的二维方式理解。
每进程有段表;段表项给出该段的页表位置及页表长度;每段各有页表。地址转换:检查段号 → 查段表 → 检查段内页号 → 查该段页表得物理块号 → 块号与页内偏移组成物理地址。无 TLB 时,查段表、查页表、访问数据,共 3 次主存访问。它便于按段共享和保护,同时用分页避免给整段寻找连续空间;仍可能有最后一页的内部碎片。
六、虚拟内存与请求分页
1. 虚拟内存的思想
传统方式常要求作业一次装入并一直驻留。基于时间局部性(近期访问的指令/数据可能再次访问)和空间局部性(邻近地址可能很快访问),系统只先装入当前需要的部分;缺少的部分按需从外存调入,内存不够时换出暂时不用的部分。特征是多次性、对换性、虚拟性。实现需要离散分配,典型方案是请求分页,也可有请求分段、请求段页式。
考研讲义常将可表示的虚拟空间上限写为 2^(虚拟地址位数) × 编址单位大小,并用 min(内存+外存容量,CPU 寻址范围) 作教材化的“实际容量”计算。现实系统还受映射、保留空间和后备存储政策等限制;考试按题目给定的模型计算。
2. 请求分页页表与缺页
请求分页的页表项在基本映射信息之外,通常还包括:状态/存在位(页面是否在内存)、访问字段(供置换算法参考)、修改位(脏页是否需写回)、外存地址(页面在磁盘的位置)。
访问流程:查页号和页表项 → 若页面在内存,则转换并访问;若不在内存,产生缺页异常/内中断 → 保存现场,缺页进程等待磁盘 I/O → 若有空闲页框直接装入,否则按置换算法选牺牲页,脏页先写回 → 读入目标页、更新页表和相应 TLB 项 → 唤醒进程并重新执行产生缺页的指令。被换出页面对应的 TLB 项必须失效。缺页不一定置换:有空闲页框时只调页;一条指令可能多次缺页。
区分:页号越界是访问了进程不合法的地址;缺页是合法页面暂时不在主存,通常可以调入后继续。TLB 未命中只表示快表无该项,不必然缺页。
七、页面置换算法
手算共同规则:画引用串,逐次记录当前页框内容;命中不计缺页;缺页但有空框不计置换;无空框才选择牺牲页。初次装页也要计入缺页次数。若题目给了初始页框状态、指针位置、访问位/修改位,以题目为准。
| 算法 | 淘汰依据 | 优缺点与考点 |
|---|---|---|
| OPT 最佳 | 未来最晚再用或永不再用 | 缺页次数理论最少,需预知未来,不能实际实现;用于比较基准 |
| FIFO 先进先出 | 最早进入页框 | 实现简单;命中通常不改变入队先后;可能出现 Belady 异常 |
| LRU 最近最久未使用 | 向过去看,最久未访问 | 性能较好,但精确实现开销高;命中要更新最近使用次序 |
| 简单 CLOCK | 环形扫描,优先访问位为 0 的页 | 遇 1 先置 0 并跳过;最多两轮找到牺牲页;置换后指针继续前进 |
| 改进型 CLOCK | 同看访问位 A 与修改位 M | 优先未访问且未修改,减少写回;按讲义的四轮扫描规则做题 |





改进型 CLOCK 的讲义规则:第一轮找 (0,0),不改位;未找到则第二轮找 (0,1),同时将扫描过的访问位置 0;仍未找到则第三轮找 (0,0);最后第四轮找 (0,1)。由于第二轮清除了访问位,最多四轮会选中。写题时要保留时钟指针当前位置,不能只按四类的静态优先级随意挑任一页。
Belady 异常:给更多页框,缺页次数反而增加。讲义用 FIFO 的经典引用串 3,2,1,0,3,2,4,3,2,1,0,4 演示:3 个页框缺页 9 次,4 个页框缺页 10 次。OPT 与 LRU 具有栈性质,不出现这种反常;考试中“只有 FIFO 会出现”应放在这几种常考算法的比较语境理解。
八、页面分配、调页与抖动
- 驻留集:分配给进程的物理页框集合。太小会频繁缺页,太大降低多道程序并发度。
- 固定分配:运行中页框数不变;可变分配:可增减。局部置换只在本进程页框内选牺牲页;全局置换还可利用系统空闲页框或其他进程的页框。常见组合是固定分配局部置换、可变分配全局置换、可变分配局部置换;“固定分配全局置换”逻辑上不成立,因为取得他进程页框会改变驻留集大小。
- 预调页:在缺页前预测并调入若干页,适合进程初次装入等场景;请求调页实际缺页才调入,目标页必然会用到,但每次缺页 I/O 成本高。
- 抖动/颠簸:页刚换出又很快需要,频繁调页使系统忙于 I/O。根本原因通常是进程频繁使用的页数超过可用页框数;可适当增加驻留集或降低并发进程数。
- 工作集:某个长度为
Δ的近期窗口里实际访问过的不同页面的集合。工作集大小不一定等于窗口长度。驻留集若长期小于工作集,容易抖动。求工作集题只看当前窗口,去重即可。 - 外存可分文件区与对换区。讲义给出不同的页面调入来源策略:对换区充足时可先把相关数据复制到对换区;对换区不足时只读页可由文件区直接调入、修改页需在换出时写入对换区;UNIX 风格中初次使用的页从文件区调入,已使用并换出的页可由对换区再次调入。按题设选择,不把某一种策略当作所有系统的统一实现。
九、内存映射文件
传统文件 I/O 通过 seek/read/write 在文件与用户缓冲区间传递数据。内存映射文件把文件内容映射到进程虚拟地址区:程序通过普通内存访问读写映射区域;操作系统按需把文件页调入页框,并负责将修改结果按映射策略回写。多个进程映射同一文件的同一部分,可共享相应的物理页,便于共享数据。考试要区分“虚拟地址映射到文件内容”与“整个文件一次性装入内存”;映射并不意味着立即把全文件读进内存。修改何时、是否持久化取决于映射方式和同步机制,题目若未给条件不要绝对化。
十、考前速查公式与易错点
| 题型 | 公式/判断 |
|---|---|
| 地址位数 | ceil(log2 可编址单元数);先确认按字节还是按字编址 |
| 分页拆地址 | P=floor(A/L),W=A mod L;若 L=2^k,低 k 位为偏移 |
| 页式物理地址 | E=bL+W;必须先验证页号、存在位等条件 |
| 页表项位置 | 连续且等长时 F+P×页表项长度 |
| 分段地址 | S<段表长度 且 W<段长,E=段基址+W |
| TLB 平均时间 | 先查快表:h(t+T)+(1−h)(t+2T);并行查询另算 |
| 多级页表 | 每级索引位数通常为 log2(页大小/页表项大小);无快表且无缺页时,n 级页表需 n+1 次主存访问 |
| 缺页率 | 缺页次数/访问页面次数,与“置换次数”分开统计 |
高频混淆清单:
- 页是逻辑单位,页框是物理单位;页号不等于物理块号。
- 页表项存的是块号;块首址还需乘页大小。段表项存的是段基址和段长。
- TLB 未命中≠缺页;缺页≠页面置换;页号越界≠缺页。
- 分页、段页式可能有内部碎片;动态分区、纯分段可能有外部碎片。
- FIFO 看进入页框的先后;LRU 看最近访问的先后;OPT 看未来访问。
- 多级页表节省了对大块连续页表空间的需求,但若无 TLB,地址转换的主存访问次数上升。
- 对请求分页的执行时间题,若发生缺页,磁盘 I/O 耗时通常远大于 TLB 与主存访问,必须单列缺页路径。
十一、自测题(附简答)
- 32 位逻辑地址、4 KiB 页、4 B 页表项,单级页表最多多大? 页号 20 位,最多
2^20项,页表2^20×4 B=4 MiB;存放它需要 1024 个 4 KiB 页框。 - 页大小 2 KiB,逻辑地址 6000,页 2 映射物理块 17。物理地址是多少?
P=2,W=6000−2×2048=1904;E=17×2048+1904=36720。 - 段表中 3 号段长 500 B、基址 10000,逻辑地址
(3,500)是否有效? 无效。段内最大合法偏移是 499。 - TLB 命中率 80%,TLB 2 ns,主存一次 100 ns,顺序查找平均时间?
0.8×102+0.2×202=122 ns,假设不发生缺页且不计其他缓存。 - 三个空页框,引用串
1,2,3,1,4,FIFO 与 LRU 各缺页多少次? 都是 4 次;最后访问 4 时,FIFO 淘汰 1,LRU 淘汰 2。虽然次数相同,最终页框内容不同。 - 窗口大小 5,最近五次访问为
2,3,2,4,3,工作集是什么?{2,3,4},大小为 3。
十二、专题精讲:把地址变换题做成固定流程
地址变换是本章最值得反复练的题。做题时先写出地址结构,再做越界检查,最后算目标物理地址和访存次数。不要一看到地址就直接除以页大小。
1. 连续分配:基址与界限
设某进程连续占用物理地址 [12000, 16999],基址为 12000,长度为 5000 B。逻辑地址 4999 合法,对应物理地址 16999;逻辑地址 5000 非法。若题目给的是“上限物理地址 16999”,则可先算 12000+A,再判定是否超过 16999。两种表述得到相同结论,但比较的对象不同。
静态重定位会把装入模块中的地址在装入时改好,因此进程运行后移动会让已改写的地址失效。动态重定位保留逻辑地址,每次访问时通过基址寄存器转换;进程移动后更新基址寄存器即可。这里的“每次访问”指硬件执行地址转换的逻辑,不等于一定要额外访问一次主存,访存次数仍按题设给出的机构计。
2. 分页:先确定“哪个页”,再确定“哪个块”
设按字节编址,页大小 4 KiB,某进程页表如下:
| 逻辑页号 | 物理块号 |
|---|---|
| 0 | 5 |
| 1 | 12 |
| 2 | 7 |
| 3 | 20 |
逻辑地址 10000:10000=2×4096+1808,所以页号 2,偏移 1808。页 2 在物理块 7,故物理地址 7×4096+1808=30480。如果页表长度是 4,页号 4 就越界;不能因为“内存里有第 4 块”就认为第 4 页有效。
页表项大小题要先求物理块编号范围。例如物理内存 4 GiB、页大小 4 KiB,共 2^20 个物理块,块号至少 20 位。若只记录块号,理论上 3 B 能放下 20 位;但实际页表项可能选 4 B,便于 4 KiB 的页正好容纳 1024 项,也为权限等信息留位。页表项“理论最少字节数”和题目指定的“实际字节数”必须分开。
一页可放多少页表项:floor(页面大小/页表项大小)。若页 4096 B、表项 3 B,可放 1365 项,剩余 1 B。若题目规定页表的每个存储页都不得跨页放表项,则第 1365 号表项从下一页开始,不能简单用 页表始址+1365×3;若题目明确页表紧密连续、允许表项跨页,则按连续公式。讲义强调为了简化查表,常把表项长度选成能整除页面大小的值。
3. 分段:必须做两次合法性检查
设段表长度为 3,段 1 的段长为 3000 B、物理基址为 50000。逻辑地址 (1,2999) 合法,对应 52999;(1,3000) 段内越界;(3,0) 段号越界。这里段长 3000 的合法偏移范围是 0~2999,段号从 0 起,段表长度 3 对应段号 0、1、2。
纯分段的段长随程序模块而变。即使段内偏移字段有 16 位、理论上能表示 0~65535,某个实际段也可能只有 3000 B,因此仍须检查段表项中的实际段长。
4. 段页式:分段检查在前,分页查询在后
设页大小 1 KiB;段表长度为 2;段 1 的页表长度为 3,页表映射 页 0→块 8、页 1→块 4、页 2→块 11。要访问段内地址 2500,可拆为段号 1、段内页号 floor(2500/1024)=2、页内偏移 452。段 1 合法,页 2 也合法,物理地址是 11×1024+452=11716。若段内地址改为 3072,段内页号变为 3,页表长度只有 3,因此越界。
有的题目直接给三元组 (段号,页号,页内偏移);有的给 (段号,段内地址)。先按题目格式拆地址,不能将段号误当成全进程统一的页号。段页式中各段有各自的页表,页号从每段内部重新编号。
5. 多级页表:从最高级逐级索引
32 位逻辑地址、4 KiB 页、4 B 页表项的两级页表,地址格式是 [10 位目录号 | 10 位二级页号 | 12 位偏移]。例如 (目录号 0, 二级页号 1, 偏移 4095):若目录项 0 指向的二级页表中,第 1 项给出物理块 4,最终物理地址 4×4096+4095=20479。目录项记录的是下一级页表的位置,不是目标数据页框。
与单级相比,两级页表可在页目录里把尚未用到的大片地址范围标成不存在,无须为其分配二级页表。进程只用到一个小范围时,页目录加少量二级页表即可;但没有 TLB 时查表级数增多,所以单次地址转换更慢。页表本身若也被换出,具体缺页处理和计时要看题设。
十三、专题精讲:时间、次数与异常的判题顺序
1. 访存次数表
下表只计主存访问,假设页表或段表已在主存、没有数据 Cache、也没有缺页:
| 机构 | 转换时要查的表 | 访问目标 | 合计 |
|---|---|---|---|
| 基本分页,单级页表 | 1 次 | 1 次 | 2 次 |
| 分段 | 1 次 | 1 次 | 2 次 |
| 段页式 | 段表、页表各 1 次 | 1 次 | 3 次 |
| 两级页表 | 页目录、二级页表各 1 次 | 1 次 | 3 次 |
n 级页表 | n 次 | 1 次 | n+1 次 |
| 快表命中 | 0 次主存查表 | 1 次 | 1 次 |
| 快表未命中、单级页表 | 1 次主存查表 | 1 次 | 2 次 |
TLB 本身也耗时,但题目若问“访存次数”,通常不把访问 TLB 算为访问主存。遇到快表与慢表同时查找的题,要看它问次数还是耗时:并行不等于没有查慢表,而是两路查找的时间重叠。
2. 平均访问时间怎么列式
先画两条路径,再乘概率。例:TLB 查找 2 ns,主存一次 100 ns,命中率 80%,先查 TLB,未命中再查主存页表。
- 命中:
2+100=102 ns。 - 未命中:
2+100+100=202 ns。 - 平均:
0.8×102+0.2×202=122 ns。
若还给缺页率 f,先分别列出“没有缺页时”和“发生缺页时”的完整路径,再写 平均时间=(1−f)×正常路径时间+f×缺页路径时间。缺页路径可能包含查页表、磁盘读取、脏页写回、进程切换和指令重启;题目给哪些费用就计哪些,切勿直接在 122 ns 上机械加一个磁盘时间。
3. 三种情况必须区分
| 现象 | 判断点 | 常见处理 |
|---|---|---|
| TLB 未命中 | 快表里没有这个页的映射 | 查内存页表;页面可能仍在内存 |
| 缺页 | 页表项显示合法页面当前不在内存 | 产生可恢复异常,调页;可能需要置换 |
| 地址越界/非法访问 | 页号、段号或段内偏移超合法范围 | 不能靠调页使非法地址变合法 |
请求分页中,先判断访问的虚拟地址属于进程的合法范围;之后再根据存在位判断是否缺页。缺页次数统计“需要调入目标页”的次数;置换次数统计“因无空闲页框而赶走旧页”的次数;后者通常不大于前者。
十四、专题精讲:分区分配题的完整推演
假设初始空闲分区为 A:(0,10)、B:(20,30)、C:(60,20),括号内是 (起始地址, 大小);先后申请 18、9 单位,每次从选中空闲区的低地址端划出请求大小。暂不考虑其他已分配区。
| 算法 | 第一次申请 18 | 更新后的空闲区 | 第二次申请 9 | 再次更新后 |
|---|---|---|---|---|
| 首次适应 | 选 B,分配 [20,38) | (0,10),(38,12),(60,20) | 从头选 A,分配 [0,9) | (9,1),(38,12),(60,20) |
| 最佳适应 | 选 C,分配 [60,78) | (0,10),(20,30),(78,2) | 选 A,分配 [0,9) | (9,1),(20,30),(78,2) |
| 最坏适应 | 选 B,分配 [20,38) | (0,10),(38,12),(60,20) | 选 C,分配 [60,69) | (0,10),(38,12),(69,11) |
此表的区间采用左闭右开记法,[20,38) 长度 18。正式题目若给地址范围为“起始地址到结束地址,均包含”,则末地址是 起始地址+长度−1。邻近适应还必须知道上次搜索停在何处;少了这一条件,可能不能唯一决定第二次选哪个空闲区。
回收练习:已有空闲区 [100,120)、[140,160),回收 [120,140) 后,三个相邻区应合并成 [100,160),长度 60。若只和前一个区合并而忘了后一个,后续分配题就会错。紧凑则是移动仍在使用的进程以消除不相邻的外部碎片,和“回收时合并相邻空闲区”不同。
十五、专题精讲:置换算法逐步演算
设有 3 个初始为空的页框,引用串是 1,2,3,1,4,1,2。每一步先判断命中,再决定是否有空框,最后才按算法选择牺牲页。
| 访问 | FIFO 页框状态 | FIFO 缺页? | LRU 页框状态 | LRU 缺页? | OPT 页框状态 | OPT 缺页? |
|---|---|---|---|---|---|---|
| 1 | [1,-,-] | 是 | [1,-,-] | 是 | [1,-,-] | 是 |
| 2 | [1,2,-] | 是 | [1,2,-] | 是 | [1,2,-] | 是 |
| 3 | [1,2,3] | 是 | [1,2,3] | 是 | [1,2,3] | 是 |
| 1 | [1,2,3] | 否 | [1,2,3] | 否 | [1,2,3] | 否 |
| 4 | [4,2,3],淘汰 1 | 是 | [1,4,3],淘汰 2 | 是 | [1,2,4],淘汰 3 | 是 |
| 1 | [4,1,3],淘汰 2 | 是 | [1,4,3] | 否 | [1,2,4] | 否 |
| 2 | [4,1,2],淘汰 3 | 是 | [1,4,2],淘汰 3 | 是 | [1,2,4] | 否 |
| 合计缺页 | 6 | 5 | 4 |
在访问第 4 页时,OPT 看后面的 1,2,发现当前在内存的 3 以后不会再用,因此淘汰 3。FIFO 的第 4 次访问虽然命中页 1,也不改变它最早进入内存这一事实;LRU 则必须把这次命中记作页 1 的最近使用。
CLOCK 手算步骤:先画页框的环、标每页访问位和指针。发生替换时,从指针处逐项检查:遇访问位 1,就清 0 并向前;遇 0,就选中替换;新页的访问位通常置 1,指针移向下一框。访问已在内存的页,只把该页访问位置 1,不要因为命中就随意移动替换指针。题目若指定初始位与替换后指针规则,严格依其设定。
改进型 CLOCK 手算除了访问位还要标修改位。(0,0) 代价最小,(0,1) 需要写回;遇到 (1,0)、(1,1) 时,按讲义的轮次规则清访问位后再考虑。由于扫描有起点,两个同类页不一定选页号小的那个,应该选本轮扫描先碰到的那个。
十六、专题精讲:驻留集、工作集与磁盘来源
1. 固定/可变与局部/全局是两个维度
“固定”回答页框数是否随运行改变;“局部”回答牺牲页从哪里挑。因此固定分配局部置换的规则是:进程缺页且自己的页框已满,只在自己的页中淘汰一个,页框数保持不变。可变分配全局置换则可为缺页进程增加一个空闲框,甚至从其他进程取得框;缺页进程与受害进程的驻留集都可能改变。可变分配局部置换允许根据缺页频率调整页框数,但某一次置换仍在本进程页面内进行。
2. 工作集用滑动窗口求
访问串 2,4,2,5,4,7,窗口大小 Δ=4:
- 访问到第 4 次时,窗口
2,4,2,5,工作集{2,4,5},大小 3。 - 访问到第 5 次时,窗口
4,2,5,4,工作集仍为{2,4,5}。 - 访问到第 6 次时,窗口
2,5,4,7,工作集{2,4,5,7},大小 4。
窗口移动时要删掉过期访问,但若同一页仍在窗口内,不能把它从工作集删掉。工作集是集合,重复访问只算一个页面。工作集大小增大通常说明该进程近期活跃页变多,可考虑增加驻留集;多个进程的工作集总需求超过可用页框时,系统容易抖动。
3. 脏页与后备存储
读入页面是一次磁盘 I/O;替换未修改页一般不需要写回,替换修改页/脏页则通常要先写回再读入新页,所以代价更高。改进型 CLOCK 把修改位纳入选择依据正是为减少这类写盘。磁盘上页面的来源可能是可执行文件/普通文件,也可能是对换区,具体回写目标按文件映射方式和题目描述判断。
十七、考研答题模板与复习优先级
1. 地址转换题模板
已知页面大小
L=…,因此页内偏移占log2 L位;逻辑地址A=…得P=…、W=…。检查P<页表长度,并查得页表项中的块号b=…。故物理地址E=bL+W=…。无快表/快表命中/未命中的访存次数分别按题设列出。
分段题把中间两句改为“检查段号合法、检查偏移小于实际段长、取段基址”,再用 E=段基址+偏移。段页式题则先查段表和该段页表,再算地址。
2. 算法题模板
写出当前空闲分区/页框状态 → 指明本次请求是否命中或能直接分配 → 如须选择,说明依据 → 更新状态 → 统计缺页、置换、写回等不同次数。
不要只写最终数字。考研主观题往往要看每一步选择是否符合算法,尤其是 FIFO、LRU、CLOCK 和动态分区的连续操作。
3. 建议的复习顺序
- 先拿稳计算:页号/偏移/物理地址、段长越界、TLB 平均时间、多级页表位数。
- 再刷算法:首次/最佳/最坏/邻近适应;OPT/FIFO/LRU/CLOCK,练到能逐步更新状态。
- 最后串概念:内部与外部碎片、局部性、请求分页流程、驻留集与工作集、抖动、内存映射文件。
如果这篇文章对你有帮助,欢迎分享给更多人!
部分信息可能已经过时