操作系统存储器管理.doc
《操作系统存储器管理.doc》由会员分享,可在线阅读,更多相关《操作系统存储器管理.doc(7页珍藏版)》请在冰点文库上搜索。
太原工业学院计算机工程系
实验报告
课程名称
操作系统
班级
1120542
实验日期
2013-12-06
姓名
聂建建
学号
06
实验成绩
实验名称
存储器管理
实验
目的
以及
要求
编程模拟实现存储器页面置换的常用算法,调试分析相关存储器管理程序,加深对存储器页面置换常用算法的理解和实现技巧
实
验
环
境
MicrosoftVisualStudio
实
验
内
容
1、自定义存储器管理有关的数据结构;
2、依据最佳置换算法(OPTIMAL)、先进先出置换算法(FIFO)、最近最久未使用算法(LRU)原理,编写对应函数,模拟系统的存储器页面置换功能;
3、为了更好地模拟和评价算法的性能,允许用户自行指定可用页块数并输入需访问的页面号序列;
4、统计以上算法实际需要的总页面数、缺页中断次数以及它们的缺页率;
5、比较/分析以上算法的置换性能,并作出自己的评价。
算
法
描
述
及
实
验
步
骤
最佳置换算法(OPTIMAL)
main()
先进先出置换算法(FIFO)
最近最久未使用算法(LRU)
在进程运行过程中,若其所访问的页面不存在内存而需要不他们调入内存,但内存已无空闲时,为了保证该进程能够正常运行,系统必须从内存中调出一页程序或数据送磁盘的对换区中。
但应掉出哪个页面需根据一定的算法来确定,算法的好坏,直接影响到系统的性能。
一个好的页面置换法,应该有较低的页面更换频率。
假设分给一个作业的物理块数为3,页面数为20个。
页面号为(20个):
1,2,5,6,0,3,6,5,3,6,5,6,0,4,2,7,0,4,3,5
1、最佳置换算法(OPTIMAL)的思路:
最佳置换算法:
intpagepro:
:
OPT()
其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面,采用最佳置换算法,通常可以保证获得最低的缺页率。
2、先进先出置换算法(FIFO)的思路:
先进先出算法:
intpagepro:
:
FIFO()
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
该算法只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。
3、最近最久未使用算法(LRU)的思路:
最近最久未使用算法:
intpagepro:
:
LRU()
最近最久未使用的页面置换算法,是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此最近最久未使用置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时,选择现有页面中其t值最大的,及最近最久未使用的页面予以淘汰。
调
试
过
程
及
实
验
结
果
最近最久未使用算法(LRU):
先进先出置换算法(FIFO):
最佳置换算法(OPTIMAL):
总
结
这个程序的主要思想主题就是实现换页、怎样输出淘汰的序列、计算缺页数和缺页率。
在程序中主要就是将在访问串中将来再也不出现的或现在离当前最远的位置上出现的页淘汰掉。
当距离相等的时候就比较使用的次数,淘汰使用次数较少的那页。
该过程共有三个函数即实现最佳置换算法(OPTIMAL)、FIFO的函数和实现LRU的函数,当主函数调用任意其中函数时来实现其算法。
通过这次试验,能够熟练的掌握一些关于分配内存管理的一些算法。
在调试过程中也出现的大多是关于内存分配和数组地址越界的问题,比如关于循环时各个事故的递增,还有就是显示给各个数组的内容等问题。
就是因为这些问题,多次造成了淘汰序列出错。
在以后的实验中应该多加注意。
附
录
#include
usingnamespacestd;
#defineBsize3//进程页块数
#definePsize20//访问序列长度
structPage
{
intnum;//页面号
inttimer;//计时
};
classpagepro
{
public:
pagepro(intpstr[]);
intfindspace();//若内存块中有空,返回该位置
intfindhave(intp);//若内存块中已有页,返回内存块中位置
intfindreplace();//找到替换页的位置(forLRU)
intfindreplace(inti);//找到替换页的位置(forOPT)
voidclear();//清理内存块
voiddisplay();//打印内存块信息
intLRU();//最近最久未使用算法
intFIFO();//先进先出算法
intOPT();//最佳置换算法
Page*block;//内存块
Page*page;//页面号串
};
pagepro:
:
pagepro(intpstr[])
{
inti=0;
block=newPage[Bsize];
for(i=0;i {
block[i].num=-1;
block[i].timer=0;
}
page=newPage[Psize];
for(i=0;i {
page[i].num=pstr[i];
page[i].timer=0;
}
}
intpagepro:
:
findspace()
{
for(inti=0;i {
if(block[i].num==-1)
returni;
}
return-1;
}
intpagepro:
:
findreplace(inti)
{
intpos[3]={0};
intpostion=0;
for(intj=0;j {
for(intk=i;k {
if(block[j].num==page[k].num)
break;
else
pos[j]++;
}
}
for(j=1;j {
if(pos[j]>pos[postion])
postion=j;
}
returnpostion;
}
intpagepro:
:
findhave(intp)
{
for(inti=0;i {
if(block[i].num==page[p].num)
returni;
}
return-1;
}
voidpagepro:
:
display()
{
for(inti=0;i {
if(block[i].num!
=-1)
cout< }
cout<}
intpagepro:
:
findreplace()
{
intpos=0;
for(inti=1;i {
if(block[i].timer>block[pos].timer)
pos=i;
}
returnpos;
}
voidpagepro:
:
clear()
{
for(inti=0;i {
block[i].num=-1;
block[i].timer=0;
}
}
intpagepro:
:
LRU()
{
inthave,space,pos;
intcount=0;//不缺页计数
for(inti=0;i {
have=findhave(i);
if(have!
=-1)
{
count++;
block[have].timer=-1;
cout<<"pagefindinblock!
"< }
else
{
space=findspace();
if(space!
=-1)
{
block[space]=page[i];
display();
}
else
{
pos=findreplace();
block[pos]=page[i];
display();
}
}
for(inti=0;i block[i].timer++;
}
returncount;
}
intpagepro:
:
FIFO()
{
inthave;
intj=0;//j%3记录替换位置
intcount=0;
for(inti=0;i {
have=findhave(i);
if(have!
=-1)
{
count++;
cout<<"pagefindinblock!
"< }
else
{
block[j%3]=page[i];
j++;
display();
}
}
returncount;
}
intpagepro:
:
OPT()
{
inthave,space;
intcount=0;
for(inti=0;i {
have=findhave(i);
if(have!
=-1)
{
cout<<"pagefindinblock!
"< count++;
}
else
{
space=findspace();
if(space!
=-1)
{
block[space]=page[i];
display();
}
else
{
block[findreplace(i)]=page[i];
display();
}
}
}
returncount;
}
intmain()
{
intpstr[20]={1,2,5,6,0,3,6,5,3,6,5,6,0,4,2,7,0,4,3,5};
//intpstr[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,1,7,0};
pageprop1(pstr);
intc=0,
select=0;
cout<<"************页面置换算法模拟*************"< cout<<"1.LRU"< cout<<"2.FIFO"< cout<<"3.OPT"< cout<<"0.exit"< cout<<"*****************************************"< while
(1)
{
cout<<"pleaseinput:
";
cin>>select;
switch(select)
{
case1:
c=p1.LRU();
cout<<"total:
20\nfind:
"< p1.clear();
break;
case2:
c=p1.FIFO();
cout<<"total:
20\nfind:
"< p1.clear();
break;
case3:
c=p1.OPT();
cout<<"total:
20\nfind:
"< p1.clear();
break;
default:
exit(0);
}
}
return0;
}