大纲对照
下面是考试大纲“内存管理”的全部条目,右边是本页对应位置。大纲内 的必须会做题;仅做理解 是教材里常见、但大纲没有列出的内容,读懂即可,不必背细节。
- 1虚拟内存基本概念→ 05
- 2请求页式管理→ 05
- 3页框分配→ 06
- 4页置换算法→ 07
- 5内存映射文件(Memory-Mapped Files)→ 08
- 6虚拟存储器性能的影响因素及改进方式→ 08
程序的链接方式 · 覆盖与交换 · 伙伴系统 / 反置页表 · 请求分段 · 页面缓冲算法。这些是旧大纲或教材扩展内容,选择题偶尔擦边,但不作为复习重点。
基本概念:地址、变换、保护、共享
x 的地址是编译器“假设程序从 0 开始放”时算出来的——这叫逻辑地址。程序真正被装到内存哪儿,要运行时才知道——那叫物理地址。OS 的工作就是在每次访存时把前者翻译成后者,并且保证你翻译不到别人的地盘去。
一、四个关键词
| 概念 | 一句话 | 谁来做 |
|---|---|---|
| 逻辑地址空间 | 程序自己看到的、从 0 开始的地址范围 | 编译 / 链接产生 |
| 物理地址空间 | 内存条上真实的地址范围 | 硬件 |
| 地址变换(重定位) | 逻辑地址 → 物理地址 | 现代 OS 用动态重定位:运行时由硬件(重定位寄存器 / MMU)完成 |
| 内存保护 | 进程只能访问自己的区域 | ① 上下限寄存器;② 重定位寄存器 + 界地址寄存器(先比界限,再加基址) |
| 内存共享 | 多个进程映射到同一块物理内存 | 分段/分页里让两张表的表项指向同一物理段/页;被共享的代码必须是可重入代码(纯代码,运行中不被修改) |
| 分配与回收 | 谁占哪块、用完怎么还 | 连续分配用空闲分区表/链;分页用空闲块表/位示图 |
- 界地址寄存器存的是长度(最大逻辑地址),比较的是逻辑地址;重定位寄存器存的是起始物理地址。
- 这两个寄存器只能在内核态用特权指令修改。
程序的链接与装入方式
静态链接 / 装入时动态链接 / 运行时动态链接;绝对装入 / 静态重定位(装入时一次性改地址)/ 动态重定位(运行时才转换)。这是旧大纲“程序装入与链接”的内容。你只需要记住结论:现代 OS 用动态重定位,所以进程可以在内存里被移动、换出再换入。
覆盖与交换
覆盖:让程序不同时用到的模块轮流占用同一块内存(程序员自己安排,早已淘汰)。交换(对换):把暂时不运行的整个进程换到磁盘的对换区,腾出内存;中级调度就是干这个。新大纲已不单列,但“对换区”这个词在请求分页里还会出现:对换区读写比文件区快(连续分配)。
连续分配管理方式
一、三种方式
| 方式 | 做法 | 碎片 |
|---|---|---|
| 单一连续分配 | 内存分系统区 + 用户区,用户区只放一道程序 | 内部碎片 |
| 固定分区分配 | 事先切好若干分区(大小可相等或不等),一区一道程序 | 内部碎片 |
| 动态分区分配 | 进程要多少给多少,分区按需切出来 | 外部碎片(可用“紧凑”解决,需动态重定位) |
二、动态分区的四种分配算法
| 算法 | 空闲分区怎么排 | 选哪块 | 特点 |
|---|---|---|---|
| 首次适应 FF | 按地址递增 | 第一个够大的 | 综合性能最好,低地址出现很多小碎片 |
| 邻近适应 NF | 按地址,循环 | 从上次停下的地方往后找第一个够大的 | 分配均匀,但高地址大块也被切碎 |
| 最佳适应 BF | 按容量递增 | 最小的够大的 | 反直觉:外部碎片最多(剩下的边角最小) |
| 最坏适应 WF | 按容量递减 | 最大的 | 大块很快被用完,大进程来了没地方放 |
三、回收:和邻居合并
回收一块时看上下邻居是否空闲,共 4 种情况:只和上邻合并、只和下邻合并、和上下都合并(空闲分区数 −1)、都不合并(空闲分区数 +1)。
伙伴系统、Slab
Linux 实际用的内存分配器:按 2 的幂切块、相邻“伙伴”可合并。大纲未列,知道名字即可。
页式管理
一、地址怎么拆
二、地址变换的步骤
- 用逻辑地址算出页号 P、偏移 W(位运算:高位是 P,低位是 W)。
- 比较 P 与页表长度:P ≥ 页表长度 则越界中断。
- 页表项地址 = 页表起始地址 + P × 页表项长度,访存一次取出块号 F。
- 物理地址 = F × 页大小 + W,再访存一次取数据。
32 位逻辑地址,页大小 4 KB,页表中第 3 页对应第 8 块。求逻辑地址 0x00003A7C 的物理地址。
A7C;页号 = 0x00003 = 3 → 块号 8 → 物理地址 = 0x8 拼 A7C = 0x8A7C。技巧:页大小是 16 的幂次时,直接按十六进制位切分,不用换成十进制。
三、快表 TLB:把“两次访存”变成“一次”
每次都查内存里的页表太慢。TLB 是一个小而快的相联存储器,缓存最近用过的“页号 → 块号”。命中则只需一次访存取数据。
- 若题目说“TLB 与页表同时查找”,未命中时只算 t_mem×2,不再加 t_TLB——先看清题目说的是串行还是并行。
- TLB 命中只省掉“查页表”那次访存,取数据那次仍然要访存(或访问 Cache)。
四、两级页表:页表太大怎么办
反置页表(倒排页表)、哈希页表
反置页表按物理块建表,全系统一张,每项记录“哪个进程的哪个页”。表很小但查找要搜索。大纲未列。
段式管理与段页式管理
一、分页 vs 分段
| 对比项 | 分页 | 分段 |
|---|---|---|
| 单位 | 物理单位,大小固定,由系统决定 | 逻辑单位,长度可变,由程序决定 |
| 地址空间 | 一维(只给一个地址,系统自动拆) | 二维(程序员要给出段号 + 段内地址) |
| 碎片 | 只有页内碎片 | 外部碎片 |
| 共享与保护 | 不方便(一页里可能混着代码和数据) | 方便 |
| 越界检查 | 只查页号 ≥ 页表长度 | 查段号越界 + 段内地址 ≥ 段长也越界 |
二、段页式:先分段,段内再分页
- 段页式的地址空间仍是二维的(由段决定)。
- “一个进程有几张页表”= 段数,不是 1。
虚拟内存与请求分页
一、虚拟内存的特征与容量
- 三个特征:多次性(分多次调入)、对换性(运行中可换入换出)、虚拟性(逻辑上扩充容量)。
- 虚拟内存的实际容量 ≤ min(内存 + 外存,CPU 地址位数决定的范围)。
- 实现必须基于离散分配(请求分页 / 请求分段 / 请求段页式)。
二、请求分页的页表项比普通页表多了什么
| 字段 | 作用 |
|---|---|
| 状态位 P(有效位) | 这一页在不在内存;0 → 缺页 |
| 访问位 A | 最近是否被访问过,给置换算法(CLOCK/LRU 近似)用 |
| 修改位 M(脏位) | 调入后是否被改过;改过的页换出时要写回磁盘 |
| 外存地址 | 这一页在磁盘的位置,缺页时去那里读 |
三、一次访存的完整流程(综合题骨架)
- 查 TLB,命中 → 得到块号,直接访存。
- 未命中 → 查内存中的页表;P = 1 → 得到块号,把该项写入 TLB,访存。
- P = 0 → 缺页中断(属于内中断/故障):进程阻塞,OS 找一个空闲页框;若没有空闲框则按置换算法选一页淘汰,若 M = 1 先写回。
- 启动磁盘把所需页读入页框,修改页表(P = 1),并更新 TLB。
- 返回重新执行引起缺页的那条指令(不是下一条)。
- 缺页中断在指令执行期间产生,一条指令可能产生多次缺页(例如跨页的操作数)。
- 缺页处理完后回到原指令重新执行;普通外中断是执行完当前指令后响应。
- “缺页”不一定要“置换”:有空闲页框就直接调入。
请求分段、请求段页式
大纲只写了“请求页式管理”。请求分段原理相同(段表加存在位、缺段中断),只是段长可变,置换更麻烦。知道有这回事即可。
页框分配
| 策略 | 含义 | 评价 |
|---|---|---|
| 固定分配 + 局部置换 | 页框数运行中不变,缺页只换自己的页 | 数目难定 |
| 可变分配 + 全局置换 | 缺页时从系统空闲框拿;没有空闲就可以淘汰任何进程的页 | 最易实现;但会拖累别的进程 |
| 可变分配 + 局部置换 | 缺页只换自己的页;OS 根据缺页率动态增减该进程的页框 | 较合理 |
| 不存在:全局置换会改变页框数,与“固定”矛盾 | ||
何时调入、从哪调入
- 预调页:运行前/首次调入时一次多调几页(利用空间局部性);请求调页:运行期间缺哪页调哪页。
- 从哪调:对换区够大 → 全从对换区(快);不够 → 不会被修改的页从文件区调,会改的换出到对换区;UNIX 方式:没运行过的页从文件区调,换出过的从对换区调。
页面置换算法
| 算法 | 淘汰谁 | 要点 |
|---|---|---|
| OPT 最佳 | 未来最长时间不再用的 | 缺页最少,无法实现,作为评价基准 |
| FIFO 先进先出 | 最早调入的 | 唯一会出现 Belady 异常(页框变多缺页反而变多) |
| LRU 最近最久未用 | 过去最久没用的 | 效果接近 OPT;需硬件支持(寄存器/栈),开销大 |
| CLOCK(NRU) | 指针转圈,遇 A=1 置 0 跳过,遇 A=0 淘汰 | LRU 的近似;最多扫两圈 |
| 改进型 CLOCK | 按 (A, M) 优先淘汰 (0,0) | 少写回磁盘;最多扫四轮 |
3 个页框,访问串 7 0 1 2 0 3 0 4 2 3 0 3 2,求 OPT / FIFO / LRU 的缺页次数(含开始装入的 3 次)。
OPT = 7 次:访问 2 时淘汰 7(以后不再用);访问 3 时淘汰 1;访问 4 时,2/3/0 下次出现位置分别为 1、2、3 步之后,淘汰最远的 0;访问 0 时淘汰 4。
LRU = 9 次:每次看“上一次使用时间”最早的那页。访问 3 时淘汰 1;访问 4 时淘汰 2;访问 2 时淘汰 3;访问 3 时淘汰 0;访问 0 时淘汰 4;最后的 3、2 命中。
FIFO = 10 次:队列依次淘汰 7、0、1、2、3、0、4,最后 3、2 命中。
规律:OPT ≤ LRU,FIFO 通常最差。画表时一行一个页框,命中格空着、缺页格打 √,最不容易数错。
改进型 CLOCK 的四轮扫描
页面缓冲算法(PBA)、LFU、MFU
PBA:被淘汰的页先挂在空闲/修改链表上,短期内又被访问可直接“捞回”。LFU/MFU 按访问次数淘汰。教材提到但大纲不考计算。
虚存性能、抖动、工作集与内存映射文件
一、缺页对访问时间的影响
二、影响缺页率的因素与改进
| 因素 | 影响 | 改进 |
|---|---|---|
| 页面大小 | 太小 → 页表大、调页次数多;太大 → 页内碎片大、调入无用内容 | 选折中大小 |
| 分配的页框数 | 越多缺页率越低,但到一定数量后收益很小 | 按工作集分配 |
| 置换算法 | OPT/LRU 优于 FIFO | 用 LRU 近似(CLOCK) |
| 程序局部性 | 局部性好则缺页少 | 编程时按行优先访问数组等 |
| 写回开销 | 脏页越多,置换越慢 | 改进型 CLOCK 优先淘汰干净页、成批写回 |
二维数组 int a[1024][1024] 按行存放,页大小 4 KB(正好放一行),只分到 1 个数据页框。按行遍历和按列遍历各缺页多少次?
三、抖动与工作集
- 工作集 W(t, Δ):在时刻 t 往前看 Δ 次访问,用到的不同页的集合。驻留集 ≥ 工作集大小时基本不抖动。
- 解决抖动:减少并发进程数(挂起一些进程)、按工作集分配页框、用缺页率控制分配;不能靠增大磁盘或换更快 CPU。
访问串 … 2 4 5 3 3 4 2 5 | t,窗口 Δ = 5,求 t 时刻工作集。
3 3 4 2 5,去重 → {2, 3, 4, 5},大小 4。四、内存映射文件
mmap)。之后读写文件就像读写数组:访问到哪页、缺页时 OS 才把文件对应的块读进来;修改后的页由 OS 在合适时机写回文件。- 好处:省去
read/write系统调用与用户缓冲区的复制;按需调页;多个进程映射同一文件即可实现共享内存。 - 与普通请求分页的区别:缺页时数据来源是该文件,换出脏页时写回该文件(而不是对换区)。
自测与考前速览
1. 分页存储管理有没有外部碎片?有没有内部碎片?
没有外部碎片;有内部碎片(每个进程最后一页可能装不满),平均半页。
2. 32 位地址、页 4 KB、页表项 4 B,采用多级页表且每级页表不超过一页,需要几级?
一页放 1024 项 → 每级 10 位;页号 20 位 → 2 级。
3. 段式管理和分页管理的越界检查有什么不同?
都要检查段号/页号是否超过表长;分段还要检查段内地址是否 ≥ 段长,分页不用(页内偏移位数固定,不会越过页)。
4. 为什么说 FIFO 会出现 Belady 异常而 LRU 不会?
LRU、OPT 属于“栈式算法”:n 个页框时内存中的页集合一定是 n+1 个页框时的子集,所以页框增加缺页不会增加;FIFO 不满足这个性质。
5. 系统 CPU 利用率 10%、对换磁盘利用率 98%,说明什么?该怎么办?
在抖动。应减少多道程序度(挂起部分进程);增加内存也有效;换更快 CPU、增大磁盘都没用。
6. 缺页中断返回后执行哪条指令?
重新执行引起缺页的那条指令。
7. 内存映射文件被修改的页换出时写到哪?
写回被映射的那个文件本身,而不是对换区。
分页:块号拼偏移;分段:基址加偏移。
EAT 串行 TLB:命中 t+m,未命中 t+2m。
级数 = ⌈页号位数 / log2(页大小÷页表项)⌉。
缺页 → 有空闲框直接调入;没有就置换,脏页先写回。
抖动 = 页框 < 工作集,降并发度。
① 最佳适应外部碎片最多。
② 固定分配 + 全局置换不存在。
③ 只有 FIFO 有 Belady 异常。
④ 段页式无 TLB 访存 3 次。
⑤ 缺页中断返回重执行原指令。