java中的OPT算法实现方式

目录

• java实现OPT算法
• FIFO LRU OPT 算法java实现

java实现OPT算法

1966年，Belady提出最佳页面替换算法(OPTimal replacement，OPT)。是操作系统存储管理中的一种全局页面替换策略 。

当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距最长时间后要访问的页面。

它所产生的缺页数最少，然而，却需要预测程序的页面引用串，这是无法预知的，不可能对程序的运行过程做出精确的断言，不过此理论算法可用作衡量各种具体算法的标准。

例子：

OPT        4    3    2    1    4    3    5    4    3    2    1    5
页1        4    4    4    4    4    4    4    4    4    2    2    2
页2            3    3    3    3    3    3    3    3    3    1    1
页3                2    1    1    1    5    5    5    5    5    5
缺页中断    x    x    x    x    v    v    x    v    v    x    x    v
共缺页中断7次

摘自百度百科

由上面的解释可知，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<Integer>();
		rd = new ReadData(filePath);
		memoryMaxSize = rd.readNext();
		processList = rd.read();
	}
	ReadData rd;
	List<Integer> processList;
	List<Integer> 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<Integer>();
		try {
			bfr = new BufferedReader(new FileReader(filePath));
		} catch (FileNotFoundException e) {
			// TODO 自动生成的 catch 块
			e.printStackTrace();
		}
	}
	private BufferedReader bfr = null;
	private List<Integer> dataList;
	public List<Integer> read() {
		Integer i;
		while ((i = readNext()) != -1) {
			dataList.add(i);
		}
		return dataList;
	};
	public Integer readNext() {
		try {
			String data = bfr.readLine();
			if (data == null) {
				return -1;
			}
			return Integer.parseInt(data);
		} catch (IOException e) {
			// TODO 自动生成的 catch 块
			e.printStackTrace();
		}
		return -1;
	}
}

FIFO LRU OPT 算法java实现

    public static void OPT(int len ,int page[]){
      int block[] = new int[len];
      double hit = 0;
      int key = 0;
      int m =0;
      for(int i =0;i<page.length;i++){
          if(m>=block.length){
            for(int j=0;j<block.length;j++) {
              if(block[j]==page[i]){
                  hit++;
                  System.out.println("命中");
                  key = 1;
                  break;
              }
           }
             if(key==1)
           {
               key = 0;
               continue;
           }
             else{
                 int temp[] =  new int[block.length];
                 Arrays.fill(temp, page.length);
                 for(int f=0;f<block.length;f++){
                     for(int k=i;k<page.length;k++){
                         if(block[f]==page[k]){
                           temp[f] = k;
                           break;
                         }
                 }
                }
                 int tag=0;
                 for(int u=0;u<temp.length;u++){
                   if(temp[u]>temp[tag]) tag = u;
                 }
                 System.out.println(block[tag]+"->"+page[i]);
                 block[tag]=page[i];
           }

          }
          else {
            for(int j=0;j<m;j++) {
              if(block[j]==page[i]){
                  hit++;
                  System.out.println("命中");
                  key = 1;
                  break;
              }
           }
           if(key==1)
            {
                key = 0;
                continue;
            }
            else {System.out.println("*null->"+page[i]);block[m]=page[i];m++;}
            }

    }
    System.out.println("命中率= "+hit/page.length);
  }

 public static void LRU(int len , int page[]){
        int block[] = new int[len];
        double hit = 0;
        int key = 0;
        int m=0;
        for(int i =0;i<page.length;i++){
           if(m>=block.length) {
              for(int j=0;j<block.length;j++){
                 if(block[j]==page[i]){
                    hit++;
                    System.out.println("命中");
                    int temp = block[j];
                    for(int v=j;v<block.length-1;v++) block[v]=block[v+1];
                    block[block.length-1]=temp;
                    key = 1;
                    break;
                   }
                }
                if(key==1)
                     {
                         key = 0;
                         continue;
                     }
                     else{
                           System.out.println(block[0]+"->"+page[i]);
                           for(int j=0;j<block.length-1;j++) block[j]=block[j+1];
                           block[block.length-1]=page[i];
                     }      

            }
            else {
              for(int j=0;j<m;j++) {
                if(block[j]==page[i]){
                    hit++;
                    System.out.println("命中");
                    key = 1;
                    break;
                }
             }
             if(key==1)
              {
                  key = 0;
                  continue;
              }
              else {System.out.println("*null->"+page[i]);block[m]=page[i];m++;}
              }
          }
            System.out.println("命中率= "+hit/page.length);
    }

  public static void FIFO(int len,int page[]){
          int block[] = new int[len];
          double hit=0;
          int key=0;
          int m =0;
          for(int i =0;i<page.length;i++){
              if(m>=block.length) {
                   for(int j=0;j<block.length;j++) {
                       if(block[j]==page[i]){
                           hit++;
                           System.out.println("命中");
                           key = 1;
                           break;
                       }
                    }
                    if(key==1)
                     {
                         key = 0;
                         continue;
                     }
                     else{
                           System.out.println(block[0]+"->"+page[i]);
                           for(int j=0;j<block.length-1;j++) block[j]=block[j+1];
                           block[block.length-1]=page[i];
                    }
                   }
                else {
                  for(int j=0;j<m;j++) {
                    if(block[j]==page[i]){
                        hit++;
                        System.out.println("命中");
                        key = 1;
                        break;
                    }
                 }
                 if(key==1)
                  {
                      key = 0;
                      continue;
                  }
                  else {System.out.println("*null->"+page[i]);block[m]=page[i];m++;}
                  }
          }
          System.out.println("命中率= "+hit/page.length);
    }

测试代码请自行编写 ，这里OPT算法中用了一个额外的数组用来标记接下来页面中该数据出现的位置，然后通过这个标记值判断替换哪个，是我自己想出来觉得还不错的一个方法，没有标注注释，请谅解。

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。