# 4.8 页面置换算法 ## 一、页面置换的基本概念 ### 1.1 什么是页面置换 **页面置换**：当内存已满，需要调入新页面时，选择内存中的某个页面换出到外存。 ### 1.2 页面置换的原因 - 内存空间不足 - 需要调入新的页面 - 需要释放页框 ### 1.3 页面置换的目标 - 减少缺页次数 - 提高系统性能 - 选择"最合适"的页面换出 --- ## 二、最佳置换算法（OPT） ### 2.1 算法思想 **选择未来最长时间内不被访问的页面换出。** ### 2.2 算法实现 **规则**： - 查看未来页面访问序列 - 选择未来最久不被访问的页面 - 或者未来不再被访问的页面 ### 2.3 算法评价 **优点**： - 理论最优，缺页率最低 **缺点**： - 无法实现，因为无法预知未来 - 仅用于评价其他算法 --- ## 三、先进先出置换算法（FIFO） ### 3.1 算法思想 **选择最先进入内存的页面换出。** ### 3.2 算法实现 **数据结构**：队列 **规则**： - 页面进入内存时，加入队列尾部 - 需要置换时，选择队列头部页面 ### 3.3 Belady异常 **现象**： - 分配页框数增加，缺页次数反而增加 **原因**： - FIFO没有考虑页面访问的局部性 - 可能换出经常使用的页面 **例子**： - 访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 - 3个页框：缺页9次 - 4个页框：缺页10次 --- ## 四、最近最久未使用置换算法（LRU） ### 4.1 算法思想 **选择最近最久未使用的页面换出。** ### 4.2 算法依据 **局部性原理**： - 最近被访问的页面，短期内可能被再次访问 - 最近未被访问的页面，短期内可能不被访问 ### 4.3 算法实现 **方法一：计数器** - 每个页面设置访问计数器 - 访问时更新计数器 - 选择计数器值最小的页面 **方法二：栈** - 页面访问时，移到栈顶 - 栈底页面就是最近最久未使用的 ### 4.4 算法评价 **优点**： - 性能接近OPT - 考虑了页面访问的局部性 **缺点**： - 实现复杂 - 需要硬件支持 - 开销大 --- ## 五、时钟置换算法（Clock） ### 5.1 算法思想 **LRU的近似实现，使用访问位。** ### 5.2 算法实现 **数据结构**： - 循环队列（时钟） - 每个页面有访问位 **算法步骤**： 1. 指针指向最先进入的页面 2. 检查访问位： - 如果为0，选择该页面换出 - 如果为1，置为0，指针下移 3. 重复步骤2，直到找到访问位为0的页面 ### 5.3 改进型时钟算法 **增加修改位**： - 优先换出未修改的页面（不用写回磁盘） **分类**： - 第1类（A=0, M=0）：最近未访问且未修改，最佳淘汰 - 第2类（A=0, M=1）：最近未访问但已修改 - 第3类（A=1, M=0）：最近已访问但未修改 - 第4类（A=1, M=1）：最近已访问且已修改 **算法步骤**： 1. 寻找第1类页面，找到则换出 2. 没找到，寻找第2类页面，找到则换出 3. 没找到，指针回到起始位置，所有访问位置0 4. 重复步骤1-3 --- ## 六、其他置换算法 ### 6.1 最少使用置换算法（LFU） **思想**：选择访问次数最少的页面换出。 **缺点**： - 可能淘汰刚开始使用但访问次数少的页面 ### 6.2 页面缓冲算法（PBA） **思想**： - 被换出的页面放入缓冲区 - 如果再次被访问，直接从缓冲区取回 - 减少I/O操作 --- ## 七、页面置换算法的比较 | 算法 | 思想 | 优点 | 缺点 | 实现难度 | |-----|------|------|------|---------| | OPT | 未来最久不用 | 最优 | 不可实现 | - | | FIFO | 先进先出 | 简单 | Belady异常 | 简单 | | LRU | 最近最久未用 | 性能好 | 开销大 | 复杂 | | Clock | LRU近似 | 较简单 | 近似LRU | 较简单 | | 改进Clock | 考虑修改位 | 减少I/O | 稍复杂 | 较复杂 | --- ## 八、考研重点 1. **各种置换算法的思想**：OPT、FIFO、LRU、Clock 2. **Belady异常**：FIFO的问题 3. **LRU的实现**：计数器、栈 4. **Clock算法**：访问位、指针移动 5. **改进型Clock**：修改位的作用 6. **算法比较**：优缺点、实现难度 --- *下一节：4.9 页面分配策略与抖动*