局部最佳页面替换算法

「局部最佳页面替换算法」是一种局部页面替换算法

其实现思想为：进程在时刻 访问某页面，如果该页面不在内存中，导致一次缺页，把该页面装入一个空闲页框。不论发生缺页与否，算法在每一步要考虑引用串，如果该页面在时间间隔 内未被再次引用，那么就移出；否则，该页被保留在进程驻留集中。

为一个系统常量，间隔 称作滑动窗口 。注意，滑动窗口看到的页面不意味着必须立即装入，等到访问到了再缺页装入也可以；但滑动窗口看不到的页必须移出。

例子

若令 。访问串顺序为

p4, p3, p3, p4, p2, p3, p5, p3, p5, p1, p4

则根据局部最佳页面替换算法有

时刻 t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10
访问 p4 p3 p3 p4 p2 p3 p5 p3 p5 p1 p4
已驻留 p4 p4 p3, p4 p3, p4 p3 p3 p3 p3, p5 p5
进入 p3 p2 p5 p1 p4
离开 p4 p2 p3 p5 p1
滑动窗口 p4 p3, p4 p3, p4 p3, p4 p4离开 p2离开 p3, p5 p3, p5 p3离开 p5离开 p1离开

解释：

  • t0 时刻，内存为空，访问 p4 缺页，因此 p4 装入
  • t1 时刻，访问 p3 缺页，因此 p3 装入。此时滑动窗口 1～4 内可以看到 p2，p3，p4，因此 p3 和 p4 都不需要移出
  • t2 时刻，访问 p3。此时滑动窗口 2～5 内可以看到 p2，p3，p4，因此 p3 和 p4 都不需要移出
  • t3 时刻，访问 p4。此时滑动窗口 3～6 内可以看到 p2，p3，p4，p5，因此 p3 和 p4 都不需要移出
  • t4 时刻，访问 p2 缺页，因此 p2 装入。此时滑动窗口 4～7 内可以看到 p2，p3，p5，由于 p4 不在滑动窗口中，因此 p4 需要离开
  • 以此类推。
Interactive Graph
Table Of Contents
局部最佳页面替换算法
例子