操作系统实验报告-存储管理的模拟实现.doc

淮海工学院计算机工程学院实验报告书课 程 名： 操作系统原理 题 目： 实验三：虚拟存储器管理 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日1、 设计目的：通过实验，掌握常用页面置换算法(OPT,FIFO,LRU,LFU)的运行机理，运用以前所学的知识，编程实现对各算法的模拟。2、 设计要求：运用所学的知识，编程实现各算法，实现平台不限。本次实验共计四课时，前两课时要求对各页面置换算法有较为深入的了解，着手进行程序编制，作出大致的程序框架；后两次课中，主要是程序的调试、实验报告的完善与修改等。3、 实验结果分析1）代码：1、OPT算法java实现）核心代码段：实验判断是否有缺页public void Opt() int m_absent;/ 缺页数 double m_absentf;/ 缺页率 double m_changef;/ 命中率 int mym;/ 存放物理块中现有的页面号 int myb; int as = 0;/ 置换页面数 myb = new intn; int m1 = 0, a; boolean x; / 页面是否需要置换 String str2, str1,str3; String m_list = OPT置换算法 被替换; mym = new intm; for (int i = 0; i n; i+) str1 = ; str2 = ; str3=; x = true; for (int k = 0; k m; k+) if (myti = mymk)/ 判断物理块中的页面是否与当前页面相等 x = false;/ 判断物理块中是不是有跟当前须替换的页面 m1+; break; if (x) int c = 0, d; if (i - m1) m) a = i - m1; / 当前物理页面未填满时直接装入 else for (int k = 0; k m; k+) for (int h = i; h n; h+) if (mymk = myth)/ 判断物理块中的页面是否与未来页面相等 mybk = h; break; if (h = n - 1) mybk = n; d = myb0; for (int h = 0; h m; h+) if (d mybh) d = mybh; c = h; a = c; / 找出物理块中未来最久将不被使用的页面号 str3=String.valueOf(myma); myma = myti;/ 将其替换 as+; for (int j = 0; j m; j+) int b; b = mymj; str2 = String.valueOf(b); str1 = str1 + + str2; m_list = m_list + n + str1+ +str3; m_absent = as; m_absentf = (double) as / n; if (as - m) = 0) m_changef = 0; else m_changef = (double)(1-m_absentf); 2、FIFO算法java实现）核心代码段：实验判断是否有缺页 public void FIFO() int m_absent;/ 缺页数 double m_absentf;/ 缺页率 double m_changef;/ 命中率 int mym;/ 存放物理块中现有的页面号 int m1 = 0, r; int as = 0;/ 置换页面数 boolean x; / 页面是否需要置换 String str1, str2,str3; String m_list = FIFO置换算法 被替换; mym = new intm; for (int i = 0; i n; i+) str1 = ; str2 = ; str3= ; x = true; for (int k = 0; k m; k+) if (myti = mymk) x = false;/ 判断物理块中是不是有跟当前须替换的页面 break; if (x) str3= String.valueOf(mym0); mym0 = myti; for (r = 0; r m - 1; r+) mymr = mymr + 1;mymr = myti; as+; int b;for (int j = 0; j m; j+) b = mymj;str2 = String.valueOf(b); str1 = str1 + + str2; m_list=m_list+n+str1+ +str3; m_absent = as; m_absentf = (double) as / n; if (as - m) = 0) m_changef = 0; else m_changef = (double) (1-m_absentf); 3、LRU算法（java实现）核心代码段：实验判断是否有缺页 public void LRU() int m_absent;/ 缺页数 double m_absentf;/ 缺页率 double m_changef;/ 命中率 int mym;/ 存放物理块中现有的页面号 int myb; int as = 0;/ 置换页面数 myb = new intn; int m1 = 0, a; boolean x; / 页面是否需要置换 String str2, str1,str3; String m_list = LUR置换算法 被替换; mym = new intm; for (int i = 0; i n; i+) str1 = ; str2 = ; str3=; x = true; for (int k = 0; k m; k+) if (myti = mymk)/ 判断物理块中的页面是否与当前页面相等 mybk = myb0; for (int j = 0; j m; j+) if (j != k) mybj = mybj + 1;/ 使物理块中的每个未使用页面的时间增一 x = false;/ 判断物理块中是不是有跟当前须替换的页面 m1+; break; if (x) int c = 0, d; if (i - m1) m) a = i - m1; / 当前物理页面未填满时直接装入 else d = myb0; for (int h = 0; h m; h+) if (d mybh) d = mybh; c = h; a = c; / 找出物理块中最久未使用的页面号 str3= String.valueOf(myma); myma = myti;/ 将其替换 myba = 0; for (int k = 0; k m; k+) if (k != a) mybk = mybk + 1;/ 使物理块中的每个未改变页面的时间增一 myba = 0; as+; for (int j = 0; j m; j+) int b; b = mymj; str2 = String.valueOf(b); str1 = str1 + + str2; m_list = m_list + n + str1+ +str3; m_absent = as; m_absentf = (double) as / n; if (as - m) = 0) m_changef = 0; else m_changef = (double)(1-m_absentf); 2）算法分析：1、OPT算法：最佳算法其选择的淘汰页面，将使以后用不使用的，或者是在长时间内不需要使用的。最佳页面置换算法通常可以保证获得一个最低的缺页率。不过最佳置换算法是一种理想化的算法，它具有最好的性能，但是实际上难以实现。2、FIFO算法：先进先出算法是一个最直观的算法，但是它性能可能是最差的故而在实际应用也很少使用。先进先出算法是最早出现的置换算法，此算法总是淘汰最先进入的页面，即选择在内存中驻留时间最长的页面淘汰。不过该算法实现比较的简单。算法思想分析：首先输入内存可用的物理块数m和用户输入的页面号的长度n，然后输入用户自定义的页面号放入mytn中。定义一个数组mymm存放当前页面。用m_absentf表示缺页率，m_changef表示 命中率，其中命中率=1-缺页率，缺页率=as/n（其中as表示缺页数）。程序执行过程如下：FIFO1254653278页10004663278页20055446327页30222554632页41111225463置换页000012546页面置换方法：以类似队列的方式，每次读入一个页面，如果数组中不存在此页面，则将数组内容保持不变。例如：上面读入5号页时，内存中存在5号页面，则保持数组内内容不变；如果数组中不存在此页面，则进行移动，例如：上面第五次读入6号页时，此时内存中不存在6号页面，则进行页面顺序移动，3、LRU算法：LRU是Least Recently Used 近期最少使用算法。假设 序列为 4 3 4 2 3 1 4 2物理块有3个 则首轮 4调入内存 4次轮 3调入内存 3 4之后 4调入内存 4 3之后 2调入内存 2 4 3之后 3调入内存 3 2 4之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）之后 4调入内存 4 1 3（原理同上）最后 2调入内存 2 4 13）代码分析：主要数据结构（1）根据用户需要随机输入数产生：数组（2）理想页面置换（OPT）算法：数组函数定义：（1）public pageChange():输入界面函数.（2）void misInPut()：获取用户自定义输入的页面号数组.（3）Void FIFO( ):计算使用FIFO算法时的命中率.（4）public displayView():输出界面函数.变量定义（1）int m_absent : 缺页数（2）double m_absentf : 缺页率（3）double m_changef : 页面命中率（4）int mym : 存放物理块中现有的页面号（5）int as = 0 : 置换页面数（6）boolean x : 页面是否需要置换程序层次结构程序包括3个类：【main】 ： 测试主函数【displayView】 ： 输出界面设计类【pageChang】 ： 输入界面设计，misInPut页面访问序列读入方法体，OPT方法体，FIFO方法体，LRU方法体。4）实验结果截图图一：OPT算法图二：FIFO算法图三：LRU算法四、实验小结本次实验的内容是页面置换算法的实现，在本次的实验过程中通过参考别人的算法结合自己对页面置换算法的理解完成本次的实验。本次的实验实现仍然