还记得最开始做出的三个假设吗？
好吧，我都不记得了。假设 2 与 3 已经在分段机制中被取消了；现在来取消最后一个假设：一个线程所需的地址空间远小于内存的真实物理空间。
有些线程所需的地址空间可能相当大，甚至远远超过内存的物理空间！
此时就需要外部存储的介入了。磁盘存储 (disk storage)，启动！
交换空间
OS 在磁盘中维护一块交换空间 (swap space) 用于存储虚拟页。
磁盘空间很大，但 I/O 很慢：此时物理内存可以被视为交换空间的缓存。
交换空间不由文件系统管理，并且在磁盘上占用连续的磁道 (track) 与块 (block)，以提升 I/O 效率。
页错误
PTE 的换页支持：
- PTE 中的存在位 (present bit) 标识该页是否位于物理内存中
- PTE 存储该页所在的磁盘地址
当硬件在地址翻译过程中发现 PTE 的存在位为 0，将触发页错误 (page fault)，OS 介入处理。
- OS 通过页错误处理器 (page fault handler) 找到 PTE 中的 磁盘地址，发出 I/O 请求
- I/O 进行当中时，OS 阻塞当前线程，选择其他的就绪线程运行（一大优点！）
- I/O 完成后，OS 将页加载至物理内存中，更新 PTE 中的 PFN 和存在位，将之前阻塞的线程重新置为就绪状态
- 重试之前导致页错误的指令（会导致一次 TLB 未命中，一次查表更新 TLB，一次 TLB 命中后成功访问内存）
之前提到过 TLB 未命中有两种处理方式：硬件处理或 OS 处理。硬件处理的优势主要是性能上的。但处理页错误涉及到非常慢的磁盘 I/O，以至于 OS 的额外开销都可以忽略不计；因此，几乎所有主流系统都使用 OS 处理页错误。
页替换
既然现在物理内存成了某种意义上的缓存，它也需要替换策略 (replacement policy) 来决定没有空闲页框时新页如何替换旧页，以最小化平均内存访问时间 (average memory access time, AMAT)。
暂不考虑 TLB，令 $T_M$ 为内存访问耗时，$T_D$ 为磁盘访问耗时，$P_{Miss}$ 为页错误发生率，有：
$$
AMAT=T_M+(P_{Miss}\cdot T_D)
$$
磁盘访问与内存访问相比相当耗时，通常是以毫秒 ms 为单位的；后者通常以 ns 为单位。
- $1$ ms $=10^6$ ns。
计算在指定访问串 (reference string) 上的命中率可以用来评估替换策略的优劣。
最优替换
最优替换需要未来访问事件的先验知识。
替换内存中在未来最长时间内不会被访问的页。
FIFO
替换最早进入内存的页。
LRU
利用时间局部性启发，替换内存中最近最长时间未被访问 (least-recently-used) 的页。
PTE 需要包含最近访问时间戳。
处理循环访问 (looping-sequential workload) 效果很差。
LFU
替换内存中最少被访问 (least-frequently-used) 的页。
PTE 需要包含访问次数计数器。
一个过去被频繁访问的页可能在未来不再被访问：这样的页可能会一直占据内存空间。
时钟替换
时钟替换 (clock replacement) 是对 LRU 的近似，只需要维护一个指针和 PTE 中的访问位 (reference bit)。
维护一个指向当前最近最长时间未被访问虚拟页的指针，称为时针 (clock hand)。将所有页视为一个环形链表。每当需要替换时：
- 检查时针指向的页，若访问位为 0，替换该页
- 否则，将该页的访问位置 0，时针向前移动到下一页，重复该过程直到找到访问位为 0 的页
将脏位 (dirty bit) 考虑进来：
- 脏位为 1 标识该页被修改过，因此需要将内容同步到磁盘中：这涉及到磁盘的写操作
- 时针优先替换脏位为 0 且访问位为 0 的页，然后是脏位为 1 且访问位为 0 的页
页选择
在一个线程执行过程中，并非所有页都需要一直存在内存中。OS 需要考虑什么时候需要将哪些页加载进内存中，这被称为页选择策略 (page selection policy)。
按需选择 (demand paging)：只有当页被显式地访问时才将其加载到内存中。高内存空间利用率，但页错误频繁。
预先选择 (prefetching/anticipatory paging)：OS 尝试预测哪些页将被访问并提前将其加载到内存中。比如，利用空间局部性启发，当代码段的第 $n$ 页被访问时，很有可能接下来的 $n+1$ 页将被访问。
页释放
OS 维护一对高水位 (high watermark, HW) 与低水位 (low watermark, LW) 以保持内存中一定数量的空闲空间。当发现空闲页框的数量小于 LW 时，OS 将唤醒在后台的交换守护进程 (swap daemon) 释放一些页。
哪些虚拟页将被驱逐 (evict)？当然也是有策略的，但在此按下不表。
抖动
当大量线程同时竞争有限的物理内存资源以放置其虚拟内存时可能造成抖动 (thrashing)。
页错误相当频繁的发生，OS 忙于在内存与磁盘间换页，从而没有足够的时间执行实际的计算任务；CPU 的高空转又会使得 OS 误判引入的线程太少，从而尝试并发更多的线程，又加剧了内存竞争。恶性循环了。
在早期的大型机中，这种现象甚至会使得硬盘产生可被肉眼观察到的抖动。
缓解方法：
- 挂起或杀死一些线程，禁止新线程启动
- 把物理内存空间给括一扩吧！