页面置换算法：在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 

常见的页面置换算法：

最佳置换算法（OPT）：这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：其所选择的淘汰页面将是以后永远不使用的，或许是在最长（未来）时间内不再被访问的页面。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。 

假定系统为某进程分配了三个物理块，并考虑有以下的页面引用串：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

1、先将7，0，1三个页面装入内存s

2、访问2号页面时，因为三个物理块都被占满了，则需要用OPT算法将一个页面置换出来，从左向右看，7，0，1三个页面中，7号页面是在最长（未来）时间内不再被访问的页面，所有用2号页面将7号页面置换出来。

3.当到4号页面的时候，2，0，3中，0号页面是在最长（未来）时间内不再被访问的页面，所有用4号页面将0号页面置换出来。

4、到0号页面时，2，4，3三个页面里面，4号页面将不再被访问，所有用0号页面将4号页面置换查出来。

5、方法同上。

 先进先出页面置换算法（FIFO）：优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

假定系统为某进程分配了三个物理块，并考虑有以下的页面引用串：

3，2，1，0，3，2，4，3，2，1，0，4

1、先将3，2，1三个页面装入内存。

2、到0号页面时，3号页面是在内存中驻留最久的的页面，所以用0号页面置换3号页面。

3、到3号页面时，0，1，2三个页面中，2号为驻留时间最久的页面，用3号置换2号页面。

4、到2号页面使0，3，1三个页面中，1号为驻留时间最久的页面，用2号置换1号页面。

5、方法同上

最近最久未使用算法 （LRU）：选择最近最久未使用的那个页面淘汰掉。

假定系统为某进程分配了三个物理块，并考虑有以下的页面引用串：

1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7，1，3，7

1、先将4个物理块存满，到2号页面时4个物理块存满，之后到3号页面需要置换。

2、从3号页面向前看，根据LRU算法，7号页面是最近最久未使用的，所以用3号置换7号。

3、到7号页面时向前看，8，2，1，3，1中，8号为最近最久未使用，则用7号置换8号页面。