当有足够的内存时，发生页错误，只需要将页加入内存即可，但是如果内存不够，就需要将内存中的一些页换出，放入磁盘中去。那么现在问题就在于，要将那些页面换出呢？

这些存在于内存中的页，可以看作是一个缓存，如果访问该页时，页在内存，就当作缓存命中，不在就是没命中，那么我们的目标就变为让缓存的命中率尽可能地提高。

最优替换策略

该替换策略是将最远的将来才会使用到的页替换出去，这样就能使得命中率最高，但是也很难实现，或者换种方式说，几乎无法实现。因为我们无法知道哪个页最远才会被使用，该算法只能作为一个比较使用。

FIFO（先进先出）

先进入系统的页就先被换出。优点是实现很简单。缺点是可能导致内存页命中率特别低，极端情况下还会为0。

随机

依靠随机数，替换出某些页。该策略实现页比较简单，但是依靠运气。

利用历史数据：LRU

该算法考虑历史使用数据，如果一个页被很频繁的使用，那么它应该是比较重要的，不应该被换出。那么那些最近最不经常使用的页，就会被换出内存。

这里使用了局部性原则，包括空间局部性和时间局部性。

面临的问题：

该算法要求我们，每次访问内存，都需要同步的做一些修改，来更新页面位于队列中的位置。为了记录那些页最少被访问，我们需要记录内存的引用，但是这些记录可能会导致占用大量空间。

如果通过硬件实现，比如给每个页设置一个时间，每次系统访问内存时，硬件去更新该时间，而需要替换出页时，扫描所有页找到最久的即可。但是页特别多的话，耗时非常高。

近似的LRU

该算法的实现需要硬件添加一个使用位。系统的每一个页都有一个存在位，该值是0或者1。每当该页被引用时，就将该位改为1。但是硬件不会将其置为0，这是由操作系统设置的。

该算法的实现是始终算法。即将所有的页放在一个循环队列中，时钟指针开始时指向某个页，当需要替换页时，会检查时钟指针指向的页的标记为是0还是1，如果是1就说明不适合换出，而0就将它换出。如果是1，就会找下一个页，一直到找到一个是0的为止。如果找完所有的页，还是没有0，那么就将所有的页都设置为0。

它的一个改进算法为，扫描到1的，不置换出该页，但是将标记位改为0，防止遍历完一遍后找不到为0的标记位。

参考

《操作系统导论》