OS酱：“哎呀内存太小了，人家又缺页了！”

操作系统--虚页面管理之页面置换算法

系统的内存并不是无限大，操作系统会为每个程序分配内存，当访问的地址块不在内存中，就要从外存（即硬盘，U盘等）调入，这就是所说的缺页异常。

当发生缺页异常时，操作系统会选择一个页面进行换出从而为新进来的页面腾出空间。对于被置换的页面有以下情况：

1. 如果要被换出的页面只被访问而没被修改，那么直接将此页面丢弃。
2. 如果要被换出的页面被修改，那么为了使得外存中的数据保证正确，先要将内存中的数据写入外存，然后在丢弃。

虽然，被置换页面的可以随机选择，但是不同的选择，所导致后续系统访存开销是不一样，甚至会出现很极端的情况，每次访存都发生缺页中断，极大的增加系统额外的访存开销。

很多的页面置换算法被提出用于操作系统，但是在其他各类应用，无论是数学还是经济学都有类似的涉猎，今天我们就来讨论一下这些算法。

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
2. 替换则遍历
3. 遍历遇1置0，遇0替换。

举例如下：

内存中共分配3个页面资源

改进后的Clock算法(二次机会法）

由 访问位A 和 修改位M 可以组合成下面四种类型的页面：

1. 最近既未被访问，又未被修改(Visit=0, Modify=0) ：是最佳淘汰页。
2. 最近未被访问，但已被修改(Visit=0, Modify=1)：并不是很好的淘汰页。
3. 最近已被访问， 但未被修改(Visit=1, Modify=0)：该页有可能再被访问。
4. 最近已被访问且被修改(Visit=1, Modify=1)：该页可能再被访问。

执行过程：5. 查找00，有，淘汰，算法结束！继续循环直到一圈结束，未找到则下一步；6. 查找01，有，淘汰，算法结束！未找到继续循环遍历直到一圈结束，在此过程中将Visit位置为“0”，未找到则下一步；7. 重复第一步。

优点：减少磁盘I/O；缺点：几轮扫描，增加开销！