页面置换

复习

多级页表：页表本身太大时如何按需展开
缺页异常：访问的页面不在内存时 CPU 和内核怎样配合
按需加载与交换空间：只把眼下需要的页面放进内存

TL;DR

内存装满了，就得挑一页换出，给新页腾地方
FIFO 简单，但可能出现“多加内存反而更差”的异常
LRU 符合局部性、效果好，却很难精确实现
现实中常用时钟算法等近似方案，用一点精度换效率

正文

　　内存满了，现在要读入一个新页，就得先请走一页。请谁走？这就是页面置换（page replacement）要回答的问题。

　　选得好，程序流畅；选得不好，刚请走的页马上又要用，又得换回来，来回折腾。

先来先出

　　最省事的策略是 FIFO（先进先出）：谁最早进来，就请谁走。

　　它实现简单——维护一个队列就行。但它不看“这页最近有没有被用”，于是可能犯傻：把一页天天要用的页，仅仅因为它“资格老”就请出去，很快又得换回来。

　　更怪的是，FIFO 会出现 Belady 异常：给它更多内存，缺页次数反而可能变多。一个置换算法竟然会“越给越差”，听起来就不合理。

近似：时钟算法

　　于是现实里退一步，用近似 LRU 的方案。最常见的是时钟算法（clock）。

　　它给每一页一个“访问位”，并把这些页想成一个环：

需要换页时，指针沿着环扫
扫到的页，如果访问位是 1，说明最近用过，就把它清成 0，指针继续走
扫到的页，如果访问位是 0，说明这一轮下来都没被用过，就换它出去

        ┌───┐
   ┌──> │页A│ 访问位1 → 清0，继续
   │    └───┘
   │    ┌───┐
   │    │页B│ 访问位0 → 换出它
   │    └───┘
   └── 指针

　　它只用一位标志，就能大致实现“最近用过的先留着”，代价很小，效果不错——所以被许多真实系统采用。

　　到这里，“换哪页”有了办法。可如果整个系统都在疯狂换页，连局部性都保不住，又会怎样？下一章我们看这种叫“抖动”的病。

思考题

　　FIFO 会出现“内存越多、缺页反而越多”的怪事（Belady 异常）。这说明“命中率”和“内存大小”之间一定是正相关吗？

小结

知识点

页面置换：内存满时决定换出哪一页
FIFO：简单，但可能出现 Belady 异常
LRU：符合局部性，但难以精确实现
时钟算法：近似 LRU，实用且开销小

参考资料

Wikipedia(zh)：页面置换算法：置换算法
Wikipedia(zh)：Belady 异常：Belady’s anomaly

思考题答案（仅供参考）

　　不一定。Belady 异常就是反例：对某些算法（如 FIFO），内存增大后缺页反而增多。这说明“命中率”不只取决于内存大小，还取决于访问序列和置换策略的配合——算法是否利用了访问规律很关键。换句话说，内存多当然有帮助，但不是无条件的；一个不聪明的算法，可能把多出来的内存用得比原来还糟。所以置換算法才值得反复研究。