把选择换出页面的算法称为页面置换算法，置换算法的好坏直接影响到系统的性能。
不适当的算法可能回导致进程发生“抖动”，即刚被换出的页很快又被访问，需要将它重新调入，此时又需要再选一页调出。
最佳置换算法和先进先出置换算法
下面两种是比较极端的算法，最佳置换算法是一种理想化的算法，具有最好的性能但是实际上无法实现。而先进先出算法是最直观的算法，由于与通常页面的使用规律不符，可能是性能最差的算法。
- 最佳置换算法
选择的淘汰页面将是以后永不使用的，或许是最长时间不再被访问的页面。
- 先进先出算法
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
最近最久未使用和最少使用置换算法
- LRU(Least Recently Used)置换算法的描述
LRU页面置换算法是根据页面调入内存后的使用情况作出决策的，LRU是选择最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面上次被访问以来所经历的时间t。当淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
- LRU置换算法的硬件支持
LRU虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有寄存器和栈两类硬件之一的支持
1） 寄存器
为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为：
R=Ra-1Ra-2Ra-3···R2R1R0当进程访问某物理块时，要将相应寄存器的Ra-1位置设置成1。此时定时信号将没隔一定时间(例如100ms)将寄存器右移一位。
这里可能有点抽象，我理解是如下。就是每隔一段时间，将寄存器右移一位，从R7 -> R6，然后判断对应的页是否被使用，如果使用了则记为1，未使用则记为0，则通过统计这8个寄存器中的记录(R值)，如：
00010011跟00000101等总共8个值，明显在00010011跟00000101比较的话，后者比前者小，则说明后者更久未使用
| 时间 | 0 | 100ms | 200ms |
|---|---|---|---|
| 页号 | 1 | 1 | 1 |
| 寄存器 | R7:0 | R6:1 | R5:1 |
如果把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面就是最近最久未使用的页面。
2） 栈
利用一个特殊的栈保存当前使用的各个页面的页面号，每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。
假设一进程，分为5个物理块，所访问的页面号序列未：
4,7,0,7,1,0,1,2,1,2,6当第四次访问时，因为7已存在在栈中，注意这里的操作是，直接将栈中的7移除了，然后再把第4次访问的7放如栈顶
- 最少使用(Least Frequently Used, LFU)置换算法
在LFU算法中采用了移位寄存器方式，刚上面的LRU的访问图完全相同。但是是将Ra-1Ra-2···R2R1求和。
应该指出，这种算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，在该时间间隔内，对某页访问一次和访问1000次是完全等效的。
Clock置换算法
虽然LRU是一种较好的算法，但由于要求比较多的硬件支持，使得其实现所需的成本较高，故实际应用中，大多采用LRU近似算法，Clock算法就是用的比较多的一种LRU近似算法
- 简单的Clock置换算法
为每页设置一位访问位，将内存中的所有页面都通过链接指针连接成一个循环队列，当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位，如果是0则置换出，如果是1则置为0，再按照FIFO算法检查下一个页面，当其访问位仍为1时，则再返回到队首去检查第一个页面。
但因为该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，故又把该算法成为最近未用算法或NRU(Not Recently Used)算法。
- 改进型Clock置换算法
在改进型Clock算法中，除须考虑页面的使用情况外，还需再增加一个因素——置换代价。这样，选择页面置换出时，既要是未使用过的页面，又要是未修改过的页面。
由访问位A和修改位M可以组合成下面四种类型的页面：
- A=0,M=0, 既最近未访问又没修改过，是最佳的淘汰页
- A=0,M=1，最近未访问，但修改过了，不是很好的淘汰页
- A=1,M=0, 最近已访问过，未修改过，可能再被访问
- A=1,M=1，最近咦访问，且修改过，可能再被访问
该算法的执行过程可分为以下三步：
- 从指针所指示的位置开始，扫描循环队列，寻找A=0且M=0的页，第一次扫描不改变访问位A
- 如果第一步失败，继续扫描循环队列，寻找A=0且M=1的页，第二轮扫描期间，将所有扫过的页面访问位设置为0
- 如果第二步页失败了，则将指针返回到开始的位置，并将所有的访问位复0，然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页
该算法与简单Clock算法比较，可减少磁盘的I/O操作次数，但为找到一个可置换的页，可能须经过几轮扫描，换言之，实现该算法本身的开销将有所增加
页面缓冲算法(Page Buffering Algorithm, PBA)
- 影响页面换进换出效率的若干因素
- 页面置换算法
- 写回磁盘的频率
- 读入内存的频率
- 页面缓冲算法PBA
PBA算法的主要特点是：
- 显著降低页面换进、换出的频率，使磁盘I/O操作次数大为减少
- 正由于换入换出的开销大幅度减少，才能使其采用一种较简单的置换策略，如FIFO
为了能显著降低页面换进、换出的频率，在内存中设置了如下两个链表
- 空闲页面链表
该链表是一个空闲物理块链表，是系统掌握的空闲物理块，用于分配给频繁发生缺页的进程，以降低该进程的缺页率。当这样的进程需要读入一个页面时，便可利用空闲物理块链表中的第一个物理块来装入该页。
当下次再次请求该页面时，不需要再从外存中读入，而直接在该链表中取出
- 修改页链表
该链表是已修改的页面所形成的链表。跟上述原理几乎一样，只是这个链表用于存放被置换出去已修改的页，这样可以减少写到外存的频率，也可以减低从外存载入到内存的频率。