模拟面置换算法FIFOLRU的实现

1、实验报告五 实验名称：模拟页面置换算法FIFO LRU的实现 期：2015129班级：13级计科 学兮：姓0 : 一、实验目的 了解页面置换的概念，理解页面置换的算法加深对页面置换算法的理解。 二、实验内容 Java编程语言实现FIFO和LUR页面算法。 三、项目要求与分析 FIFO算法当需要置换页面时，主要通过置换最早进入内存的页面从而达到先进先出的目 的。 LRU算法当需要置换页面时，主要通过置换进入内存中最久没有被访问的页面而达到最 近最久未使用的目的。程序中可以通过标志位进行记录。 四、具体实现 1FIFO算法实现代码以及运行结果： public class FIFO *内存块的个数

2、7 public static int /* *内存块数组 */ Object array new Object N； * 要访问的页面数组 */ public static int private Jvisit int size ; * 内存是非空为否 * return 7 public boolea n isEmpty() if (0 = size ) return true ; else return false *内存是非空满 return */ public boolea n isFulled() if (size = N) return true; else return fals

3、e ; * 元素(页框)的个数 * return */ public int size() return size ; 查找元素0在数组中的位置 param o return public int in dexOfEleme nt(Objecto) for (int i =0; i N; i +) if ( o = array i ) return i ; return -1; * 页面转换 * param obj */ public Object trans(Objectobj) Objecte = null ; intt = O; if (indexOfElement( obj) != -

4、1) t = indexOfElement( obj); for (int i =t; i size ; i +) array i = array i +1; array size -1 = obj ; else if (!isFulled() array size = obj ; size +; else for (int i =0; i size ； i +) array i = array i +1; array size -1 = obj ; if (-1 = t) return null ; else return array t ; /* *输出内存区中的各数据 */ public

5、 void showMemoryBlock() for (int i =0; i size ; i +) )； *清空队列(页框) */ public void clear() * param args */ args) public static void main( Stri ng Scanner sc = new Seanner; “请输入内存块的数量:n); N=()； ”请输入总页面数目：”)； int n=(k visit =new int n; ”请输入各个页的页面号码：”); for (int i =0;i vn; i +) visit i= =0； FIFO fifo = n

6、ew FIFO(); for (int i =0; i ; i+) visit i); 0； 运行结果: Con sole FIFO Java Application C:Proqram Fil 请输入内存块的数量：3 请输入总页面数目，10 请输入各个页的页面号码： 12 3 4567 8910 1 1 2 1 23 2 34 3 45 4 56 5 67 6 78 7 89 8 910 2. LUR算法实现代码以及运行结果： public class LRU static int volum ; / 栈的容量 static List list =new Li nkedList(); 链表用

7、来模拟栈存放页面 static int visit; 要访问的页面数组 static int count =0; / 记录缺页次数 public static void main(String args ) Seannersc = new Seanner; ”请输入栈的容量：”)； volum =(); ”请输入总页面数目：”); int n=(); visit =new int n; ”请输入各个页的页面号码：”)；for (int i =0; i n; i +) visit i=(); sLRU(); /调用最近最久未使用算法 ”置换页面的数目为：”+count); public stat

8、ic void sLRU() int index =0; while (index boolean flag =false ; if ()= volum ) for (int i =0; i ()； i +) if (int)(i )= visit index ) (i)；/先删除 (visit index ); / 再添加到尾部 flag =true : break : if (! flag) if () volum ) 如果栈未满，而且此页面没有在栈中，就将它入栈 (visit index ); else 将新页插入 如果栈已经满了，且该页面号码没有在栈中，就把栈底元素删除， int te

9、mp =(0); (0)； / 最开始一个换岀(visit index ); / 加到末尾 count +; ”开始换页了，将栈底的” +temp +”换出n); 运行结果 “经过第”+(index +1)+ ”个页面的栈内容为”);for (int k=0; k(); k+) index +; ir hi iduiw psvci ij %-Ar vyicim i “匚匸一 请输入栈的容量：5请输入总页面数目：10请输 入各个页的页面号码：123456789 10怪过第1 个页面的栈内容为1经过第2个页面的栈内容为 1 2经过第?个页面的栈内容为1 2 3经过第4个 页面的栈内容为12 3 4

10、经过第5个页面的栈内容 为1 2 345开始换页了，将栈底的1换出这也 是没有办法的事情，毕竟栈是有限的经过第6 个页面的栈内容为2 34 5 6幵始换页了，将栈底 的2换出这也是没有办法的事情，毕竟栈是有 限的经过第7个页面的栈内容为？ 45 6 7开始 换页了，将栈底的3换出这也是没有办法的事 情，毕竟栈是有限的经过第8个页面的栈内容 为4 5 678幵始换页了，将栈底的4换出这也 是没有办法的事情，毕竟栈是有限的经过第9 个页面的栈内容为5 6789幵始换页了，将栈底 的5换出这也是没有办法的事情，毕竞栈是有 限的 经过第20个页面的栈内容为6 7 89 10置 换页面的数目为；5 五、所遇问题与解决方法 问题： 针对于FIFO算法定义选择在内存中驻留时间最久的页面予以淘汰，对于内存中的驻留 时间理解复杂了不知道如何下手。 解决方案： 我们只需要设置一个先进先出队列就可以。最先进入内存的页面最早被转换岀去。 六、实验总