Java语言实现模拟页面置换算法-Read.doc

前言 在存储管理当中，页面置换算法通常可分为两种：一种基于进程驻留集大小不变；另一种基于驻留集大小可变。在驻留集大小不变的页面置换算法当中，常用的算法主要有：FIFO、OPT 、LRU。本文讨论的对象是FIFO、LRU算法。 在进程运行过程中，若所要访问的页面不在内存中，需要调入页面时，选择内存中的那个物理页面将其调出。通常只能在局部性原理指导下，把不再使用的页面调出。如何选择调度策略即页面置换算法至关重要，置换算法的好坏，直接影响着系统的性能，因此我们有必要将常见的FIFO和LRU两种算法进行比较，分析性能。 一、设计目的 了解页面置换的概念；理解页面置换的算法加深对页面置换算法的理解。 二、设计内容 编程实现FIFO和LRU页面算法。可以通过随机数产生新的页面，计算缺页次数和缺页率、置换次数和置换率。 页面置换算法原理 1) 先进先出算法（First In First Out），总选择作业中最先进入内存的一页淘汰。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出。只有在线性顺序访问地址空间时才是理想的，否则效率不高。在未给进程或作业分配足够的页面数时，缺页次数反而增加，从而产生Belady现象， 2) 最近最久不用的页面置换算法（Least Recently Used Replacement），当需要置换一页面时，选择在最近一段时间内最久不使用的页面予以淘汰。此算法通过周期性的对“引用位”进行检测，并利用它来记录一个页面自上次访问以来所经历的时间T；淘汰时，选择T为最大的页。选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。 四、 页面置换算法设计 1) FIFO算法 A. 算法简述： ① 开始时，因为内存中没有放有页面，所以先将insertPageNumber[]（存放要调入的页面，数组大小为pageNumber(页面数））中的一个页面调入内存并放入pageNumberM[]（存放调入内存的页面，数组大小为memBlock(物理块数））中； ② 如果insertPageNumber[]中的页面还没有访问完，则从insetPageNumber[]中调入新的页面。否则进入步骤④。如果该页面不在内存中存在，则将pageNumberM[memBlock]中最先进入内存的那个页面调出，然后将新页面放入。进入步骤③。 ③ 返回到步骤②。 ④ 结束，退出。 B. 算法流程图如下： FIFO流程图 Y N N N Y N Y Y N Y LRU算法 A. 原理简述 ① 开始时，因为内存中没有放有页面，所以先将insertPageNumber[]（存放要调入的页面，数组大小为pageNumber(页面数））中的一个页面调入内存并放入pageNumberM[]（存放调入内存的页面，数组大小为memBlock(物理块数））中； ② 如果insertPageNumber[]中的页面还没有访问完，则从insetPageNumber[]中调入新的页面。否则进入步骤④。如果该页面不在内存中存在，则通过访问flagArray[],获得数组元素最大值对应的数组下标index1，然后将新页面放入pageNumber[index1]中。进入步骤③。 ③ 返回到步骤②。④ 结束，退出。 Y N N Y N Y 五、结果显示 七、 心得体会 FIFO算法当需要置换页面时，主要通过置换最早进入内存的页面从而达到先进先出的目的。 LRU算法当需要置换页面时，主要通过置换进入内存中最久没有被访问的页面而达到最近最久未使用的目的。在这个程序中我只是通过一个标志数组来存储未被访问的次数。 在这个课程设计依据计算出的缺页次数和缺页率、置换次数和置换率，来论证FIFO算法与LRU算法的效果区别，通过测试可以看到对于调入页面的一般情况下LRU算法的置换次数明显的比FIFO算法的置换次数要少，但由于LRU算法是“向前看”的，而页面过去和未来的走向之间并无必然的联系。所以LRU算法与FIFO算法的缺页次数之间并无区别。 1. 通过本次课程设计,加深了对操作系统的页面置换有了一定的了解,并能够用高级语言进行模拟演示。通过查阅相关资料基本掌握了JAVA应用程序编写的基本方法。使用Java编程极大的减少了代码量，直观的界面设计，不仅便于实现而且简化了编码，便于集中精力到主算法的编写上。 2. 两种页面置换算法FIFO和LRU理解起来相当容易，但在实际