页面置换-操作系统实验报告.doc

实验二 页面置换算法实现
一、实验目的
（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（最近最久未使用算法）。在进程运行过程中，若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运行，系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应将哪个页面调出，需根据一定的算法来确定。

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）