Sherfiter's wiki for fun

第 7 章 · 页面置换与工作集

先看一次真实的服务器异常。某天凌晨监控告警,机器负载正常但接口延迟翻了十倍,登上去先看内存:

$ free -h
       total  used  free  available
Mem:    15Gi  15Gi  82Mi       1.2Gi
Swap:   4.0Gi 2.1Gi  1.9Gi

物理内存吃满,交换区吃掉 2GB。再用 vmstat 看一眼,si/so(每秒换入换出的页数)高得吓人。诊断:内存不够,系统在疯狂地把页在内存和磁盘之间搬来搬去,整机效率被磁盘拖进地狱。这个现象叫抖动(thrashing),它背后的机制,就是本章的主题:物理页框不够时,踢谁?

7.1 置换算法:一道可以手算的题

设页访问序列,3 个页框,把每个算法真算一遍(考试就是考这个,工程上考的是直觉):

访问串:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

FIFO(先进先出):谁进得最早踢谁。手动模拟(加粗为缺页):

7    0    1    2    0    3    0    4    2    3    0    3    2    1    2    0    1    7    0    1
[7]  [7]  [7]  [2]  [2]  [2]  [2]  [4]  [4]  [4]  [0]  [0]  [0]  [0]  [0]  [0]  [0]  [7]  [7]  [7]
     [0]  [0]  [0]  [0]  [3]  [3]  [3]  [2]  [2]  [2]  [2]  [2]  [1]  [1]  [1]  [1]  [1]  [0]  [0]
          [1]  [1]  [1]  [1]  [1]  [4]...        [3]  [3]  [3]  [3]  [3]  [2]...     [7]...
缺页共 15 次

LRU(最近最久未用):踢「上次访问离现在最远」的页。同样的串算下来缺页 12 次。差别出在第 4 次访问:2 来了,FIFO 踢 7(它最早进),LRU 踢 1(它是三者中最近最久没用的)。LRU 用「过去」预测「未来」,FIFO 用「到来顺序」预测,后者和「将来还会不会用」毫无关系,这是两者差距的根源。

OPT(最佳置换):踢「未来最久不用」的页,上帝视角,缺页 9 次,是所有算法的理论下界。它不可实现(谁也不能预知未来),价值在于当标尺:LRU 的 12 距离下界 9 已经相当近,CLOCK 的 14 略逊,FIFO 的 15 敬陪末座。

CLOCK(时钟算法):LRU 的硬件穷人版。精确 LRU 要给每次访问记时间戳或维护链表,开销太大;CLOCK 给每页一个访问位,所有页排成环,指针扫过去:访问位是 1,清零继续走;是 0,踢它。直觉是「最近被用过的页获得一次免死金牌」,对 LRU 的一次粗略逼近,一个 bit 的硬件成本。真实的 Linux 更精细:两链表(active/inactive)+ 二次机会,思想同源。

7.2 Belady 异常:内存越大反而更糟

一个反直觉的实验结果:FIFO 在访问串 1 2 3 4 1 2 5 1 2 3 4 5 上,3 个页框缺页 9 次,4 个页框反而缺页 10 次。内存变大,性能变差,这就是 Belady 异常。

病因:FIFO 踢的是「最早到来」,这和「将来还会不会用」毫无关联,多一个页框只是多了一个「早到」的陪跑。LRU 和 OPT 没有这个病(它们有栈性质:页框多的命中集合包含页框少的命中集合)。这道题的实用价值,一是提醒你「资源加量不一定改善性能」,二是考你对各算法性质的理解深度。

7.3 抖动:钱花在搬运上

回到开头的服务器事故。抖动的机制:每个进程都需要一个「当前频繁访问的页集合」常驻内存(即工作集),如果分给它的页框数低于工作集大小,它每前进几步就缺页一次,磁盘排队爆满,CPU 倒闲下来了。

正常:    CPU ████████ 磁盘 ██        CPU 在干活
抖动:    CPU ██      磁盘 ████████   全系统在等磁盘

监控里「CPU 利用率暴跌 + 磁盘 IO 打满 + load 偏高」同时出现,基本就是它。经典的医疗方案是工作集模型:算出每个进程的工作集,给够;给不够就别硬撑,把整个进程挂起换出(中级调度,第 3 章那个层次),腾出页框喂饱剩下的进程。少而饱胜过多而饿。Linux 的实际做法更宽容,页回收按 LRU 近似慢慢挤,配合 cgroup 限制各家配额,但「内存超卖过头的代价是指数级恶化」这个结论完全一致。

一道公式题收尾:缺页率 p(介于 0 和 1 之间),内存访问 100ns,缺页处理(读盘)8ms:

EAT=(1−p)×100+p×8‘,‘000‘,‘000‘ns‘EAT = (1-p) \times 100 + p \times 8`{,}`000`{,}`000 \text`{ ns}`

p = 1% 时 EAT ≈ 80μs,慢了 800 倍。缺页率是性能的悬崖,不是斜坡:99% 好和 100% 好,可能差几百倍。这也是为什么容量规划要留余量,别让工作集差一页。

常见错误

  • 混淆「缺页」和「错误」。缺页是虚拟内存的正常工作机制(第 6 章讲过首次访问的次缺页),只有高频 major fault 才是病。
  • 给大内存应用关掉 swap 后裸奔。swap 全关,内存一满就是 OOM killer 直接杀进程(挑占内存最大者,常常是你最重要的那个);留一点 swap 当缓冲,换页慢但活着。
  • 以为 LRU 在数据库场景天生最优。全表扫描会污染 LRU(把热点全刷走),InnoDB 用改良版(新页先进 young 区的闸门外的 old 区)防冲刷,详见数据库课索引章。

练习

  1. 手算:用本章访问串,3 页框,完整模拟 LRU,验证缺页 12 次;再换 CLOCK(访问位初始 0)算一遍,对比。
  2. 手算:缺页率 0.5%、99.9%、99.99%,内存 100ns、缺页 8ms,分别求 EAT,画出「缺页率-EAT」曲线感受悬崖。
  3. 动手:在你的机器上跑 vmstat 1,同时开一个吃内存的程序(比如分配并写满一个 20GB 的数组,若内存小于它),观察 si/so 列变化,亲眼看一次抖动。
  4. 思考:多进程同时抖动时,「挂起谁」是个调度决策。按内存占用挑、按优先级挑、按最近 CPU 使用挑,各有什么副作用?
豫ICP备2026027944号