​「操作系统」OPT算法详解

「操作系统」OPT算法详解

B、考虑下述页面走向:6，7，5，2，6，7，3，6，7，5，2，3 当分配的内存物理块数量分别为 3 和 4 时: OPT(最优页面置换算法) 的缺页次数分别是多少?

OPT（最佳置换算法）：从主存中移出永远不再需要的页面，如果没有这样的页面存在，那就选择最长时间不需要访问的页面，来保证最低的缺页率

当分配的内存物理块数量为3时

先放入6，7，5，当放入2的时候，显而易见，最长时间不需要访问的页面就是5，那么先将5给置换掉

当放入6的时候，已经存在，不需要置换

当放入7的时候，已经存在，不需要置换

当放入3的时候，最长时间不需要访问的页面就是2，那么先将2给置换掉

当放入6的时候，已经存在，不需要置换

当放入7的时候，已经存在，不需要置换

当放入5的时候，最长时间不需要访问的页面就是6和7，可以将其中一页置换掉

当放入2的时候，最长时间不需要访问的页面就是5和7或者5和6，可以将其中一页置换掉

最后当放入3的时候，已经存在，不需要置换

显而易见，缺页次数达到7次，少于用FIFO得到的结果

当分配的内存物理块数量为4时

先放入6，7，5，2，当放入6的时候，显而易见，已经存在，不需要置换

当放入7的时候，已经存在，不需要置换

当放入3的时候，最长时间不需要访问的页面就是2，那么先将2给置换掉

当放入6的时候，已经存在，不需要置换

当放入7的时候，已经存在，不需要置换

当放入5的时候，已经存在，不需要置换

当放入2的时候，最长时间不需要访问的页面就是5、6、7，可以将其中一页置换掉

最后当放入3的时候，已经存在，不需要置换

显而易见，缺页次数达到6次，少于用FIFO得到的结果