操作系统页面置换算法之最优置换（OPT）算法

       最优置换算法（OPT）是指，其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。

       现举例说明如下。

       7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

       进程运行时，先将7，0，1 三个页面装入内存。以后，当进程要访问页面2 时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7 予以淘汰。这是因为页面0 将作为第5 个被访问的页面，页面1 是第14 个被访问的页面，而页面7 则要在第18 次页面访问时才需调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面1 被淘汰；因为，它在现有的1，2，0 三个页面中，将是以后最晚才被访问的。下图所示出了采用最佳置换算法时的置换图。由图可看出，采用最佳置换算法发生了6 次页面置换。

利用最佳页面置换算法时的置换图

java模拟代码如下：

import java.util.LinkedList; import java.util.List; public class OPT { public static void main(String[] args) { int framesize = 5;//帧数量 int[] s = { 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 };//引用串 int[] is = new int[s.length]; for (int i = 0; i < s.length; i++) is[i] = 0; int aa[][] = new int[s.length][framesize]; for (int i = 0; i < s.length; i++) { for (int j = 0; j < framesize; j++) { aa[i][j] = 0; } } List q = new LinkedList(); int count = 0; for (int i = 0; i < s.length; i++) { if (count < framesize) { if (!q.contains(new Integer(s[i]))) { q.add(new Integer(s[i])); count++; is[i] = 1; } } else { if (!q.contains(new Integer(s[i]))) { int A; int max = 0; int pos = 0; for (A = 0; A < framesize; A++) {// 链表元素位置 int B; for (B = i + 1; B < s.length; B++) {// 数组元素 if (s[B] == q.get(A)) { break; } } if (B > max) { max = B; pos = A; } } q.remove(pos); q.add(pos, s[i]); count++; is[i] = 1; } } int j = 0; for (Integer v : q) aa[i][j++] = v; } for (int i = 0; i < framesize; i++) { for (int j = 0; j < s.length; j++) { System.out.print(aa[j][i] + " "); } System.out.println(); } System.out.println(); for (int i = 0; i < s.length; i++) { System.out.print(is[i] + " "); } System.out.println(); System.out.println("total : " + count); } }

说明：由于使用0填充空闲帧，因此引用串中不能包含0。

执行结果如下：

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2  0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3  0 0 0 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6  0 0 0 0 0 0 5 5 5 5 5 5 7 7 7 7 7 7 7 7  ======================= 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0  total : 7

其中，等号上方每一列代表一个队列，0代表空闲帧。等号下方1表示发生页面置换，0表示为发生页面置换。