实验三 模拟操作系统的页面置换文档格式.docx
《实验三 模拟操作系统的页面置换文档格式.docx》由会员分享，可在线阅读，更多相关《实验三 模拟操作系统的页面置换文档格式.docx（26页珍藏版）》请在冰点文库上搜索。
B：
25%的指令是均匀分布在前地址部分
C：
25%的指令是均匀分布在后地址部分
具体的实施方法是：
在[0，319]的指令地址之间随机选取一起点m
顺序执行一条指令，即执行地址为m+1的指令
在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m'
D：
顺序执行一条指令，其地址为m'
+1
E：
在后地址[m'
+2，319]中随机选取一条指令并执行
F：
重复步骤A-E，直到320次指令
（2）将指令序列变换为页地址流
设：
页面大小为1K；
用户内存容量4页到32页；
用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的
存放方式为：
第0条-第9条指令为第0页（对应虚存地址为[0，9]）
第10条-第19条指令为第1页（对应虚存地址为[10，19]）
……
第310条-第319条指令为第31页（对应虚存地址为[310，319]）
按以上方式，用户指令可组成32页。
4、页面大小的取值范围为1K，2K，4K，8K，16K。
按照页面大小将指令地址转化为页号。
对于相邻相同的页号，合并为一个。
5、分配给程序的内存块数取值范围为1块，2块，直到程序的页面数。
6、分别采用OPT、FIFO和LRU算法对页号序列进行调度，计算出对应的缺页中断率。
7、打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。
8、分析页面大小和分配给程序的内存块数对缺页中断率的影响。
分析不同
的页面置换算法的调度性能。
二、中文摘要
这次实验是模拟操作系统的页面置换，分别用先进先出算FIFO、最近最久未使用算法LRU和最佳淘汰算法OPT等三种置换算法来管理管理内存块，并打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。
最后对不同算法的调度性能。
三、关键词
页面置换FIFOLRUOPT
四、前言
本实验的目的及要求
1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。
2、掌握用随机数生成满足一定条件的指令地址流的方法。
3、掌握页面置换的模拟方法。
五、实验设计
（一）、需求分析
1、用一种熟悉的语言，如C、PASCAL或C++等，编制程序。
2、分别采用OPT、FIFO和LRU算法对页号序列进行调度。
（二）、设计流程
1、根据实验目标，明确实验的具体任务；
2、编写程序实现页面置换；
3、运行程序，调试；
4、记录并分析实验结果。
（二）、关键技术
根据实验要求，使得50%的指令地址是顺序执行，25%向前跳，25%向后跳。
可采取下列方法：
开一个数组address[]来记录指令地址，另一个数组pagenum[]记录指令地址转换后所在的页，这样就得到原始程序的页面访问序列。
然后将相邻相同的页号合并。
（三）详细设计
1、设计算法流程图
2、数据结构
//程序类，指明程序地址范围和指令数
classProgram
{
public:
intAddressSize;
//（0~AddressSize）
intStructureNum;
//指令数
Program（intm,inti）
{
AddressSize=m;
StructureNum=i;
}
};
//内存块节点类
classPhysicsPageNode
{
inthave;
//是否有页面占领该内存块，-1代表没有，1代表有
intPage_Num;
//第几页占领该内存块
intElapsed_Time;
//内存块的存在时间
PhysicsPageNode*next;
PhysicsPageNode（）
have=-1;
Elapsed_Time=0;
//刚生成时内存块的存在时间为0
next=NULL;
//模拟操作系统的页面置换类
classPageReplacement
private:
int*address;
//存储所有指令的地址
int*pagenum;
//存储所有指令地址所在的页
floatinstr_sum;
intpagesize;
//页面大小（字节）
intmem_sum;
//程序获得的内存块数
voidtransform（Programp）;
//分析程序p，得到指令页面序列,初始化有关成员
PhysicsPageNode*getphysage（PhysicsPageNode*pp,intpn）;
//检查指定页是否已在内存块中
PhysicsPageNode*getfreepage（PhysicsPageNode*pp）;
//检查是否有空的内存块
PhysicsPageNode*getlongelapsed（PhysicsPageNode*pp）;
//获得最长时间没访问的内存块
voidFIFO（）;
//先进先出算法
voidLRU（）;
//最近最久未使用算法
voidOPT（）;
//最佳淘汰算法
六、实验实现
（一）、实验主要硬件软件环境
32位PC机，VC++6.0
（二）、主要功能模块分析
1、获得页号序列模块
分析程序指令，获得页面序列。
Dn为地址，D0=10000；
Dn的地址获取方法：
循环随机一个数a[1,1024];
落在1-512，Dn=D（n-1）+1，513-768，Dn为1~D（n-1）的随机数。
如果a落在769-1024，Dn为D（n-1）~到所分析程序地址大小（32767）。
然后根据页面大小，将各指令地址化为页面号。
最后将相邻相同的页号合并。
/*
分析程序，
功能：
得到指令页面序列。
入口参数：
一个程序类，指明程序地址范围和指令数。
*/
voidPageReplacement:
:
transform（Programp）
Sleep（10）;
srand（time（0））;
inta,q,r;
//初始化
instr_sum=p.StructureNum;
address=newint[instr_sum];
pagenum=newint[instr_sum];
cout<
<
"
原程序页面链:
endl;
address[0]=10000;
//指令起始地址
pagenum[0]=address[0]/pagesize;
//指令地址所在的页
pagenum[0]<
ends;
for（inti=1;
i<
instr_sum;
i++）
a=1+rand（）%1024;
if（a<
=512）//顺序执行
address[i]=address[i-1]+1;
elseif（a<
=768）//向前跳
address[i]=1+rand（）%（address[i-1]）;
=1024）//向后跳
address[i]=address[i-1]+rand（）%（p.AddressSize-address[i-1]）;
//求得指令所在的页
q=address[i]/pagesize;
r=address[i]%pagesize;
if（r）
pagenum[i]=q;
else
pagenum[i]=q-1;
cout<
pagenum[i]<
//输出指令所在的页面
endl<
//将相邻相同的页号合并
int*newpagenum=newint[instr_sum];
newpagenum[0]=pagenum[0];
将相邻相同的页号合并为一个后的页面链"
intj=0;
for（i=1;
i++）
if（newpagenum[j]!
=pagenum[i]）
{
j++;
newpagenum[j]=pagenum[i];
}
instr_sum=j+1;
//新的页面访问串的访问数（j为下标，所以加一）
新的页面访问串的访问数="
instr_sum<
for（i=0;
pagenum[i]=newpagenum[i];
}
2、FIFO模块
先进先出算法：
设置缺页中断次数breaktimes，当中断发生时，+1.获取可用内存块数，根据内存块数，申请对应长度的内存块链。
然后进行调度。
内存块内有一项Elapsed_Time作为存在时间，每调用一次，所有内存块得存在时间++。
刚被调入时间为1.当要淘汰时，比较在内存块中的各存在时间，把存在时间最大的换掉。
//内存页的存在时间，为存在时间。
FIFO（）
floatbreaktimes=0;
inti,pn;
//生成内存页空间
PhysicsPageNode*head=newPhysicsPageNode（）;
PhysicsPageNode*p=head,*ppn=NULL;
mem_sum;
i++）//mem_sum:
程序获得的内存块数
PhysicsPageNode*np=newPhysicsPageNode（）;
p->
next=np;
p=np;
pn=pagenum[i];
//需要载入的页号（这里还没简化）
ppn=getphysage（head,pn）;
//是否存在内存页
if（ppn==NULL）//载入的页不在内存页中
//缺页中断次数+1
breaktimes++;
//获取空闲页面
ppn=getfreepage（head）;
if（ppn!
=NULL）//获取成功
{
ppn->
Page_Num=pn;
Elapsed_Time=1;
}
else//获取空闲页失败.置换存在时间最大的页面
{
ppn=getlongelapsed（head）;
else//载入的页在内存页中。
{
//什么也不发生
//将在内存中的页存在时间+1
PhysicsPageNode*copp=head;
while（copp!
=NULL）
copp->
Elapsed_Time++;
copp=copp->
next;
//输出算法，页面大小，缺页中断率等。
页面大小="
pagesize<
内存块数="
mem_sum<
FIFO缺页中断率="
;
cout.precision
（2）;
//输出小数点后两位
breaktimes/instr_sum<
3、LRU模块
最近最久未使用页面置换算法（LRU）
LRU在固定时间内将各个内存页的存在时间复位，增加计数器counter，每到30将所有内存页存在时间复位。
并且每使用一次内存页，将是把存在时间减3个单位，这样存在时间最大的就是最久未使用的。
LRU（）
PhysicsPageNode*head=newPhysicsPageNode（）;
PhysicsPageNode*p=head,*ppn;
intcounter=0;
//计数器
counter++;
//增加计数器counter，每到30将所有内存页存在时间复位。
if（counter>
30）
counter=0;
//计数器归零
PhysicsPageNode*q=head;
//内存页存在时间复位
while（q!
q->
q=q->
//需要载入的页号
if（ppn==NULL）//载入的页不在内存页中
else//获取空闲页失败
//存在时间最大的为最久未使用。
因为每使用一次是减3个单位的存在时间。
{
ppn->
Elapsed_Time=ppn->
Elapsed_Time-3;
LRU缺页中断率="
4、OPT模块
最优淘汰算法OPT
当页面存在时，存在时间参数不变化。
当要淘汰一个页时，预读未来50页，并用内存页的存在时间计数。
然后淘汰存在时间最短的。
计数方法，未来出现1次，将存在时间减3个单位。
到时候存在时间值最大的将被淘汰。
OPT（）
//缺页中断次数+1
breaktimes=breaktimes+1;
//在这里增加预读未来50个页面计数。
intnextpage=i+1;
//从下一页开始算。
intendread=i+50;
intnextpagenum;
PhysicsPageNode*temp;
temp=head;
//先复位。
while（temp!
{
temp->
temp=temp->
}
//下面预读未来页面并计数
for（;
（（nextpage<
endread）&
&
（nextpage<
=instr_sum））;
nextpage++）
nextpagenum=pagenum[nextpage];
temp=getphysage（head,nextpagenum）;
if（temp!
temp->
Elapsed_Time=temp->
//在OPT中无需变化。
OPT缺页中断率="
5、辅助模块
//检查指定页是否在已内存块中
PhysicsPageNode*PageReplacement:
getphysage（PhysicsPageNode*pp,intpn）
PhysicsPageNode*tmp=pp;
while（tmp!
if（tmp->
Page_Num==pn）
returntmp;
//找到对应的页并返回
else
tmp=tmp->
returnNULL;
//没找到，返回NULL
//检查是否有空的内存块
getfreepage（PhysicsPageNode*pp）
have==-1）
tmp->
have=1;
//找到空的内存块并返回
//查找存在时间最长的内存块并返回
getlongelapsed（PhysicsPageNode*pp）
PhysicsPageNode*tmp=pp,*t=pp;
Elapsed_Time>
t->
Elapsed_Time）
t=tmp;
tmp=tmp->
returnt;
七、结果及结果分析
（一）测试数据
1、程序中地址范围
0~32767
2、页面大小（k）
1K，2K，4K，8K，16K
3、分配给程序的内存块数
1块，2块……直到程序的页面数。
4、算法
OPT、FIFO和LRU
（二）测试结果记录
分析以上的实验结果可知：
1、一般情况下，当页面大小一定时，分配给程序的内存块数越多，缺页中断率的越小；
当分配给程序的内存块数一定时，页面大小越大，缺页中
升级会员 