第 16 讲：虚拟内存、缺页与页面置换

分页只解决“物理上可以不连续”；如果程序的所有页仍必须一次全装入 RAM，程序就不能超过内存，并发进程数也会很少。虚拟内存再放松一步：进程的页只有在需要时才必须在 RAM，其他页可留在可执行文件、映射文件或交换区。

虚拟内存靠什么成立

依据是局部性原理：

时间局部性：刚访问过的指令/数据很可能很快再被访问；
空间局部性：刚访问地址附近的地址很可能随后被访问。

循环、顺序指令流、数组遍历和调用栈都使程序在一段时间里只需较小页集合。虚拟内存不是创造了与 RAM 一样快的无限空间；它是利用局部性，让慢速外存作为 RAM 后援。

课件将虚拟存储的特征概括为：物理分配可以离散，页面可在执行期间多次调入调出，需要时与外存对换，进程最终看见大于当前物理驻留集的虚拟空间。它和 Cache 都利用局部性、都在快慢两层间缓存副本；不同在于页的迁移主要由 OS 参与、缺页代价可能是磁盘 I/O，错误替换远比一次 Cache miss 昂贵，所以必须配合页表、保护和进程调度。

页表要多记什么

请求分页的页表项除 PFN 外，还常有：

present/resident：页当前是否在 RAM；
protection：可读、可写、可执行、用户/内核；
referenced/accessed：近期是否访问，供 Clock/近似 LRU 使用；
dirty/modified：调入后是否写过，决定换出前是否需回写；
backing location：不驻留时去文件或交换区哪里找。

一个不驻留的页表项不一定表示错误，它可能只是在说“这个虚拟页合法，但要先调入”。

缺页处理的完整链路

CPU 发出虚拟地址，MMU 查页表发现页不驻留，陷入内核；
内核判断地址是否属于该进程的合法映射，且访问类型是否有权限；
非法就向进程报错/发信号；合法则确定页的后备位置；
找空闲页框；若没有，用置换算法选牺牲页；
牺牲页若是脏页，先发起回写，其所属进程页表项改为不驻留；
从外存把所需页读入页框，缺页进程在 I/O 期间阻塞，CPU 可调度别的进程；
I/O 完成中断后，内核更新页表/TLB 状态，唤醒原进程；
回到用户态重启引发缺页的指令，这次转换成功。

缺页异常必须是可精确重启的：处理完以后重执行原指令，程序才会觉得那个页一直存在。

按需调页与预调页

Demand Paging 只在真正访问时调入，不会装不需要的页，但初期可能连续缺页；
Prepaging 利用顺序性一次预取多页，减少独立 I/O，但猜错会浪费内存和带宽。

预取的成败取决于工作负载是否具有可预测空间局部性。

页面置换算法

OPT：上界参考

换出“从现在开始，最晚才再被访问”的驻留页；永不再访问的最优。它需要知道未来引用串，无法在通用系统实现，但可作为对照下界。

FIFO 与 Belady 异常

FIFO 换出最早调入的页，只管“来了多久”，不管“最近是否在用”。它可能出现分配页框变多，缺页反而变多的 Belady 异常。

课件的经典引用串：

1 2 3 4 1 2 5 1 2 3 4 5

在 FIFO 下，3 个页框产生 9 次缺页，4 个页框反而产生 10 次。这不是算错，而是 FIFO 驻留集不满足“页框多时必包含页框少时的集合”的栈性质。

Second Chance 与 Clock

为每页加访问位 $R$ 。候选 FIFO 队首若 $R=1$ ，就把 $R$ 清 0 并给它第二次机会；继续找到 $R=0$ 的页。Clock 用环形页框和指针实现同一思路，避免真正搬动队列元素。

Clock 不是精确 LRU，而是用一个最近访问位便宜地近似。

LRU 与老化算法

LRU 换出“距离上次访问最久”的页，用过去估计将来。精确实现可用时间戳、栈或课件展示的硬件矩阵，但每次访存都更新顺序的成本很高。

老化算法为每页保留移位寄存器，周期性地右移，并把当期访问位 $R$ 放入最高位。数值越小，说明近期访问记录越少/越远，优先置换。

完整置换算例

设 3 个空页框，引用串为：

7 0 1 2 0 3 0 4

FIFO

访问	驻留集（旧 → 新）	结果
7	7	缺页
0	7, 0	缺页
1	7, 0, 1	缺页
2	0, 1, 2	缺页，换 7
0	0, 1, 2	命中
3	1, 2, 3	缺页，换 0
0	2, 3, 0	缺页，换 1
4	3, 0, 4	缺页，换 2

共 7 次缺页。注意第 5 次命中 0 并不会让 FIFO 中的 0 “变年轻”，所以后面仍换出 0。

LRU

前四步同样得到 {0,1,2}；第 5 步再访问 0，使 0 成为最近使用。访问 3 时换出最久未用的 1，访问 0 命中，访问 4 时换出 2，共 6 次缺页。

全局/局部置换与页框分配

局部置换：只从缺页进程自己的驻留集里选，性能隔离好，但某进程页框不足时无法借用闲置能力；
全局置换：可从所有进程页框里选，灵活但进程会相互干扰；
固定分配：进程生命期内页框数不变；
可变分配：OS 根据缺页和负载动态调整。

固定分配通常搭配局部置换；可变分配可与全局或局部策略结合。

初始页框怎样分

有多个活跃进程时，课件给出三种起点：

等分：可用页框平均分给各进程，简单但忽略地址空间大小；
比例分配：按进程地址空间占所有进程地址空间的比例分配；
优先权分配：在大小之外再给高优先级进程更多页框。

这只是初始值。可变分配系统还会依据缺页率/工作集调大或回收驻留集；计算结果也必须满足架构所需最小页框数，否则一条指令跨页时可能连基本执行条件都不具备。

工作集、驻留集与抖动

时间 $t$ 的工作集 $W(t,\Delta)$ 是过去 $\Delta$ 个访问/时间窗口内访问过的页集合。驻留集是 OS 当前真正给进程留在 RAM 的页。

若驻留集远小于当前工作集，进程会：

访问 A 缺页 → 换出 B → 很快访问 B 又缺页
                        → 换出 C → 很快又要 C ……

系统大量时间用于换页而不是执行有用指令，称为抖动（thrashing）。不能看到 CPU 利用率低就继续增加并发进程；那会让每个进程分到更少页框，进一步恶化缺页。

应对方法包括：

按工作集或缺页率调整驻留集；
降低多道程序度，挂起部分进程；
用局部置换限制抖动向其他进程扩散；
用课件中的 $L=S$ 思路调负载：两次缺页间平均执行时间 $L$ 与一次缺页服务时间 $S$ 相当时，再增负载已很危险。

课件还给出基于全局 Clock 扫描速度的“50% 准则”：扫描指针移动很快，说明大量页很快失去第二次机会、近期缺页压力高，应降低负载；移动很慢则可考虑增加活跃进程。需要挂起时可比较优先级、驻留集大小、进程总体大小、是否正因缺页阻塞以及是否刚被激活。选择标准是在尽快释放页框和将来恢复成本之间权衡，不是机械地永远挂起最大进程。

回写、页面缓冲与性能

干净页若来自可执行文件且从未修改，可直接丢弃；脏页需回写后备存储。页清除策略可提前在后台批量回写，避免缺页关键路径同时等待写出与读入。

页面缓冲算法会将刚被置换的页暂时留在空闲/已修改链表，若很快又需要，可在尚未覆写时召回，降低 FIFO 错换的代价。

课件列出的 2Q、MQ、LFU-Aging、ARC、Working Set Clock 等算法，都是在“最近性、频率、扫描开销、对工作集变化的适应性”之间换取不同近似。课程主线仍是 OPT 提供下界、FIFO 展示异常、Clock 低成本近似最近使用、LRU 表达局部性；扩展算法不应只背缩写。

包含缺页的平均访问时间可写成：

EAT=(1-p)\times t_{memory}+p\times t_{fault}.

因为 $t_{fault}$ 比 $t_{memory}$ 大很多个数量级，即使 $p$ 很小也可以主导 EAT。

写时复制与内存映射文件

Copy-on-Write

fork 初始时不立即复制所有物理页，而让父子页表共同指向只读页框。某一方第一次写时：

触发写保护异常；
内核识别这是 COW 页；
分配新页框，复制原内容；
只把写方页表改指新页并设可写；
重启写指令。

如果子进程很快 exec，绝大多数原页根本不用复制。

`mmap`

内存映射文件将文件的一段绑到进程虚拟地址区间。进程像访问数组一样访问文件，缺页机制负责按需读入，脏页机制负责同步。多进程将同一文件映射为共享页时，它又成为一种 IPC。

把虚拟内存题分成三层

地址层：虚拟页号如何查页表，该访问是否合法；
缺页层：页不在时从哪读，有没有空页框，牺牲页是否需回写；
策略层：用哪种置换算法，局部还是全局，工作集是否容得下。

先判合法性，再模拟置换。对一个本来就越界或无权的地址，再精巧的换页算法也不会把它变成合法访问。

课件最后用历史 UNIX 的双指针 Clock/页面链表、惰性伙伴分配，以及 Windows NT 的“保留地址空间—提交后备存储—按工作集驻留”说明：具体系统的数据结构各异，但仍在实现同一组决策——地址是否已承诺、页是否驻留、从哪里取页、换谁以及何时写回。这里保留其原理位置，不把旧版本字段当作今天所有内核的固定实现。