天天热文: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(); 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 = 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=block.length){ for(int j=0;j temp[tag]) tag = u; } System.out.println(block[tag]+"->"+page[i]); block[tag]=page[i]; } } else { for(int j=0;j "+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=block.length) { for(int j=0;j "+page[i]); for(int j=0;j "+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=block.length) { for(int j=0;j "+page[i]); for(int j=0;j "+page[i]);block[m]=page[i];m++;} } } System.out.println("命中率= "+hit/page.length); }
测试代码请自行编写 ,这里OPT算法中用了一个额外的数组用来标记接下来页面中该数据出现的位置,然后通过这个标记值判断替换哪个,是我自己想出来觉得还不错的一个方法,没有标注注释,请谅解。
以上为个人经验,希望能给大家一个参考,也希望大家多多支持脚本之家。
X 关闭
X 关闭
- 1转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 2充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 3好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 4名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?
- 5亚马逊云科技成立量子网络中心致力解决量子计算领域的挑战
- 6京东绿色建材线上平台上线 新增用户70%来自下沉市场
- 7网红淘品牌“七格格”chuu在北京又开一家店 潮人新宠chuu能红多久
- 8市场竞争加剧,有车企因经营不善出现破产、退网、退市
- 9北京市市场监管局为企业纾困减负保护经济韧性
- 10市场监管总局发布限制商品过度包装标准和第1号修改单