操作系统---(37)常用的页面置换算法

1. OPT（最佳页面置换）算法

该算法选择以后不再使用的、或者要隔最长时间才能使用的页面予以淘汰。OPT算法尽量避免刚调出去又要立即调入。是一种理想化了的页面置换算法。

例：可用页框（帧）数量为3，引用串如下：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

缺页率p=9/20=45%

OPT应用分析：实际系统无法预知将来页面的访问情况
OPT算法在实际系统中不易实现
OPT算法用于衡量实际页面置换算法的性能

2. FIFO（先进先出页面置换算法）

系统选择驻留在内存中时间最长的页面(最早装入的页面)作为被淘汰的对象。这种算法的出发点是局部性原理，但是没考虑“先装入内存者有可能是主程序常驻模块’

例：可用页框（帧）数量为3，引用串如下：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

缺页率p=15/20=75%
问题:最先装入的不一定是以后不用的。例如C程序中的main函数部分，在整个程序的生命周期中使用频率都很高。FIFO算法容易理解和实现，性能并不总是很好

3. LRU（最近最久未使用页面置换算法）

系统选择内存中上次使用距当前最远的页予以淘汰。根据程序局部性原理，在较长时间里未被使用的页面，可能不会马.上使用到。实现时通常使用栈来组织各个驻留页，通过调整、维护栈来记录各驻留页被访问的先后顺序。

例：可用页框（帧）数量为3，引用串如下：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

优点:缺页中断率接近OPT
缺点:几乎每一次页面访问都要调整栈，系统开销大。