页面淘汰算法实验报告

《页面淘汰算法实验报告》由会员分享，可在线阅读，更多相关《页面淘汰算法实验报告（29页珍藏版）》请在金锄头文库上搜索。

1、操作系统实验报告课题：页面淘汰算法专业：班级：学号：姓名：年月日目录实验目的实验要求3背景知识3四总体设计4详细设计运行结果分析91314 15一、实验目的本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。学生通过设计与实现 Clock 算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。 利用简单的数据结构， 模拟实现操作系统中的页面置换机制， 通过写程序模拟实现上述三种内存页面置换算法，使学生进一步掌握内存页面置换的方法。 对操作系统中内存的管理有一个实践上的认识。1、用 C语言编写 OPT、FIFO、LRU三种置换算法。2、熟悉内存

2、分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的运用能力和实践能力。二、实验要求设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的影响编写页面淘汰算法 (FIFO 、OPT、LRU)结果数据的显示或提取结果数据的分析几点说明：设计并绘制算法流程，附加说明所需的数据结构如何标记时间的先后、最久的将来、最久未被使用描述 Clock 算法的基本原理、 必要的数据结构、 算法执行流程图、 编码实现。1）初始化：输入作业可占用的总页框数，初始化置空。2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用；

3、3）Clock 算法：当页框全部占用后， 对于后续新的页号访问请求， 执行 Clock算法，淘汰 1 个页面后装入新的页号。4）显示当前分配淘汰序列：显示淘汰的页号序列。三、背景知识：在操作系统当中，在进程运行过程中，若其访问的页面不在内存中而需把他们调入内存，但内存已无空闲空间时，为了保证该进程能够正常的运行，系统必须从内存中调出一页程序或数据送到磁盘的兑换区中，但是应该是哪个页面被调出，需根据一定的算法来确定。 通常，我们把这一类的算法称为“页面置换算法”，页面置换算法执行效率的高低，往往直接影响到操作系统的性能。内存页面置换算法：1、 先进先出调度算法（ FIFO）先进先出调度算法根据页

4、面进入内存的时间先后选择淘汰页面。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次置换掉最早进入的页面。这是最早出现的置换算法， 该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面换出，予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、 常用函数、 例程等的页面， FIFO算法并不能保证这些页面不被淘汰。最近最久未使用的置换算法（LRU）最近最久未使用的置换算法， 是根据页面调入内存后的使用

5、情况进行决策的。由于无法预测各页面将来的使用情况， 只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段， 用来记录一个页面自上次被访问以来所经历的时间 t, ，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。 最佳置换算法（ OPT）最佳置换算法是可以说的一种理想的页面置换算法，它是由 Belady 于1966年提出的一种理论上的算法。 其所选择的被淘汰页面， 将是以后永不使用的或许是在最长 ( 未来 ) 时间内不再被访问的页面。 采用最佳置换算法， 通常可保证获得最低的缺

6、页率。 但由于人目前还无法预知一个进程在内存的若干个页面中， 哪一个页面是未来最长时间内不再被访问的， 因而该算法是无法实现的， 但可以利用此算法来评价其它算法。时钟页面置换算法时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中， 一个表针指向最老的页面，如图所示。当发生缺页中断时， 算法首先检查表针指向的页面，如果它的 R位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果 R 位是 1 就清除 R 位并把表针前移一个位置， 重复这个过程直到找到了一个 R 位为 0 的页面为止。四、 总体设计根据要求设计页面淘汰算法的活动图运行程序进入主页面，在正上方，

7、已经通过随机生成函数生成了页面号，在其下方，显示可选项： 0、退出程序 1、FIFO 算法 2、OPT算法 3、LRU算法。根据需要，选择相应的法，程序自动生成页面淘汰的先后顺序，以及置换次数和缺页次数，并打印在下方，执行完以后，再次进入主页面，到输入0，退出程序。算法流程图FIFO算法流程图：新的指令页面内存中的所有已在内存物理块页面 time+1中？否载入新页面否内存物理块集合已time=0满？是选择time 值最大的页面换出OPT算法流程图内存中所有页面time+1是载入该页面否LRU算法流程图：新的指令页面是已在内存物理块中？否内存物理块集合已满？是对内存中每个页面，向后遍历剩余指令集

8、合，记录每个页面距离再次被利用的页面跨度选择跨度最大的页面换出新的指令页面内存中所有页面time+1内存中的所有已在内存物理块是该页面time=0页面time+1中？否载入新页面否内存物理块集合已time=0满？是选择time值最大的页面换出五、 详细设计（一）、设计思想1、最佳置换算法 (OPT)用数组 Temppages存储当前物理块中页面信息，数组 TimeArry 存储当前在物理块中的页面的获得内存时的时间， 当页面不在内存中时，根据当前已获得物理块数的页面在所有的页面当中将来不在请求内存或者很少请求内存的情况进行置换2、先进先出算法 (FIFO)用数组 Temppages 存储当前物

9、理块中页面信息， 变量 temp 记录内存中物理块页面置换状态，每进行一次置换，页面置换状态变化，便于下一次的置换。3、最近最久未使用算法 (LRU)用数组 Temppages存储当前物理块中页面信息，数组 TimeArry 存储当前在物理块中的页面的获得内存时的时间， 当页面不在内存中时，选择 TimeArry 数组中值最小并且对应物理块中的页面进行置换。（二）、设计步骤首先根据程序要求，我们分别定义两个宏，用以存放我们的物理块数目以及页面数目，再定义一个结构体，用以物理块的存储，代码如下：#define MemPageCount 4#define InstructionCount 20st

10、ruct pageint serial; /int time; /页面号时间计数mempageMemPageCount;其次，建立主函数，根据程序需要，定义相应的变量，建立 switch 语句，用以算法的选择，部分定义如下：int i,j,k,m,n;/指令页面集合, 可以考虑让页面指令集合随机生成int instructionInstructionCount;int mem_counter; / int switch_counter; /内存页面集合计数器置换次数最后，根据算法流程图，实现相应算法的代码编写。（三）、算法流程设计主函数流程 :STEP1:输入分配的页框数，页面访问次数和要访问

11、的页面号序列STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，含有页号值 yehao 和访问位值 a。开始时页号均为 -1 ，访问位为 0.STEP3：测试数据。具体算法是依要访问的页面号，调用 find() 函数查找是否已经存在于内存中。 若存在，则修改其访问位为 1. 若不存在，触发缺页中断，调用 tihuan() 函数。最后，打印当前内存状态。如此循环直至测试串都访问完毕。1) 主要函数实现a) Makenode(double) 函数：用于初始化一个节点。b) Find（ double ）函数：依据输入的页号，查询内存中是否已存在此页面。若存在返回值 1，不存在返回值 0.c)Tihuan （double ）函数：在发生缺页中断时，时钟指针查找访问位为0的页面进行替换，指针扫过的页面访问位置0，新加入的页面访问位置1。替换后指针下移。d) Print_state() 函数：打印当前内存中存在的页面的状态以及当前时钟指针所指向的页面位置。2) 测试数据估计输入：输入分配的页框数3输入页面访问次数15输入要访问的页面号