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