操作系统基础40-最优页面置换

2021-01-06 01:28·重学IT的老猫

发现 Belady 异常的一个结果是寻找最优页面置换算法，这个算法具有所有算法的最低的缺页错误率，并且不会遭受Belady异常。这种算法确实存在，它被称为OPT或MIN。该算法的思想是：置换最长时间不会使用的页面。 这种页面置换算法确保对于给定数量的帧会产生最低的可能的缺页错误率。

假设有3个帧并且引用串为：

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

例如，针对示例引用串，最优置换算法会产生9个缺页错误，如下图所示

最优置换算法

头3个引用会产生缺页错误，以填满3个空闲帧。对页面2的引用会置换页面7，因为页面7直到第18 次引用时才使用，页面0在第5次引用时使用，页面1在第14次引用时使用。对页面3的引用会置换页面1，因为页面1是位于内存的3个页面中最后被再次引用的页面。 有9个缺页错误的最优页面置换算法要好于有15个缺页错误的FIFO置换算法（如果我们忽略前3个，这是所有算法都会遭遇的，那么最优置换要比FIFO置换好一倍）。事实上，没有置换算法能够只用3个帧并且少于9个缺页错误，就能处理样例引用串。

整个过程缺页中断发生了9次，页面置换发生了6次。缺页率 = 9 / 20 = 45%。 最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的