关于LinkedHashMap实现LRU

Question

用LinkedHashMap实现LRU，然后要求把每次置换的页输出到一个文档里，小弟不才~看LinkedHashMap的源代码看的稀里糊涂的，不知道怎么才能把置换的页面输出出来，谢谢各位了

Answer 1

详细讲一下需求。Map中存储些什么数据。页中存储的是些什么信息。具体的应用情景。

Answer 2

看到没人写,就试着写了一个,是用LinkedHashMap实现的,希望能对你有帮助.import java.util.*;
//分页调度,最近最久未曾使用,合用LinkedHashMap实现
public class LRU {
public static void LRU(int n, int m, List<Integer> list) {
// 其中key为最近记问时间, value为页号,如果容量超出内存,则淘汰相关的页面,反过来存会容易很多
LinkedHashMap<Integer, Integer> memory = new LinkedHashMap<Integer, Integer>();
int sum = 0; // 累加缺页次数
for (Integer k : list) {
System.out.println("当前访问的是页号为: "+k);
System.out.print("此时内存中缓存的页面为:    ");
if(memory.size()!=0){
for(int i=1;i<=memory.size();i++){
System.out.print(memory.get(i)+" ");
}
System.out.println();
}else{
System.out.println("此时内存为空!");
}
if (memory.size() == 0) {// 第一次定然缺页,因为内存中还未装入页面
sum++;
System.out.println("处理该作业的第 " + k + " 个页面时发生了缺页现象!,这是第 " + sum
+ "次缺页");
memory.put(memory.size() + 1, k);// 将页面缓存入内存,并记录一其时间
} else {
if (memory.containsValue(k)) {// 待访问的页面已经存在于内存,则需考虑是否将各页的访问时序进行调整
int order = 1;//记录正在访问的是哪一项
for (int i = 1; i <= memory.size(); i++) {
if (memory.get(i) == k) {
order = i;
break;
}
}
if (memory.get(memory.size()) != k) {// 调整页序
for (int i = order; i < memory.size(); i++) {
memory.put(i, memory.get(i + 1));
}
memory.put(memory.size(), k);
}
} else {// 不存在,则需要调度
sum++;
System.out.println("处理该作业的第 " + k + " 个页面时发生了缺页现象!,这是第 "
+ sum + "次缺页");
if (memory.size() == n) {// 内存已满
for (int i = 1; i < memory.size(); i++) {
memory.put(i, memory.get(i + 1));
}
memory.put(memory.size(), k);
} else {// 内存未满
memory.put(memory.size() + 1, k); // 直接置入即可
}
}
}
System.out.println("################################################################");
}
System.out.println();
System.out.println("总的缺页次数为: "+sum);
System.out.println("缺页率为: "+(sum*1.0/m)*100+"%");
} public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入内存的物理块数:");
int n = sc.nextInt();
System.out.println("请输入待处理的作业的数目:");
int m = sc.nextInt();
System.out.println("请输入作业的业面走向:");
List<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < m; i++) {
list.add(sc.nextInt());
}
System.out.println("LRU算法的页面调度过程如下: ");
System.out.println();
LRU(n, m, list);
}
}运行结果如下:(楼主可调试其它测试数据,本人只测了这一组)
请输入内存的物理块数:
4
请输入待处理的作业的数目:
12
请输入作业的业面走向:
1 3 2 1 1 3 5 1 3 2 1 5
LRU算法的页面调度过程如下: 当前访问的是页号为: 1
此时内存中缓存的页面为:    此时内存为空!
处理该作业的第 1 个页面时发生了缺页现象!,这是第 1次缺页
################################################################
当前访问的是页号为: 3
此时内存中缓存的页面为:    1 
处理该作业的第 3 个页面时发生了缺页现象!,这是第 2次缺页
################################################################
当前访问的是页号为: 2
此时内存中缓存的页面为:    1 3 
处理该作业的第 2 个页面时发生了缺页现象!,这是第 3次缺页
################################################################
当前访问的是页号为: 1
此时内存中缓存的页面为:    1 3 2 
################################################################
当前访问的是页号为: 1
此时内存中缓存的页面为:    3 2 1 
################################################################
当前访问的是页号为: 3
此时内存中缓存的页面为:    3 2 1 
################################################################
当前访问的是页号为: 5
此时内存中缓存的页面为:    2 1 3 
处理该作业的第 5 个页面时发生了缺页现象!,这是第 4次缺页
################################################################
当前访问的是页号为: 1
此时内存中缓存的页面为:    2 1 3 5 
################################################################
当前访问的是页号为: 3
此时内存中缓存的页面为:    2 3 5 1 
################################################################
当前访问的是页号为: 2
此时内存中缓存的页面为:    2 5 1 3 
################################################################
当前访问的是页号为: 1
此时内存中缓存的页面为:    5 1 3 2 
################################################################
当前访问的是页号为: 5
此时内存中缓存的页面为:    5 3 2 1 
################################################################总的缺页次数为: 4
缺页率为: 33.33333333333333%

Answer 3

Map模拟memory，里面存的是page, 如下，第一列是pageID，第二列是PageContent5 theSpiderOut
77 soIBSclimbed
3 theRain
34 IBSclimbed
9 outCame
2 upTheSpoutAgain用户从命令行输入buffer的大小，比如为3，那么Map大小就为三，一开始就只存入5,77,3，后面有读写的操作，比如需要对第34进行写操作，然后34现在不在里面，就需要用LRU原则置换掉5,34进来，进行写操作，被指换掉的5就要写进一个file里
PS：以这个file里被置换的页面顺利来评判LRU是不是做的对

Answer 4

LinkedHashMap可以理解为HashMap+LinkedList：HashMap保证hash的效率，linkedList来保持hashmap没法保持的顺序。
只有当用LinkedHashMap(int, float, true)来构造的时候才是LRU，否则都是根据插入顺序来排序。