FIFO与LRU 算法实现（java）

/*
 * 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--。

本文地址：http://com.8s8s.com/it/it11532.htm