适合读者软考中级备考同学阅读时间4分钟内容四种页面置换算法的原理、示例、优缺点、Belady异常、例题1. 为什么需要页面置换在虚拟存储器中当程序访问的页面不在物理内存中缺页且内存已满时必须选择换出某个页面腾出空间装入所需页面。选择换出哪个页面的规则就是页面置换算法。软考中常考查四种经典算法OPT最佳置换、FIFO先进先出、LRU最近最久未使用、CLOCK时钟算法。2. 算法介绍2.1 OPTOptimal最佳置换算法原理选择未来最长时间内不会被访问的页面换出。特点理论最优缺页率最低但无法实现因为无法预知未来。作用作为衡量其他算法性能的参照标准。示例访问序列7,0,1,2,0,3,0,4,2,3,0,3,2内存容量3帧OPT的缺页次数为7具体过程略。软考通常要求计算OPT的缺页次数或判断哪个算法最优。2.2 FIFOFirst In First Out先进先出原理选择在内存中驻留时间最长的页面换出即最早进入的页面。实现维护一个队列新页面加入队尾换出队首。优点实现简单。缺点可能出现Belady异常分配更多帧缺页次数反而增加性能不佳。Belady异常示例访问序列1,2,3,4,1,2,5,1,2,3,4,5内存3帧时缺页9次4帧时缺页10次。软考常考计算FIFO的缺页次数以及判断是否发生Belady异常。2.3 LRULeast Recently Used最近最久未使用原理选择最近最长时间没有被访问的页面换出。依据过去推测未来。实现可用栈或计数器记录访问时间。优点性能较好接近OPT。缺点硬件支持开销大需要维护访问顺序。示例同上访问序列LRU的缺页次数通常少于FIFO。软考LRU是重点常要求手工模拟缺页过程注意与FIFO区分。2.4 CLOCK时钟算法又称NRUNot Recently Used原理是LRU的近似实现性能较好且开销小。每个页面有一个使用位访问位Reference Bit。算法步骤内存中的页面排成循环队列指针指向某个页面。发生缺页时检查当前指针指向的页面若使用位为1则将其清0指针前移若使用位为0则换出该页面装入新页面并置使用位为1指针前移。重复直到找到使用位为0的页面。改进型CLOCK增加修改位脏位优先淘汰未使用且未修改的页面。软考常考CLOCK算法的工作过程有时会要求模拟。3. 四种算法对比表算法依据是否可实现缺页率硬件开销Belady异常OPT未来访问时间否最低无无FIFO进入时间是较高低有LRU最近一次访问时间是近似较低高无CLOCK近期是否被访问是较低中无4. 经典例题题目1某系统采用FIFO置换算法内存分配3个页框访问序列为1,2,3,4,1,2,5,1,2,3,4,5求缺页次数初始为空。解模拟过程略缺页次数为9。答案9次题目2同访问序列内存分配4个页框FIFO缺页次数为10此现象称为 。答案Belady异常题目3采用LRU算法内存3个页框访问序列4,7,0,7,1,0,1,2,1,2,6求缺页次数。解手动模拟访问4缺内存[4]7缺[4,7]0缺[4,7,0]7命中顺序更新为[4,0,7]1缺淘汰最久未用的4[0,7,1]0命中[7,1,0]1命中[7,0,1]2缺淘汰7[0,1,2]1命中[0,2,1]2命中[0,1,2]6缺淘汰0[1,2,6]缺页次数7次。答案7次题目4CLOCK算法中每个页面的使用位初始为0。当前指针指向页框0页框内容及使用位为页0:1页1:0页2:1页3:0。发生缺页时按照CLOCK算法哪个页框被换出解检查页0使用位1 → 清0指针移到页1检查页1使用位0 → 换出页1指针移到页2答案页15. 记忆口诀OPT看未来理论最优实难求。FIFO排队走Belady异常要记熟。LRU寻旧页过去最近未使用。CLOCK转圈查使用位零就换走。6. 给备考同学的一句话页面置换算法是软考操作系统的必考内容。重点掌握FIFO和LRU的缺页次数计算手工模拟Belady异常只出现在FIFOOPT用于参考CLOCK是实际常用算法考试时如果遇到较长的访问序列建议画表格逐行模拟避免出错。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #页面置换算法 #OPT #FIFO #LRU #CLOCK #计算机系统知识
页面置换算法（OPT、FIFO、LRU、CLOCK）
适合读者软考中级备考同学阅读时间4分钟内容四种页面置换算法的原理、示例、优缺点、Belady异常、例题1. 为什么需要页面置换在虚拟存储器中当程序访问的页面不在物理内存中缺页且内存已满时必须选择换出某个页面腾出空间装入所需页面。选择换出哪个页面的规则就是页面置换算法。软考中常考查四种经典算法OPT最佳置换、FIFO先进先出、LRU最近最久未使用、CLOCK时钟算法。2. 算法介绍2.1 OPTOptimal最佳置换算法原理选择未来最长时间内不会被访问的页面换出。特点理论最优缺页率最低但无法实现因为无法预知未来。作用作为衡量其他算法性能的参照标准。示例访问序列7,0,1,2,0,3,0,4,2,3,0,3,2内存容量3帧OPT的缺页次数为7具体过程略。软考通常要求计算OPT的缺页次数或判断哪个算法最优。2.2 FIFOFirst In First Out先进先出原理选择在内存中驻留时间最长的页面换出即最早进入的页面。实现维护一个队列新页面加入队尾换出队首。优点实现简单。缺点可能出现Belady异常分配更多帧缺页次数反而增加性能不佳。Belady异常示例访问序列1,2,3,4,1,2,5,1,2,3,4,5内存3帧时缺页9次4帧时缺页10次。软考常考计算FIFO的缺页次数以及判断是否发生Belady异常。2.3 LRULeast Recently Used最近最久未使用原理选择最近最长时间没有被访问的页面换出。依据过去推测未来。实现可用栈或计数器记录访问时间。优点性能较好接近OPT。缺点硬件支持开销大需要维护访问顺序。示例同上访问序列LRU的缺页次数通常少于FIFO。软考LRU是重点常要求手工模拟缺页过程注意与FIFO区分。2.4 CLOCK时钟算法又称NRUNot Recently Used原理是LRU的近似实现性能较好且开销小。每个页面有一个使用位访问位Reference Bit。算法步骤内存中的页面排成循环队列指针指向某个页面。发生缺页时检查当前指针指向的页面若使用位为1则将其清0指针前移若使用位为0则换出该页面装入新页面并置使用位为1指针前移。重复直到找到使用位为0的页面。改进型CLOCK增加修改位脏位优先淘汰未使用且未修改的页面。软考常考CLOCK算法的工作过程有时会要求模拟。3. 四种算法对比表算法依据是否可实现缺页率硬件开销Belady异常OPT未来访问时间否最低无无FIFO进入时间是较高低有LRU最近一次访问时间是近似较低高无CLOCK近期是否被访问是较低中无4. 经典例题题目1某系统采用FIFO置换算法内存分配3个页框访问序列为1,2,3,4,1,2,5,1,2,3,4,5求缺页次数初始为空。解模拟过程略缺页次数为9。答案9次题目2同访问序列内存分配4个页框FIFO缺页次数为10此现象称为 。答案Belady异常题目3采用LRU算法内存3个页框访问序列4,7,0,7,1,0,1,2,1,2,6求缺页次数。解手动模拟访问4缺内存[4]7缺[4,7]0缺[4,7,0]7命中顺序更新为[4,0,7]1缺淘汰最久未用的4[0,7,1]0命中[7,1,0]1命中[7,0,1]2缺淘汰7[0,1,2]1命中[0,2,1]2命中[0,1,2]6缺淘汰0[1,2,6]缺页次数7次。答案7次题目4CLOCK算法中每个页面的使用位初始为0。当前指针指向页框0页框内容及使用位为页0:1页1:0页2:1页3:0。发生缺页时按照CLOCK算法哪个页框被换出解检查页0使用位1 → 清0指针移到页1检查页1使用位0 → 换出页1指针移到页2答案页15. 记忆口诀OPT看未来理论最优实难求。FIFO排队走Belady异常要记熟。LRU寻旧页过去最近未使用。CLOCK转圈查使用位零就换走。6. 给备考同学的一句话页面置换算法是软考操作系统的必考内容。重点掌握FIFO和LRU的缺页次数计算手工模拟Belady异常只出现在FIFOOPT用于参考CLOCK是实际常用算法考试时如果遇到较长的访问序列建议画表格逐行模拟避免出错。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #页面置换算法 #OPT #FIFO #LRU #CLOCK #计算机系统知识
