java实现操作系统中的最佳置换Optimal算法

Java实现操作系统中的最佳置换Optimal算法攻略

算法介绍

最佳置换算法（Optimal）也称为理论最优算法。其思想是根据还未完成的进程未来的使用情况，计算出每一个进程在什么时候会访问页面，然后选择最长时间以后才用到的页面进行置换。

实现步骤

首先根据需要分配的内存大小，将所有的物理块置为空闲状态，并初始化所有页面的最近使用时间为正无穷大。
当一个新页面需要进入物理块时，检查空闲块，如果有则直接分配。如果没有空闲块，我们需要检查将要置换的页，选择预计最长时间未被使用的页进行置换。
遍历所有getPageList()页面，记录每个页面下一次的使用时间（找到下一个访问时间最大的页）。
比较每一页最近的下次使用时间，选择将距离下一次访问时间最远的页面进行替换，将其写入磁盘、更新页面表与页表即可。
重复上述步骤，直到完成所有的分配请求。

Java代码

import java.util.*;

class OptimalPageReplacement {

    private final List<Integer> getPageList() {
        // 内部页面列表，根据任务中定义方式生成
        return Arrays.asList(1, 2, 3, 2, 4, 5, 6, 7, 6, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2);
    }

    private final void replacePages(int numFrames) {
        List<Integer> pageList = getPageList();
        List<Integer> frames = new ArrayList<>();
        Map<Integer, Integer> nextOccurrences = new HashMap<>();
        int pageFault = 0;
        for (int i = 0; i < numFrames; i++) {
            frames.add(-1);
        }
        for (int i = 0; i < pageList.size(); i++) {
            int currentPage = pageList.get(i);
            int frameIndex = frames.indexOf(currentPage);
            if (frameIndex != -1) {
                System.out.println("Request for page " + currentPage + " already found in Frame " + frameIndex);
                continue;
            }
            System.out.println("Request for page " + currentPage + " not found");
            if (frames.contains(-1)) {
                int emptyFrameIndex = frames.indexOf(-1);
                frames.set(emptyFrameIndex, currentPage);
                System.out.println("Page " + currentPage + " allocated to empty frame " + emptyFrameIndex);
                nextOccurrences.put(currentPage, getNextOccurrence(pageList, i));
                continue;
            }
            int replacement = getNextToReplace(frames, nextOccurrences);
            int replacedPageIndex = frames.indexOf(replacement);
            frames.set(replacedPageIndex, currentPage);
            nextOccurrences.put(currentPage, getNextOccurrence(pageList, i));
            System.out.println("Page " + replacement + " replaced with page " + currentPage + " in Frame " + replacedPageIndex);
            pageFault++;
        }
        System.out.println("Total Page Faults:" + pageFault);
    }

    private final int getNextOccurrence(List<Integer> pageList, int currentPageIndex) {
        for (int i = currentPageIndex + 1; i < pageList.size(); i++) {
            if (pageList.get(i) == currentPageIndex) {
                return i;
            }
        }
        return pageList.size() + 1;
    }

    private final int getNextToReplace(List<Integer> frames, Map<Integer, Integer> nextOccurrences) {
        int max = -1;
        int replace = -1;
        for (int i = 0; i < frames.size(); i++) {
            int currentPage = frames.get(i);
            if (!nextOccurrences.containsKey(currentPage)) {
                return i;
            } else {
                if (nextOccurrences.get(currentPage) > max) {
                    max = nextOccurrences.get(currentPage);
                    replace = i;
                }
            }
        }
        return replace;
    }

    public static void main(String[] args) {
        OptimalPageReplacement opr = new OptimalPageReplacement();
        opr.replacePages(3);
    }
}

示例说明

示例1

在这个示例中，CPU占用一个包含3个物理页面的系统。对于这类小系统，函数的执行顺序取决于输入的页请求序列。

请求页1。在请求1时，物理块是空的。第一个页面被分配到物理块0。
请求页2。在请求2时，物理块中没有空的物理块。在这种情况下，根据Optimal算法，算法分配被分配最长时间周期内没有使用的页面。在这种情况下，即使整个未来将使用的时间取决于请求码，但最佳可用的物理块是0。这意味着物理块1和2分别为1和2，从而执行相应的页面错误。
请求页3。在请求3时，物理块0和1都包含了一个页面。但是页面3并不在主存中。在这种情况下，根据Optimal算法，算法为3分配被分配最长时间周期内没有使用的页面。在这种情况下，optimal算法将页面0和1中的任意一个页面替换为页面3。此时，选择可以替换的页面是0，因为在页面调用链中，最长的时间为7。
请求页2。在请求2时，物理块1和2分别为1和2。因此，找到页面2，因此不需要将当前所需的任何页面替换掉。
请求页4。在请求4时，页面4并不在主存中。此时的页面分配情况为（2，1，0）。在这种情况下，算法使用有最长使用时间的页面（在这种情况下，页面1的下一个访问将在9次调用后进行，而其他页面的下一个访问在5和8次之后）。此时，可以替换的页面是页面0或页面2。因为页面0有更长的时间或未使用，因此将页面4换掉，并将新的页面0放入物理块0中。
请求5。请求5时，页面5不在物理块中。此时的页面分配情况为（4，1，5）。在这种情况下，根据Optimal算法，使用拥有最长时间段的页面分配，因为希望在页面请求依赖关系中尽可能长时间地放置当前要求。在这种情况下，页面1的下一个使用周期最长。这时可以替换的页面是页面0或页面2。因为页面0比页面2下一个使用时间更长（页2应该在6次访问以后），页面0被替换为页面5。因此，页面分配变成了(5, 1, 4)。
请求页6。在请求6时，可以替换的页面是页面4或页面1。然而，因为页面1比页面4下一个使用时间长，因此页面1被替换为页面6。此时，物理块分配变成了(5, 6, 4)。

示例2

在这个示例中，CPU占用一个包含3个物理页面的系统。

请求页3.页面调入位于物理块0。
请求页2.页面调入位于物理块1。
请求页4。页面调入位于物理块2。
请求页6。发现所有物理块都已经分配出去了，根据Optimal算法，要查找下一个将要被使用的页，发现所有人将在未来无限的某个时刻被使用。按顺序每个页面都被标记以寻找将来访问的页面，在这个例子中，唯一不同的是一个页面标记解封期间是很近的，这个页面将会被换出物理块。页面4被替换为页面6，物理块分配变成(3, 2, 6)。
请求页2。因为页面2已经在物理块中了，因此不需要置换。
请求页4。因为页面4已经在物理块中了，因此不需要置换。
请求页3。此时物理块内所有页面都已经被使用，需要选择一个最佳页面移除。需要整个页面序列来算法，以查找下一个每个页面将被访问的时间。由于所有页面都曾经出现过，所以算法无法从物理块中移除任何页面。

因此，总共有1个页面错误。

总结

Optimal算法是一种最佳的估计算法，旨在像未来一样分配对于所有物理/虚拟页面调用快照都最优。尽管在实际情况下无法预测所有请求，但它仍然作为理论原型被使用。由于它是一种最佳的算法，因此在实际情况下可能不太可能出现不同的结果。在一些情况下，其他算法例如LRU可能会提供更好的结果。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：java实现操作系统中的最佳置换Optimal算法 - Python技术站