Java语言实现模拟页面置换算法

1、前言 在存储管理当中，页面置换算法通常可分为两种：一种基于进程驻留集大小不变；另一种基于驻留集大小可变。在驻留集大小不变的页面置换算法当中，常用的算法主要有：fifo、opt 、lru。本文讨论的对象是fifo、lru算法。在进程运行过程中，若所要访问的页面不在内存中，需要调入页面时，选择内存中的那个物理页面将其调出。通常只能在局部性原理指导下，把不再使用的页面调出。如何选择调度策略即页面置换算法至关重要，置换算法的好坏，直接影响着系统的性能，因此我们有必要将常见的fifo和lru两种算法进行比较，分析性能。一、设计目的 了解页面置换的概念；理解页面置换的算法加深对页面置换算法的理解。二、设计

2、内容编程实现fifo和lru页面算法。可以通过随机数产生新的页面，计算缺页次数和缺页率、置换次数和置换率。3、 页面置换算法原理1) 先进先出算法（first in first out），总选择作业中最先进入内存的一页淘汰。较早调入的页往往是经常被访问的页，这些页在fifo算法下被反复调入和调出。只有在线性顺序访问地址空间时才是理想的，否则效率不高。在未给进程或作业分配足够的页面数时，缺页次数反而增加，从而产生belady现象，2) 最近最久不用的页面置换算法（least recently used replacement），当需要置换一页面时，选择在最近一段时间内最久不使用的页面予以淘汰。此

3、算法通过周期性的对“引用位”进行检测，并利用它来记录一个页面自上次访问以来所经历的时间t；淘汰时，选择t为最大的页。选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。四、 页面置换算法设计1) fifo算法a. 算法简述： 开始时，因为内存中没有放有页面，所以先将insertpagenumber（存放要调入的页面，数组大小为pagenumber(页面数）中的一个页面调入内存并放入pagenumberm（存放调入内存的页面，数组大小为memblock(物理块数）中； 如果insertpagenumber中的页面还没有

4、访问完，则从insetpagenumber中调入新的页面。否则进入步骤。如果该页面不在内存中存在，则将pagenumbermmemblock中最先进入内存的那个页面调出，然后将新页面放入。进入步骤。 返回到步骤。 结束，退出。b. 算法流程图如下：fifo流程图 开始 取一块页面页面在内存中是否存在y内存块是否填满nnny内存数组的下标等于物理块数n从第一个开始循环y 下标置零 将页面插入到下标index处; 下标增一 取下一块页面页面是否全部访问y n y 终止2) lru算法a. 原理简述 开始时，因为内存中没有放有页面，所以先将insertpagenumber（存放要调入的页面，数组大小

5、为pagenumber(页面数）中的一个页面调入内存并放入pagenumberm（存放调入内存的页面，数组大小为memblock(物理块数）中； 如果insertpagenumber中的页面还没有访问完，则从insetpagenumber中调入新的页面。否则进入步骤。如果该页面不在内存中存在，则通过访问flagarray,获得数组元素最大值对应的数组下标index1，然后将新页面放入pagenumberindex1中。进入步骤。 返回到步骤。 结束，退出。 开始 取一块页面 页面在内存中是否存在yn物理块是否已满ny遍历标志数组；获得数组元素的最大值对应的数组下标 将页面放入对应数组下标的内存

6、数组中将标志数组的其余元素值加一，对应元素的值赋零，下标加一 取下一块页面 页面是否全部访问n 结束y五、结果显示七、 心得体会fifo算法当需要置换页面时，主要通过置换最早进入内存的页面从而达到先进先出的目的。lru算法当需要置换页面时，主要通过置换进入内存中最久没有被访问的页面而达到最近最久未使用的目的。在这个程序中我只是通过一个标志数组来存储未被访问的次数。在这个课程设计依据计算出的缺页次数和缺页率、置换次数和置换率，来论证fifo算法与lru算法的效果区别，通过测试可以看到对于调入页面的一般情况下lru算法的置换次数明显的比fifo算法的置换次数要少，但由于lru算法是“向前看”的，而

7、页面过去和未来的走向之间并无必然的联系。所以lru算法与fifo算法的缺页次数之间并无区别。1. 通过本次课程设计,加深了对操作系统的页面置换有了一定的了解,并能够用高级语言进行模拟演示。通过查阅相关资料基本掌握了java应用程序编写的基本方法。使用java编程极大的减少了代码量，直观的界面设计，不仅便于实现而且简化了编码，便于集中精力到主算法的编写上。2. 两种页面置换算法fifo和lru理解起来相当容易，但在实际编程实现的时候需要注意各种细节，需要耐心细致，实际编程中遇到一些细节上的小问题确实需要仔细考虑才行。3. 为了简化编程的困难,采用随即数的思想,使得程序易于实现。通过两种页面置换算法的比较，对页面置换有更深一层的了解。使我对操作系统特别是页面置换这一部分的认识有了很大的加深。4. 使自己对java语言的基本框架有新的了解，加深了对可视化程序的认识。在使用java语言来实