『操作系统』酱：“哎呀内存太小了，人家又缺页了！”
『操作系统』酱：“哎呀内存太小了，人家又缺页了！”
OS 酱：“哎呀内存太小了，人家又缺页了！”
操作系统–虚页面管理之页面置换算法
系统的内存并不是无限大，操作系统会为每个程序分配内存，当访问的地址块不在内存中，就要从外存（即硬盘，U 盘等）调入，这就是所说的缺页异常。
当发生缺页异常时，操作系统会选择一个页面进行换出从而为新进来的页面腾出空间。对于被置换的页面有以下情况：
如果要被换出的页面只被访问而没被修改，那么直接将此页面丢弃。
如果要被换出的页面被修改，那么为了使得外存中的数据保证正确，先要将内存中的数据写入外存，然后在丢弃。
虽然，被置换页面的可以随机选择，但是不同的选择，所导致后续系统访存开销是不一样，甚至会出现很极端的情况，每次访存都发生缺页中断，极大的增加系统额外的访存开销。
很多的页面置换算法被提出用于操作系统，但是在其他各类应用，无论是数学还是经济学都有类似的涉猎，今天我们就来讨论一下这些算法。
OPT 算法（最佳置换算法）
算法特点：
最佳置换算法是由 Belady 于 1966 年提出的一种理论上的算法。每次选择以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面的页面被淘汰。显然 OPT 算法是最优的，但是在实际操作往往无法预知未来，所以 OPT 只存在理论而不能真的实现，通常用于衡量其他置换算法的优劣。
算法流程：
在缺页中断发生时，首先从 主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。
举例如下：
缺页 9 次，总访问次数 12 次缺页率：6/12 = 50%
FIFO 算法（先进先出置换算法）
Belady 异常：
采用 FIFO 算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
实现方法：
最简单的页面置换算法，每次淘汰最先调入内存的页面。由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾，每次淘汰队首页面。因为先进入的页面可能已经使用完毕，所以不会再被使用的概率可能性较大，优先淘汰。但是 FIFO 容易产生 Belady 异常。
该算法实现比较简单，对具有线性顺序访问的程序比较合适，而对其他情况效率不高。因为经常被访问的页面，往往在内存中停留最久，结果这些常用的页面却因变老而被淘汰。
举例如下：
缺页 9 次，总访问次数 12 次缺页率：9/12 = 75%
LRU 算法 (最近最久未使用算法)
利用局部性原理，根据一个作业在执行过程中过去的页面访问==历史来推测未来==的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。 即淘汰最近最长时间未访问过的页面。
LRU 置换算法的硬件支持
寄存器为每个在内存中的页面配置一个移位寄存器，用来记录某进程在内存中各页的使用情况。移位寄存器表示为 R=Rn-1Rn-2Rn-3…R2R1R0 当进程访问某物理块时，要将相应寄存器的 Rn-1 位置成 1;同时，每隔一定时间将寄存器右移一位；如果把 n 位寄存器的数看作一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
栈利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。
举例如下：
缺页 7 次，总访问次数 12 次缺页率：7/12 = 58.3%
实际上，LRU 算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。LRU 性能较好，但需要寄存器和栈的硬件支持。
LRU 是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现 Belady 异常。
FIFO 算法基于队列实现，不是堆栈类算法。
LRU 算法的性能接近于 OPT，但是实现起来比较困难，且开销大；FIFO 算法实现简单，但性能差。
Clock 算法（时钟置换算法）
也称为 NRU 算法（最近未使用算法）是 LRU 和 FIFO 的折中算法。
实现：CLOCK 算法是给每一个页面设置一个访问位，用来标识是否最近被访问过，Clock 维护的是内存中页面组成的循环链表。当页面被装入内存时，或是内存中的页面被访问时，访问位被置为 1。若内存已被装满，那就需要淘汰一个页面，于是指针就从上一个被淘汰的页面的下一个位置开始，顺序去遍历这循环列表，访问到访问位为 1 的页面时，就把该访问位置 0，继续遍历，只要遇到访问位为 0 的页面时，淘汰该页面。其实调入内存也是访问，那么上面就变成了：
访问则置 1
替换则遍历
遍历遇 1 置 0，遇 0 替换。
举例如下：
内存中共分配 3 个页面资源
改进后的 Clock 算法(二次机会法）
由 访问位 A 和 修改位 M 可以组合成下面四种类型的页面：
最近既未被访问，又未被修改(Visit=0, Modify=0) ：是最佳淘汰页。
最近未被访问，但已被修改(Visit=0, Modify=1)：并不是很好的淘汰页。
最近已被访问， 但未被修改(Visit=1, Modify=0)：该页有可能再被访问。
最近已被访问且被修改(Visit=1, Modify=1)：该页可能再被访问。
执行过程：5. 查找 00，有，淘汰，算法结束！继续循环直到一圈结束，未找到则下一步；6. 查找 01，有，淘汰，算法结束！未找到继续循环遍历直到一圈结束，在此过程中将 Visit 位置为“0”，未找到则下一步；7. 重复第一步。
优点：减少磁盘 I/O；缺点：几轮扫描，增加开销！