页面置换算法有哪些？FIFO、LRU 和 Clock

当进程访问的页面不在内存、又没有空闲页框时，内核需要回收页面。干净的文件映射页通常可直接丢弃，之后从文件重新读取；匿名页若没有其他副本，可能需要先写入 Swap。置换策略希望减少代价高的缺页，同时兼顾实现成本、工作集和内存回收公平性。

FIFO按进入内存的先后回收最早页面，实现简单，但可能淘汰很快还会用到的页面，并存在 Belady 异常：增加页框数反而可能增加缺页数。理想 OPT淘汰未来最晚才会访问的页，可作为理论下界比较，但真实系统不知道未来访问序列。

LRU淘汰最长时间未被访问的页面，利用局部性假设近期访问过的页面更可能再次访问。精确维护每次访问的时间顺序很贵，实际操作系统通常用访问位、时钟算法或其他近似策略。Clock把页面组织成环形，检查访问位：最近访问过就清位并跳过，未访问则作为候选回收。增强型策略还可能结合脏位，优先选择干净页以减少写回成本。

真实内核回收远不止教科书中对一个进程做 LRU。它会考虑文件缓存与匿名页、脏页写回、NUMA 节点、内存 cgroup、回收成本和并发访问；不同内核版本策略会演进。因此面试回答应先讲经典模型，再说明实现通常近似且受系统约束。

常见追问#

Q：为什么不能精确实现 LRU？
A：每次内存访问都更新全局顺序会带来很高的硬件和软件成本。常见实现利用访问位或采样近似近期使用程度。

Q：FIFO 为什么会出现 Belady 异常？
A：FIFO 只看装入时间，增加页框会改变队列淘汰顺序，可能使后续访问序列产生更多缺页；这不是所有置换算法都会出现的性质。

Q：脏页和干净页回收成本有什么差别？
A：脏页内容比磁盘副本新，回收前通常需要写回；干净文件页可丢弃后按需重读，成本往往较低。