1、FIFO页置换
最简单的页置换算法。选择最旧的页进行置换。具体为创建一个FIFO队列来管理内存中的所有页，队列中的首页被置换，而新调入的页则加到队列的尾部。
FIFO算法容易理解和实现，但性能不总是很好。所替代的页可能仍在使用，换出去以后马上报页错误，要求换回来。
2、最优置换
置换最长时间不使用的页（预测其未来经过多长时间才被使用）。这种算法页错误率最低。这种算法问题在于难以实现。
3、LRU页置换（最近最少使用算法）
最优置换的近似。最优置换与FIFO的关键区别在于，FIFO使用的是页调入时间，而最优置换看重的是页将来使用的时间。如果使用离过去最近作为不远将来的近似，那么可置换最长时间没有使用的页。根据过去来猜测未来。这种方法称为 最近最少使用算法。
实现LRU算法，可用计数器，也可用栈：凡用过的页，就放到顶部，不用的就沉到栈底。
4、近似LRU页置换
很少有计算机系统能提供足够的硬件来支持真正的LRU页置换。然而，许多系统通过引用位方式来进行近似置换：页表内的每个条目都关联一个引用位，每当引用一个页时，相应的引用位就被硬件置位；刚开始时，所有引用位都清零，后来许多被置为1。通过检查引用位，可以知道哪些页使用过而哪些没有。这个信息是近似LRU置换算法的基础。
5、基于计数的页置换
为每个页设置一个计数器，形成两种方案
1）最不经常使用页置换算法（LFU)
置换计数最小页。理由是活动页应该有更大的引用次数。但可能有如下问题：一个页可能开始时使用很多，但以后就不再使用。解决方法是定期将次数寄存器右移一位，以形成指数衰减的平均使用次数。
2）最常使用页置换算法（MFU)
置换计数最大页。理由：最小次数页可能刚刚调进来，且还没使用。
网友评论