操作系统中的内存管理：页面置换算法（FIFO、LRU、OPT） 1. 问题背景 虚拟内存允许进程的部分页面驻留在物理内存中，其余页面保存在磁盘上。当访问的页面不在内存时，会触发“缺页异常”（Page Fault），此时操作系统需选择一个内存中的页面换出到磁盘，为请求的页面腾出空间。如何选择被换出的页面？这就是 页面置换算法 要解决的问题。 2. 核心目标 最小化缺页率（Page Fault Rate），避免频繁的磁盘I/O，提升系统性能。 3. 常见算法详解 （1）先进先出（FIFO） 思想 ：选择最早进入内存的页面换出。 实现 ：使用队列记录页面进入顺序，换出队首页面，新页面加入队尾。 例子 ： 假设物理内存容量为3，页面访问序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 访问页面1, 2, 3：缺页3次，内存状态[ 1,2,3 ]（队列顺序1→2→3） 访问页面4：换出1（最早进入），缺页1次，内存[ 2,3,4 ] 访问页面1：换出2，缺页1次，内存[ 3,4,1 ] ...（继续模拟） 缺点 ：可能换出常用页面（如最早进入但频繁使用的页面），导致“Belady异常”（增加内存帧数反而缺页率上升）。 （2）最近最少使用（LRU） 思想 ：换出最久未被访问的页面，基于“局部性原理”（最近使用的页面可能被再次使用）。 实现 ： 维护链表或栈：访问页面时移至头部，队尾页面即最久未使用。 或使用硬件计数器：记录每个页面的最后访问时间。 例子 （内存容量3，序列同FIFO例子）： 访问1,2,3：缺页3次，内存[ 1,2,3 ]（按访问时间排序） 访问4：换出1（最久未使用），内存[ 2,3,4 ] 访问1：换出2，内存[ 3,4,1 ] 访问2：换出3，内存[ 4,1,2 ] 优势 ：比FIFO更贴合访问规律，缺页率更低。 缺点 ：硬件实现成本高（需维护精确访问历史）。 （3）最优置换（OPT） 思想 ：换出“未来最长时间不会被访问”的页面，是理想化的理论算法。 实现 ：需预知未来页面访问序列，选择未来最晚出现的页面换出。 例子 （内存容量3，序列同上）： 访问1,2,3：缺页3次 访问4：根据未来序列(1,2,5...)，页面1下次出现在第5次访问，页面2在第6次，页面3在最晚（第11次），故换出3 → 内存[ 1,2,4 ] 访问1：命中，不换出 访问2：命中 访问5：未来序列中，页面1下次出现在第8次，页面2在第9次，页面4不再出现，故换出4 → 内存[ 1,2,5 ] 意义 ：作为其他算法的性能上界（缺页率最低），但实际不可实现（无法预知未来）。 4. 算法对比 FIFO ：简单但效率低，可能Belady异常。 LRU ：接近OPT性能，是实际常用算法（近似实现如Clock算法）。 OPT ：理论最优，用于评估其他算法。 5. 总结 页面置换算法的选择需权衡实现复杂度与性能。现代操作系统常采用LRU的变种（如二次机会算法、Clock算法），在硬件支持下平衡效率与开销。