在虚拟内存管理的实现中，最关键的就是页面的调入策略和页面的置换算法。
页面的调入策略主要有两种：预先调入策略和页面请求调入策略。由于前者需要对进程的运行过程进行一定量的预测，所以实现起来比较困难和低效，所以经常采用的是后一种策略，即当执行进程所需的某个页面不在内存时，产生缺页中断，再由专门的缺页中断服务程序(ISR)根据进程页表将所需页面调入内存。
当缺页中断服务程序发现，内存中已经没有空闲的物理页面(通常称之为帧)时，就会执行一种页面换出程序，它采取一定的置换算法将某个页面换出到外存的交换(文件)分区。通常，衡量一种页面置换算法性能好坏的指标就是对于大量的页面请求序列，在一定数量的物理帧上，产生缺页中断的平均次数。页面置换算法较多，其变种更多，常常见诸于各大OS教材的主要由下面的几种。
-
先入先出法(FIFO)
Fist In Fist Out, 这是一种实现起来最为简单的算法，其实质是，最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是，总是选择在主存中停留时间最长(即最老)的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。另外，FIFO算法还有一个比较有意思的缺陷，称之为Berlady异常(或者?)，说当物理内存也即帧数增加时，其缺页中断的次数反而有可能增加！ -
最优置换算法(OPT)
最优置换(OPTimal replacement)，顾其名，知其义，这是一种最优的算法，因为对于任一页面请求序列，其产生的缺页中断次数时最少的，但，这只是理论上的最优。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。其最优性是容易证明的。
但是最优页面置换算法的实现是困难的，因为它需要我们预先就知道一个进程整个运行过程中页面走向的全部情况，而这几乎时不可能的。所以，这个算法主要还是用来衡量其他算法的优劣的。 -
最近最久未使用算法(LRU)
最近最久未使用算法(Least-Recently Used)，它的核心思想是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。既然要以时间为替换依据，那么肯定就要用到定时/计数器，因此这个算法通常需要一定的硬件支持，这样的话其通用性也会降低。还有一种LRU的近似算法，最近未使用算法(Not Recently Used，NUR)，相比LRU实现起来更简单一些。它在页表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。需要页面替换时，就可把该位是0的页淘汰出去。
-
二次机会算法(SC)
这是一种FIFO和LRU的折中，或者说结合，它避免了FIFO的缺陷，即可能把经常使用的页面替换出去(比如说装入程序?)。它的思想是：需要页面替换时，检查它的访问位。如果是0，就淘汰这页；如果访问位是1，就将其清0，同时给它第二次机会，然后检验下一个FIFO页面。因此，如果一个页面经常使用，它的访问位总保持为1，它被淘汰出去的几率是很小的。
还有其他很多页面置换算法，实际使用的算法通常就是这些算法的一些折中或者说变种，可见，要想把一个理论上的好算法应用到具体的问题上，会受到很多限制，还需要做不少其他的工作。
原文地址：http://www.dutor.net/index.php/2009/11/vm-page-schedule/