NO IMAGE

/*
 * Created on 2004-12-25
 *
 * TODO To change the template for this generated file go to
 * Window – Preferences – Java – Code Style – Code Templates
 */

/**
 * @Michelangelo
 *
 * TODO To change the template for this generated type comment go to
 * Window – Preferences – Java – Code Style – Code Templates
 */

import java.util.*;
public class TestReplacement {

 /**
  *
  */
 private final int ArraySize=20;
 private int digitalArray[]=new int [ArraySize];
 
 //private int digitalArray[]={1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6};
 
 private static final int frameSize[]={1,2,3,4,5,6,7};
 private static int errorCount=0;
 
 Vector frame=new Vector();
     
 public TestReplacement() {
  super();
  // TODO Auto-generated constructor stub
 }

 public static void main(String[] args) {
  TestReplacement aT=new TestReplacement();
  
  aT.generateRandomDigit();
  aT.output();
  
  System.out.println(“————-Using FIFO————–“);
  System.out.println();
  for(int i=0;i<frameSize.length;i ){
   System.out.println(“Frame size:  ” frameSize[i] “/n”);
   aT.initFrameForFIFO(frameSize[i]);
   aT.FIFOReplace(frameSize[i]); 
   System.out.println(“Total errors found:  ” errorCount);   
   System.out.println(“/n************************************/n”);
   
   errorCount=0;
  }
  System.out.println();
  System.out.println(“—————-Using LRU—————-“);
  System.out.println();
  for(int i=0;i<frameSize.length;i ){
   System.out.println(“Frame size:  ” frameSize[i] “/n”);
   aT.initFrameForLRU(frameSize[i]);
   aT.LRUReplace(frameSize[i]); 
   System.out.println(“Total errors found:  ” errorCount);
   System.out.println(“/n************************************/n”);
   errorCount=0;
  }
 }
 
 public void generateRandomDigit(){
  for(int i=0;i<ArraySize;i ){
   digitalArray[i]=(int)Math.round(Math.random()*9);
  }
 }
 
 public void output(){
  System.out.println(“隨機序列:”);
  for(int i=0;i<ArraySize;i ){
   System.out.print(” ” digitalArray[i]);
  }
  System.out.println();
 }
 
 public void initFrameForFIFO(int fS){
  frame.removeAllElements();
  for(int i=0;i<fS;i ){   
   frame.addElement(new Couple(fS-i));
  } 
 }
 public void initFrameForLRU(int fS){
  frame.removeAllElements();
  for(int i=0;i<fS;i ){   
   frame.addElement(new Couple(0));
  } 
 }
 
 
 public void LRUReplace(int fS){
        boolean findThesame=false;
        int pre=-1;//存放剛剛查詢到的位置
        int flag=-1;
       
  for(int j=0;j<digitalArray.length;j ){
   boolean match=false;
   for(int i=0;i<fS;i ){   
    
    if(((Couple)frame.elementAt(i)).value==digitalArray[j]){
     ((Couple)frame.elementAt(i)).time=0;
     match=true;//是否找到匹配 
     System.out.println(j “: find ” ((Couple)frame.elementAt(i)).value ” ” “at location ” i);
     System.out.println();     
     
     flag=i;
     break;     
    }
   }
   
   if(match==true&&flag!=pre){
     for(int i=0;i<fS;i ){
    if(i!=flag){
     ((Couple)frame.elementAt(i)).time–;
    }      
     }
     pre=flag;
   }
   else if(match==false){
    int temp=0;
    int index=0;
    for(int i=0;i<fS;i ){
     if(((Couple)frame.elementAt(i)).time<temp){
      temp=((Couple)frame.elementAt(i)).time;
      index=i;
     } 
    } 
    for(int i=0;i<fS;i ){
     if(i!=index){
      ((Couple)frame.elementAt(i)).time–;
     }
     else{
      ((Couple)frame.elementAt(i)).time=0;
      System.out.print(j “: replace ” ((Couple)frame.elementAt(i)).value ” “);      
      System.out.print(“at location ” index ” “);
      ((Couple)frame.elementAt(i)).value=digitalArray[j];
      System.out.println(“with ” ((Couple)frame.elementAt(i)).value);
       errorCount ;
       System.out.println(“error count    ” errorCount);
       System.out.println();
     }
    }
   }
  }  
 }
 public void FIFOReplace(int fS){
  //boolean blank=true;//是否開始的已填充完
  int i=0;
  for(int j=0;j<digitalArray.length;j ){  
   boolean match=false;
   for(i=0;i<fS;i ){
    if(((Couple)frame.elementAt(i)).value==digitalArray[j]){
     match=true;//是否找到匹配
     System.out.println(j “: find ” ((Couple)frame.elementAt(i)).value ” ” “at location ” i);
     break;
    }
   }
   if(match==false){
    int temp=0;
    int index=-1;
    for(i=0;i<fS;i ){     
     if(((Couple)frame.elementAt(i)).time>temp){
      temp=((Couple)frame.elementAt(i)).time;
      index=i;
     }
    }
    for(i=0;i<fS;i ){
         if(i==index){
       System.out.print(j “: replace ” ((Couple)frame.elementAt(i)).value ” “);      
       System.out.print(“at location ” i ” “);
          ((Couple)frame.elementAt(i)).value=digitalArray[j];
          System.out.println(“with ” ((Couple)frame.elementAt(i)).value);
       ((Couple)frame.elementAt(i)).time=1;
        errorCount ; 
        System.out.println(“error count    ” errorCount);
        System.out.println();
      }
      
      
      
      else{
       ((Couple)frame.elementAt(i)).time ;
      }
     
     
     
    }
   }
   
  
  }
 }
 
}

class Couple{ 
 public int value=-1;
 public int time=-1;
 public Couple(int t){  
  time=t;  
 }
}

演算法思想:用Vector來模擬頁表,而扔進去的Couple的個數就是表的大小。Couple 中的Time設定衰老時間(FIFO)或未使用週期(LRU),Value為請求序列中digitalArray[]的值。序列長為20由隨機函式產生的0-9的整型值。frameSize[]中存放的是頁表的大小(也就是對應著扔幾個Couple進去啦)

FIFO:初始化時先清空然後放Couple,將他們的Time屬性按放的順序分別置為frameSize,frame-1,frame-2…….1.數值越大放的越早,value通通置-1。接下來的工作就是對value和time的處置。若在vector中的couple的value裡找到了value匹配則pass。如果沒有找的話就從中time裡找最老的,(誰的time最大就最老),找到後把它的value變成相應的請求的頁面值,把它的time=1.對於不是最老的呢,就把他們的歲數都加一吧。

LRU:初始化時先清空然後放Couple,將他們的Time屬性置-1,value通通置-1。接下來處理請求序列了。若在value裡找到對應的頁面話就把對應的Time置0。其他的Couple對應的time- -。如果沒有找到的話就找一個最近使用的最少的啦(就是對應的time最負的那個),找到以後就把它的Value換成請求的頁面值並且把它的time置0.與此同時,其他的time–。