(备战招聘)操作系统之页面置换算法概述

大家好，讲到虚拟内存以及分页技术，就不得不提到操作原理中一个重要的概念，页面置换。
页面置换，简单理解就是操作系统通过某种算法将内存中空闲的页置换（淘汰）出去，将磁盘置换空间中的页置换回内存以完成从虚拟内存地址到物理内存的访问。
下面就来给大家总结一下几大常用的页面置换算法以及需要重点掌握的置换算法（有标注）
1、最佳页面置换算法（OPT 难以实现）
设计思路：置换以后不再需要的或最远的将来才会用到的页面
2、先进先出算法（FIFO 掌握）
设计思路：选择在内存中驻留最长的页并置换它
实现：页面链表法
3、第二次机会算法（SCR 了解）
按照先进先出算法选择某一页面，检查其访问位R，如果为0则置换该页面，如果为1，则给第二次机会，并将访问位置0
4、最近未使用算法（NRU Not Recently Used 了解）
选择在最近时间内未使用过的一页并置换
5、最近最少使用算法（LRU Least Recently Used 最重要）
选择最后一次访问时间距离当前时间最长的一页并置换，即置换使用时间最长的一页
性能接近OPT，缺点是需要使用时间戳或者维护一个访问页的栈
6、最不经常使用算法（NFU Not Frequently Used）
选择访问次数最少的页面置换，是LRU算法的一种软件实现
实现：软件计数器，一页一个，初值为0 ，每次时钟中断时，计数器加R（一个整数值），发生缺页中断时，选择计数器值最小的一页置换

算法具体举例：
如下图 系统给某进程分配三个页框（固定分配策略），初始为空
进程执行时，页面访问顺序为 2 3 2 1 5 2 4 5 3 2 5 2

如果是FIFO算法，到第四次该进程占用了三个页框，那么第五次访问页框5的时候将进入内存时间最长的页框2置换出去，第六次访问页框的时候将进入内存时间最长的页框3置换出去，以此类推
如果是LRU算法，到第四次该进程占用了三个页框，第五次访问的时候，页框3距离现在使用时间最长（页框2又被访问了一次），因此置换出去，第七次访问的时候，页框1距离现在使用时间最长，因此将页框1置换出去，以此类推

如果是OPT算法，第五次访问的时候，页框1在未来不再使用，所以将页框1置换出去，第七次访问的时候，页框2是最远的将来才需要用到的页框，所以将页框2置换出去，如果该算法遇到两个可置换出去的页框，则随机选择一个置换出去。

置换算法总结