【操作系统不挂科】逐步骤详解——＞四种页面置换算法例题＜LPU最近最久未使用＆OPT最优＆FIFO先进先出＆CLOCK时钟置换算法＞

前言 大家好吖，欢迎来到 YY 滴 操作系统不挂科 系列 ，热烈欢迎！ 本章主要内容面向接触过C++的老铁 本博客主要内容主要是解析四种算法

同类型题-前置知识点：

1. 缺页错误 ：即缺页
2. 置换数 ：即 置换数=缺页数-物理块数

一.FIFO置换算法（先进先出算法）——最简单置换算法

1.基本规则介绍：

• 当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即 先进入主存的页面先淘汰。
• 遇到重复的，就 直接跳过 就行

2.例题演示：

• 考虑下面的页面引用串： 7，2，3，1，2，5，3，4，6，7，7，1，0，5，4，6，2，3，0，1 假设采用3个帧的请求调页，FIFO置换算法会发生多少次缺页错误？
• 17

• 遇到重复就跳过
• 依此类推得到最后结果：

二.LPU置换算法（最近最久未使用置换算法）——往前看

1.基本规则介绍：

• LRU替换算法: 使用lru算法进行页面置换时，每次替换 最近，最久，未被使用 的页面。下面是使用LRU算法进行页面置换时的过程
• 遇到重复的，就 直接跳过 就行

2.例题演示：

• 考虑下面的页面引用串： 7，2，3，1，2，5，3，4，6，7，7，1，0，5，4，6，2，3，0，1 假设采用3个帧的请求调页，LPU置换算法会发生多少次缺页错误？
• 18

• 遇到重复就跳过
• 依此类推得到最后结果：

三.OPT置换算法（最优置换算法）——往后看

1.基本规则介绍：

• 遇到重复的，就 直接跳过 就行
• 需要淘汰页面时，选择将来 最长时间内不再被访问 的页面，或者选择 以后永不使用的页面 进行淘汰， 往后看 。————————（例题1）
• 重点：需要淘汰页面时，遇到要选择 两个/两个以上页面以后永不使用的页面谁要淘汰时 ，这时我们用 先进先出原则 ——————————（例题2）

2.例题1演示：

• 考虑下面的页面引用串： 7，2，3，1，2，5，3，4，6，7，7，1，0，5，4，6，2，3，0，1 假设采用3个帧的请求调页，OPT置换算法会发生多少次缺页错误？
• 13

>

• 如果后面没有出现7，即找到不再用到的数字（7）的物理块替换

• 以此类推

3.例题2演示：（遇到要选择 两个/两个以上页面以后永不使用的页面谁要淘汰时）

• 考虑下面的页面引用串： 1、2、3、4、1、2、5、1、2、3、4、5假设采用3个帧的请求调页，OPT置换算法会发生多少次缺页错误？
• 7
• 基本做法和例题1一致：但是会遇到“两个/两个以上页面以后永不使用的页面谁要淘汰时”这种情况
• 重点：需要淘汰页面时，遇到要选择 两个/两个以上页面以后永不使用的页面谁要淘汰时 ，这时我们用 先进先出原则 ，也就是先出1

• 下一步我们继续沿用这个原则，最终得出结果

四.CLOCK置换算法（时钟置换算法）

1.基本规则介绍：

• 总结：内存块满时，循环扫描各页面，第一轮淘汰访问位=0的，若没选中（访问位由1改0），进行下一轮循环
• 每个页面设置一个 访问位： 当某页被访问时，其访问位，置为1
• 当需要淘汰一个页面时，只需检查页的访问位；

1. 如果是0，选择此页换出；
2. 如果是1，把它置0，暂不换出；
3. 继续检查下一个页

• 每次新换入一个页面后，访问位，置1； 指针指向下一个页面

2.例题演示：

• 考虑下面的页面引用串： 1、2、3、4、1、2、5、1、2、3、4、5假设采用3个帧的请求调页，CLOCK置换算法会发生多少次缺页错误？
• 9
• 每次新换入一个页面后， 访问位，置1；
• 指针指向下一个页面

• 同理，我们一直进行到下内存块满

• 第一轮循环

• 第二轮循环
• 发现内存块物理1，的1，的访问位=0，替换掉
• 换入一个新页面，4的标志位，置1；指针指向下一个页面

• 下一步我们继续沿用这个原则，要么直接替换，要么进行一轮循环二轮循环

• 重复就跳过

• 最终得出结果

• 缺页错误9次