e2hang/Operating-System

Fork 0

Files

e2hang ef7621a1ae New Homework

2026-06-25 00:09:09 +08:00

47 KiB

Raw Permalink Blame History

第七章虚拟存储管理

一、知识讲解

7.0 章节定位与学习目标

本章是存储管理的"高潮章节"——在前一章基本分页/分段的基础上，把"一次性、驻留性"的常规存储管理扩展为"部分装入、按需调入"的虚拟存储。它要解决的核心问题是：当程序比内存还大、或者多道程序并发占用内存导致内存不足时，怎么办？

需要掌握的关键词：局部性原理、虚拟存储器特征、缺页中断、请求分页地址变换、OPT、FIFO、Belady 异常、LRU、栈性质、NUR/Clock、改进 Clock、LFU、MFU、抖动、工作集、驻留集、请求调页/预调页、全局置换/局部置换、动态链接、共享段表、伙伴算法。

7.1 外存资源管理

7.1.1 外存空间的划分与基本单位

外存（磁盘）按"块"（block）管理：块长度静态等长，为 2 的幂（2^i 字节）。块既是外存分配的基本单位，也是 I/O 传输的基本单位。这一点非常重要，与内存以"页"为单位完全对称：内存管理单位是页，外存管理单位是块，二者大小可以相等（如都为 4KB），也可以不等（一般块 = 多个页）。

为什么块长必须是 2 的幂？ 出于效率考虑：

便于按位运算定位（地址/块长即为块号，可用移位实现）；
便于伙伴（Buddy）算法对半分割、合并；
与内存分页的页大小易于对齐。

7.1.2 外存空间的分配方式

外存空间的组织有三种典型方式：

方式	原理	优缺点
空闲块链	把所有空闲块用链表串起来	简单，但分配/释放需遍历链表，慢
空闲块表（UNIX）	系统维护一张"空闲块号表"，记录连续空闲区段	速度较快，是 UNIX 成组链接法的思想
字位映像图（位图法）	外存按块编号，每块对应一位，0=空闲 1=占用	查找空闲块快速，可一次找多个连续块

外存区域按用途划分：

Swap 空间（交换区）：存放被换出的页面，访问频率高，要求读写快；
File 空间（文件区）：存放文件，访问频率相对低，要求空间利用率高；
输入井/输出井：用于批处理系统中作业的输入/输出缓冲。

易考点：外存块长的取值、字位映像图的"1 位对应一块"。

7.1.3 进程与外存的对应关系

按进程运行时组织方式不同，进程在外存的存放方式有 4 种：

方式	内存单位	外存单位	适用
界地址（连续）	连续区	一组/两组连续块	简单存储管理
页式	一页	一块	虚拟页式
段式	一段（变长）	若干连续块	虚拟段式
段页式	一页	一块	虚拟段页式

双对界：每个进程在外存中占两段连续区（用户区 + 交换区副本），便于成批换入换出。

7.2 虚拟存储系统概述

7.2.1 为什么要虚拟存储

没有虚拟存储的两大问题：

不能运行比内存大的程序：单道程序年代，一旦程序超过内存容量就无法运行；
进程全部装入内存会浪费空间：程序运行时具有局部性，一个进程某一时刻真正使用的页面只占其全部页面的一小部分，把整个进程都装入内存意味着大部分页面"白占"。

局部性原理（Locality Principle） 是虚拟存储的根基：

时间局部性：某指令/数据被访问后，短时间内很可能再次被访问（如循环体、热点数据）；
空间局部性：某存储单元被访问后，其相邻单元短期内很可能被访问（如顺序执行、数组顺序访问）。

由于局部性的存在，单控制流进程只需把"当前活跃"的一小部分装入内存即可运行；多控制流进程（如多线程）则需要更多活跃页面。

7.2.2 虚拟存储的定义与特征

虚拟存储器：是指具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和决定，运行速度接近内存，成本接近外存。

虚拟存储的四大特征（背诵）：

多次性（最重要）：一个作业被分成多次调入内存运行（不是一次性装入）；
对换性：作业在运行过程中可以换入/换出内存；
虚拟性：从逻辑上扩充内存容量，使用户看到的内存比实际大；
离散性：进程的多个页面在外存/内存可以离散存放（这要求分页或分段管理才能实现）。

易错点：虚拟性的前提是离散性 —— 没有离散分配，虚拟存储无法实现。

7.2.3 虚拟页式存储管理基本原理

这是最常见的虚拟存储实现方式。

进程运行前：全部页面装入外存，部分活跃页面装入内存。 进程运行时：若访问的页面不在内存 → 触发缺页中断（Page Fault），由中断处理程序完成：

保存现场；
在外存找到该页地址；
在内存找一个空闲页框；若无空闲，按置换算法选一页淘汰；
若被淘汰页"脏"（被修改过），需先写回外存；
把所需页面读入内存；
修改该进程的页表和系统的总页表（标记该页在内存、更新页框号等）；
重新执行被中断的指令（重新启动而非"继续执行"是缺页中断的特色）。

为什么缺页中断要"重新启动指令"而不是"返回下一条指令"？ 因为缺页中断发生时，该指令可能还未执行完（例如取操作数阶段发现数据页不在内存），必须重新执行该指令才能拿到正确数据。

7.2.4 虚拟页式地址映射（重点）

地址变换流程（结合快表/页表）：

逻辑地址 (p, d)
   │
   ▼
查快表（TLB）得 f
   ├─ 命中 ──→ f+d 得物理地址 [硬件完成]
   └─ 未命中 ─→ 由 (b, p) 查页表得 f
                  ├─ 页在内存 ─→ 修改快表（如快表满则淘汰一项），f+d 得物理地址
                  └─ 缺页 ─→ 缺页中断处理（见上）
   ※ p 越界 → 越界中断

关键点：

快表（TLB, Translation Lookaside Buffer）：一种特殊的高速缓存，存放最近使用的页表项（p → f 的映射）。命中时硬件直接合成物理地址，极快；未命中才访问内存中的页表（慢）。
快表一般采用组相联或全相联，容量小（几十到几百项），查找由硬件并行完成。
一次地址变换可能触发两次内存访问（访问页表 + 访问数据），故引入快表。

7.2.5 页表与快表的改进

页表项 应包含：

页框号 f
访问权限 {r, w, e}
修改标志（脏位）0/1
有效位（在内存？）、访问位等

快表项 应包含：逻辑页号 p、页框号 f、访问权限、修改标志等。

7.2.6 内存页框分配策略（静态）

策略	公式/方法	优缺点
平均分配	m 个页框 / n 个进程 = m/n 个	简单但不考虑进程实际需要
按进程长度比例	a_i = (s_i / S) × m	较合理，但忽略优先级
按进程优先级比例	a_i = (priority_i / ΣP) × m	体现优先级
按长度与优先级综合	加权	最灵活

静态策略的缺陷：不能反映（1）程序结构（如有些程序天然就是局部性差）；（2）程序在不同时刻的行为特性（同一进程在不同阶段访问的页面集不同）。所以实际操作中多用动态分配（基于工作集或缺页率反馈）。

7.2.7 外存块的分配策略

策略	含义	优点	缺点
静态分配	外存长期保持进程全部页面	淘汰时若未修改可直接丢弃，快	外存浪费
动态分配	外存仅保存进程不在内存的部分页面	外存省	淘汰时若被修改必须写回，慢

易考点：静态/动态分配 vs 静态/动态页面调入，二者不要混淆！

7.2.8 页面调入时机

方式	触发时机	优点	缺点
请求调页（Demand Paging）	缺页中断发生时才调入	按需调入，外存访问次数少	缺页时进程必须等待 I/O
预调页（Prepaging）	根据程序顺序行为提前调入即将访问的页	缺页率可能降低	预测不一定准，调入的页可能根本不用

预调页必须辅以请调：因为预调预测不可能 100% 准确，必须用请求调页作为兜底，否则一旦预测失败将持续缺页。

7.3 页面置换算法（核心考点）

目标：最低的缺页率（page fault rate）。当内存已无空闲页框时，按某种规则选一页淘汰。

置换算法同时适用于：页淘汰、段淘汰、快表淘汰。三处的淘汰策略可以独立选择。

7.3.1 OPT（最佳置换算法，Optimal）

原理：淘汰将来最长时间以后才被使用的页面（或者"以后永远不再被使用"的页面）。

优缺点：

优点：缺页率最低，可作为衡量其他算法优劣的基准；
缺点：不可实现 —— 因为操作系统无法预知进程未来的访问序列。这是最常考的一句话："OPT 缺页率最低，但不能实现，只能作为理论基准"。

OPT 缺页率计算：

设引用串：6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 6, 0, 1，分配 3 个页框。

访问	6	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	6	0	1
框1	6	6	6	2	2	2	2	2	2	2	2	2	2	1	1	1	1	1	1	1
框2		0	0	0	0	0	0	4	4	4	0	0	0	0	0	0	0	6	6	6
框3			1	1	1	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3
缺页?	×	×	×	×		×		×			×			×				×

缺页次数 = 9，缺页率 = 9/20 = 45%。

OPT 每次淘汰"未来最远才用到的页面"：访问 2 时淘汰 1（1 在未来位置 13 出现，距离 11）；访问 3 时淘汰 6（6 未来在位置 17 才出现，最远）等等。

7.3.2 FIFO（先进先出）

原理：淘汰最早调入内存的页面（认为是"最旧"的页面）。实现简单，用一个队列记录调入顺序即可。

依据：先调入的页面可能已经用完了。

缺点：

Belady 异常（必考）：分配的页框数增加，缺页次数反而可能不减反增（违反常识）；
没有考虑页面的使用情况，可能淘汰仍在使用的页面。

Belady 异常示例：

引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

内存=3 框	1	2	3	4	1	2	5	1	2	3	4	5
框1	1	1	1	4	4	4	5	5	5	5	5	5
框2		2	2	2	1	1	1	1	1	3	3	3
框3			3	3	3	2	2	2	2	2	4	4
缺页?	×	×	×	×	×	×	×			×	×	×

缺页次数 = 9，缺页率 = 9/12。

内存=4 框	1	2	3	4	1	2	5	1	2	3	4	5
框1	1	1	1	1	1	1	5	5	5	5	4	4
框2		2	2	2	2	2	2	1	1	1	1	5
框3			3	3	3	3	3	3	2	2	2	2
框4				4	4	4	4	4	4	3	3	3
缺页?	×	×	×	×			×	×	×	×	×	×

缺页次数 = 10，缺页率 = 10/12。

结论：4 框比 3 框的缺页率反而更高（10/12 > 9/12），这就是 Belady 异常。

重要结论：FIFO 是唯一会出现 Belady 异常的常用置换算法；OPT、LRU、Clock 等都满足"栈性质"（stack property），即分配的页框越多缺页率不会上升。

7.3.3 LRU（最近最少使用）

原理：淘汰最近一次访问距当前时间最长的页面。即"过去最久没用的页面，未来也最可能不被用"。

实现：用栈（stack）。当一个页面被访问时，将其从栈中取出（如果存在），再压到栈顶。栈顶是最新访问的，栈底是 LRU 页（即下一次该被淘汰的）。

性质：LRU 满足栈性质（Stack Property）：n 个页框的 LRU 内存内容是 n+1 个页框 LRU 内存内容的子集。即增加页框数，缺页率不会上升。

LRU 缺页率计算：

引用串：6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 6, 0, 1，分配 3 个页框。

访问	6	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	6	0	1
框1	6	6	6	2	2	2	2	4	4	4	0	0	0	1	1	1	1	6	6	6
框2		0	0	0	0	0	0	0	0	3	3	3	3	3	3	0	0	0	0	0
框3			1	1	1	3	3	3	2	2	2	2	2	2	2	2	2	2	2	1
缺页?	×	×	×	×		×		×	×	×	×			×		×		×		×

缺页次数 = 12，缺页率 = 12/20 = 60%。

注意：LRU 在本例中缺页率反而比 OPT 高（12 > 9），但比 FIFO 通常更低。LRU 缺页率与 OPT 缺页率之间的差，可以衡量算法与最优算法的差距。

7.3.4 NUR / Clock（最近未用）

LRU 思想很好，但需要维护精确的时间戳，开销太大。NUR（Not Used Recently） 是 LRU 的近似：

原理：为每页增加一个访问位（引用位）r。访问该页时置 r=1；系统定时（如每次时钟中断）将所有 r 清 0。淘汰时选择 r=0 的页淘汰。

Clock 算法（时钟算法，又称 Second Chance 的变种）：

将所有页框组织成一个环形链表（钟面），有一个指针指向当前位置。需要淘汰时：

从指针所指位置开始检查；
若当前页面 r=0 → 直接淘汰；
若 r=1 → 置 r=0，指针顺时针移动到下一页；
重复 2-3 直到找到一个 r=0 的页面。

Clock 与 Second Chance 的区别：两者淘汰效果基本相同，但 Clock 算法直接利用页表中的引用位，外加一个指针，无需额外链表，速度更快、节省空间。

Clock 算法执行示意（访问第 18 页，指针最初指向框 12 即页 6，r=1）：

步骤	指针位置	该页 r 值	处理
初始	框 12（页 6, r=1）	1	r 清 0，指针移到框 23
	框 23（页 3, r=1）	1	r 清 0，指针移到框 51
	框 51（页 4, r=0）	0	淘汰页 4

7.3.5 改进的 Clock 算法

进一步考虑修改位 m（脏位，标识页面是否被修改过），形成 4 类页面：

r	m	类别	处理
0	0	最佳淘汰页	最近未访问且未修改，直接淘汰（无需写回）
0	1	次佳	最近未访问但被修改，淘汰前需写回
1	0	较差不淘汰	最近访问但未修改
1	1	最差不淘汰	最近访问且被修改

改进 Clock 算法分 4 轮扫描（PPT 给出 3 步流程）：

步骤 1：从指针当前位置开始扫描，找第一个 r=0 且 m=0 的页面，淘汰；本次扫描不修改任何 r 位。
步骤 2：若步骤 1 失败，再次从原位置扫描，找第一个 r=0 且 m=1 的页面；同时将扫描过的页面的 r 位清 0。
步骤 3：若步骤 2 失败，指针回到原位置；由于步骤 2 已经把所有 r=1 的页面置 0，重新执行步骤 1 必能找到 r=0,m=0 的页面；若仍找不到则再次执行步骤 2，此次一定成功。

最优性证明：经过两轮扫描，所有 r=1 的页面 r 都已被清 0，第 3 轮必然能找到 r=0,m=0 或 r=0,m=1 的页面。

7.3.6 LFU（最不经常使用）

原理：淘汰访问次数最少的页面。依据是"活跃访问页面访问次数应该较大"。

实现：每页一个计数器，调入时清 0，访问时增 1；淘汰选计数器最小者。

缺点：

前期使用多但之后不再使用的页面（如初始化代码）计数器很大，难换出；
刚调入的新页面计数器小，可能被错误换出。

7.3.7 MFU（最经常使用）

原理：淘汰访问次数最多的页面。依据是"已经用得最多的页面可能已经用完了"。

缺点：有些程序段（系统库、错误处理代码）在整个程序运行中都要使用，MFU 会错误地淘汰它们。

7.3.8 二次机会（Second Chance）

原理：淘汰装入最久且最近未被访问的页面。即在 FIFO 队列的基础上检查访问位：若队首页 r=0 则淘汰；若 r=1 则清 0 并放到队尾（相当于给它"第二次机会"）。

与 Clock 的关系：本质相同，区别仅在数据结构 —— Second Chance 用链表（额外空间、摘/入链慢），Clock 用环形 + 指针（直接用页表 r 位，省空间、速度快）。

7.3.9 各种置换算法对比表

算法	思路	缺页率	实现难度	备注
OPT	淘汰未来最远才用	最低（基准）	不可能实现	理论参考
FIFO	淘汰最早调入	较高	极简（队列）	Belady 异常
LRU	淘汰最近最久未用	接近 OPT	较高（栈/时间戳）	满足栈性质
Clock	NUR + 环形指针	接近 LRU	中	实用
改进 Clock	Clock + 脏位	优于 Clock	中	实用
LFU	淘汰访问最少	不稳定	中	计数器
MFU	淘汰访问最多	差	中	几乎不用

7.4 抖动（Thrashing）与工作集

7.4.1 抖动现象

定义：如果一个进程在运行中频繁地发生缺页，以致于大部分 CPU 时间都用于处理缺页中断而非执行用户指令，则称该进程处于抖动（颠簸）状态。

形象描述：页面在内存与外存之间来回频繁换入换出，看似在"剧烈抖动"，但实际有效工作几乎为零。

原因：

分给进程的物理页框过少（小于其工作集），导致频繁缺页；
置换算法不合理，例如 FIFO；
多个进程竞争内存（多道程序度过高），总内存需求超出物理内存。

处理方法：

增加分给进程的物理页框数；
改进置换算法（如用 LRU/Clock 替代 FIFO）；
降低多道程度，挂起部分进程。

思考题（PPT Slide 34）："在某些虚拟页式存储管理系统中，内存中总保持一个空闲的物理页架，这样做有什么好处？"

答：保证缺页中断处理时立即有空闲页框可用，无需临时置换，缩短缺页中断处理时间；同时降低抖动概率。但代价是内存少了一个可用页框，相当于"预留应急资源"。

7.4.2 工作集模型（Working Set Model）

工作集定义：进程在某段时间内所访问页面的集合，记为 WS(t, Δ)，其中：

t：当前时刻；
Δ（窗口尺寸）：考察的时间窗口长度（用访问次数或时间衡量）。

例如引用串 … 2 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 …，取 Δ=10，最近 10 次访问涉及 {5,7,1,6,2}，则 WS(t,Δ) = {5,7,1,6,2}。

Denning 原则：为使程序有效运行，工作集应能全部装入内存。若分配给进程的页框数 < 工作集大小，则必然频繁缺页（即抖动）。

工作集与 Δ 的关系：

Δ 太小：活动页面不能全部装入，缺页率高；
Δ 太大：内存浪费，且反应迟钝；
经验值（Madnick & Donovan）：Δ ≈ 10000 次访内。

工作集大小估算（PPT Slide 38 给出的递推公式）：

\tau_{n+1} = \alpha \cdot W_n + (1 - \alpha) \cdot \tau_n

其中：

W_n = 第 n 个 Δ 周期内实际工作集大小；
τ_n = 第 n 个 Δ 周期工作集估算值；
α 通常取 0.5。

实现：在页表中增加"访问位"。Δ 开始时全部清 0；Δ 期间访问置 1；Δ 结束时访问位为 1 的页面即为该 Δ 周期的工作集。

7.4.3 缺页率反馈模型（PFFB）

原理：根据缺页率动态调整分配给进程的页框数。

缺页率 ≥ 上界阈值 → 内存页面少 → 增加页框；
缺页率 ≤ 下界阈值 → 内存页面多 → 减少页框。

缺页率公式：

\text{缺页率} = \frac{\text{缺页次数}}{\text{访问内存总次数}}

这是另一种动态控制内存分配的方法（与工作集异曲同工，工作集是基于"过去一段时间活跃页面"，PFFB 是基于"最近缺页频率"）。

7.5 虚拟段式存储系统

7.5.1 基本思想

与虚拟页式类似，但基本单位是段（变长）。进程运行前全部装入外存，部分装入内存；访问不在内存的段时，发生缺段中断。

7.5.2 地址映射

逻辑地址 (s, d)
   │
   ▼
查快表得 (b', l')
   ├─ 命中 ──→ 0≤d≤l'-1 越界检查 → b'+d 得物理地址
   └─ 未命中 ─→ 由 (b, s) 查段表得 (b', l')
                  ├─ 段在内存 ──→ 修改快表
                  └─ 缺段 ──→ 缺段中断：紧凑够?→紧凑;→选段淘汰→写回→读入→修改段表和快表
   ※ s 越界 → 越界中断

注意：虚拟段式要解决"变长段调入"的复杂问题 —— 当内存剩余空间不够装入新段时，可能需要紧凑（compaction） 操作，把分散的空闲区合并成连续大区。这与虚拟页式"固定大小页框"截然不同，是虚拟段式实现起来更复杂的主要原因。

7.5.3 动态链接（Dynamic Linking）

类型	时机	由谁完成
静态链接	装入/运行前	链接程序（linker）
动态链接	运行时	操作系统

静态链接的缺点：

链接时间长；
目标代码长（即使不用的段也被链入）；
不使用的链接段占据空间。

动态链接的实现（Multics 为例）：

段名-段号对照表：每进程一个，记录"符号名 → 段号"；
符号表：每段一个，记录段内"符号 → 段内地址"；
段形式：符号表 + 目标代码（或数据）。

执行时遇到间接寻址指令且链接位 L=1，触发链接中断：

由 D 取出符号地址；
查段名-段号对照表：
- 已分配段号 → 取段号查段表 → 找段内地址 → 填入 (段号,段内地址) → D，置 L=0（链接完成）；
- 未分配段号 → 从外存/文件读入该段 → 分配段号 → 填写对照表 → 重新进入步骤 2。

7.5.4 动态链接与共享的矛盾

矛盾点：

动态链接：要修改代码（修改间接字 D 和 L 位）；
段的共享：要求代码是纯代码（pure code），即代码执行过程中不会被修改。

解决方法：把共享段拆成纯段（共享）和杂段（私有）。纯段用于共享执行；杂段存放可变数据（如全局变量），每个进程一份。

7.6 虚拟段页式存储系统

7.6.1 为什么要段页式

段式便于动态链接、共享、动态增长；页式便于内存管理、无外碎片。把两者结合：先分段再分页，就是段页式 —— 兼顾段式的灵活和页式的简洁。

7.6.2 所需数据结构

表	数量	内容
段表	每进程 1 个	段号 → (页表长度, 页表首址) 等
页表	每段 1 个	逻辑页号 → 页框号
共享段表	系统 1 个	段名、(页表长度, 页表首址)、扩充标志、共享计数
段名-段号对照表	每进程 1 个	段名 → 段号

7.6.3 寄存器

段表长度寄存器 l（保存当前进程段表长度）
段表首址寄存器 b（保存当前进程段表首址）
快表（TLB）

7.6.4 地址映射

逻辑地址 (s, p, d) → 物理地址 (f, d)

(s, p, d)
   │
   ▼
查快表 (s, p) → f
   ├─ 命中 ──→ 形成物理地址 (f, d)
   └─ 未命中 ─→ 由 (s, b) 查段表 → (b', l')
                  ├─ 0≤s≤l-1 越界检查 ─→ 不通过：越界中断
                  └─ 通过 → 由 (b', p) 查页表
                       ├─ 0≤p≤l'-1 越界检查 ─→ 不通过：越界中断（可扩展则扩展该段）
                       ├─ 页在内存 → (s,p,f) 入快表
                       └─ 缺页 → 缺页中断
   ※ 间接寻址且 L=1 → 链接中断
   ※ 访问权限不匹配 → 越权中断

7.6.5 中断类型

中断	处理
链接中断	见 7.5.3；共享段时共享计数加 1
缺页中断	调入页 → 更新页表/总页表
越界中断（段号）	错误处理
越界中断（页号）	若可扩展则扩展该段（增页）并修改页表/段表；否则错误处理
越权中断	错误处理

7.6.6 各种虚拟存储管理比较

特性	虚拟页式	虚拟段式	虚拟段页式
地址空间	一维	二维	二维
存储分配	简单	复杂	简单
存储碎片	无	有（外碎片）	无
存储共享	不便	方便	方便
存储保护	不便	方便	方便
动态扩充	不可	可以	可以
动态连接	不可	可以	可以

7.7 Linux 存储管理（系统举例）

7.7.1 物理存储管理

三级页表：页目录 → 页中间目录 → 页表 → 页内偏移；
伙伴堆算法（Buddy Heap）：管理空闲物理页框。

7.7.2 虚拟存储管理

请求调页（demand paging）；
无预调（no pre-paging）；
无工作集（no working set）；
页守护进程 kswapd：每秒运行一次，保持内存中有足够的空闲页；
刷新守护进程 bdflush：周期性唤醒，将脏页写回磁盘。

7.7.3 Buddy Heap 伙伴堆算法（必考）

核心思想：把内存按 2 的幂次大小组织成块组。

块组 i：由 2^i 个连续页框组成的空闲区；
共 10 个块组（i = 0,1,…,9），对应 1,2,4,…,512 个页框；
每个块组维护一个空闲链表和一个位图。

分配算法（申请 fn 个页框）：

找到满足 2^(i-1) < fn ≤ 2^i 的块组 i；
若块组 i 有空闲块 → 直接分配一个；
否则找更高块组 j（2^j ≥ 2^i），将 2^j 拆成 2^i + 2^(j-i)（按 2 的整数次幂拆分）；
修改位图。

释放算法：

释放 2^i 个页框；
检查相邻块是否是伙伴（buddy）：
- 两块大小相同（都是 2^i 个页框）；
- 物理地址连续；
- 后一块的最后页框编号 + 1 是 2^(i+1) 的整数倍；
若伙伴也空闲 → 合并为 2^(i+1) 大块；递归向上合并；
修改位图。

位图规则（PPT Slide 71）：

一对 buddy 中：若一个空闲、另一个全部或部分占用 → 位图位置 1；
若都空闲或都被全部或部分占用 → 位图位置 0。

内部碎片问题：申请 17 个页框时按 Buddy 算法要分配 32 个页框，浪费 15 个页框。Linux 用 slab 分配器（second memory allocator）将剩余小空闲块单独管理；vmalloc（third memory allocator）用于分配物理不连续的内存。

7.7.4 分配示例

申请 fn=3，2^1 < 3 ≤ 2^2，所以在块组 2 分配 4 个页框（页框 8,9,10,11）。

7.8 Windows Vista 存储管理（系统举例）

7.8.1 进程地址空间

32 位虚拟地址，寻址 4GB；
用户空间：低地址 2GB；
系统空间：高地址 2GB。

7.8.2 存储管理方式：虚拟页式

页面尺寸：4KB ~ 64KB；
可交换页面：用户空间所有页均可换出；系统空间部分页（如 DLL）也可换出；
页表结构：二级页表（页目录 + 页表）。

32 位地址划分：

|  PDE (10位)  |  PTE (10位)  |  d (12位)  |

7.8.3 存储共享及保护

原型页表（Prototype Page Table）：用于共享页。共享页的页表项不直接指向物理页框，而是指向原型页表，原型页表的表项才指向实际物理页框。
保护单位：以页为单位。访问类型有只读、读写、执行、不可操作、写时复制（copy-on-write）等。

7.8.4 内存优先级与页面调度

内存按 0~7 优先级组织：

高优先级：进程工作集，活跃使用；
低优先级：待机列表（standby list）、已修改页列表等。

进程虚拟页面状态：

状态	含义
闲置（free）	未分配内存；访问将导致缺页
预定（reserved）	已分配但不可立即使用；需解除预订才能用
确认（committed）	已分配且可访问

二、考点总结

考点 1：虚拟存储器的定义与四大特征

内容：虚拟存储器是具有请求调入和置换功能，能从逻辑上扩充内存容量的存储系统。四大特征：多次性、对换性、虚拟性、离散性。
考查方式：选择、填空、简答。
可能的题目：
1. 选择题：虚拟存储器的特征不包括（）。A. 多次性 B. 对换性 C. 一次性 D. 离散性。答案：C（一次性是常规存储管理的特征，与虚拟存储的多次性对立）。
2. 简答题：为什么离散性是虚拟性的前提？答案：因为只有离散分配（分页/分段），进程的多个页面才可能不连续地放在内存和外存，从而实现部分装入；如果必须连续分配，则装入部分页面到不连续区域是做不到的。

考点 2：缺页中断与一般中断的区别

内容：缺页中断发生在执行指令过程中（如取操作数/取指令阶段），由硬件陷入 OS 缺页中断处理程序；处理完成后必须重新执行该指令（不是返回下一条）。一般中断处理完返回下一条指令即可。
考查方式：选择、简答。
可能的题目：
1. 选择题：缺页中断处理完成后应（）。A. 返回下一条指令 B. 重新执行被中断指令 C. 终止进程 D. 跳过本指令。答案：B。

考点 3：OPT 算法（最佳置换）

内容：淘汰将来最长时间以后才被使用的页面。不可实现，但缺页率最低，常作为基准。
考查方式：计算题、简答。
可能的题目：
1. 计算题：引用串 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，分配 4 个页框，用 OPT 计算缺页次数。解：访问 7,0,1,2 → 缺页 4 次（填满）；访问 0 命中；访问 3 → 淘汰未来最远才用的：未来用到 4、2、3、0、3、2、1、2、0、1、7、0、1，位置 17 才出现 7，最远。等等。最优淘汰策略下缺页次数约为 6~8 次（具体需逐步推算）。

考点 4：FIFO 算法与 Belady 异常

内容：FIFO 用队列实现，淘汰最早调入的页面。唯一会出现 Belady 异常（页框增加、缺页不减反增）。
考查方式：计算题（必考）、简答。
可能的题目：
1. 计算题：引用串 1,2,3,4,1,2,5,1,2,3,4,5，FIFO、3 框和 4 框的缺页率。解：参见 7.3.2 节，3 框缺页 9 次（9/12），4 框缺页 10 次（10/12），出现 Belady 异常。
2. 简答题：哪些置换算法不会出现 Belady 异常？为什么？答案：OPT、LRU、Clock 等都满足栈性质（n 框内容 ⊆ n+1 框内容），增加页框只会减少缺页。FIFO 是唯一常见会 Belady 异常的算法。

考点 5：LRU 算法与栈性质

内容：LRU 淘汰最近最久未访问的页面。用栈实现，栈顶最新、栈底最久。满足栈性质，无 Belady 异常。
考查方式：计算题、简答。
可能的题目：
1. 计算题：引用串 6,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,6,0,1，3 框，LRU 缺页率。解：参见 7.3.3 节，缺页 12 次，缺页率 12/20 = 60%。

考点 6：Clock 算法

内容：用页表引用位 r + 环形指针实现。r=0 淘汰；r=1 清 0 后移指针。
考查方式：分析题、计算题。
可能的题目：
1. 分析题：给定 8 个页框的 r 位状态，画出连续 3 次缺页的 Clock 淘汰过程。解：从指针所指位置开始，按顺时针方向扫描；遇到 r=1 清 0 后跳过；遇到 r=0 直接淘汰。详细过程参见 7.3.4 节示例。

考点 7：改进 Clock 算法（4 类页面、3 步扫描）

内容：考虑访问位 r 和修改位 m，分 4 类：最佳 (0,0)、次佳 (0,1)、较佳 (1,0)、最差 (1,1)。3 步流程：先找 (0,0) 不改 r；再找 (0,1) 清 r；最后回到起点必找到。
考查方式：分析题。
可能的题目：
1. 分析题：8 个页框，r、m 状态给定，访问新页，画出改进 Clock 淘汰过程。解：参见 7.3.5 节三步流程。

考点 8：LFU 与 MFU

内容：LFU 淘汰访问次数最少的；MFU 淘汰访问次数最多的。LFU 缺点是前期热点页难换出、新页易被错误淘汰；MFU 缺点是会误淘汰全程使用的代码。
考查方式：选择、简答。
可能的题目：
1. 选择题：下列说法正确的是（）。A. LFU 不会淘汰刚开始使用的页 B. MFU 适用于全程都用的代码 C. LFU 用计数器实现 D. MFU 是最优置换算法。答案：C。

考点 9：抖动（Thrashing）

内容：频繁缺页导致 CPU 时间大量浪费在中断处理上的现象。原因：页框过少、置换算法差、多道度过高。处理：增加页框、改进算法、降低多道度。
考查方式：选择、简答。
可能的题目：
1. 简答题：系统出现抖动时有哪些处理方法？答案：① 增加物理页框数（或减少进程数）；② 改用更优置换算法（如 LRU）；③ 利用工作集模型给活跃进程分配足够页框；④ 挂起部分进程；⑤ 调度时优先调度缺页率低的进程。

考点 10：工作集模型

内容：WS(t,Δ) 是进程在 [t-Δ, t] 期间访问的页面集合。Denning 原则：工作集应能全部装入内存。Δ 经验值约 10000 次访内。
考查方式：选择、计算（工作集大小估算）。
可能的题目：
1. 计算题：引用串 … 2 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 …，Δ=10，求当前工作集。解：最近 10 次访问：7,7,7,7,5,1,6,2,2,1 → 涉及页面 {1,2,5,6,7}。WS = {1,2,5,6,7}，大小 = 5。

考点 11：请求调页 vs 预调页

内容：请求调页（demand paging）在缺页时调入；预调页（prepaging）在缺页前提前调入。预调必须辅以请调（兜底）。
考查方式：选择、简答。
可能的题目：
1. 简答题：为什么预调页必须辅以请求调页？答案：预调基于对未来的预测，而预测不可能 100% 准确；一旦预测错误（如调入的页实际不被访问）就会浪费 I/O，且真正要用到的页还是得靠请求调入，故二者必须配合。

考点 12：动态链接 vs 静态链接

内容：静态链接由 linker 在运行前完成，缺点是慢、长、不必要的段被链入；动态链接由 OS 在运行时完成，可节省空间、按需链接，但实现复杂、需"链接中断"处理。
考查方式：选择、简答。
可能的题目：
1. 简答题：动态链接与段的共享有什么矛盾？如何解决？答案：矛盾是动态链接会修改代码中的间接字（修改是杂段），而共享要求纯代码。解决方法是把共享段拆为纯段（共享执行）和杂段（私有数据，每进程一份）。

考点 13：虚拟段式 vs 虚拟页式 vs 虚拟段页式比较

内容：参见 7.6.6 节对比表。
考查方式：选择、简答。
可能的题目：
1. 选择题：便于动态连接和共享的虚拟存储管理方式是（）。A. 虚拟页式 B. 虚拟段式 C. 虚拟段页式 D. 以上都不能。答案：B、C。
2. 简答题：虚拟段页式相比虚拟段式和虚拟页式各有什么优点？答案：相比虚拟段式 —— 无外碎片、内存管理简单；相比虚拟页式 —— 便于动态链接、共享、动态扩充。

考点 14：Linux 伙伴算法（Buddy Heap）

内容：按 2 的幂组织空闲块组。分配时找满足 2^(i-1)<fn≤2^i 的块组 i，不够就拆分更高块组；释放时检查伙伴条件（大小相同、物理连续、后块最后页框号+1 是 2^(i+1) 倍数）并合并。
考查方式：计算题（分配/释放过程）、简答。
可能的题目：
1. 计算题：伙伴堆中，已知初始空闲区 64 页框；依次 req(8)、req(8)、req(4)、rel(8)、rel(8)，画出每次操作后的空闲区状态。解：
  - 初始：64 页框空闲；
  - req(8)：从 64 中分出 8，余 56；56 又拆分（32+24→32+16+8）→ 空闲 {32,16,8}，分配 8；
  - req(8)：从 {32,16,8} 中分出 8 即可（取 16 拆分）→ 空闲 {32,16,8} 中已有 8，直接分配；
  - req(4)：从 {16} 拆分出 8，将 8 拆分出 4 → 空闲 {32,16,8,4} 中分配 4；
  - rel(8)：把 8 放回 → 若有伙伴则合并；空闲 {32,16,8,8,4} → 两 8 合并为 16 → {32,16,16,4}；
  - rel(8)：把 8 放回 → 空闲 {32,16,16,4,8} → 与原 16 合并？需要看伙伴关系。

考点 15：地址变换综合题（常考大题）

内容：给定逻辑地址、页大小、页表内容、置换算法，求物理地址。
考查方式：计算题（必考大题）。
可能的题目：
1. 2010 年考研题（PPT Slide 31-33）：某虚拟页式系统，进程空间和内存空间都是 64KB，页长 1KB；某进程 6 个页（页号 0~5），分配 4 个页框，框号 5,12,8,3 装入页 0,2,3,5；280 时刻访问逻辑地址 13B7H。 (1) 逻辑页号？ (2) 若用 FIFO 置换，物理地址？ (3) 若用 CLOCK 置换，物理地址？
  
  解：
  - (1) 13B7H = 0001 0011 1011 0111B；页长 1KB = 2^10 → 后 10 位是页内地址 0FB7H？不对，应该是最后 10 位：1011 0111 → 11 1011 0111B = 0 1110 1101 11 取后 10 位 = 11 1011 0111 = 0x3B7？等等，原题是"后 10 位为页内地址"。13B7H = 0001 0011 1011 0111B，共 16 位；前 6 位为页号 = 000100 = 4，后 10 位为页内地址 = 11 1011 0111 = 0x3B7。
  - 进程页号 0,1,2,3,4,5；当前内存中装入页 0,2,3,5（缺 1,4）；访问页 4 → 缺页。
  - (2) FIFO：原 4 个页框装入顺序未知，按 FIFO 淘汰最先进入的（假设是页 0）→ 淘汰页 0，页 4 装入框 5（替换页 0）。等等，按 PPT 答案："4 号页不在内存，发生缺页中断，按 FIFO 置换算法，应置换第 5 页，所得页框号 3"。
  - 物理地址：原页 0 的框号 5，页 5 的框号 3。FIFO 淘汰页 5（最后装入或最先装入的，需根据入队顺序），页 4 替换框 3，物理地址 = 00 0011 + 11 1011 0111 = 0000 1111 1011 0111B = 0FB7H。
  - (3) CLOCK：原页框 5（页 0）的访问位为 0（设初始 r=0），则淘汰页 0 → 页 4 装入框 5 → 物理地址 = 0001 0101 + 11 1011 0111 = 0001 0111 1011 0111B = 17B7H。

考点 16：缺页率计算综合题

内容：给定访问序列、页框数、置换算法，求缺页次数和缺页率。
考查方式：计算题。
可能的题目：
1. 例题：引用串 1,2,3,4,1,2,5,1,2,3,4,5；3 个页框 FIFO 缺页率？解：参见 7.3.2 节，缺页 9 次，缺页率 = 9/12 = 75%。

考点 17：有效访问时间（EAT）计算

内容：EAT = 命中时的访问时间 + 缺页率 × 缺页中断处理时间。
考查方式：计算题（常考）。
可能的题目：
1. PPT Slide 85 题：请求分页系统中，页表保存在寄存器。若有可用空页/被置换页未修改，处理缺页中断需 8ms；若被置换页已修改，需 20ms（多写回外存时间）。一次内存存取 1ns。70% 被置换页被修改。为保证 EAT ≤ 12ns，求最大缺页率 p。解：设缺页率 p，平均缺页处理时间 = 0.7×20 + 0.3×8 = 14 + 2.4 = 16.4 ms = 16,400,000 ns。 EAT = 1 + p × 16,400,000 ≤ 12 p × 16,400,000 ≤ 11 p ≤ 11/16,400,000 ≈ 6.7 × 10⁻⁷（约百万分之 0.67）
2. PPT Slide 86 题：LRU 请求分页系统，页面 4KB，内存访问 100ns/次，快表访问 20ns/次，缺页中断 25ms/次。30KB 进程进入系统，分配 3 块，访问序列 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1（20 次访问），快表命中率 20%。求平均有效访问时间。解：
  - 先算 LRU 缺页率：参见 7.3.3 节 LRU 示例，3 框 20 次访问中缺页 12 次 → 缺页率 p = 12/20 = 0.6；
  - 但本题中快表命中率 20%，意味着 80% 需访问内存页表；
  - 命中快表：20ns；
  - 未命中快表 + 命中内存页 + 命中内存数据：100ns + 100ns = 200ns；
  - 缺页时：缺页中断 25ms = 25,000,000 ns；
  - 平均：EAT = 0.2×20 + 0.8×200 + 0.6×25,000,000 = 4 + 160 + 15,000,000 ≈ 15,000,164 ns ≈ 15ms（绝大多数时间花在缺页中断处理上）

考点 18：缺页率反馈模型（PFFB）

内容：根据缺页率上下界阈值动态调整进程页框分配：缺页率高 → 加页框；缺页率低 → 减页框。
考查方式：简答、选择。
可能的题目：
1. 选择题：PFFB 模型调整页框数的依据是（）。A. 工作集大小 B. 缺页率 C. 进程优先级 D. 进程长度。答案：B。

考点 19：内存保护与越界/越权中断

内容：段式有段号越界和段内偏移越界、越权中断；页式有页号越界；段页式综合。
考查方式：选择、填空。
可能的题目：
1. 填空题：段页式系统中可能发生的中断类型有、、、。答案：链接中断、缺页中断、越界中断（段号或页号）、越权中断。

考点 20：Windows Vista 段共享（原型页表）

内容：共享页的页表项不直接指向物理页框，而是指向原型页表，原型页表项才指向物理页框。这样多个进程可共享同一物理页。
考查方式：选择、简答。
可能的题目：
1. 简答题：Windows Vista 中共享页的页表项为什么不直接指向物理页框？答案：通过原型页表实现共享。当物理页框号变化时（如换出换入），只需修改原型页表的对应项，所有引用该原型的进程页表项都自动跟随，避免每个进程都修改。

考点 21：Linux 虚拟存储特征

内容：三级页表、请求调页、无预调、无工作集、kswapd 每秒运行一次保持空闲页、bdflush 周期性刷脏页。
考查方式：填空、选择。
可能的题目：
1. 填空题：Linux 的页守护进程是 ____，刷新守护进程是 ____，虚拟存储采用 （请调/预调），是否有工作集？（有/无）。答案：kswapd、bdflush、请调、无。

附录：典型计算题汇总

计算题 1：FIFO + Belady 异常验证

题目：引用串 1,2,3,4,1,2,5,1,2,3,4,5，分别用 3 个和 4 个页框执行 FIFO，求缺页次数。

解（参见 7.3.2）：

3 框：缺页 9 次，缺页率 9/12；
4 框：缺页 10 次，缺页率 10/12；
页框多反而缺页多 → Belady 异常。

计算题 2：LRU 缺页率

题目：引用串 6,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,6,0,1，3 个页框，LRU。

解：参见 7.3.3，缺页 12 次，缺页率 12/20 = 60%。

计算题 3：OPT 缺页率（理论下限）

题目：引用串 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，3 个页框，OPT。

解（参考答案）：

访问	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
框1	7	7	7	2	2	2	2	2	2	2	2	2	2	1	1	1	1	1	1	1
框2		0	0	0	0	0	0	4	4	4	0	0	0	0	0	0	0	7	7	7
框3			1	1	1	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3
缺页?	×	×	×	×		×		×			×			×				×

缺页 9 次，缺页率 9/20 = 45%（最低）。

计算题 4：Clock 算法

题目：8 个页框，r 位依次为 1,1,0,0,1,0,0,1（顺时针），访问新页，画 Clock 淘汰过程。

解：

指针指向第一个 r=1 → 清 0，指针后移；
第二个 r=1 → 清 0，指针后移；
第三个 r=0 → 淘汰。

共扫描 3 个位置才找到淘汰页。

计算题 5：改进 Clock 算法

题目：8 个页框 (r,m) 依次为 (1,1),(1,1),(1,0),(1,0),(1,0),(0,1),(0,1),(1,0)，访问新页，画改进 Clock 过程。

解：

步骤 1：从指针起找 (0,0)，没有；扫描一遍不修改 r；
步骤 2：再次扫描找 (0,1)，扫描过程中把所有 r=1 清 0；
- 扫描 (1,1)→r 清 0 → (0,1)；
- 扫描 (1,1)→r 清 0 → (0,1)（第二个）；
- 扫描 (1,0)→r 清 0 → (0,0)；
- 扫描 (1,0)→r 清 0 → (0,0)；
- 扫描 (1,0)→r 清 0 → (0,0)；
- 扫描到 (0,1) → 淘汰（这是第 6 个位置）。
（步骤 3 在此例中不需要，步骤 2 已成功）

计算题 6：2010 考研题（地址变换）

参见考点 15。答案：

(1) 逻辑页号 4；
(2) FIFO 淘汰页 5，物理地址 0FB7H；
(3) CLOCK 淘汰页 0，物理地址 17B7H。

计算题 7：有效访问时间

参见考点 17。答案：

题 1：p ≤ 6.7 × 10⁻⁷；
题 2：EAT ≈ 15,000,164 ns ≈ 15 ms。

计算题 8：工作集大小

题目：引用串 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6，Δ=5，求最近 5 次访问的工作集。

解：最近 5 次访问：3,2,1,2,3 → 涉及页面 {1,2,3}。WS = {1,2,3}，大小 = 3。

计算题 9：伙伴堆分配

题目：伙伴堆中空闲区大小 256 页框；依次 req(50), req(30), req(20)。

解：

req(50)：2^5 < 50 ≤ 2^6 = 64，分配 64 页框；剩余 256-64=192 → 拆分为 128+64 → 128 入块组 7，64 已分配；
req(30)：2^4 < 30 ≤ 2^5 = 32，从块组 7 拆出 64，64-32=32 入块组 5，分配 32 页框；
req(20)：2^4 < 20 ≤ 2^5 = 32，从块组 5 分配 32 页框（块组 5 还有一块 32 即可）。
最终空闲区：块组 7 = 128 页框；块组 5 空（已分配）；其他为空。

本章核心要点速记：

虚拟存储四大特征：多次性、对换性、虚拟性、离散性。
缺页中断处理后重新执行该指令。
OPT 不可实现但缺页率最低（理论基准）。
FIFO 唯一可能 Belady 异常；LRU/OPT/Clock 等都满足栈性质。
改进 Clock 分 4 类页面、3 步扫描，前 r 不清、后 r 清 0。
抖动 = 频繁缺页；工作集应能全部装入内存。
动态链接用"间接字 + 链接位 L"，L=1 触发链接中断。
Linux 伙伴算法按 2 的幂组织；申请 fn 满足 2^(i-1)<fn≤2^i 时从块组 i 取。
Windows 共享用原型页表。
有效访问时间 EAT = 1 + 缺页率 × 缺页中断开销（含置换、写回）。

47 KiB Raw Permalink Blame History Unescape Escape

第七章 虚拟存储管理