页面置换算法的模拟实现及命中率对比实验报告

页面置换算法的模拟实现及命中率对比实验报告

一、问题描述

课程设计目的

（1）、通过请求页式管理方式中页面置换算法的模拟设计，了解虚拟存储 术的特点，掌握请求页式存储管理中的页面置换算法。 （2）、课程设计内容

模拟实现OPT（最佳置换）、FIFO和LRU算法，并计算命中率。

（3） 、课程设计要求：

a) 首先用随机数生成函数产生“指令”序列，然后将指令序列变换成相应

的页地址流，再计算不同算法下的命中率。

b) 通过随机数产生一个指令序列，共产生400条。其中50%的指令是顺序

执行的（灵位50%就是非顺序），且25%的指令分布在前半部分地址空间，25%的指令分布在后半部分地址空间。 c) 将指令地址流变换成页地址流

d) 循环运行，使用户内存容量从4到40,。计算每个内存容量下不同页面

置换算法的命中率。

二、概要设计

1.程序的数据结构：

#define total_instruction 100 /*指令流长*/ #define M 100 /*实际页数*/

#define N 5 序的主函数： int main() {

Pro p[total_instruction];

Pro *page=new Pro[N]; char c; int t=0,i; float n=0; Input(p); do{

for( i=0;iprintf(\"系统产生的随机数为：\"); for(int e=0;ei=0;

cout<<\"f:FIFO页面置换\"<>c;

if(c=='f')um,page)>=0) i++;um=p[i].num; print(page); t++; } }

} cout<<\"

缺

页

次

数

：

\"<命

中

率

：

\"<<1-n/total_instruction<}

if(c=='l')um,page); if(t>=0)

page[t].time=0;

else { n++;

t=Max(page);

page[t].num=p[i].num; page[t].time=0; }

for(int j=0;jif(j!=t)page[j].time++; }

/*if(t==0){page[t+1].time++;page[t+2].time++;} if(t==1){page[2].time++;page[0].time++;} if(t==2){page[1].time++;page[0].time++;}*/ if(k==-1) print(page); i++; }

cout<<\"缺页次数：\"<\"<<1-n/total_instruction<}

if(c=='o')um,page)>=0)i++; else {

if(page[N-1].num==-1) {

for(int g=0;gpage[g].num=p[i].num; i++; n++; print(page); break; } } else{ int temp=-1,cn; for(t=0;tif(temptemp=Compfu(page,i,t,p); cn=t; }

}

page[cn]=p[i]; n++;

print(page); i++; } } } cout<<\"

缺

页

次

数

：

\"<命

\"<<1-n/total_instruction<}while(c=='f'||c=='l'||c=='o');

return 0; }

三、详细设计

程序代码如下： #include<>

#include #include<> #include<>

using namespace std;

#define total_instruction 100 /*指令流长*/ #define M 100 /*实际页数*/

率

中

：

#define N 5 um=a[i]/10; p[i].time = 0; } }

void print(Pro *page1)um); um<<\" \"; cout<int Max(Pro *page1) {

Pro *page=new Pro[N]; page=page1;

int e=page[0].time,i=0; while(ifor( i=0;ireturn -1; }

int Compfu(Pro *page1,int i,int t,Pro p[M]) {

Pro *page=new Pro[N]; page=page1;

int count=0;

for(int j=i;jif(page[t].num==p[j].num )break; else count++; }

return count; }

int main() {

Pro p[total_instruction]; Pro *page=new Pro[N]; char c; int t=0,i; float n=0; Input(p); do{

for( i=0;iprintf(\"系统产生的随机数为：\"); for(int e=0;ei=0;

cout<<\"f:FIFO页面置换\"<>c;

if(c=='f')um,page)>=0) i++;um=p[i].num; print(page); t++; } } } cout<<\"

缺

页

次

数

：

\"<命

\"<<1-n/total_instruction<if(c=='l')um,page); if(t>=0)

page[t].time=0; else { n++;

t=Max(page);

page[t].num=p[i].num; page[t].time=0; }

率

中

：

for(int j=0;jif(j!=t)page[j].time++; }

/*if(t==0){page[t+1].time++;page[t+2].time++;} if(t==1){page[2].time++;page[0].time++;} if(t==2){page[1].time++;page[0].time++;}*/ if(k==-1) print(page); i++; } cout<<\"

缺

页

次

数

：

\"<命

\"<<1-n/total_instruction<if(c=='o')um,page)>=0)i++; else {

if(page[N-1].num==-1) {

for(int g=0;gpage[g].num=p[i].num; i++; n++; print(page); break; }

率

中

：

} else{ int temp=-1,cn; for(t=0;tif(temptemp=Compfu(page,i,t,p); cn=t; } }

page[cn]=p[i]; n++;

print(page); i++; } } } cout<<\"

缺

页

次

数

：

\"<命

\"<<1-n/total_instruction<}while(c=='f'||c=='l'||c=='o'); return 0; }

率

中

：

四、调试与分析

程序的主界面：

这里测试用的数据是M=40，N=5，三种算法置换结果如以下的图： FIFO算法：

LRU算法：

OPT算法：

多运行几次，产生不同的随机数组，查看对比结果。 在某一次实验中，可能FIFO算法的命中率比LRU

算法要高，但经过多组测试数据及总体的结果表明：LRU的平均性能比FIFO 的平均性能好。