Java里面的OPT算法是怎么实现的呢？具体方式是什么？-群英

Java里面的OPT算法是怎么实现的呢？具体方式是什么？

Admin发表于 2022-10-12 17:31:57450 次浏览

这篇文章给大家分享的是“Java里面的OPT算法是怎么实现的呢？具体方式是什么？”，文中的讲解内容简单清晰，易于理解，而且实用性强吗，对大家认识和了解“Java里面的OPT算法是怎么实现的呢？具体方式是什么？”都有一定的帮助，有需要的朋友可以参考了解看看，那么接下来就跟随小编的思路来往下学习吧

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算法中用了一个额外的数组用来标记接下来页面中该数据出现的位置，然后通过这个标记值判断替换哪个，是我自己想出来觉得还不错的一个方法，没有标注注释，请谅解。

通过以上内容的阐述，相信大家对“Java里面的OPT算法是怎么实现的呢？具体方式是什么？”已经有了进一步的了解，更多相关的问题，欢迎关注群英网络或到群英官网咨询客服。

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：mmqy2019@163.com进行举报，并提供相关证据，查实之后，将立刻删除涉嫌侵权内容。

标签： java实现OPT

上一篇： Maven继承的概念和作用是什么，与聚合有何差异？

下一篇：如何十分钟理解Java中的动态代理

目录

java实现OPT算法

FIFO LRU OPT 算法java实现