实验四操作系统存储管理实验报告.docx
《实验四操作系统存储管理实验报告.docx》由会员分享,可在线阅读,更多相关《实验四操作系统存储管理实验报告.docx(21页珍藏版)》请在冰点文库上搜索。
实验四操作系统存储管理实验报告
实验四操作系统存储管理实验报告
一、实验目的
存储管理的主要功能之一是合理地分配空间。
请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。
二、实验内容
(1)
通过计算不同算法的命中率比较算法的优劣。
同时也考虑了用户内存容量对命中率的影响。
页面失效次数为每次访问相应指令时,该指令所对应的页不在内存中的次数。
在本实验中,假定页面大小为1k,用户虚存容量为32k,用户内存容量为4页到32页。
(2)produce_addstream通过随机数产生一个指令序列,共320条指令。
A、指令的地址按下述原则生成:
1)50%的指令是顺序执行的
2)25%的指令是均匀分布在前地址部分
3)25%的指令是均匀分布在后地址部分
B、具体的实施方法是:
1)在[0,319]的指令地址之间随机选取一起点m;
2)顺序执行一条指令,即执行地址为m+1的指令;
3)在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m’;
4)顺序执行一条指令,地址为m’+1的指令
5)在后地址[m’+2,319]中随机选取一条指令并执行;
6)重复上述步骤1)~5),直到执行320次指令
C、将指令序列变换称为页地址流
在用户虚存中,按每k存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
第0条~第9条指令为第0页(对应虚存地址为[0,9]);
第10条~第19条指令为第1页(对应虚存地址为[10,19]);
。
。
。
。
。
。
第310条~第319条指令为第31页(对应虚存地址为[310,319]);
按以上方式,用户指令可组成32页。
(3)计算并输出下属算法在不同内存容量下的命中率。
1)先进先出的算法(FIFO);
2)最近最少使用算法(LRU);
3)最佳淘汰算法(OPT);
4)最少访问页面算法(LFR);
其中3)和4)为选择内容
三、系统框图
五运行结果
首先打印出产生的指令信息,第一列为指令序列号,第二列为指令地址,第三列为指令所在的虚页号
选择FIFO调度算法,并且内存从3也开始逐渐增加到32页,打印出缺页次数缺页率,命中率
选择LRU调度算法,并且内存从3也开始逐渐增加到32页,打印出缺页次数缺页率,命中率
选择OPT调度算法,并且内存从3也开始逐渐增加到32页,打印出缺页次数缺页率,命中率
六实验程序
产生指令流文件produce_addstream.h
#ifndefPRODUCE_ADDSTREAM_H
#definePRODUCE_ADDSTREAM_H
#include
#include
#include
#include
#include
usingnamespacestd;
#definerandom(x)(rand()%x)
#defineMAX_LENGTH320
structproduce
{
intnum;//指令序号
intzhiling;//指令地址
intvirtualpage;//指令虚页号
produce*next;
};
structproduce*creatlist();
voidinsert(structproduce*first,structproduce*s);//插入一个节点(尾插法)
voidprint(structproduce*first);//打印函数
intmax(vector>,int);
structproduce*creatlist()
{
srand((int)time(0));
structproduce*first=newproduce;
first->next=NULL;
intm=0,m1=0;
/*
intyanzheng[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
for(inti=0;i<(MAX_LENGTH/4);i++)
{
structproduce*s0;
s0=newproduce;
s0->num=i*4+0;
s0->zhiling=yanzheng[i*4+0];
s0->virtualpage=s0->zhiling;
insert(first,s0);
structproduce*s1;
s1=newproduce;
s1->num=i*4+1;
s1->zhiling=yanzheng[i*4+1];
s1->virtualpage=s1->zhiling;
insert(first,s1);
structproduce*s2;
s2=newproduce;
s2->num=i*4+2;
s2->zhiling=yanzheng[i*4+2];
s2->virtualpage=s2->zhiling;
insert(first,s2);
structproduce*s3;
s3=newproduce;
s3->num=i*4+3;
s3->zhiling=yanzheng[i*4+3];
s3->virtualpage=s3->zhiling;
insert(first,s3);
}
//*/
//*
for(inti=0;i<(MAX_LENGTH/4);i++)
{
structproduce*s0;
s0=newproduce;
m=random(MAX_LENGTH);
s0->num=i*4+0;
s0->zhiling=m+1;
s0->virtualpage=s0->zhiling/10;
insert(first,s0);
m1=random(m+1);
structproduce*s1;
s1=newproduce;
s1->num=i*4+1;
s1->zhiling=m1;
s1->virtualpage=s1->zhiling/10;
insert(first,s1);
structproduce*s2;
s2=newproduce;
s2->num=i*4+2;
s2->zhiling=m1+1;
s2->virtualpage=s2->zhiling/10;
insert(first,s2);
structproduce*s3;
s3=newproduce;
s3->num=i*4+3;
s3->zhiling=random(MAX_LENGTH-m1-2)+m1+2;
s3->virtualpage=s3->zhiling/10;
insert(first,s3);
}//*/
returnfirst;
}
voidinsert(structproduce*first,structproduce*s)
{
structproduce*r=first;
structproduce*p;
while(r){p=r;r=r->next;}
p->next=s;p=s;
p->next=NULL;
}
voidprint(structproduce*first)//打印函数
{
structproduce*p;
p=first->next;
cout<<"随机产生的指令的信息如下"<cout<<"指令序号"<<"指令地址"<<"指令虚页号"<while(p)
{
cout<num<<'\t'<zhiling<virtualpage<p=p->next;
}
}
intmax(vector>page,intMaxpage)
{
inta=0,position=0;
for(inti=0;i{
if(page[i][1]>a)
{
a=page[i][1];
position=i;
}
}
returnposition;
}
#endif
先来先出调度算法:
fifo.h
#ifndefFIFO_H
#defineFIFO_H
voidfifo(structproduce*first,intMaxpage)
{
vectorpage(Maxpage);//
for(inti=0;iintrear=0;//定义一个变量,指向要被替换的位置
intpages;//定义变量保存当前指令的所在的地址
intcount1=0;//
intcount2=0;//缺页次数
intfind=1;
structproduce*p=first->next;
while(p)
{
pages=p->virtualpage;
for(inti=0;i{
if(page[i]==-1||count1{
page[i]=pages;
count1++;
count2++;
find=1;
break;
}
elseif(page[i]==pages)
{
find=1;
break;
}
find=0;
}
if(find==0)
{
page[rear]=pages;
rear++;
rear=rear%Maxpage;
count2++;
}
p=p->next;
}
cout<<"FIFO调度算法缺页次数缺页率命中率"<cout<}
#endifFIFO_H
LRU调度算法lru.h
#ifndefLRU_H
#defineLRU_H
#include
usingnamespacestd;
//intmax(vector>,int);
voidlru(structproduce*first,intMaxpage)
{
structproduce*p=first->next;
vector>page2(Maxpage,vector
(2));
intcount1=0;//定义内存已经被占用的页数
intcount2=0;//定义记录缺页次数
intequal=0;//定义判断如果当前页数与比较的页数,如果相等则为1,否则为0
intplace=0;//定义要替换的位置
for(inti=0;i{
page2[i][0]=-1;page2[i][1]=0;
}
while(p)
{
if(count1{
for(inti=0;i{
page2[i][1]=page2[i][1]+1;
if(page2[i][0]==-1)
{
page2[i][0]=p->virtualpage;
count2++;
break;
}
elseif(page2[i][0]==p->virtualpage)
{
page2[i][1]=1;
}
}
count1++;
}
else
{
for(inti=0;i{
page2[i][1]+=1;
if(page2[i][0]==p->virtualpage)
{equal=1;place=i;break;}
}
if(equal==1)
{
page2[place][1]=1;
equal=0;
}
else
{
place=max(page2,Maxpage);
page2[place][1]=1;
page2[place][0]=p->virtualpage;
count2++;
}
}
p=p->next;
}
cout<<"LRU调度算法缺页次数缺页率命中率"<cout<}
#endifLRU_H
OPT调度算法opt.h
#ifndefOPT_H
#defineOPT_H
#include
usingnamespacestd;
intsearch(structproduce*place,intposition);
voidopt(structproduce*first,intMaxpage)
{
structproduce*p=first->next;
vector>page3(Maxpage,vector
(2));
intcount1=0;//定义内存已被使用的页数
intcount2=0;//定义缺页次数
intcurrent=0;//定义当前工作位置
intequal=0;//定义判断如果当前页数与比较的页数,如果相等则为1,否则为0
intplace=0;//定义要替换的位置
for(inti=0;i{
page3[i][0]=-1;page3[i][1]=0;
}
while(p)
{
//cout<<1111<if(count1{
for(inti=0;i{
if(page3[i][0]==-1)
{
page3[i][0]=p->virtualpage;
page3[i][1]=search(p,current);
count2++;
break;
}
elseif(page3[i][0]==p->virtualpage)
{
page3[i][1]=search(p,current);
}
}
count1++;
}
else
{
for(inti=0;i{
if(page3[i][0]==p->virtualpage)
{equal=1;place=i;break;}
}
if(equal==1)
{
page3[place][1]=search(p,current);
equal=0;
}
else
{
place=max(page3,Maxpage);
page3[place][1]=search(p,current);
page3[place][0]=p->virtualpage;
count2+=1;
}
}
p=p->next;
current+=1;
}
cout<<"OPT调度算法缺页次数缺页率命中率"<cout<}
intsearch(structproduce*place,intposition)
{
structproduce*p=place->next;
intcurrent=place->virtualpage;
intposition1=position+1;
while(p)
{
if(current==p->virtualpage)
{
returnposition1;
}
position1++;
p=p->next;
}
returnposition1;
}
#endif
主函数控制台ccglmain.cpp
#include
#include"produce_addstream.h"
#include"fifo.h"
#include"lru.h"
#include"opt.h"
voidmain()
{
intS;//定义变量记录用户选择
charagain;//定义变量用户选择继续还是退出
cout<<"开始产生内存指令"<structproduce*first=creatlist();//产生随机指令
cout<<"打印产生的指令信息"<print(first);//打印产生的指令信息
while
(1)
{
intMaxpage=3;//定义内存最大页面数
cout<<"输入你的选择"<cout<<"1:
FIFO(先进先出)调度算法\n"<<"2:
LRU(最近最少使用算法)\n"<<"3:
OPT(最佳淘汰算法)\n"<<"4:
清屏"<cin>>S;
while(S>4||S<1)
{
cout<<"输入错误重新输入"<cin>>S;
}
if(S!
=4)
{
while(Maxpage<=32)
{
switch(S)
{
case1:
fifo(first,Maxpage);break;
case2:
lru(first,Maxpage);break;
case3:
opt(first,Maxpage);break;
default:
break;
}
Maxpage++;
}
cout<<"是否继续调用其他算法?
是请按y/Y,否请按其它键"<cin>>again;
if(again=='y'||again=='Y')
{
continue;
}
elsebreak;
}
elsesystem("cls");
}
}