题记：
今天，我们来介绍几个页面置换算法。页面置换算法实在请求分页存储时，调页时候会用到的。
正文：
最佳置换算法（OPT）
提出：
由Belady于1966年提出的一种理论上的算法。
思想：
选择那些以后永不使用的，或在最长（未来）时间内不再被访问的页面作为淘汰的页面。
优点：
可保证最低缺页率。
缺点：
对页面的访问时间无法预知，故该算法无法实现。
范例：
假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。
我们对于已知的页面号引用串可以看到，在逐步判断哪个页面在接下来最长时间不用，就替换该页面。
先进先出置换算法（FIFO）
思想：
总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面予以淘汰。
优点：
实现简单
缺点：
往往与进程实际运行的规律不相符。有些页面，如存放全局变量、常用函数的页面，在整个进程的运行过程中将会被频繁访问。如果频繁将其换进换出，则会产生“抖动”现象，因此，这种算法在实际中应用很少。
范例：
假设最小物理块数为3块。页面引用序列如下：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
依次按顺序置换。
最近最久未使用置换算法（LRU）
思想：
赋予每个页面一个访问字段，用来记录相应页面自上次被访问以来所经历的时间t，当淘汰一个页面时，应选择所有页面中其t值最大的页面，即内存中最近一段时间内最长时间未被使用的页面予以淘汰。
LRU的硬件支持 — 栈：
可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它再压入栈顶。即栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。
用栈保存当前使用页面时栈的编号情况。
优点：
由于考虑程序访问的时间局部性，一般能有较好的性能。
实际应用多。
缺点：
实现需要较多的硬件支持，会增加硬件成本。
范例：
假设最小物理块数为3块。页面引用序列如下：
对应，每个页面进入后的栈（栈的深度与物理块数量一致）： 
Clock置换算法（NRU）
含义：
Clock置换算法是一种LRU的近似算法。由于LRU算法需要较多的硬件支持，采用Clock算法只需相对较少的硬件支持。Clock也称之为最近未用算法NRU。
执行过程：
只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。在选择页面淘汰时，只需检查页的访问位，如果是0，就选择该页换出；若为1，则重新将它置为0，暂时不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。由于该算法是循环地检查各页面的使用情况，故称为Clock算法。
优点：
可减少磁盘的I/O操作数
缺点：
实现该算法本身的开销将有所增加
改进型Clock置换算法：
由访问位A和修改位M可以组合成下面四种类型的页面：
1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。
2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。
3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。
4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。
最少使用置换算法（LFU）
为每个页面配置一个计数器，一旦某页被访问，则将其计数器的值加1，在需要选择一页置换时，则将选择其计数器值最小的页面，即内存中访问次数最少的页面进行淘汰。
页面缓冲算法（PBA）
规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入已经修改页面的链表中的一个。
须注意的是，这时页面在内存中并不做物理上的移动，而只是将页表中的表项移到上述两个链表之一中。