I IT 面试题库
为什么真实系统很少用「精确 LRU」而多用近似算法?请结合工作集模型与 Clock 谈谈工程权衡。
高级开放讨论题后端开发工程师操作系统LRUClock工作集内存管理
题目
考察点:精确 LRU 的实现成本、工作集模型对「分配多少页」的指导、近似 LRU(Clock 及其改进)的工程取舍。开放讨论。
参考答案
内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 72 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
要点:
- 精确 LRU 的代价:要维护所有页的严格访问时序(时间戳或链表),每次访存都需更新,且需硬件支持完整历史;在多核/大内存下开销不可接受,因此硬件通常只提供「引用位」这类粗粒度信息。
- 近似方案(Clock):只用引用位做环形扫描,O(1) 摊销、无需全局排序,是性能与实现的折中;改进型 Clock 再结合「修改位」优先淘汰干净页,避免无谓的写回。很多系统(如 Linux 的 2Q/LRU 双链、MySQL/Redis 的近似 LRU)都用变种近似算法。
- 工作集模型的意义:Denning 提出「工作集」= 进程在最近 τ 窗口内访问过的页集合;只要分配给进程的内存 ≥ 其工作集,就能把缺页率压到很低。它是「该给进程多少页框」的理论依据,也是判断抖动是否将至的尺子。
- 工程权衡:精确算法效果上限高但实现贵、难扩展;近似算法用很少的硬件/软件成本拿到接近 OPT 的表现。实际选型要在命中率、实现复杂度、多核扩展性之间权衡,并配合监控(缺页率、工作集大小)动态调参。
题目与答案就在本页;收藏、批注和错题重练在应用内