[!info] related notes 操作系统 MOC 页面置换算法（OPT/FIFO/LRU/Clock）

页面置换：FIFO（先进先出）

一句话

缺页且页框已满时，淘汰“最早进入内存”的那一页。

手算方法（用队列思维）

• 维护一个队列，队头是最早进入的页
• 命中：队列顺序不变
• 缺页且未满：入队
• 缺页且已满：出队（淘汰队头），再把新页入队

常考点

• FIFO 实现最简单
• 可能出现 Belady 异常：页框数增加，缺页次数反而增加

高频陷阱

• FIFO 不看“最近是否被访问”，只看“进入内存的先后”
• Belady 异常不是所有算法都有，典型出现在 FIFO

Belady 异常

**Belady 异常（Bélády’s Anomaly）**是计算机操作系统内存管理中（特别是页面置换算法）出现的一个反直觉现象。

简单来说，通常情况下，当我们给一个进程分配更多的物理内存（即增加页面帧数 Page Frames）时，该进程发生“缺页中断”（Page Fault，即需要的数据不在内存中，必须从硬盘调取）的次数应该减少，或者至少保持不变。但 Belady 异常是指：在某些特定的页面访问序列下，分配的内存增加了，缺页中断的次数反而也增加了。

为什么会发生 Belady 异常？

这个现象最典型地出现在 FIFO（先进先出，First-In, First-Out） 页面置换算法中。

• 算法的盲目性： FIFO 算法只关注页面进入内存的先后顺序，总是无脑淘汰最早进入内存的那个页面，而完全不考虑这个页面最近是否被频繁访问过。
• 空间增加的负面效应： 当内存容量增加时，原本早就该被淘汰的页面在内存里多停留了一段时间。这就有可能导致一种尴尬的情况：它刚好在下一次急需被访问的前一刻，变成了队列里“最老”的页面而被无情淘汰，从而引发了本不该发生的缺页中断。

哪些算法可以避免 Belady 异常？

并不是所有页面置换算法都有这个缺陷。具备“栈特性”（Stack Property）的算法就不会出现 Belady 异常，例如：

• LRU（最近最少使用，Least Recently Used）
• OPT（最佳页面置换算法，Optimal）