结论:Belady 异常是指增加物理页框数量后,缺页次数反而增多的反常现象。它出现在 FIFO 这类不具有"栈性质"的置换算法中;LRU、OPT 等栈式算法数学上保证不会出现该异常。
展开:经典反例:访问序列 1 2 3 4 1 2 5 1 2 3 4 5,FIFO 算法下 3 个页框产生 9 次缺页,4 个页框反而产生 10 次。原因:FIFO 只看进驻时间,换出的可能是即将被用的页,页框增多改变了置换顺序,恰好把热页更早踢出。栈式算法(LRU、OPT)的数学性质是"n 个页框在任意时刻装的内容是 n+1 个页框所装内容的子集",页框更多意味着旧页集合被包含,缺页必然不增。工程意义:LRU 的此性质让"加内存一定更好"成立,系统调优有确定性预期;FIFO 实现简单但行为不可预测,所以实际系统用的是 LRU 近似(时钟算法、Linux 的 active/inactive 双链表)。易错点:近似 LRU(如 CLOCK)在极端序列下也可能出现类似异常,只是实践中罕见。
追问方向:LRU 精确实现的代价(每次访问更新数据结构)与近似方案、MySQL buffer pool 的中点插入策略解决了什么扫描污染问题。