基于java实现的OPT算法基于java实现的OPT算法

1966年，Belady提出最佳页面替换算法(OPTimal replacement，OPT)。是操作系统存储管理中的一种全局页面替换策略。
当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距最长时间后要访问的页面。它所产生的缺页数最少，然而，却需要预测程序的页面引用串，这是无法预知的，不可能对程序的运行过程做出精确的断言，不过此理论算法可用作衡量各种具体算法的标准。
例子：

OPT4 3 2 1 4 3 5 4 3 2 1 5 页14 4 4 4 4 4 4 4 4 2 2 2 页23 3 3 3 3 3 3 3 3 1 1 页32 1 1 1 5 5 5 5 5 5 缺页中断 x x x x v v x v v x x v 共缺页中断7次

【基于java实现的OPT算法】摘自百度百科
由上面的解释可知，opt算法就是将最远要访问到的页或者不再访问的页淘汰掉。
直接上代码：

import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.List; /* * 说明： * 数据由文件读入，需要自己创建文件，然后将数据放入其中 * 第一个数据代表内存中的页数 * 接下来为访问次序，数据已回车分隔*/public class OPTTest { public static void main(String[] args) { OPT opt = new OPT("E:\\java\\io_copy\\opt.txt"); opt.algorithm(); } }class OPT { public OPT(String filePath) { memoryList = new ArrayList(); rd = new ReadData(filePath); memoryMaxSize = rd.readNext(); processList = rd.read(); } ReadData rd; List processList; List memoryList; int memoryMaxSize; public void algorithm() {//opt算法 int missPage = 0; for (int i = 0; i < processList.size(); i++) { int nowProcess = processList.get(i); if (memoryList.contains(nowProcess)) { ; } else if (memoryList.size() < memoryMaxSize) { missPage++; memoryList.add(nowProcess); } else { int val = 0, index = 0; for (int j = 0; j < memoryList.size(); j++) { int now = processList.lastIndexOf(memoryList.get(j)); if (now > index || now < i) { index = now < i ? Integer.MAX_VALUE : now; val = memoryList.get(j); } } memoryList.remove(memoryList.indexOf(val)); memoryList.add(nowProcess); missPage++; } for (int k = 0; k < memoryList.size(); k++) { System.out.println(memoryList.get(k)); } System.out.println("-------------"); }System.out.println(missPage); } }class ReadData {//读取数据 public ReadData(String filePath) { dataList = new ArrayList(); try { bfr = new BufferedReader(new FileReader(filePath)); } catch (FileNotFoundException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); } } private BufferedReader bfr = null; private List dataList; public List read() { Integer i; while ((i = readNext()) != -1) { dataList.add(i); } return dataList; }; public Integer readNext() { try { String data = https://www.it610.com/article/bfr.readLine(); if (data == null) { return -1; } return Integer.parseInt(data); } catch (IOException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); } return -1; }}