Appearance
虚拟内存：请求分页、页面置换算法
概念
虚拟内存（virtual memory）指只把程序当前用到的部分装入内存，其余留在磁盘上，需要时再调入——它让程序"看起来"拥有比物理内存大得多的地址空间。
一句话说清它是什么：虚拟内存就是"把磁盘当内存的延伸来用"——arch/13-virtual.md 从硬件侧讲过"主存当 Cache、磁盘当主存"的那套机制，本章从操作系统侧讲"谁来搬、按什么规则搬"。
⚠️ 三大特征的定位：虚拟内存属于内存管理四功能里的"内存空间的扩充"（回顾 os/20-contiguous.md 的那张四功能表），它与"分配回收""地址转换""内存保护"是三件不同的事。
text
虚拟地址空间(每个进程都以为自己独占)
┌────────────────────────────────────────┐
│ 0 ~ 4GB, 连续、巨大, 程序眼里的样子 │
└───────────────────┬────────────────────┘
│ 只有"用到的页"才真在内存
▼
┌────────────────────────────────────────┐
│ 物理内存 (几 GB) │
└───────────────────┬────────────────────┘
│ 其余页留在磁盘的"页文件/交换区"
▼
┌────────────────────────────────────────┐
│ 磁盘 (几百 GB) │
└────────────────────────────────────────┘原理
一、局部性原理（虚拟内存能成立的基石）
没有局部性，虚拟内存的性能会灾难性地崩溃——因为磁盘比内存慢 5 个数量级。
| 局部性 | 含义 | 例子 |
|---|---|---|
| 时间局部性 | 刚被访问过的，很可能马上又被访问 | 循环体、反复调用的函数 |
| 空间局部性 | 刚被访问过的地址附近，很可能马上被访问 | 数组顺序遍历、顺序执行的指令 |
⚠️ 收益有多大：一个 16 MiB 的程序，一次运行实际只触碰 264 KiB（
arch/13-virtual.md里的锚点）——"只用 1.6%"，这就是虚拟内存可行的直接证据。
二、请求分页的页表项扩充
请求分页（demand paging）在 os/21-paging.md 的页表项基础上，再增加四个字段：
| 字段 | 作用 |
|---|---|
| 状态位 / 有效位 P | 该页是否在内存（= 0 → 缺页） |
| 访问字段 A | 本页被访问过没有 / 最近被访问的次数（给 LRU、CLOCK 用） |
| 修改位 / 脏位 M | 本页是否被写过（写过 → 换出时必须写回磁盘） |
| 外存地址 | 该页在磁盘上的位置（换出时要知道往哪写、换入时要知道从哪读） |
⚠️ 为什么缺页率必须压到
以下：主存 100 ns 对磁盘 10 ms，相差 5 个数量级——下面例 4 会把这条账算清。
三、缺页中断处理流程
text
①访问某页, 硬件查页表发现有效位 = 0 -> 产生"缺页中断"(fault)
②操作系统接管: 查该页的外存地址
③内存里还有没有空闲页框?
有 -> 直接用
无 -> ★ 按置换算法选一个"牺牲页"换出 (脏位=1 则写回磁盘)
④从磁盘把缺页读入页框 (★ 这一步极慢)
⑤修改页表项: 页框号 = 新位置, 有效位 = 1, 访问位置 1; 脏位清 0
⑥★ 返回后"重新执行那条指令" (不是执行下一条)⚠️ 三个易错口径：
- 缺页中断是"故障"（fault），不是"自陷"——处理完要"重执行当前指令"（
arch/13-virtual.md的"异常三型返回语义"讲过）。答成"执行下一条"直接错。- 缺页中断在"指令执行期间"产生，一条指令可能触发多次缺页（如
add A, B两个操作数都不在内存 → 两次缺页）。- "有否空闲页框"与"要不要置换"是两件事——有闲框就直接用，没闲框才走置换算法。
四、页面置换算法（本章最核心）
所有算法的任务都相同：内存满了、又缺页时，淘汰哪一页？ 引用串用下例的 20 次访问：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1。
| 算法 | 淘汰谁 | 能否实现 | 缺页数（3 帧 / 20 次引用） | 备注 |
|---|---|---|---|---|
| 最佳置换 OPT（Optimal） | 未来最长时间内不再被访问的那一页 | 不能（要预知未来） | 9 次（45%） | 理论下界，用来衡量其他算法 |
| 先进先出 FIFO | 最早进入内存的那一页 | 能，最简单 | 15 次（75%） | 有 Belady 异常 |
| 最近最久未使用 LRU | 最长时间没被访问的那一页（看过去） | 能，但要用栈或计数器 | 12 次（60%） | 属"栈算法"，无 Belady 异常 |
| 时钟 CLOCK / 简单时钟 | 按访问位循环扫描，遇到 A = 0 就淘汰 | 能，开销小 | 14 次（70%） | LRU 的近似，性能介于 FIFO 与 LRU 之间 |
| 改进型 CLOCK | 在 CLOCK 基础上把"未访问且未修改(A=0,M=0)"优先淘汰 | 能 | —— | 减少写回磁盘的次数 |
LRU 与 FIFO 的本质差别（一句话）：FIFO 看"你什么时候进来"，LRU 看"你什么时候被用过"。 所以FIFO 会把"刚进来但一直要用"的页冤枉地淘汰掉，LRU 不会。
⚠️ "栈算法"（stack algorithm）的含义：把引用串的"驻留集"看成随帧数增大而单调扩张的栈——LRU 与 OPT 都是栈算法，因此"帧数越多，缺页绝不会增加"。FIFO 不是，所以才会出现 Belady 异常。
五、Belady 异常
帧数增加，缺页反而更多——这是 FIFO 独有的丑陋行为。
最小反例（引用串 1 2 3 4 1 2 5 1 2 3 4 5）：
| 帧数 | FIFO 缺页次数 | 缺页率 |
|---|---|---|
| 3 帧 | 9 次 | 75.0% |
| 4 帧 | 10 次 | 83.3%（反而变差！） |
⚠️ 为什么 LRU/OPT 没有这个毛病：它们都是"栈算法"——把帧数从 3 加到 4，内存里永远保存着"3 帧时保存的那 3 页 + 1 页额外的"，不可能把原本装得下的页挤出去。FIFO 没有这个性质，所以帧数一变，被淘汰的可能完全换人。
六、分配策略与调入策略（三个必答问题）
| 问题 | 选项 | 说明 |
|---|---|---|
| 何时调入 | 预调页 / 请求调页 | 请求调页只在缺页时才调（主流）；预调页按局部性提前调 |
| 从何处调入 | 对换区 / 文件区 | 对换区（swap）比文件区快；被换出过的页下次从对换区调 |
| 如何分配页框 | 固定分配 / 可变分配 × 局部置换 / 全局置换 | 四个组合：固定+局部（最稳但最笨）、可变+全局（能救急但会影响别人）、固定+全局（不成立）、可变+局部（工作集法的思路） |
⚠️ "固定分配 + 全局置换"是自相矛盾的（全局置换意味着从别人那里拿页框，那就是"可变分配"了）——这个组合不能成立，是选择题常设的陷阱。
示例
例 1：三种置换算法在 20 次引用上的完整轨迹
引用串：
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1（共 20 次），3 个页框。
FIFO（先进先出，队尾进、队首出）：
| 次 | 引用 | 结果 | 页框（左 = 最早进入） |
|---|---|---|---|
| 0 | 7 | 缺页 | 7 − − |
| 1 | 0 | 缺页 | 7 0 − |
| 2 | 1 | 缺页 | 7 0 1 |
| 3 | 2 | 缺页 | 0 1 2 |
| 4 | 0 | 命中 | 0 1 2 |
| 5 | 3 | 缺页 | 1 2 3 |
| 6 | 0 | 缺页 | 2 3 0 |
| 7 | 4 | 缺页 | 3 0 4 |
| 8 | 2 | 缺页 | 0 4 2 |
| 9 | 3 | 缺页 | 4 2 3 |
| 10 | 0 | 缺页 | 2 3 0 |
| 11 | 3 | 命中 | 2 3 0 |
| 12 | 2 | 命中 | 2 3 0 |
| 13 | 1 | 缺页 | 3 0 1 |
| 14 | 2 | 缺页 | 0 1 2 |
| 15 | 0 | 命中 | 0 1 2 |
| 16 | 1 | 命中 | 0 1 2 |
| 17 | 7 | 缺页 | 1 2 7 |
| 18 | 0 | 缺页 | 2 7 0 |
| 19 | 1 | 缺页 | 7 0 1 |
FIFO 缺页 15 次，缺页率 15/20 = 75.0%。
LRU（最近最久未使用，命中也要"挪到最新端"）：
| 次 | 引用 | 结果 | 页框（左 = 最久未用） |
|---|---|---|---|
| 0 | 7 | 缺页 | 7 − − |
| 1 | 0 | 缺页 | 7 0 − |
| 2 | 1 | 缺页 | 7 0 1 |
| 3 | 2 | 缺页 | 0 1 2 |
| 4 | 0 | 命中 | 1 2 0 |
| 5 | 3 | 缺页 | 2 0 3 |
| 6 | 0 | 命中 | 2 3 0 |
| 7 | 4 | 缺页 | 3 0 4 |
| 8 | 2 | 缺页 | 0 4 2 |
| 9 | 3 | 缺页 | 4 2 3 |
| 10 | 0 | 缺页 | 2 3 0 |
| 11 | 3 | 命中 | 2 0 3 |
| 12 | 2 | 命中 | 0 3 2 |
| 13 | 1 | 缺页 | 3 2 1 |
| 14 | 2 | 命中 | 3 1 2 |
| 15 | 0 | 缺页 | 1 2 0 |
| 16 | 1 | 命中 | 2 0 1 |
| 17 | 7 | 缺页 | 0 1 7 |
| 18 | 0 | 命中 | 1 7 0 |
| 19 | 1 | 命中 | 7 0 1 |
LRU 缺页 12 次，缺页率 60.0%。
OPT（淘汰"未来最久才会用到"的页）：
| 次 | 引用 | 结果 | 淘汰 | 页框 |
|---|---|---|---|---|
| 0 | 7 | 缺页 | − | 7 − − |
| 1 | 0 | 缺页 | − | 7 0 − |
| 2 | 1 | 缺页 | − | 7 0 1 |
| 3 | 2 | 缺页 | 7 | 0 1 2 |
| 4 | 0 | 命中 | − | 0 1 2 |
| 5 | 3 | 缺页 | 1 | 0 2 3 |
| 6 | 0 | 命中 | − | 0 2 3 |
| 7 | 4 | 缺页 | 0 | 2 3 4 |
| 8 | 2 | 命中 | − | 2 3 4 |
| 9 | 3 | 命中 | − | 2 3 4 |
| 10 | 0 | 缺页 | 4 | 2 3 0 |
| 11 | 3 | 命中 | − | 2 3 0 |
| 12 | 2 | 命中 | − | 2 3 0 |
| 13 | 1 | 缺页 | 3 | 2 0 1 |
| 14 | 2 | 命中 | − | 2 0 1 |
| 15 | 0 | 命中 | − | 2 0 1 |
| 16 | 1 | 命中 | − | 2 0 1 |
| 17 | 7 | 缺页 | 2 | 0 1 7 |
| 18 | 0 | 命中 | − | 0 1 7 |
| 19 | 1 | 命中 | − | 0 1 7 |
OPT 缺页 9 次，缺页率 45.0%——注意后 8 次全部命中，这就是"预知未来"的威力。
三种算法在 3/4/5 帧下的总对照：
| 帧数 | FIFO | LRU | OPT |
|---|---|---|---|
| 3 帧 | 15（75%） | 12（60%） | 9（45%） |
| 4 帧 | 10（50%） | 8（40%） | 8（40%） |
| 5 帧 | 9（45%） | 7（35%） | 7（35%） |
⚠️ 结论句：OPT ≤ LRU ≤ FIFO 在本题成立（但"LRU 一定优于 FIFO"不是普遍定律，只是绝大多数局部性良好的程序上成立）。帧数从 3 增到 5，三者缺页数都单调不增——因为 LRU 与 OPT 是栈算法，FIFO 在本题恰好也没出现异常。
例 2：Belady 异常的最小反例
引用串
1 2 3 4 1 2 5 1 2 3 4 5（12 次），分别用 3 帧与 4 帧的 FIFO 跑。
| 帧数 | FIFO 缺页次数 | 缺页率 | 结论 |
|---|---|---|---|
| 3 帧 | 9 次 | 75.0% | 基准 |
| 4 帧 | 10 次 | 83.3% | ★ 帧数多了，缺页反而多了 1 次 |
⚠️ 这就是"Belady 异常"（也叫 FIFO 异常）：物理资源增加、性能反而下降——它说明"置换算法不能只看'公平'，而要看"是否满足栈性质"。LRU 用同样的串跑 3 帧 vs 4 帧，缺页是 12 → 8，单调下降，不出现异常。
例 3：C 实现——FIFO 与 LRU 的缺页统计
#include <stdio.h>
#define NF 3 /* 页框数 */
#define NR 20 /* 引用串长度 */
static int ref[NR] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
/* FIFO: 用"循环指针"记录队首(最早进入的那一页) */
static int fifo(void) {
int frame[NF], i, j, faults = 0, next = 0, hit;
for (i = 0; i < NF; i++) frame[i] = -1; /* -1 表示空框 */
for (i = 0; i < NR; i++) {
hit = 0;
for (j = 0; j < NF; j++)
if (frame[j] == ref[i]) { hit = 1; break; }
if (hit) continue; /* 命中: 不改 FIFO 次序 */
faults++;
frame[next] = ref[i]; /* 队首被替换 */
next = (next + 1) % NF;
}
return faults;
}
/* LRU: 给每框一个"最近使用时刻"stamp, 淘汰 stamp 最小的那个 */
static int lru(void) {
int frame[NF], stamp[NF], i, j, k, faults = 0, t = 0, hit;
for (i = 0; i < NF; i++) { frame[i] = -1; stamp[i] = 0; }
for (i = 0; i < NR; i++) {
t++;
hit = 0;
for (j = 0; j < NF; j++)
if (frame[j] == ref[i]) { hit = 1; stamp[j] = t; break; }
if (hit) continue; /* 命中: 刷新时刻即可 */
faults++;
k = 0;
for (j = 1; j < NF; j++)
if (stamp[j] < stamp[k]) k = j; /* 最久未用 */
frame[k] = ref[i];
stamp[k] = t;
}
return faults;
}
int main(void) {
int f1, f2, i;
printf("引用串:");
for (i = 0; i < NR; i++) printf(" %d", ref[i]);
printf("\n页框数 = %d\n\n", NF);
f1 = fifo();
f2 = lru();
printf("FIFO 缺页 = %d 次, 缺页率 = %.4f\n", f1, f1 / (double)NR);
printf("LRU 缺页 = %d 次, 缺页率 = %.4f\n", f2, f2 / (double)NR);
printf("命中率: FIFO %.4f, LRU %.4f\n", 1 - f1 / (double)NR, 1 - f2 / (double)NR);
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
引用串: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
页框数 = 3
FIFO 缺页 = 15 次, 缺页率 = 0.7500
LRU 缺页 = 12 次, 缺页率 = 0.6000
命中率: FIFO 0.2500, LRU 0.4000⚠️ 三点说明：
- FIFO 用"循环指针
next"实现——不必真的搬动数组元素；这个指针指向的就是"最早进入的那一页"。命中时不改指针（这正是 FIFO 与 LRU 的关键差别）。 - LRU 用"时间戳"实现（每次访问
t++）——命中也要刷新stamp[j] = t（漏掉这一步，LRU 就退化成 FIFO 了）。真实硬件里用"栈"或"计数器"实现，开销比 FIFO 大得多，所以才需要 CLOCK 这种近似算法。 - 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现（下例同一份引用串）实跑核对过输出——FIFO 15 次 / LRU 12 次，与例 1 的手算表完全一致。
例 4：Python——四算法对照、Belady 异常与缺页代价
REF = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
BELADY = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] # Belady 异常反例
def fifo(ref, n):
q, faults = [], 0
for r in ref:
if r not in q:
faults += 1
if len(q) < n:
q.append(r)
else:
q.pop(0)
q.append(r)
return faults
def lru(ref, n):
q, faults = [], 0
for r in ref:
if r in q:
q.remove(r)
q.append(r)
else:
faults += 1
if len(q) < n:
q.append(r)
else:
q.pop(0)
q.append(r)
return faults
def opt(ref, n):
q, faults = [], 0
for i, r in enumerate(ref):
if r in q:
continue
faults += 1
if len(q) < n:
q.append(r)
else:
far, victim = -1, None
for x in q:
nxt = None
for j in range(i + 1, len(ref)):
if ref[j] == x:
nxt = j
break
if nxt is None: # 以后不再用 -> 直接淘汰
victim = x
break
if nxt > far:
far, victim = nxt, x
q.remove(victim)
q.append(r)
return faults
def clock(ref, n):
frames, use = [None] * n, [0] * n
hand, faults = 0, 0
for r in ref:
if r in frames:
use[frames.index(r)] = 1
continue
faults += 1
while use[hand] == 1: # 给过第二次机会
use[hand] = 0
hand = (hand + 1) % n
frames[hand] = r
use[hand] = 1
hand = (hand + 1) % n
return faults
print('=== ① 四种算法在不同帧数下的缺页次数 ===')
print('引用串长度 = %d' % len(REF))
print('帧数 FIFO LRU OPT CLOCK')
for n in [3, 4, 5]:
print(' %d %4d %4d %4d %5d'
% (n, fifo(REF, n), lru(REF, n), opt(REF, n), clock(REF, n)))
print()
print('=== ② Belady 异常(FIFO 独家) ===')
print(' 引用串 = %s' % BELADY)
for n in [3, 4]:
f = fifo(BELADY, n)
print(' %d 帧 -> FIFO 缺页 %d 次 (%.4f)' % (n, f, f / len(BELADY)))
print(' 3 帧 9 次 < 4 帧 10 次 -> 帧数增加, 缺页反而变多!')
print(' 对照: 同一串 LRU -> 3 帧 %d 次 / 4 帧 %d 次 (单调下降, 无异常)'
% (lru(BELADY, 3), lru(BELADY, 4)))
print()
print('=== ③ 缺页率 vs 有效访问时间(主存 100 ns, 磁盘 10 ms) ===')
MEM, DISK = 100.0, 10e6
for c in [1e-2, 1e-3, 1e-4, 1e-5]:
eat = (1 - c) * MEM + c * DISK
print(' 缺页率 %g: EAT = %10.1f ns (是主存的 %.1f 倍)' % (c, eat, eat / MEM))
print(' 结论: 只有缺页率压到 1e-5 以下, EAT 才接近主存(200 ns = 2 倍)')
print()
print('=== ④ 三种"调入/分配"策略的组合合法性 ===')
for alloc, repl, ok in [('固定分配', '局部置换', '成立'),
('可变分配', '全局置换', '成立'),
('可变分配', '局部置换', '成立(工作集法)'),
('固定分配', '全局置换', '★ 不成立(全局置换必然要动别人的页框)')]:
print(' ' + alloc + ' + ' + repl + ': ' + ok)
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
输出对照（真实运行结果）：
=== ① 四种算法在不同帧数下的缺页次数 ===
引用串长度 = 20
帧数 FIFO LRU OPT CLOCK
3 15 12 9 14
4 10 8 8 9
5 9 7 7 9
=== ② Belady 异常(FIFO 独家) ===
引用串 = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
3 帧 -> FIFO 缺页 9 次 (0.7500)
4 帧 -> FIFO 缺页 10 次 (0.8333)
3 帧 9 次 < 4 帧 10 次 -> 帧数增加, 缺页反而变多!
对照: 同一串 LRU -> 3 帧 10 次 / 4 帧 8 次 (单调下降, 无异常)
=== ③ 缺页率 vs 有效访问时间(主存 100 ns, 磁盘 10 ms) ===
缺页率 0.01: EAT = 100099.0 ns (是主存的 1001.0 倍)
缺页率 0.001: EAT = 10099.9 ns (是主存的 101.0 倍)
缺页率 0.0001: EAT = 1100.0 ns (是主存的 11.0 倍)
缺页率 1e-05: EAT = 200.0 ns (是主存的 2.0 倍)
结论: 只有缺页率压到 1e-5 以下, EAT 才接近主存(200 ns = 2 倍)
=== ④ 三种"调入/分配"策略的组合合法性 ===
固定分配 + 局部置换: 成立
可变分配 + 全局置换: 成立
可变分配 + 局部置换: 成立(工作集法)
固定分配 + 全局置换: ★ 不成立(全局置换必然要动别人的页框)四条结论：
- 缺页次数的排序在所有帧数下都是
OPT ≤ LRU < FIFO，CLOCK 的表现则随帧数波动：3 帧 14 次（介于 LRU 的 12 与 FIFO 的 15 之间）、4 帧 9 次（反而优于 FIFO 的 10 次）、5 帧 9 次（与 FIFO 持平）——CLOCK 只是"用一次访问位换来接近 LRU 的效果"，它是启发式而非严格算法，不保证落在那两者之间。 - Belady 异常只在 FIFO 上出现（3 帧 9 次 → 4 帧 10 次）；同一串 LRU 是 3 帧 10 次 → 4 帧 8 次，单调下降——"栈算法免疫 Belady 异常"不是空话，这一行就是证据。
- 缺页率每降一个数量级，EAT 就掉一个数量级：
- "固定分配 + 全局置换"不成立——因为"全局置换"的定义就是"可以从其他进程那里拿页框"，那分配就不可能固定。 这个矛盾组合是选择题常设陷阱。
考点
考点
1. 必背结论
- 局部性原理：时间局部性 + 空间局部性——虚拟内存能工作的前提。
- 请求分页页表项在
os/21-paging.md基础上增加：状态位/有效位、访问字段、修改位（脏位）、外存地址。 - 缺页中断是"故障"：处理完返回后"重新执行当前指令"（不是下一条）；一条指令可能引发多次缺页。
- 缺页处理流程：查页表 → 找牺牲页（脏则写回）→ 从磁盘读入 → 改页表项 → 重新执行。
- 四算法一句话：OPT 淘汰未来最久不用的（不可实现，作为下界）；FIFO 淘汰最早进入的；LRU 淘汰最久未被访问的；CLOCK 按访问位循环扫描。
- 锚点数据（20 次引用、3 帧）：OPT 9 次 / LRU 12 次 / CLOCK 14 次 / FIFO 15 次；4 帧：8 / 8 / 9 / 10；5 帧：7 / 7 / 9 / 9（顺序均为 OPT / LRU / CLOCK / FIFO）。
- Belady 异常只属 FIFO：反例串
1 2 3 4 1 2 5 1 2 3 4 5，3 帧 9 次、4 帧 10 次。 - 栈算法（LRU/OPT）帧数增加，缺页绝不增加；FIFO 不是栈算法。
- 缺页代价锚点（主存 100 ns / 磁盘 10 ms）：缺页率
- 分配/置换四种组合：固定+局部、可变+全局、可变+局部成立；固定+全局不成立。
- 改进型 CLOCK 优于简单 CLOCK：优先淘汰"未访问且未修改"的页，减少写回磁盘。
2. 高频陷阱
- 把缺页中断的返回语义说成"执行下一条指令"：错。缺页是"故障"，要"重新执行"当前指令（只有系统调用/自陷才是"下一条"）。
- 认为"帧数越多缺页一定越少"：错。FIFO 会 Belady 异常（3 帧 9 次、4 帧 10 次）；只有栈算法（LRU、OPT）才有这个单调性保证。
- 把 LRU 与 FIFO 说成"差不多"：错。FIFO 看"何时进入"，LRU 看"何时使用"；LRU 每次命中都要刷新时间戳/挪栈，命中处理比 FIFO 贵得多。
- 认为"OPT 可以实现"：错。OPT 需要预知未来引用串，只能用于理论对照与算法评估（它的缺页数是所有算法的下界）。
- 说"CLOCK 一定优于 FIFO"：错。CLOCK 只是 LRU 的启发式近似——本题 4 帧时 CLOCK 9 次优于 FIFO 的 10 次，5 帧时却与 FIFO 同为 9 次，并未更优；它换来的是"实现开销小"，不是"一定更准"。
- 忘了"脏位为 1 才需要写回磁盘"：错。没写过的页直接丢弃即可，不必写回——这正是"改进型 CLOCK"要"优先淘汰 A=0、M=0"的原因。
- 把"驻留集"与"工作集"混为一谈：错。驻留集 = 实际分配给进程的物理页框集合（"给了多少"）；工作集 = 进程在某段时间窗口内实际访问的页集合（"要用多少"）——两者相等才不抖动（见
os/24-thrashing.md）。 - 说"页框不够时随便挑一页换出"：错。要按置换算法选，且脏页要写回——"随便挑"就是 FIFO，性能最差。
- 认为"虚拟内存越大越好"：错。虚拟内存过大而物理内存不足会引发"抖动"（下章）——多道程序度超过某个点后，CPU 利用率会急剧下降。
- 把"对换区"与"文件区"的需求搞混：对换区（swap）要的是读写速率，文件区要的是空间利用率——被换出的页优先从对换区调回，因为更快。
3. 解题模板（"页面置换大题"）
① 抄下引用串与页框数, 画一张表: 列 = 引用串次数, 行 = 每次的页框状态
② 严格按定义淘汰:
FIFO: 记录"进入次序", 淘汰最早的(可用循环指针, 命中不改次序)
LRU : 记录"最近访问时刻", 淘汰时刻最小的(命中要刷新时刻!)
OPT : 对每页往后找"下一次出现的位置", 淘汰"下一次最远或不再出现"的
CLOCK: 维护"访问位", 指针循环, 遇 A=0 淘汰, 遇 A=1 置 0 继续
③ 结尾必答: 缺页次数、缺页率(= 缺页次数 / 引用次数)、命中率(= 1 - 缺页率)
④ 若问 Belady: 用"3 帧 vs 4 帧的 FIFO"作反例, 给出 9 vs 10
⑤ 若问 EAT: EAT = (1-c)·t_内存 + c·t_磁盘, c 是缺页率4. 与相邻章节的接口
os/21-paging.md（分页）：本章在页表项上加"有效位、访问位、修改位、外存地址"四个字段；那里的"页号越界"是非法访问，本章的"缺页"是可修复的故障。os/22-segment.md（分段）：请求分段也按同一套思路加"缺段"处理（段的换入换出粒度更大、更慢）。os/24-thrashing.md（抖动与工作集）：本章例 4 的"缺页率 1e-5 才实用"直接引出下章 —— 缺页率压不下来的后果就是抖动。arch/13-virtual.md（虚拟存储器）：硬件侧的三项式 EAT（含 TLB 与两级页表）与本章例 4 的简化 EAT 是不同口径，两处数字不可互相引用；那边的"缺页处理六步"与本章"缺页中断六步"是同一件事的两面。os/10-process.md（进程与线程）：每个进程有自己的页表，所以进程切换要换页表、刷 TLB（那 5 倍的切换开销来自这里）。os/32-io.md（I/O 管理）：缺页的"从磁盘读一页"就是一次块设备 I/O，它的开销受 I/O 方式（查询/中断/DMA）直接影响。
小结
- 虚拟内存 = 只装用到的部分，其余留磁盘；能成立的基石是局部性原理（时间局部性 + 空间局部性）。
- 请求分页页表项 = 页框号 + 有效位 + 访问位 + 修改位 + 外存地址。
- 缺页中断是"故障"→ 处理完要"重新执行当前指令"；一条指令可能多次缺页。
- 四算法：OPT（未来最久不用，不可实现）< LRU（最久未使用）< CLOCK（访问位近似）< FIFO（最早进入）。
- 锚点（20 次引用）：3 帧 → OPT 9 / LRU 12 / CLOCK 14 / FIFO 15；4 帧 → 8 / 8 / 9 / 10；5 帧 → 7 / 7 / 9 / 9。
- Belady 异常只属 FIFO：
1 2 3 4 1 2 5 1 2 3 4 5，3 帧 9 次、4 帧 10 次；LRU 同串为 10 → 8，单调下降。 - "栈算法"是免于 Belady 异常的充要条件；LRU 与 OPT 是栈算法，FIFO 不是。
- 缺页代价锚点：缺页率
- 组合合法性：固定+局部、可变+全局、可变+局部成立；固定+全局不成立。
下一篇：抖动与工作集
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。