首页/考点精讲/操作系统 · 内存管理
考点精讲操作系统大纲 · 内存管理

内存管理
程序看到的地址,怎么变成内存里的地址

OS 里分值最重的章节之一:选择 3–4 道,综合题常和地址变换、TLB、页面置换、有效访问时间一起出,还经常与组成原理的 Cache/虚拟存储联考。

整章只有一条主线:逻辑地址 →(查表)→ 物理地址。连续分配“不用查表、加个基址”;分页“查页表”;分段“查段表”;虚拟内存“查表时发现不在内存就去磁盘搬”。

11 个大纲条目 4 类必会计算 5 处仅做理解
00
先看范围

大纲对照

★★★★★ 必考选择 + 综合

下面是考试大纲“内存管理”的全部条目,右边是本页对应位置。大纲内 的必须会做题;仅做理解 是教材里常见、但大纲没有列出的内容,读懂即可,不必背细节。

(一)内存管理基础
  1. 1内存管理的基本概念逻辑地址与物理地址空间、地址变换、内存共享、内存保护、内存分配与回收→ 01
  2. 2连续分配管理方式→ 02
  3. 3页式管理→ 03
  4. 4段式管理→ 04
  5. 5段页式管理→ 04
(二)虚拟内存管理
  1. 1虚拟内存基本概念→ 05
  2. 2请求页式管理→ 05
  3. 3页框分配→ 06
  4. 4页置换算法→ 07
  5. 5内存映射文件(Memory-Mapped Files)→ 08
  6. 6虚拟存储器性能的影响因素及改进方式→ 08
本页标为“仅做理解”的内容

程序的链接方式 · 覆盖与交换 · 伙伴系统 / 反置页表 · 请求分段 · 页面缓冲算法。这些是旧大纲或教材扩展内容,选择题偶尔擦边,但不作为复习重点。

逻辑地址 → 物理地址是全章唯一主线。分页 = 页号查页表换成块号,偏移不变;虚拟内存 = 查表时发现“不在内存”就产生缺页中断,从磁盘调入,必要时用置换算法踢掉一页。
01
大纲(一)1

基本概念:地址、变换、保护、共享

★★★☆☆选择
你写的程序里,变量 x 的地址是编译器“假设程序从 0 开始放”时算出来的——这叫逻辑地址。程序真正被装到内存哪儿,要运行时才知道——那叫物理地址。OS 的工作就是在每次访存时把前者翻译成后者,并且保证你翻译不到别人的地盘去。

一、四个关键词

概念一句话谁来做
逻辑地址空间程序自己看到的、从 0 开始的地址范围编译 / 链接产生
物理地址空间内存条上真实的地址范围硬件
地址变换(重定位)逻辑地址 → 物理地址现代 OS 用动态重定位:运行时由硬件(重定位寄存器 / MMU)完成
内存保护进程只能访问自己的区域① 上下限寄存器;② 重定位寄存器 + 界地址寄存器(先比界限,再加基址)
内存共享多个进程映射到同一块物理内存分段/分页里让两张表的表项指向同一物理段/页;被共享的代码必须是可重入代码(纯代码,运行中不被修改)
分配与回收谁占哪块、用完怎么还连续分配用空闲分区表/链;分页用空闲块表/位示图
保护 + 变换(连续分配时): if 逻辑地址 ≥ 界地址寄存器 → 越界中断 else 物理地址 = 重定位寄存器(基址) + 逻辑地址
  • 界地址寄存器存的是长度(最大逻辑地址),比较的是逻辑地址;重定位寄存器存的是起始物理地址。
  • 这两个寄存器只能在内核态用特权指令修改。

程序的链接与装入方式

静态链接 / 装入时动态链接 / 运行时动态链接;绝对装入 / 静态重定位(装入时一次性改地址)/ 动态重定位(运行时才转换)。这是旧大纲“程序装入与链接”的内容。你只需要记住结论:现代 OS 用动态重定位,所以进程可以在内存里被移动、换出再换入。

覆盖与交换

覆盖:让程序不同时用到的模块轮流占用同一块内存(程序员自己安排,早已淘汰)。交换(对换):把暂时不运行的整个进程换到磁盘的对换区,腾出内存;中级调度就是干这个。新大纲已不单列,但“对换区”这个词在请求分页里还会出现:对换区读写比文件区快(连续分配)。

02
大纲(一)2

连续分配管理方式

★★★☆☆选择
“连续”就是一个进程必须占一整段相邻的内存。像停车场里一辆大巴要连着占几个车位——车位总数够但不相邻,也停不进去,这就是外部碎片。

一、三种方式

方式做法碎片
单一连续分配内存分系统区 + 用户区,用户区只放一道程序内部碎片
固定分区分配事先切好若干分区(大小可相等或不等),一区一道程序内部碎片
动态分区分配进程要多少给多少,分区按需切出来外部碎片(可用“紧凑”解决,需动态重定位)
内部碎片 = 分给你了但你没用完(在分区内部);外部碎片 = 没分给任何人但太小没人能用(在分区外部)。

二、动态分区的四种分配算法

算法空闲分区怎么排选哪块特点
首次适应 FF按地址递增第一个够大的综合性能最好,低地址出现很多小碎片
邻近适应 NF按地址,循环从上次停下的地方往后找第一个够大的分配均匀,但高地址大块也被切碎
最佳适应 BF按容量递增最小的够大的反直觉:外部碎片最多(剩下的边角最小)
最坏适应 WF按容量递减最大的大块很快被用完,大进程来了没地方放

三、回收:和邻居合并

回收一块时看上下邻居是否空闲,共 4 种情况:只和上邻合并、只和下邻合并、和上下都合并(空闲分区数 −1)、都不合并(空闲分区数 +1)。

伙伴系统、Slab

Linux 实际用的内存分配器:按 2 的幂切块、相邻“伙伴”可合并。大纲未列,知道名字即可。

03
大纲(一)3

页式管理

★★★★★ 必考选择 + 计算
连续分配的问题是“一整段放不下”。分页的办法:把进程切成一样大的页,把内存切成同样大的页框(块),哪个空框都能放任何一页。代价是要一张页表记住“第几页放在第几块”。只有最后一页可能没装满 → 只有很小的内部碎片,没有外部碎片。

一、地址怎么拆

逻辑地址 = | 页号 P | 页内偏移 W | 页内偏移位数 = log2(页大小) 例:4 KB = 2^12 → 偏移 12 位 页号位数 = 逻辑地址位数 − 偏移位数 物理地址 = 块号(查页表得到) 拼接 页内偏移(原样照抄)

二、地址变换的步骤

  1. 用逻辑地址算出页号 P、偏移 W(位运算:高位是 P,低位是 W)。
  2. 比较 P 与页表长度:P ≥ 页表长度 则越界中断。
  3. 页表项地址 = 页表起始地址 + P × 页表项长度,访存一次取出块号 F。
  4. 物理地址 = F × 页大小 + W,再访存一次取数据。

32 位逻辑地址,页大小 4 KB,页表中第 3 页对应第 8 块。求逻辑地址 0x00003A7C 的物理地址。

偏移 12 位 = 低 3 个十六进制位 A7C;页号 = 0x00003 = 3 → 块号 8 → 物理地址 = 0x8 拼 A7C = 0x8A7C。
技巧:页大小是 16 的幂次时,直接按十六进制位切分,不用换成十进制。

三、快表 TLB:把“两次访存”变成“一次”

每次都查内存里的页表太慢。TLB 是一个小而快的相联存储器,缓存最近用过的“页号 → 块号”。命中则只需一次访存取数据。

有效访问时间 EAT(TLB 与内存串行查): EAT = 命中率 × (t_TLB + t_mem) + (1 − 命中率) × (t_TLB + 2·t_mem) 例:t_TLB = 20 ns,t_mem = 100 ns,命中率 90% EAT = 0.9 × 120 + 0.1 × 220 = 108 + 22 = 130 ns
  • 若题目说“TLB 与页表同时查找”,未命中时只算 t_mem×2,不再加 t_TLB——先看清题目说的是串行还是并行。
  • TLB 命中只省掉“查页表”那次访存,取数据那次仍然要访存(或访问 Cache)。

四、两级页表:页表太大怎么办

32 位地址、4 KB 页 → 220 个页表项,每项 4 B 就是 4 MB,而且必须连续存放。解决:把页表本身也分页,再用一张“页目录”记住每一页页表放在哪。
一页能放多少个页表项 = 页大小 / 页表项大小 = 4 KB / 4 B = 1024 = 2^10 → 每级页号 10 位:| 一级 10 | 二级 10 | 偏移 12 | 级数 = ⌈ 页号位数 / 每级位数 ⌉ (一级页表最多只能占一页) 访存次数(无 TLB)= 级数 + 1
常见问法:给出地址位数、页大小、页表项大小,问“至少几级页表”“每级几位”“访问一个数据要访存几次”;或者给出页目录号 / 页表索引,让你算物理地址。

反置页表(倒排页表)、哈希页表

反置页表按物理块建表,全系统一张,每项记录“哪个进程的哪个页”。表很小但查找要搜索。大纲未列。

04
大纲(一)4–5

段式管理与段页式管理

★★★★☆选择 + 计算
分页是 OS 按固定大小硬切,程序员看不见;分段是按程序的逻辑意义切:代码段、数据段、栈段……每段长度不同,各自从 0 编址,便于共享和保护(比如“代码段只读、可共享”)。

一、分页 vs 分段

对比项分页分段
单位物理单位,大小固定,由系统决定逻辑单位,长度可变,由程序决定
地址空间一维(只给一个地址,系统自动拆)二维(程序员要给出段号 + 段内地址)
碎片只有页内碎片外部碎片
共享与保护不方便(一页里可能混着代码和数据)方便
越界检查只查页号 ≥ 页表长度查段号越界 + 段内地址 ≥ 段长也越界
分段地址变换: 段号 S ≥ 段表长度 → 越界 段内地址 W ≥ 段表[S].段长 → 越界 ← 分页没有这一步 物理地址 = 段表[S].基址 + W ← 是“相加”,不是“拼接”

二、段页式:先分段,段内再分页

逻辑地址 = | 段号 S | 页号 P | 页内偏移 W | 每个进程 1 张段表;每个段 1 张页表 段表项 = (页表长度, 页表起始地址) 访存次数(无 TLB):查段表 1 + 查页表 1 + 取数据 1 = 3 次
  • 段页式的地址空间仍是二维的(由段决定)。
  • “一个进程有几张页表”= 段数,不是 1。
05
大纲(二)1–2

虚拟内存与请求分页

★★★★★ 必考选择 + 综合
程序不会同时用到所有代码和数据(局部性原理),所以只把“马上要用的几页”放进内存,其余放磁盘。用到了却发现不在内存?产生缺页中断,现搬进来。用户感觉内存“变大了”——这就是虚拟内存。

一、虚拟内存的特征与容量

  • 三个特征:多次性(分多次调入)、对换性(运行中可换入换出)、虚拟性(逻辑上扩充容量)。
  • 虚拟内存的实际容量 ≤ min(内存 + 外存,CPU 地址位数决定的范围)。
  • 实现必须基于离散分配(请求分页 / 请求分段 / 请求段页式)。

二、请求分页的页表项比普通页表多了什么

字段作用
状态位 P(有效位)这一页在不在内存;0 → 缺页
访问位 A最近是否被访问过,给置换算法(CLOCK/LRU 近似)用
修改位 M(脏位)调入后是否被改过;改过的页换出时要写回磁盘
外存地址这一页在磁盘的位置,缺页时去那里读

三、一次访存的完整流程(综合题骨架)

  1. 查 TLB,命中 → 得到块号,直接访存。
  2. 未命中 → 查内存中的页表;P = 1 → 得到块号,把该项写入 TLB,访存。
  3. P = 0 → 缺页中断(属于内中断/故障):进程阻塞,OS 找一个空闲页框;若没有空闲框则按置换算法选一页淘汰,若 M = 1 先写回。
  4. 启动磁盘把所需页读入页框,修改页表(P = 1),并更新 TLB。
  5. 返回重新执行引起缺页的那条指令(不是下一条)。
  • 缺页中断在指令执行期间产生,一条指令可能产生多次缺页(例如跨页的操作数)。
  • 缺页处理完后回到原指令重新执行;普通外中断是执行完当前指令后响应。
  • “缺页”不一定要“置换”:有空闲页框就直接调入。

请求分段、请求段页式

大纲只写了“请求页式管理”。请求分段原理相同(段表加存在位、缺段中断),只是段长可变,置换更麻烦。知道有这回事即可。

06
大纲(二)3

页框分配

★★★☆☆选择
给每个进程分几个页框(叫驻留集)?给少了频繁缺页,给多了能并发的进程变少。还要决定:缺页时只能踢自己的页(局部),还是可以抢别人的(全局)?
策略含义评价
固定分配 + 局部置换页框数运行中不变,缺页只换自己的页数目难定
可变分配 + 全局置换缺页时从系统空闲框拿;没有空闲就可以淘汰任何进程的页最易实现;但会拖累别的进程
可变分配 + 局部置换缺页只换自己的页;OS 根据缺页率动态增减该进程的页框较合理
固定分配 + 全局置换不存在:全局置换会改变页框数,与“固定”矛盾

何时调入、从哪调入

  • 预调页:运行前/首次调入时一次多调几页(利用空间局部性);请求调页:运行期间缺哪页调哪页。
  • 从哪调:对换区够大 → 全从对换区(快);不够 → 不会被修改的页从文件区调,会改的换出到对换区;UNIX 方式:没运行过的页从文件区调,换出过的从对换区调。
07
大纲(二)4

页面置换算法

★★★★★ 必考选择 + 综合
页框满了又缺页,必须赶走一页。理想情况:赶走“以后最久都不会用的”那页——但没法预知未来,所以有各种近似办法。
算法淘汰谁要点
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 的四轮扫描

类别:(A=0,M=0) 最近没用也没改 → 最佳淘汰对象 (A=0,M=1) 没用但改过 → 淘汰前要写回 (A=1,M=0) 用过没改 (A=1,M=1) 用过也改过 → 最不该淘汰 第 1 轮:找 (0,0),不改任何标志 第 2 轮:找 (0,1),扫过的页把 A 置 0 第 3 轮:重复第 1 轮;第 4 轮:重复第 2 轮(此时一定能找到)

页面缓冲算法(PBA)、LFU、MFU

PBA:被淘汰的页先挂在空闲/修改链表上,短期内又被访问可直接“捞回”。LFU/MFU 按访问次数淘汰。教材提到但大纲不考计算。

08
大纲(二)5–6

虚存性能、抖动、工作集与内存映射文件

★★★★☆选择 + 计算

一、缺页对访问时间的影响

EAT = (1 − p) × t_mem + p × t_缺页处理 (p 为缺页率) 例:t_mem = 100 ns,缺页处理 = 10 ms = 10^7 ns,p = 0.001 EAT ≈ 0.999 × 100 + 0.001 × 10^7 ≈ 100 + 10000 = 10.1 μs → 千分之一的缺页率就让速度慢了约 100 倍

二、影响缺页率的因素与改进

因素影响改进
页面大小太小 → 页表大、调页次数多;太大 → 页内碎片大、调入无用内容选折中大小
分配的页框数越多缺页率越低,但到一定数量后收益很小按工作集分配
置换算法OPT/LRU 优于 FIFO用 LRU 近似(CLOCK)
程序局部性局部性好则缺页少编程时按行优先访问数组等
写回开销脏页越多,置换越慢改进型 CLOCK 优先淘汰干净页、成批写回

二维数组 int a[1024][1024] 按行存放,页大小 4 KB(正好放一行),只分到 1 个数据页框。按行遍历和按列遍历各缺页多少次?

按行:每行一次,共 1024 次;按列:每访问一个元素就换一行,共 1024 × 1024 次。这就是“程序局部性”对缺页率的影响。

三、抖动与工作集

抖动(颠簸):刚换出的页马上又要用,又换回来……CPU 大部分时间在搬页面而不是干活。根本原因是分配给进程的页框数少于它正在频繁使用的页数(并发进程太多)。
  • 工作集 W(t, Δ):在时刻 t 往前看 Δ 次访问,用到的不同页的集合。驻留集 ≥ 工作集大小时基本不抖动。
  • 解决抖动:减少并发进程数(挂起一些进程)、按工作集分配页框、用缺页率控制分配;不能靠增大磁盘或换更快 CPU。

访问串 … 2 4 5 3 3 4 2 5 | t,窗口 Δ = 5,求 t 时刻工作集。

往前数 5 次:3 3 4 2 5,去重 → {2, 3, 4, 5},大小 4。

四、内存映射文件

把一个磁盘文件“挂”到进程的虚拟地址空间里(如 mmap)。之后读写文件就像读写数组:访问到哪页、缺页时 OS 才把文件对应的块读进来;修改后的页由 OS 在合适时机写回文件。
  • 好处:省去 read/write 系统调用与用户缓冲区的复制;按需调页;多个进程映射同一文件即可实现共享内存。
  • 与普通请求分页的区别:缺页时数据来源是该文件,换出脏页时写回该文件(而不是对换区)。
09
收口

自测与考前速览

★★★★★自测
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 次。
⑤ 缺页中断返回重执行原指令。