操作系统之常用的页面淘汰算法(未竟)

最佳算法(OPT 算法, Optimal)

思想

• 淘汰不再需要或最远将来才会用到的页面.

例子

分配 3 个页框. 页面序列: A, B, C, D, A, B, E, A, B, C, D, E. 分析其按照 OPT 算法淘汰页面的缺页情况.

缺页次数 = 7　　　缺页率 = 7 / 12 = 58%

特点

理论上最佳, 实践中该算法无法实现.

先进先出淘汰算法(FIFO 算法)

思想

淘汰在内存中停留时间最长的页面

例子

分配 3 个页框. 页面序列: A, B, C, D, A, B, E, A, B, C, D, E. 分析其按照 FIFO 算法淘汰页面的缺页情况.

缺页次数 = 9　　　缺页率 = 9 / 12 = 75%

优点

实现简单: 页面按进入内存的时间顺序排序, 淘汰队头页面.

缺点

进程只有按顺序访问地址空间时页面命中率才最理想.

异常现象

对于一些特定的访问序列, 分配页框越多, 缺页率越高!

最久未使用淘汰算法(LRU, Least Recently Used)

思想

淘汰最长时间未被使用的页面.

例子

分配 3 个页框. 页面序列: A, B, C, D, A, B, E, A, B, C, D, E. 分析其按照 LRU 算法淘汰页面的缺页情况.

缺页次数 = 10　　　缺页率 = 10 / 12 = 83%

LRU 的实现方法(硬件方法)