java中的OPT算法實(shí)現(xiàn)方式
更新時(shí)間：2022年07月11日 09:44:46 作者：Gee_Zer
這篇文章主要介紹了java中的OPT算法實(shí)現(xiàn)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
java實(shí)現(xiàn)OPT算法
1966年，Belady提出最佳頁(yè)面替換算法(OPTimal replacement，OPT)。是操作系統(tǒng)存儲(chǔ)管理中的一種全局頁(yè)面替換策略 。
當(dāng)要調(diào)入一頁(yè)而必須淘汰舊頁(yè)時(shí)，應(yīng)該淘汰以后不再訪問(wèn)的頁(yè)，或距最長(zhǎng)時(shí)間后要訪問(wèn)的頁(yè)面。
它所產(chǎn)生的缺頁(yè)數(shù)最少，然而，卻需要預(yù)測(cè)程序的頁(yè)面引用串，這是無(wú)法預(yù)知的，不可能對(duì)程序的運(yùn)行過(guò)程做出精確的斷言，不過(guò)此理論算法可用作衡量各種具體算法的標(biāo)準(zhǔn)。
例子：
OPT?? ??? ?4?? ?3?? ?2?? ?1?? ?4?? ?3?? ?5?? ?4?? ?3?? ?2?? ?1?? ?5 頁(yè)1?? ??? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?4?? ?2?? ?2?? ?2 頁(yè)2?? ??? ??? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?3?? ?1?? ?1 頁(yè)3?? ??? ??? ??? ?2?? ?1?? ?1?? ?1?? ?5?? ?5?? ?5?? ?5?? ?5?? ?5 缺頁(yè)中斷?? ?x?? ?x?? ?x?? ?x?? ?v?? ?v?? ?x?? ?v?? ?v?? ?x?? ?x?? ?v 共缺頁(yè)中斷7次
摘自百度百科
由上面的解釋可知，opt算法就是將最遠(yuǎn)要訪問(wèn)到的頁(yè)或者不再訪問(wèn)的頁(yè)淘汰掉。
直接上代碼：
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
/*
* 說(shuō)明：
* 數(shù)據(jù)由文件讀入，需要自己創(chuàng)建文件，然后將數(shù)據(jù)放入其中
* 第一個(gè)數(shù)據(jù)代表內(nèi)存中的頁(yè)數(shù)
* 接下來(lái)為訪問(wèn)次序，數(shù)據(jù)已回車(chē)分隔*/
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 {//讀取數(shù)據(jù)
public ReadData(String filePath) {
dataList = new ArrayList<Integer>();
try {
bfr = new BufferedReader(new FileReader(filePath));
} catch (FileNotFoundException e) {
// TODO 自動(dòng)生成的 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 自動(dòng)生成的 catch 塊
e.printStackTrace();
}
return -1;
}
}FIFO LRU OPT 算法java實(shí)現(xiàn)
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);
}
測(cè)試代碼請(qǐng)自行編寫(xiě) ，這里OPT算法中用了一個(gè)額外的數(shù)組用來(lái)標(biāo)記接下來(lái)頁(yè)面中該數(shù)據(jù)出現(xiàn)的位置，然后通過(guò)這個(gè)標(biāo)記值判斷替換哪個(gè)，是我自己想出來(lái)覺(jué)得還不錯(cuò)的一個(gè)方法，沒(méi)有標(biāo)注注釋?zhuān)?qǐng)諒解。
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
mybatis那些約定的配置你真的都了解嗎(經(jīng)驗(yàn)總結(jié))
mybatsi中Mapper和xml文件之間有很多約定俗稱(chēng)的規(guī)則，比如名稱(chēng)匹配，包掃描，別名等，這些規(guī)則是什么。如果想更加靈活，該如何配置呢？今天就給大家講一下如何配置mybatsi的xml文件2021-06-06
這篇文章主要介紹了java?map的key值轉(zhuǎn)駝峰,通過(guò)實(shí)例代碼介紹了Map把“_”形式的key轉(zhuǎn)化為駝峰形式，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2023-12-12
Spring?Boot項(xiàng)目中使用?TrueLicense?生成和驗(yàn)證License的詳細(xì)步驟
這篇文章主要介紹了Spring?Boot項(xiàng)目中使用?TrueLicense?生成和驗(yàn)證License,本文分步驟給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-10-10
SpringCloud Eureka實(shí)現(xiàn)服務(wù)注冊(cè)與發(fā)現(xiàn)
Eureka是一種基于REST(具像狀態(tài)傳輸)的服務(wù)，主要用于AWS云中定位服務(wù)，以實(shí)現(xiàn)中間層服務(wù)器的負(fù)載平衡和故障轉(zhuǎn)移。本文記錄一個(gè)簡(jiǎn)單的服務(wù)注冊(cè)與發(fā)現(xiàn)實(shí)例。感興趣的小伙伴們可以參考一下2019-01-01
Java中幾個(gè)Reference常見(jiàn)的作用詳解
這篇文章主要給大家介紹了Java中關(guān)于Reference多個(gè)作用的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面跟著小編一起來(lái)學(xué)習(xí)學(xué)習(xí)吧。2017-06-06
這篇文章主要介紹了在SpringBoot中使用HATEOAS的方法，HATEOAS是實(shí)現(xiàn)REST規(guī)范的一種原則，通過(guò)遵循HATEOAS規(guī)范，可以解決我們實(shí)際代碼實(shí)現(xiàn)的各種個(gè)問(wèn)題，下文更多相關(guān)介紹，需要的小伙伴可以參考一下2022-05-05
SpringBoot @PostMapping接收HTTP請(qǐng)求的流數(shù)據(jù)問(wèn)題
這篇文章主要介紹了SpringBoot @PostMapping接收HTTP請(qǐng)求的流數(shù)據(jù)問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
Java 腳本 API 是一種獨(dú)立于框架的腳本語(yǔ)言，使用來(lái)自于Java代碼的腳本引擎 ?？梢允褂肑ava語(yǔ)言編寫(xiě)定制/可擴(kuò)展的應(yīng)用程序并將自定義腳本語(yǔ)言選擇留給最終用戶(hù) 。下面我們來(lái)詳細(xì)了解一下吧2019-06-06
這篇文章主要介紹了java中如何截取字符串最后一位的實(shí)現(xiàn)方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
Java利用POI實(shí)現(xiàn)導(dǎo)入導(dǎo)出Excel表格
這篇文章主要為大家詳細(xì)介紹了Java利用POI實(shí)現(xiàn)導(dǎo)入導(dǎo)出Excel表格，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08