页面置换算法模拟课程设计.doc

《操作系统原理与Linux》 课程设计报告 专 业 计算机科学与技术 班 级 学 号 姓 名 指导教师 完成时间 成 绩  目录 一、 设计题目 2 二、 设计目的 2 三、 设计要求 2 四、 设计思想说明 2 1. 最佳置换算法（OPT） 2 2. 先进先出置换算法（FIFO) 3 3. 最近最久未使用置换算法(LRU) 3 五、 系统结构说明 3 1. 内存信息类(MemInfo) 5 2. 访问器(MemVisitor) 5 3. 加载器(MemLoader) 6 4. 页面走向列表类(MemReqs) 6 5. MemReplacement 6 六、 数据结构说明 6 1. 内存信息类(MemInfo) 6 2. 访问器(MemVisitor) 7 3. 加载器(MemLoader) 8 4. 页面走向列表类(MemReqs) 9 七、 程序清单 9 1. 访问器 9 2. 加载器 10 3. 最佳置换算法 11 4. 先进先出算法 13 5. 最近最久末使用算法 13 八、 使用说明书 14 九、 实验体会、建议 16 十、 参考文献 17  设计题目 页面置换算法模拟 设计目的 编写页面置换算法，实现计算机中页面置换的模拟。 通过算法模拟的实现，理解几种常用的页面置换算法的执行过程。 设计要求 1、实现OPT,LRU,FIFO三种算法并进行对比分析。 2、要求界面简单,易懂,关键代码部分要注释。 3、编程语言可以采用自己任意精通的语言。 设计思想说明 最佳置换算法（OPT） 最佳置换算法所选择的被淘汰掉的页面，将是以后永久不再使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置算法，通常可保证获得最低的缺页率。本模拟算法中，最佳页面置换算法实现所采用的思想是：循环读入每个页表项，若该页表在内存中，则读取下一个页表项。若页表不存在内存中：一种情况是内存不满，则将页表放入内存中；若内存块已满，刚分别计算内存中各个页表再次被使用的时间，并将最久不被访问的调出，放入当前读入页表项。 先进先出置换算法（FIFO) 选择先进入内存的页面予以淘汰。这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。实现简单，但是算法与进程实际运行规律不适应，例如在进程中，有些页面是经常被访问的。 最近最久未使用置换算法(LRU) 选择最近一段时间最长时间没有被访问过的页面予以淘汰。 LRU算法是根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，采取“最近的过去”作为“最近的将来”的近似。选择最近最久未使用的页面予以淘汰。实现：赋予每个页面一个方位字段，用来记录一个页面自上次被访问以来所经历的时间T，当要淘汰一个页面的，选择现有页面中其T值最大的，即最近最久未使用的页面予以淘汰。 系统结构说明 本次算法模拟主要产生了7个类，访问器(MemVisitor)、加载器(MemLoader)、内存信息类(MemInfo)、页面走向列表类(MemReqs)、最佳置换算法类(AlgOpt)、先进先出算法类(AlgFIFO)、最近最久未使用算法类(AlgLRU)。 三个算法类都从MemReplacement继承，它主要包含一个方法，用于取得下一个要淘汰页面的ID，通过这种继承实现算法类多态。 而系统结构图大致如下。 内存信息类(MemInfo) 主要包含页表信息以及服务于先进先出算法的页面换入队列和服务于最近最久未使用算法的页面访问栈。 访问器(MemVisitor) 通过页面走向列表依次访问每一个页面，若页面已存在内存（通过MemInfo 得知），直接访问；若页面不在内存中，则调用加载器加载相应的页。 加载器(MemLoader) 通过MemInfo得知内存块是否已占满，若未占满，则将相应的页载入空闲的内存块；若内存块已满，则调用已设置的置换算法，得出最佳淘汰页。加载器将在页表中将其移出，并且将欲载入的页加载到相应的内存块中。 页面走向列表类(MemReqs) 包含页面走向列表，在应用程序中设置。 MemReplacement 是置换算法基类，它包含一个虚函数 NextPage(MemInfo info) ，加载器将调用此方法得到欲淘汰的页。加载器在设置使用的置换算法时