资源描述
实验二 页面置换算法实现
一、实验目的
(1)了解内存分页管理策略
(2)掌握调页策略
(3)掌握一般常用的调度算法
(4)学会各种存储分配算法的实现方法。
(5)了解页面大小和内存实际容量对命中率的影响。
二、实验内容
采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,
同时也考虑页面大小及内存实际容量对命中率的影响,设计一个虚拟存储区和内
存工作区,并使用下述算法来模拟实现页面的置换:
1. 先进先出的算法(FIFO)
2. 最近最久未使用算法(LRU)
3. 最佳置换算法(OPT)
实验分析
在进程运行过程中,若其所访问的页面不存在内存而需要把它们调入内存,
但内存已无空闲时,为了保证该进程能够正常运行,系统必须从内存中调出一页
程序或数据送磁盘的对换区中。但应调出哪个页面,需根据一定的算法来确定,
算法的好坏,直接影响到系统的性能。一个好的页面置换算法,应该有较低的页面更换频率。
2.1 先进先出(FIFO )页面置换算法
当需要访问一个新的页面时,首先查看物理块中是否就有这个页面,若要查
看的页面物理块中就有,则直接显示,不需要替换页面;如果要查看的页面物理
块中没有,就需要寻找空闲物理块放入,若存在有空闲物理块,则将页面放入;
若没有空闲物理块,则替换页面。并将物理块中所有页面 timer++。
2.2 最近久未使用 (LRU) 置换算法的思路
最近久未使用置换算法的替换规则,是根据页面调入内存后的使用情况来进
行决策的。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问
以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进
行淘汰。
2.3 最佳(OPT)置换算法的思路
其所选择的被淘汰的页面,是以后不使用的,或者是在未来时间内不再被访
问的页面,采用最佳算法,通常可保证获得最低的缺页率。
三、 实验流程
3.1 系统功能图
图3-1 系统功能图
3.2 算法流程图
1) 先进先出(FIFO )页面置换算法流程图
图3-2 先进先出页面置换算法流程图
2) 最近久未使用 (LRU) 置换算法
图3-3 最近久未使用置换算法流程图
3) 最佳( OPT )置换算法
图3-4 最佳置换算法流程图
四、 源程序
#include<iostream.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#define L 20 //页面长度最大为20
int M; //内存块
struct Pro//定义一个结构体
{
int num,time;
};
Input(int m,Pro p[L])//打印页面走向状态
{
cout<<"请输入页面长度(10~20):";
do
{
cin>>m;
if(m>20||m<10)
{ cout<<endl;
cout<<"页面长度必须在10~20之间"<<endl<<endl;
cout<<"请重新输入L:";
}
else break;
}while(1);
int i,j;
j=time(NULL);//取时钟时间
srand(j);//以时钟时间j为种子,初始化随机数发生器
cout<<endl;
cout<<"输出随机数: "<<endl;
cout<<endl;
for(i=0;i<m;i++)
{
p[i].num=rand( )%10;//产生0到9之间的随机数放到数组p中
p[i].time=0;
cout<<p[i].num<<" ";
}
cout<<endl<<endl;
return m;
}
void print(Pro *page1)//打印当前的页面
{
Pro *page=new Pro[M];
page=page1;
for(int i=0;i<M;i++)
cout<<page[i].num<<" ";
cout<<endl;
}
int Search(int e,Pro *page1 )//寻找内存块中与e相同的块号
{
Pro *page=new Pro[M];
page=page1;
for(int i=0;i<M;i++)if(e==page[i].num)return i;//返回i值
return -1;
}
int Max(Pro *page1)//寻找最近最长未使用的页面
{
Pro *page=new Pro[M];
page=page1;
int e=page[0].time,i=0;
while(i<M) //找出离现在时间最长的页面
{
if(e<page[i].time) e=page[i].time;
i++;
}
for( i=0;i<M;i++)if(e==page[i].time)return i;//找到离现在时间最长的页面返回其块号
return -1;
}
int Count(Pro *page1,int i,int t,Pro p[L])//记录当前内存块中页面离下次使用间隔长度
{
Pro *page=new Pro[M];
page=page1;
int count=0;
for(int j=i;j<L;j++)
{
if(page[t].num==p[j].num )break;//当前页面再次被访问时循环结束
else count++;//否则count+1
}
return count;//返回count的值
}
int main()
{
int c;
int m=0,t=0;
float n=0;
Pro p[L];
m=Input(m,p);//调用input函数,返回m值
cout<<"请输入分配的物理块m(2~6): ";
cout<<endl<<endl;
do{
cin>>M;
if(M>6||M<2)
{ cout<<endl;
cout<<"物理块m必须在2~6之间"<<endl<<endl;
cout<<"请重新输入m: ";}
else break;
}while(1);
Pro *page=new Pro[M];
do{
for(int i=0;i<M;i++)//初始化页面基本情况
{ page[i].num=0;
page[i].time=m-1-i;
}
i=0;
cout<<endl;
cout<<"1:FIFO页面置换 2:LRU页面置换"<<endl;
cout<<"3:OPT页面置换 4:退出"<<endl;
cout<<"请选择页面置换算法:"<<endl;
cin>>c;
if(c==1)//FIFO页面置换
{
n=0;
cout<<" FIFO算法页面置换情况如下: "<<endl;
cout<<endl;
while(i<m)
{
if(Search(p[i].num,page)>=0) //当前页面在内存中
{
cout<<p[i].num<<" "; //输出当前页p[i].num
cout<<"不缺页"<<endl;
i++; //i加1
}
else //当前页不在内存中
{
if(t==M)t=0;
else
{
n++; //缺页次数加1
page[t].num=p[i].num; //把当前页面放入内存中
cout<<p[i].num<<" ";
print(page); //打印当前页面
t++; //下一个内存块
i++; //指向下一个页面
}
}
}
cout<<endl;
cout<<"缺页次数:"<<n<<" 缺页率:"<<n/m<<endl<<endl;
}
if(c==2)//LRU页面置换
{
n=0;
cout<<" LRU算法页面置换情况如下: "<<endl;
cout<<endl;
while(i<m)
{
int a;
t=Search(p[i].num,page);
if(t>=0)//如果已在内存块中
{ page[t].time=0;//把与它相同的内存块的时间置0
for(a=0;a<M;a++)
if(a!=t)page[a].time++;//其它的时间加1
cout<<p[i].num<<" ";
cout<<"不缺页"<<endl;
}
else //如果不在内存块中
{
n++; //缺页次数加1
t=Max(page); //返回最近最久未使用的块号赋值给t
page[t].num=p[i].num; //进行替换
page[t].time=0; //替换后时间置为0
cout<<p[i].num<<" ";
print(page);
for(a=0;a<M;a++)
if(a!=t) page[a].time++; //其它的时间加1
}
i++;
}
cout<<endl;
cout<<"缺页次数:"<<n<<" 缺页率:"<<n/m<<endl<<endl;
}
if(c==3)//OPT页面置换
{
n=0;
cout<<" OPT算法置换情况如下:"<<endl;
cout<<endl;
while(i<m)
{
if(Search(p[i].num,page)>=0)//如果已在内存块中
{
cout<<p[i].num<<" ";
cout<<"不缺页"<<endl;
i++;
}
else//如果不在内存块中
{
int a=0;
for(t=0;t<M;t++)
if(page[t].num==0)a++;//记录空的内存块数
if(a!=0) //有空内存
{
int q=M;
for(t=0;t<M;t++)
if(page[t].num==0&&q>t)q=t;//把空内存块中块号最小的找出来
page[q].num=p[i].num;
n++;
cout<<p[i].num<<" ";
print(page);
i++;
}
else
{
int temp=0,s;
for(t=0;t<M;t++)//寻找内存块中下次使用离现在最久的页面
if(temp<Count(page,i,t,p))
{
temp=Count(page,i,t,p);
s=t; }//把找到的块号赋给s
page[s].num=p[i].num;
n++;
cout<<p[i].num<<" ";
print(page);
i++;
}
}
}
cout<<endl;
cout<<"缺页次数:"<<n<<" 缺页率:"<<n/m<<endl<<endl;
}
if(c == 4) break;
}while(c==1||c==2||c==3);
return 0;
}
五、实验结果
5.1 程序主界面
运行程序后,将会提示用户输入页面长度,长度在10到20之间。当用户输入长度(以12为例)后,系统将会显示随机数。系统提示用户输入分配的物理块,用户输入数据(以3为例)。程序主界面运行图如图5-1所示。
图5-1 程序主界面
5.2 先进先出(FIFO) 页面置换算法运行结果
选择算法1之后,进入算法1 的操作。系统会显示算法的页面置换情况。先来先服务算法的运行图如图5-2所示。
图5-2 先进先出页面置换算法运行结果图
5.3 最近久未使用 (LRU) 置换算法运行结果
选择算法2之后,进入算法2 的操作。系统会显示算法的页面置换情况。最近久未使用的运行图如图5-3所示。
图5-3 最近久未使用置换算法运行结果图
4) 最佳( OPT )置换算法运行结果
选择算法3之后,进入算法3 的操作。系统会显示算法的页面置换情况。最近久未使用的运行图如图5-4所示。
图5-4 最佳置换算法运行结果图
四、 总结
通过本次实验,我对页面置换算法的了解更加的深刻。页面置换算法主要有以下置换算法:OPT(最佳置换算法)、FIFO(先进先出置换算法)、LRU(最近最久未使用算法)。在进程运行过程中,若其访问的页面不在内存而需把它们调入内存,但内存以无空闲空间时,为了保证该进程能正常的运行,系统必须从内存中调出一页程序或数据送磁盘的兑换区中,但应将哪个页面调出,需根据一定的算法来确定。
(注:专业文档是经验性极强的领域,无法思考和涵盖全面,素材和资料部分来自网络,供参考。可复制、编制,期待你的好评与关注)
展开阅读全文