设计程序对比分析页面置换策略《操作系统》实验报告.docxVIP

设计程序对比分析页面置换策略《操作系统》实验报告 年级、专业、班级实验题目 2010 级信安 一班 姓名 黄耿设计程序对比分析页面置换策略 实验时间 2013.5.7 实验地点 主教 410 实验成绩 实验性质 □验证性 □设计性 □综合性 教师评价： □算法/实验过程正确； □源程序/实验内容提交 □程序结构/实验步骤合理； □实验结果正确； 其他： □语法、语义正确； □报告规范； 评价教师签名： 一、实验目的 熟悉常用的页面置换策略的基本原理； 通过模拟实验分析不同置换策略的性能差异； 理解操作系统关于内存管理的一些方法。 二、实验项目内容 在 Windows 操作系统上开发一个具备图形界面的程序。程序功能： 动态演示四种页面置换策略（OPT，FIFO，LRU，CLOCK）。 能够可视化观察每种置换策略的工作工程。 能够输入一个数字表示页执行序列的总长度（不小于 1000），能够设置进程的总页数，然后随机产生页执行序列。 能够输入一个数字设置操作系统分配给进程的页面数。 统计每种置换策略在不同输入数据情况下的页面失效数。 根据实验结果分析不同置换策略的性能。并在实验报告中画出页面失效数与分配的页面数之间的关系曲线。参考教材图 8.17。 观察 FIFO 的 belady 效应。 三、实验过程或算法（源程序） 1. 先进先出（FIFO）算法 先进先出算法（ FIFO），总选择作业中最先进入内存的一页淘汰。较早调入的页往往是经常被访问的页，这些页在 FIFO 算法下被反复调入和调出。只有在线性顺序访问地址空间时才是理想的，否则效率不高。 算法流程图： 2、最近最久不用的页面置换算法（LRU） 根据页面调入内存后使用情况进行决策，选择在最近一段时间内最久不用的页面予以淘汰，当页面进入内存时设计一个数组，记录每个页面自上次访问内存以来经历的时间 t，淘汰时，总是选择 t 值最大的页面予以淘汰！ 算法流程图： 3 、Clock算法 为内存中的每一个页面设置一位访问位，当某页被访问时，其访问位置 1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是 0，就 选择将该页换出，若为 选择将该页换出，若为 1，则重新将它置 0，暂不换出，而给该页面第二次驻留内存的机会，再按 FIFO 算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为 1，则在返回到队首检查第一个页面! 流程图如图： 4、最佳置换算法（Opt） 需要进行页面置换时，把内存中以后一段时间都不使用或是使用时间离现在很远的页面置换出去 流程图如图： 各算法的实现代码见附录。 四、实验结果及分析和（或）源程序调试过程 4.1 操作流程 图 4-1 程序主界面 界面下输入物理块数，置换页面数还有页表长度，点击 Random 按钮， 产生一组页面引用号，如图 图 4-2 随机产生页面地址序列 在随机产生一组页面引用串后，点击“FIFO”按钮，OPT 算法置换过程界面，如图 图 4-3 FIFO 算法的置换过程 清空界面，点击 Random 按钮随机产生页面引用串，接着点击“ LRU” 按钮，LRU 算法置换过程界面，如图 清空界面，点击 Random 按钮随机产生一组页面引用串，接着点击“Optimal”按钮，Optimal 算法置换过程界面，如图 清空界面，点击 Random 按钮随机产生一组页面引用串，接着点击“Clock”按钮，Clock 算法置换过程界面，如图 通过随机产生一引用串，比较Option 算法，FIFO 算法，LRU 算法，Clock 算法的命中率，缺也率。比较如图 打开“性能模拟”面板： 在“页表长度”输入框中输入页表长度，并单击“生成随机序列”按钮， 效果如图： 点击“模拟”按钮，开始算法的模拟，如图： 模拟结果： 四种算法对应不同页框数时页面失效率的比较： 性能比较：从上图可看出，Optimal 算法的性能较优，在先进先出算法(FIFO)——选择装入最早的页面置换的过程中，可以通过链表来表示各页的装入时间先后。FIFO 的性能较差，因为较早调入的页往往是经常被访问的页，这些页在FIFO 算法下被反复调入和调出，并且有Belady 现象。所谓 Belady 现象是指：采用FIFO 算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。 五、心得体会 通过本次实验，我对四种页面置换策略有了更深的了解，理解了操作系统关于内存管理的一些方法，并通过编程实现了 Option 算法，FIFO 算法，LRU 算法，Clock 算法。也进一步提高了我们的编程能力，从中学会了很多。 六、附录：源代码 OPT 置换算法实现类 public class OPT { private int m,n,len