跳转至

09 交换与页替换 — 磁盘假装内存,以及「踢谁出去」这门学问

1. 这一章讲什么

页表还是太大,内存还是不够装下所有进程——本章把最后两个窟窿一起堵上。 前一半:让页表瘦身(混合分段、多级页表——今天所有主流 CPU 的选择); 后一半:让磁盘假装内存的一部分(交换),以及交换引出的全书最难的策略题: 内存满了,把谁踢出去? 踢错的代价是程序以「磁盘速度」运行—— 比内存慢一万到十万倍。

2. 顶层全景

  页表太大 → 三个解法:
    大页(简单,但页内浪费 = 内部碎片)
    分段+分页的混合(每段一张页表;消灭了表内的空洞,却复活了外部碎片)
    多级页表(页表按页切块,整页无效就不分配;页目录管记账)★ 今天的主流
        │
  内存不够 → 交换:
    磁盘上留一块交换空间(swap);页表项加「存在位」
    访问不在内存的页 → 缺页异常 → OS 从磁盘换入(内存满则先踢一页)
        │
  踢谁?→ 页替换策略(本章后半的全部):
    最优(看未来,不可实现,只作基准) > LRU(用过去预测未来) > FIFO/Random
    实现:L R U 太贵 → 时钟算法(用页的访问位当近似)

图说:上半是「表太大」的三个答案与取舍,下半是「内存不够」的机制 加上那个老问题——不知道未来时,怎么用历史凑合。

3. 核心原理

3.1 页表瘦身:三个解法的账

解法一:大页。32 位地址空间、16KB 页 → 表从 4MB 缩到 1MB。 但页是给程序的最小分配单位,页越大、页内用不满的浪费(内部碎片) 越狠——多数系统日常仍是 4KB(x86)或 8KB(SPARCv9)1。 (补充:现代系统用大页(如 2MB/1GB)是给 TLB 减压,不是省表, 管理软件复杂度大增——书里在旁注里点了这个方向2。)

解法二:分段+分页的混合。Multics 的 Jack Dennis 想出来的: 每个逻辑段各配一张页表,段的基址寄存器不再指段本身,而是 指该段的页表在物理内存的位置,界限寄存器记这张页表有几个有效项。 32 位地址的最高两位选段(00 未用、01 代码、10 堆、11 栈)3。 好处:堆栈之间那片大空洞不再占用页表空间(16KB 例子里 线性页表 16 项、大半无效;混合方案只为实际使用的页付账4)。 两个代价:它假设地址空间的使用模式(大但稀疏的堆照样浪费); 页表本身变成变长块,外部碎片又回来了5。

解法三:多级页表(主线例子,数值照抄原书)。不再按段切, 而是把页表自身按页大小切块,整块的表项全无效就整块不分配, 用一张页目录记账:页目录项(PDE)有效 = 它指向的那页表页里 至少有一个有效页6。

书里的完整小例子:16KB 地址空间、64 字节页 → 14 位地址 (8 位 VPN + 6 位偏移);线性页表 256 项 × 4 字节 = 1KB, 切成 16 个 64 字节的「表页」,每页装 16 个表项 → 页目录 16 项。 于是 VPN 的 8 位劈成两段:高 4 位索引页目录(PDIndex), 低 4 位索引表页(PTIndex)7。地址空间只用了 VPN 0、1(代码)、 4、5(堆)、254、255(栈):线性页表要为全部 256 项付内存; 多级方案只为 4 个表页付账,页目录里其余 12 项标无效—— 省下的正是稀疏的那部分。

取舍表里写着两个代价:TLB 未命中时,线性表查 1 次内存, 两级表要查 2 次(页目录 + 表页);表不再连续,管理更复杂8。 这就是经典的时间换空间——书里的原话:想结构快通常要付空间的税, 想省空间就要接受更慢的访问9。

3.2 交换的机制:存在位与缺页

交换空间(swap space)是磁盘上预留的一块,按页读写,OS 记得 每页落在哪个盘块10。页表项里加一个存在位(present bit): 1 = 页在内存,一切照旧;0 = 页在盘上11。

一次缺页的全流程(控制流程图 21.2/21.3 的合并走法):

  1. 程序访问一个合法页号的地址;TLB 没有 → 查页表。
  2. PTE 有效但存在位 = 0 → 硬件抛缺页异常(page fault), 进入操作系统的缺页处理程序12。
  3. OS 找空闲帧;没有 → 调页替换算法踢出一页(见 3.3)。
  4. OS 发磁盘 I/O,把页从交换空间读进内存;等 I/O 期间该进程 阻塞,CPU 去跑别的进程——又一次重叠13。
  5. I/O 完成:更新 PTE(存在位置 1、填 PFN)、重试指令; 再 TLB miss、填入 TLB、命中——访存成功。

两个细节值得记住:页不在内存时,PTE 里的 PFN 字段可以复用为磁盘地址14; 为什么硬件不自己处理缺页?一是磁盘本来就慢,软件那点开销无所谓; 二是硬件不懂交换空间、不会发 I/O——信任 OS 反而是简单解15。 书里还替「fault」这个词平了反:这其实是合法访问,叫「页缺失」更贴切, 只是处理路径和异常一样,名字就传下来了16。

什么时候真的换页?不一定等内存全满。不少系统维持一个 高水位线:空闲帧低于它就启动换出守护进程,批量腾出若干帧, 让正常路径总能拿到空闲帧17。

3.3 页替换策略:AMAT 账与四种政策

先看这笔账为什么非算不可。平均访存时间:

  AMAT = 访存时间 + (缺页率 × 磁盘访问时间)

取内存 100 纳秒、磁盘 10 毫秒:缺页率 10% 时 AMAT ≈ 1 毫秒 (慢一万倍);缺页率 0.1% 时 ≈ 10.1 微秒(只差百倍)18。 磁盘太慢,命中率必须贴着 100%,策略的微小差别会被放大成数量级。

最优策略(OPT,Belady)是基准线:踢「未来最久才会被用到」的那页。 书里的轨迹:访问流 0,1,2,0,1,3,0,3,1,2,1,缓存 3 页—— 第 6 次访问(页 3)触发首次替换,看未来:0 马上用、1 稍后、2 最久, 踢 2;末段再踢 3。总命中率 6/11 = 54.5%19。 不可实现(需要预言),但作为对照点价值极大:「我的算法 80% 命中」 没有意义,「最优 82%,我 80%」才知道该停手了20。

FIFO 与 Random。FIFO 踢最早进来的页:同一轨迹只到 36.4% 命中 (排除强制缺失 57.1%)——它分不清页的重要程度,页 0 明明一直在用, 照样因为「先进来」被踢21。FIFO 还有个著名反例 Belady 异常: 缓存从 3 页加到 4 页,命中率反而下降(访问流 1,2,3,4,1,2,5,1,2,3,4,5); LRU 这类有「栈性质」的算法不会犯22。Random 在 1 万次模拟里 波动巨大:四成时候和最优打平,差的时候只有 2 次命中—— 随机没有最坏情况,但也没有保证23。

LRU(最近最久未用)与局部性。和第 04 章的 MLFQ 同一个思路: 用历史预测未来。理论靠山是局部性原理(principle of locality): 程序倾向于反复访问同样的代码序列和数据结构24。 还是那条轨迹,LRU 两次替换(踢 2、再踢 0)都和最优一致—— 这个例子里 LRU 追平了 OPT25。

工作负载才是判决。三个模拟看清全部:

负载 结果
无局部性(100 页随机访问) LRU/FIFO/Random 打平,命中率只由缓存大小决定
80-20(80% 访问落在 20% 热页) LRU 明显更好——热页一直被抱着;最优仍更高
循环顺序(0→49 循环,数据库式扫描) LRU 和 FIFO 的灾难:缓存 49 页、访问 50 页,命中率 0%!Random 反而有非零命中

图说:第三行就是「每种策略都有杀手负载」的活证据;Random 在循环负载下的 韧性,就是书里「随机没有奇怪角例」论点的回报26。

3.4 时钟算法:LRU 的工程替身

真 LRU 要维护全局顺序(每次访问都挪动链表),太贵。 时钟算法用 PTE 里现成的访问位(accessed bit,硬件在访存时自动置 1):

  所有帧摆成一个环形,指针扫过:
    访问位 = 1 → 清成 0,指针前进(「再给一次机会」)
    访问位 = 0 → 这帧就是牺牲页,踢掉

效果近似 LRU:最近用过的页访问位是 1,能活过一轮扫描; 久未用的页两轮都没人碰,自然被踢27。

3.5 比替换更狠的问题:抖动

如果系统里同时运行的程序的工作集(这段时间真正在用的页)加起来 超过物理内存,缺页会接连不断——刚换入的页马上又被踢出, 磁盘成了主存储器,系统整体塌进「磁盘速度」。这叫抖动 (thrashing)28。对策不是更好的替换算法,而是少放进程: 控制多道程序的度数,或按工作集模型挑进程挂起29。

4. 作者的判断与证据

书里给了证据的判断:

  • AMAT 的量级账(缺页率差 0.9 个百分点 = 慢一百倍)是策略研究的全部动机18。
  • 四种策略在同一轨迹、三种工作负载下的对比有完整模拟图;LRU 追平最优、 循环负载下 LRU 归零,都是可复算的192526。
  • 时钟算法用访问位近似 LRU,是真实系统的标准答案(x86 的 A 位就是为此存在)。

作者的判断(立场):

  • 「和最优比」被立为方法论:没有基准线的命中率数字没有意义20。
  • 对抖动的判词很 OS 工程师:这是负载管理问题,换算法救不了29。

5. 边界与局限

  • 多级页表的成本(TLB miss 多一次访存)在有 TLB 的世界里可以接受; 但对 TLB miss 本身贵的大表(如 4 级页表)链条更长——大页正是 为打断这条链条而生的,这属于本章之后的工程演进。
  • LRU 的循环负载失效在真实数据库上有缓解办法(扫描的页标「一次性」), 书里只给了问题没给处方。
  • 交换在今天的桌面/服务器上常被禁用或限用(内存便宜了; 云主机换出等于计费 I/O)——但机制仍处处在: mmap 文件、 hibernation、容器 cgroup 限额,都是换入换出的变体。

6. 可带走的

  1. 多级页表的口诀:页表按页切块,全无效的块不分配,页目录记账; VPN 劈成「目录索引 + 表索引」两段。省的是稀疏,付的是 miss 多一步。
  2. 时间换空间是最基本的权衡句式;看到「数据结构更小」先问「哪次访问变贵了」。
  3. 缺页不是错误,是合法访问遇上了异步状态(数据此刻不在它该在的地方);把它当异常处理, 但心里要知道它是缓存未命中。
  4. AMAT 思维:慢介质参与的系统,整体性能由最差那条路径的命中决定。 优化「平均」没用,优化「最差」才有用。
  5. 没有最优可算时,「和最优的差距」就是最好的标尺——无论调优什么系统。
  6. 时钟算法教的是用硬件免费提供的传感器(访问位)替代昂贵的软件记账—— 系统设计里到处都是这类替身。

7. 原文地图

主题 原书章 原文位置
4MB 页表的账 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:9(搜「4MB」)
大页与内碎 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:24(搜「Bigger Pages」)
混合:段基址指向段页表 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:126(搜「hybrid」)
混合方案的两个问题 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:187(搜「not without problems」)
多级页表基本思想 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:198(搜「multi-level」)
页目录与 PDE 语义 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:254(搜「page directory」)
16KB 例子的 4+4 位劈分 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:299(搜「Detailed」)
时间换空间 20. Paging: Smaller Tables text/22-ch20-20-paging-smaller-tables.txt:274(搜「TIME-SPACE」)
交换空间定义 21. Beyond Physical Memory: Mechanisms text/23-ch21-21-beyond-physical-memory-mechanisms.txt:51(搜「swap space」)
存在位 21. Beyond Physical Memory: Mechanisms text/23-ch21-21-beyond-physical-memory-mechanisms.txt:116(搜「present bit」)
缺页处理流程 21. Beyond Physical Memory: Mechanisms text/23-ch21-21-beyond-physical-memory-mechanisms.txt:156(搜「page-fault handler」)
I/O 期间进程阻塞、跑别人 21. Beyond Physical Memory: Mechanisms text/23-ch21-21-beyond-physical-memory-mechanisms.txt:193(搜「blocked」)
换错的代价:万倍到十万倍 21. Beyond Physical Memory: Mechanisms text/23-ch21-21-beyond-physical-memory-mechanisms.txt:211(搜「10,000」)
硬件为何不处理缺页 21. Beyond Physical Memory: Mechanisms text/23-ch21-21-beyond-physical-memory-mechanisms.txt:169(搜「WHY HARDWARE」)
AMAT 账(1ms vs 10.1µs) 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:58(搜「AMAT」)
最优策略 Belady 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:79(搜「furthest in the future」)
与最优比较的方法论 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:84(搜「COMPARING AGAINST OPTIMAL」)
FIFO 的 36.4% 与 Belady 异常 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:200(搜「36.4%」)与:205(搜「Anomaly」)
Random 万次实验 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:247(搜「10,000」)
局部性原理与 LRU 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:275(搜「LRU」)与:292(搜「locality」)
三种工作负载对比 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:341(搜「Workload」)
循环顺序负载:LRU 归零 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:426(搜「looping」)
时钟算法 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:504(搜「use bit」)与:513(搜「clock algorithm」)
抖动 22. Beyond Physical Memory: Policies text/24-ch22-22-beyond-physical-memory-policies.txt:602(搜「Thrashing」)与:607(搜「thrashing」)

  1. 出处:「20. Paging: Smaller Tables」第 49–57 段(text/22-ch20-20-paging-smaller-tables.txt:24,搜「Bigger Pages」)。 ↩

  2. 出处:「20. Paging: Smaller Tables」第 32–47 段(text/22-ch20-20-paging-smaller-tables.txt:32,搜「MULTIPLE PAGE SIZES」)。 ↩

  3. 出处:「20. Paging: Smaller Tables」第 126–152 段(text/22-ch20-20-paging-smaller-tables.txt:141,搜「two bits」)。 ↩

  4. 出处:「20. Paging: Smaller Tables」第 71–125 段(text/22-ch20-20-paging-smaller-tables.txt:122,搜「full of invalid entries」)。 ↩

  5. 出处:「20. Paging: Smaller Tables」第 187–196 段(text/22-ch20-20-paging-smaller-tables.txt:187,搜「not without problems」)。 ↩

  6. 出处:「20. Paging: Smaller Tables」第 198–262 段(text/22-ch20-20-paging-smaller-tables.txt:205,搜「chop up」)。 ↩

  7. 出处:「20. Paging: Smaller Tables」第 299–356 段(text/22-ch20-20-paging-smaller-tables.txt:299,搜「Detailed」)。 ↩

  8. 出处:「20. Paging: Smaller Tables」第 285–297 段(text/22-ch20-20-paging-smaller-tables.txt:286,搜「two loads」)。 ↩

  9. 出处:「20. Paging: Smaller Tables」第 274–277 段(text/22-ch20-20-paging-smaller-tables.txt:274,搜「TIME-SPACE」)。 ↩

  10. 出处:「21. Beyond Physical Memory: Mechanisms」第 51–69 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:51,搜「swap space」)。 ↩

  11. 出处:「21. Beyond Physical Memory: Mechanisms」第 92–119 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:116,搜「present bit」)。 ↩

  12. 出处:「21. Beyond Physical Memory: Mechanisms」第 216–239 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:238,搜「PAGE_FAULT」)。 ↩

  13. 出处:「21. Beyond Physical Memory: Mechanisms」第 193–198 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:193,搜「blocked」)。 ↩

  14. 出处:「21. Beyond Physical Memory: Mechanisms」第 160–165 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:165,搜「disk address」)。 ↩

  15. 出处:「21. Beyond Physical Memory: Mechanisms」第 169–180 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:169,搜「WHY HARDWARE DOESN'T HANDLE」)。 ↩

  16. 出处:「21. Beyond Physical Memory: Mechanisms」第 123–143 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:123,搜「SWAPPING TERMINOLOGY」)。 ↩

  17. 出处:「21. Beyond Physical Memory: Mechanisms」第 287–297 段(text/23-ch21-21-beyond-physical-memory-mechanisms.txt:294,搜「high watermark」)。 ↩

  18. 出处:「22. Beyond Physical Memory: Policies」第 43–70 段(text/24-ch22-22-beyond-physical-memory-policies.txt:58,搜「AMAT」)。 ↩↩

  19. 出处:「22. Beyond Physical Memory: Policies」第 72–163 段(text/24-ch22-22-beyond-physical-memory-policies.txt:79,搜「furthest in the future」)。 ↩↩

  20. 出处:「22. Beyond Physical Memory: Policies」第 84–93 段(text/24-ch22-22-beyond-physical-memory-policies.txt:84,搜「COMPARING AGAINST OPTIMAL」)。 ↩↩

  21. 出处:「22. Beyond Physical Memory: Policies」第 165–204 段(text/24-ch22-22-beyond-physical-memory-policies.txt:200,搜「36.4%」)。 ↩

  22. 出处:「22. Beyond Physical Memory: Policies」第 205–216 段(text/24-ch22-22-beyond-physical-memory-policies.txt:205,搜「Anomaly」)。 ↩

  23. 出处:「22. Beyond Physical Memory: Policies」第 236–251 段(text/24-ch22-22-beyond-physical-memory-policies.txt:247,搜「10,000」)。 ↩

  24. 出处:「22. Beyond Physical Memory: Policies」第 275–304 段(text/24-ch22-22-beyond-physical-memory-policies.txt:320,搜「principle of locality」)。 ↩

  25. 出处:「22. Beyond Physical Memory: Policies」第 305–339 段(text/24-ch22-22-beyond-physical-memory-policies.txt:335,搜「matching optimal」)。 ↩↩

  26. 出处:「22. Beyond Physical Memory: Policies」第 341–438 段(text/24-ch22-22-beyond-physical-memory-policies.txt:426,搜「looping」)。 ↩↩

  27. 出处:「22. Beyond Physical Memory: Policies」第 504–527 段(text/24-ch22-22-beyond-physical-memory-policies.txt:504,搜「use bit」)。原文:硬件在读写页时把 use bit 置 1;时钟算法扫描,见 1 清 0 前进,见 0 选中替换。 ↩

  28. 出处:「22. Beyond Physical Memory: Policies」第 602–609 段(text/24-ch22-22-beyond-physical-memory-policies.txt:602,搜「Thrashing」)。 ↩

  29. 出处:「22. Beyond Physical Memory: Policies」第 609–640 段(text/24-ch22-22-beyond-physical-memory-policies.txt:609,搜「cope」)。原文:老系统用检测+控制多道程序度数的机制应对抖动。 ↩↩