Belady 最优置换算法

定义

Belady 最优置换算法(又称 OPT 或 MIN)由匈牙利裔计算机科学家 László Bélády 于 1966 年在 IBM 提出:每次淘汰「未来最长时间内不会被再次访问」的缓存条目,可证明其缺页/未命中次数最少。

原理

该算法需要预知完整的未来访问序列,因此无法在线实现,属于「离线最优」策略。它的价值在于给出理论上界:任何可实现的置换算法(LRU、LFU、ARC 等)的命中率都不会超过 OPT,研究者用它衡量实际算法距离最优还有多远。

相关概念

Bélády 还发现了著名的「Belady 异常」:对 FIFO 置换算法,增加缓存容量反而可能导致缺页次数上升,这一反直觉现象说明并非所有算法都满足栈特性(LRU 等栈算法不存在此异常)。

应用

近年有研究用机器学习模拟 OPT 的决策(如学习型缓存),即通过预测未来访问来逼近 Belady 边界;它也是操作系统课程中页面置换一节的标准内容。