I IT 面试题库
常见的页面置换算法有哪些?请给出 FIFO、LRU、Clock 的原理、优缺点,并说明 Belady 异常。
中级场景题后端开发工程师操作系统页面置换FIFOLRUClock
题目
考察点:页面置换算法对比、Belady 异常(FIFO 特例)、各算法在真实系统中的可行性。以场景题形式给出访问序列让候选人分析。
参考答案
内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 72 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
要点:
- FIFO(先进先出):淘汰最早进入的页。实现简单,但有 Belady 异常——分配的物理页框增多时缺页率反而可能上升,且无法反映页面近期热度,性能差。
- LRU(最近最少使用):淘汰最久未被访问的页,近似「局部性原理」下的最优(OPT)效果。性能最好但实现开销大(需维护精确的访问时间戳或栈),硬件通常只提供「引用位」而非完整历史。
- Clock(时钟/二次机会):把所有页排成环,每页一个引用位;扫指针遇引用位=1 则清 0 并跳过(给第二次机会),遇 0 则淘汰。是 LRU 的近似,开销小、工程常用。改进版(改进型 Clock)还会结合「修改位」优先淘汰未修改页以减少写回。
- OPT(最佳):淘汰「未来最久才被访问」的页,理论下界,但需预知未来,仅用于对比评估。
- 场景结论:面试常给访问序列让你手算缺页数;记住 FIFO 可能 Belady 异常、LRU/Clock 不会,工程上多用 Clock 或其变种。
题目与答案就在本页;收藏、批注和错题重练在应用内