页面置换算法模拟 实验报告

实验5 页面置换算法模拟实验一．实验目的1.进一步掌握虚拟存储器的实现方法。

2.掌握各种页面置换算法。

3.比较各种页面置换算法的优缺点。

二．实验内容模拟实现页面置换算法，步骤为：①使用产生随机数函数得到一个随机的数列，作为将要载入的页面序列。

②使用先进先出（FIFO）算法、最近最久未使用（LRU）置换算法和最佳（OPT）置换算法，列出所需淘汰的页面号序列。

③列出缺页中断次数。

三．参考源程序如下：#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 10#define B 4/*------------------------------------------------------------------------函数名：IsInBuf()，返回某个数X在不在缓冲Buf[],如在，返回位置，否则返回－1--------------------------------------------------------------------------*/int IsInBuf(int buf[],int x){int i,j=-1;for(i=0;i<B;i++){if(buf[i]==x){ j=i;break; }else if(buf[i]==-1){ buf[i]=x;j=i;break; } }return j;}/*------------------------------------------------------------------------函数名：oldest()，返回最近最久未使用的页面位置--------------------------------------------------------------------------*/int oldest(int f[]){int i,j=0,max=-1;for(i=0;i<B;i++){if(f[i]>max){ max=f[i]; j=i; }f[i]++; }return j;}/*------------------------------------------------------------------------函数名：oldest2()，返回未来最久未使用的页面位置--------------------------------------------------------------------------*/int oldest2(int list[],int buf[],int f[],int start){int i,j;for(i=0;i<B;i++){for(j=start;j<N;j++){ if(buf[i]==list[j]) break; }f[i]=j; }return oldest(f);}int main(void){int list[N];int buf[B],f[B],i,j ;int old=0;int change=0;srand((int)time(NULL)); /*生成一系列随机数并初始化环境*/for(i=0;i<B;i++) {buf[i]=f[i]=-1;}printf("\nThe Random List:\n");for(i=0;i<N;i++){ list[i]=(int)rand()%10; printf("%2d",list[i]); } printf("\nFIFO\n");/*显示FIFO淘汰的页面序列*/change=0;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){printf("%2d",buf[old]);buf[old]=list[i];old=(old+1)%(int)B;change++;}else printf(" "); }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/printf("\nLRU\n");/*显示LRU淘汰的页面序列*/change=0;for(i=0;i<B;i++) {buf[i]=f[i]=-1;}for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);old=oldest(f);if(j==-1){printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++;}else{ f[j]=0; printf(" "); } }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/printf("\nOPT\n");/*显示OPT淘汰的页面序列*/change=0;for(i=0;i<B;i++) {buf[i]=f[i]=-1;}for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){old=oldest2(list,buf,f,i);printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++; }else{ f[j]=0; printf(" "); } }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/ getch();return 0; }（假设当前随机产生的页面序列为：7 1 0 4 2 5 8 6 9 1)四.填表题(1).在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为4时，试计算采用先进先出淘汰算法时的缺页率(假设开始执行时主存中没有页面)，并将所得结果填表。

页面置换算法实验报告院系:****************学院班级:***********姓名:***学号:************一、实验题目: 页面置换算法二. 实验目的：1.用C语言编写OPT、FIFO、LRU三种置换算法。

2.熟悉内存分页管理策略。

3.了解页面置换的算法。

4.掌握一般常用的调度算法。

5.根据方案使算法得以模拟实现。

6.锻炼知识的运用能力和实践能力。

三. 实验内容及要求:设计一个虚拟存储区和内存工作区, 编程序演示下述算法的具体实现过程, 并计算访问命中率:要求设计主界面以灵活选择某算法, 且以下算法都要实现1) 最佳置换算法(OPT): 将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。

2) 先进先出算法(FIFO)：淘汰最先进入内存的页面, 即选择在内存中驻留时间最久的页面予以淘汰。

3) 最近最久未使用算法(LRU): 淘汰最近最久未被使用的页面。

四、实验结果初始化结果1, 先进先出（FIFO）算法实验结果:2, 最近最久未使用（LRU）算法实验结果: 3, 最佳使用法（OPT）实验结果:五、实验总结选择置换算法, 先输入所有页面号, 为系统分配物理块, 依次进行置换:OPT基本思想:是用一维数组page[]存储页面号序列, memery[]是存储装入物理块中的页面。

数组next[]记录物理块中对应页面的最后访问时间。

每当发生缺页时, 就从物理块中找出最后访问时间最大的页面, 调出该页, 换入所缺的页面。

若物理块中的页面都不再使用, 则每次都置换物理块中第一个位置的页面。

FIFO基本思想:是用队列存储内存中的页面, 队列的特点是先进先出, 与该算法是一致的, 所以每当发生缺页时, 就从队头删除一页, 而从队尾加入缺页。

或者借助辅助数组time[]记录物理块中对应页面的进入时间, 每次需要置换时换出进入时间最小的页面。

LRU基本思想:是用一维数组page[]存储页面号序列, memery[]是存储装入物理块中的页面。

页面置换算法实验报告
一、实验内容
本次实验主要围绕页面置换算法进行，以实验课本的实例介绍，采用FIFO页面置换算法对后面提到的参数进行置换，最终得出页面置换的结果和比较所得结果。

二、实验步骤
(一) 熟悉FIFO算法
首先是要了解FIFO页面置换算法，FIFO全称（First In First Out），按页面进入内存的顺序来替换相应内存页面，先进先出，将先进入内存的页面先替换出去。

(二) 阅读实验课本
在阅读实验课本之前要先熟悉实验书上所介绍的FIFO算法，然后在实验书上找出需要做的实验，并对实验环境和表格进行观察，掌握实验的基本内容。

(三) 开始页面置换
在开始实验之前，熟悉实验环境，根据实验书上的参数，首先模拟进程分配内存，根据FIFO算法去进行计算，根据上表中的参数去比较，最后得出最终结果。

(四) 在本次实验的补充
这次实验中，可以把FIFO的概念应用到实际应用中，也可以模拟不同情况，例如改变页面的大小，观察不同页面置换算法的结果，实验出最合适的结果。

三、实验结论
本次实验是为了了解FIFO页面置换算法，实验出最终的结果，最后得出页面置换的结果及比较结果。