最近最少使用算法有两种实现方式：
(1)记时法：对于每一页增设一个访问时间计时器。每当一个页面被访问时，当时的绝对时钟内容被复制到对应的访问时间计时器中。这样系统就记录了内存中所有页面最后一次被访问的时间。淘汰时，选取访问时间计时器值中最小者对应的页面。
import java.util.Date; // IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
// DEFINE ANY CLASS AND METHOD NEEDED
// CLASS BEGINS, THIS CLASS IS REQUIRED
public class LeastRecentPage
{
// METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] pages = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0};//结果是11;
System.out.println(lruCountMiss(3, pages));
}
public static int lruCountMiss(int max_cache_size, int[] pages)
{
// INSERT YOUR CODE HERE
int[] cache = new int[max_cache_size];
int TIME = 1;
int[] time=new int[max_cache_size];
int index=-1;
int miss=0;
L: for(int k=0;k<pages.length;k++){
int min = Integer.MAX_VALUE;
int min_index=0;
for(int i=0;i<max_cache_size;i++){
index = (index+1)%max_cache_size;
if(time[index]==0){
cache[index]=pages[k];
time[index]= TIME++;
miss++;
continue L;
}
if(cache[index]==pages[k]){
time[index] = TIME++;
continue L;
}
if(time[index]<min){
min = time[index];
min_index = index;
}
}
miss++;
cache[min_index]=pages[k];
time[min_index]= TIME++;
index=min_index;
}
return miss;
}
// METHOD SIGNATURE ENDS
}
(2)栈法：按照页面最后一次访问的时间次序将页面号依次排列到栈中。当一个页面最访问时，其对应的页面号由站内取出送入栈顶。淘汰时，取栈底页面号所对应的页面。这里的栈不是通常定义的先入先出栈。为了便于对栈中任意位置的操作，应用双向链表来构造栈。
import java.util.LinkedList;
import java.util.List; // IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
// DEFINE ANY CLASS AND METHOD NEEDED
// CLASS BEGINS, THIS CLASS IS REQUIRED
public class LeastRecentPage
{
// METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] pages = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0};//结果是11;
System.out.println(LinkedListlruCountMiss(3, pages));
}
public static int LinkedListlruCountMiss(int max_cache_size, int[] pages)
{
// INSERT YOUR CODE HERE
int[] cache = new int[max_cache_size];
List<Integer> li = new LinkedList<Integer>();
int index=-1;
int miss=0;
L: for(int k=0;k<pages.length;k++){
for(int i=0;i<max_cache_size;i++){
index = (index+1)%max_cache_size;
if(cache[index]==pages[k]){
li.remove(new Integer(index));
li.add(new Integer(index));
continue L;
}
}
miss++;
if(cache[index]==0){
li.add(index);
continue L;
}
index = li.remove(li.size()-1);
li.add(new Integer(index));
cache[index] = pages[k];
}
return miss;
}
// METHOD SIGNATURE ENDS
}
运行结果都是：11次。
最近最少使用算法的实现开销是很大的。