虚拟内存与页面置换算法 描述 虚拟内存是操作系统内存管理的一种技术，它允许程序认为自身拥有连续可用的内存空间，而实际上物理内存可能被分割成多个碎片，甚至部分数据存储在外部磁盘上。当物理内存不足时，操作系统需要通过 页面置换算法 选择将哪些页面换出到磁盘，以腾出空间给急需的页面。常见的页面置换算法包括 最佳置换算法（OPT） 、 先进先出算法（FIFO） 、 最近最久未使用算法（LRU） 等。 循序渐进讲解 虚拟内存的基本概念 程序运行时，只有部分代码和数据需要加载到物理内存，其余部分可暂存在磁盘的 交换区 。 内存被划分为固定大小的块（称为 页 ），磁盘中的对应块称为 页框 。 当程序访问一个不在物理内存中的页时，触发 缺页异常 ，操作系统需要从磁盘调入该页。 为何需要页面置换 物理内存空间有限，当缺页异常发生且物理内存已满时，必须选择一个现有页面换出到磁盘。 目标：尽可能减少缺页次数，避免系统频繁访问磁盘（磁盘速度远慢于内存）。 常见页面置换算法详解 （1）最佳置换算法（OPT） 思想 ：换出未来最长时间不会被访问的页面（理想化算法，无法实际实现，但作为性能对比基准）。 举例 ：假设页面访问序列为 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ，物理内存容量为3页： 访问页5时，内存中已有 1,2,3 ，但页4即将被访问，而页3在未来最晚出现，故换出页3。 缺点 ：需要预知未来访问序列，仅用于理论分析。 （2）先进先出算法（FIFO） 思想 ：维护一个队列，先进入内存的页面先被换出。 举例 ：同样序列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ，内存容量3页： 访问页4时，换出最早进入的页1；访问页5时，换出页2。 缺点 ：可能换出频繁使用的页面（如首页被换出后很快又需调入），导致 Belady异常 （内存增大后缺页率反而升高）。 （3）最近最久未使用算法（LRU） 思想 ：根据历史访问时间，换出最久未被访问的页面（基于局部性原理：最近被访问的页面可能很快再被访问）。 实现方式 ： 维护一个链表，访问某页时将其移到链表头部，缺页时淘汰链表尾部的页面。 或用硬件计数器记录每个页面的访问时间戳。 举例 ：序列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ，内存容量3页： 访问页4时，内存中 1,2,3 ，页3是最近最久未使用的（时间顺序：1最早被访问，但页1在中间被重新访问过，需动态计算）。 优点 ：接近OPT效果，实际应用广泛。 算法对比与总结 OPT ：理论最优，但不可实现。 FIFO ：简单但效率低，可能出现Belady异常。 LRU ：需要硬件支持（如时间戳或链表），开销大但效果好。 实际系统中可能采用 近似LRU 的算法（如时钟算法/二次机会算法），平衡性能与开销。 关键点记忆 页面置换算法的核心是 减少缺页率 。 LRU及其变种是实践中最常用的策略。 理解算法需结合具体访问序列模拟置换过程（可动手画图）。