页面置换操作系统实验报告.docx
《页面置换操作系统实验报告.docx》由会员分享，可在线阅读，更多相关《页面置换操作系统实验报告.docx（16页珍藏版）》请在冰点文库上搜索。
页面置换操作系统实验报告
实验二页面置换算法实现
一、实验目的
（1）了解内存分页管理策略
（2）掌握调页策略
（3）掌握一般常用的调度算法
（4）学会各种存储分配算法的实现方法。
（5）了解页面大小和内存实际容量对命中率的影响。
二、实验内容
采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，
同时也考虑页面大小及内存实际容量对命中率的影响，设计一个虚拟存储区和内
存工作区，并使用下述算法来模拟实现页面的置换：
1.先进先出的算法（FIFO）
2.最近最久未使用算法（LRU）
3.最佳置换算法（OPT）
实验分析
在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，
但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页
程序或数据送磁盘的对换区中。
但应调出哪个页面，需根据一定的算法来确定，
算法的好坏，直接影响到系统的性能。
一个好的页面置换算法，应该有较低的页面更换频率。
2.1先进先出（FIFO）页面置换算法
当需要访问一个新的页面时，首先查看物理块中是否就有这个页面，若要查
看的页面物理块中就有，则直接显示，不需要替换页面；如果要查看的页面物理
块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；
若没有空闲物理块，则替换页面。
并将物理块中所有页面timer++。
2.2最近久未使用（LRU）置换算法的思路
最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进
行决策的。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问
以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进
行淘汰。
2.3最佳（OPT）置换算法的思路
其所选择的被淘汰的页面，是以后不使用的，或者是在未来时间内不再被访
问的页面，采用最佳算法，通常可保证获得最低的缺页率。
3、实验流程
3.1系统功能图
图3-1系统功能图
3.2算法流程图
1）先进先出（FIFO）页面置换算法流程图
图3-2先进先出页面置换算法流程图
2）最近久未使用（LRU）置换算法
图3-3最近久未使用置换算法流程图
3）最佳（OPT）置换算法
图3-4最佳置换算法流程图
4、源程序
#include
#include
#include
#include
#defineL20//页面长度最大为20
intM;//内存块
structPro//定义一个结构体
{
intnum,time;
};
Input（intm,Prop[L]）//打印页面走向状态
{
cout<<"请输入页面长度（10～20）：
";
do
{
cin>>m;
if（m>20||m<10）
{cout<cout<<"页面长度必须在10～20之间"<cout<<"请重新输入L：
";
}
elsebreak;
}while
（1）;
inti,j;
j=time（NULL）;//取时钟时间
srand（j）;//以时钟时间j为种子，初始化随机数发生器
cout<cout<<"输出随机数:
"<cout<for（i=0;i{
p[i].num=rand（）%10;//产生0到9之间的随机数放到数组p中
p[i].time=0;
cout<}
cout<returnm;
}
voidprint（Pro*page1）//打印当前的页面
{
Pro*page=newPro[M];
page=page1;
for（inti=0;icout<cout<}
intSearch（inte,Pro*page1）//寻找内存块中与e相同的块号
{
Pro*page=newPro[M];
page=page1;
for（inti=0;ireturn-1;
}
intMax（Pro*page1）//寻找最近最长未使用的页面
{
Pro*page=newPro[M];
page=page1;
inte=page[0].time,i=0;
while（i{
if（ei++;
}
for（i=0;ireturn-1;
}
intCount（Pro*page1,inti,intt,Prop[L]）//记录当前内存块中页面离下次使用间隔长度
{
Pro*page=newPro[M];
page=page1;
intcount=0;
for（intj=i;j{
if（page[t].num==p[j].num）break;//当前页面再次被访问时循环结束
elsecount++;//否则count+1
}
returncount;//返回count的值
}
intmain（）
{
intc;
intm=0,t=0;
floatn=0;
Prop[L];
m=Input（m,p）;//调用input函数，返回m值
cout<<"请输入分配的物理块m（2～6）:
";
cout<do{
cin>>M;
if（M>6||M<2）
{cout<cout<<"物理块m必须在2～6之间"<cout<<"请重新输入m：
";}
elsebreak;
}while
（1）;
Pro*page=newPro[M];
do{
for（inti=0;i{page[i].num=0;
page[i].time=m-1-i;
}
i=0;
cout<cout<<"1:
FIFO页面置换2:
LRU页面置换"<cout<<"3:
OPT页面置换4:
退出"<cout<<"请选择页面置换算法：
"<cin>>c;
if（c==1）//FIFO页面置换
{
n=0;
cout<<"FIFO算法页面置换情况如下:
"<cout<while（i{
if（Search（p[i].num,page）>=0）//当前页面在内存中
{
cout<cout<<"不缺页"<i++;//i加1
}
else//当前页不在内存中
{
if（t==M）t=0;
else
{
n++;//缺页次数加1
page[t].num=p[i].num;//把当前页面放入内存中
cout<print（page）;//打印当前页面
t++;//下一个内存块
i++;//指向下一个页面
}
}
}
cout<cout<<"缺页次数：
"<"<}
if（c==2）//LRU页面置换
{
n=0;
cout<<"LRU算法页面置换情况如下:
"<cout<while（i{
inta;
t=Search（p[i].num,page）;
if（t>=0）//如果已在内存块中
{page[t].time=0;//把与它相同的内存块的时间置0
for（a=0;aif（a!
=t）page[a].time++;//其它的时间加1
cout<cout<<"不缺页"<}
else//如果不在内存块中
{
n++;//缺页次数加1
t=Max（page）;//返回最近最久未使用的块号赋值给t
page[t].num=p[i].num;//进行替换
page[t].time=0;//替换后时间置为0
cout<print（page）;
for（a=0;aif（a!
=t）page[a].time++;//其它的时间加1
}
i++;
}
cout<cout<<"缺页次数：
"<"<}
if（c==3）//OPT页面置换
{
n=0;
cout<<"OPT算法置换情况如下:
"<cout<while（i{
if（Search（p[i].num,page）>=0）//如果已在内存块中
{
cout<cout<<"不缺页"<i++;
}
else//如果不在内存块中
{
inta=0;
for（t=0;tif（page[t].num==0）a++;//记录空的内存块数
if（a!
=0）//有空内存
{
intq=M;
for（t=0;tif（page[t].num==0&&q>t）q=t;//把空内存块中块号最小的找出来
page[q].num=p[i].num;
n++;
cout<print（page）;
i++;
}
else
{
inttemp=0,s;
for（t=0;tif（temp{
temp=Count（page,i,t,p）;
s=t;}//把找到的块号赋给s
page[s].num=p[i].num;
n++;
cout<print（page）;
i++;
}
}
}
cout<cout<<"缺页次数：
"<"<}
if（c==4）break;
}while（c==1||c==2||c==3）;
return0;
}
五、实验结果
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最佳置换算法运行结果图
4、总结
通过本次实验，我对页面置换算法的了解更加的深刻。
页面置换算法主要有以下置换算法：
OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU（最近最久未使用算法）。
在进程运行过程中，若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运行，系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应将哪个页面调出，需根据一定的算法来确定。
升级会员 