java中的OPT算法實現方式

Posted on by

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算法中用瞭一個額外的數組用來標記接下來頁面中該數據出現的位置，然後通過這個標記值判斷替換哪個，是我自己想出來覺得還不錯的一個方法，沒有標註註釋，請諒解。

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。 

推薦閱讀：