用LinkedHashMap实现LRU算法

(在学习操作系统时，要做一份有关LRU和clock算法的实验报告，很多同学都应该是通过数组去实现LRU,可能是对堆栈的使用和链表的使用不是很熟悉吧，在网上查资料时看到了LinkedHashMap,于是自己试着用它去实现了LRU.)

LRU算法介绍：

LRU是Least Recently Used 近期最少使用算法。内存管理的一种页面置换算法，对于在内存中但又不用的数据快（内存块）叫做LRU，Oracle会根据那些数据属于LRU而将其移出内存而腾出空间来加载另外的数据，一般用于大数据处理的时候很少使用的数据那么就直接请求数据库，如果经常请求的数据就直接在缓存里面读取。

最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰（可以使用这种方法去实现）。

LRU的实现

可利用一个栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。

LRU算法也可以过双向链表来实现，而LinkedHashMap恰好是通过双向链表实现的java集合类，它的一大特点是，以当某个位置被命中，它就会通过调整链表的指向，将该位置调整到头位置，新加入的内容直接放在链表头，如此一来，最近被命中的内容就向链表头移动，需要替换时，链表最后的位置就是最近最少使用的位置。

假定现有一进程所访问的页面序列为：

4，7，0，7，1，0，1，2，1，2，6

随着进程的访问，栈中页面号的变化情况如图所示。在访问页面6时发生了缺页，此时页面4是最近最久未被访问的页，应将它置换出去。

代码如下：

package 作业;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;


/*LRU是Least Recently Used 近期最少使用算法。
 *通过HashLiekedMap实现LRU的算法的关键是，如果map里面的元素个数大于了缓存最大容量，则删除链表头元素
 */

/*public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)
 *LRU参数参数：
 *initialCapacity - 初始容量。
 *loadFactor - 加载因子（需要是按该因子扩充容量）。
 *accessOrder - 排序模式( true) - 对于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU  最近最少被使用的调度算法），对于插入顺序，则为 false,可以不断加入元素。
 */

 /*相关思路介绍：
  * 当有一个新的元素加入到链表里面时，程序会调用LinkedHahMap类中Entry的addEntry方法，
  *而该方法又会 会调用removeEldestEntry方法，这里就是实现LRU元素过期机制的地方，
  * 默认的情况下removeEldestEntry方法只返回false，表示可以一直表链表里面增加元素，在这个里  *修改一下就好了。 
  *
  */
 
/*
测试数据：
5
11
4 7 0 7 1 0 1 2 1 2 6
*/

import java.util.*;
public class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{     
    private int capacity;                     //初始内存容量
    
    LRULinkedHashMap(int capacity){          //构造方法，传入一个参数
        super(16,0.75f,true);               //调用LinkedHashMap，传入参数    
        this.capacity=capacity;             //传递指定的最大内存容量
    }
    @Override
    public boolean removeEldestEntry(Map.Entry<K, V> eldest){     
        //，每加入一个元素，就判断是size是否超过了已定的容量
        System.out.println("此时的size大小="+size());
        if((size()>capacity))
        {
            System.out.println("超出已定的内存容量，把链表顶端元素移除："+eldest.getValue());
        }
        return size()>capacity;        
    }
    
    public static void main(String[] args) throws Exception{
        Scanner cin = new Scanner(System.in);
        
        System.out.println("请输入总共内存页面数： ");
        int n = cin.nextInt();
        Map<Integer,Integer> map=new LRULinkedHashMap<Integer, Integer>(n);
        
        System.out.println("请输入按顺序输入要访问内存的总共页面数： ");
        int y = cin.nextInt();
        
        System.out.println("请输入按顺序输入访问内存的页面序列： ");
        for(int i=1;i<=y;i++)
        {
            int x = cin.nextInt();
            map.put(x,  x);  
        }
        System.out.println("此时内存中包含的页面数是有:");
        //用for-each语句，遍历此时内存中的页面并输出
        for(java.util.Map.Entry<Integer, Integer> entry: map.entrySet()){
            System.out.println(entry.getValue());
        }
    }
}

实验截图：

秒客网

用LinkedHashMap实现LRU算法

代码如下：

相关文章