山东大学操作系统实验七内存页面置换算法问题.docx
《山东大学操作系统实验七内存页面置换算法问题.docx》由会员分享，可在线阅读，更多相关《山东大学操作系统实验七内存页面置换算法问题.docx（17页珍藏版）》请在冰点文库上搜索。
山东大学操作系统实验七内存页面置换算法问题
计算机科学与技术学院操作系统实验报告
实验题目：
内存页面置换算法问题
假请在以上示例实验程序中补充“增强二次机会”等置换算法的模拟程序。
输入不同的内存页面引用串和实存帧数,观察并分析其页面置换效果和性能,并将其与LRU和FIFO算法进行比较。
改进以上示例实验程序,使之能够随机的产生内存页面引用串,以便能动态的观测各种置换算法的性能。
实验目的：
加深对于存储管理的了解,掌握虚拟存储器的实现原理;观察和了解重要的页面
置换算法和置换过程。
练习模拟算法的编程技巧,锻炼分析试验数据的能力。
硬件环境：
Inter（R）Core（TM）i5-3210MCPU@2.50GHz内存：
4GB硬盘：
500G
软件环境：
XUbuntu－Linux操作系统
Gnome桌面2.18.3
BASH_VERSION='3.2.33
（1）-release
gccversion4.1.2
gedit2.18.2
OpenOffice2.3
实验步骤：
1、问题分析:
示例实验程序中模拟两种置换算法:
LRU算法和FIFO算法
能对两种算法给定任意序列不同的页面引用串和任意帧实内存块数的组合测试,显示页置换的过程。
能统计和报告不同置换算法情况下依次淘汰的页号、缺页次数（页错误数）和缺页率。
比较两种置换算法在给定条件下的优劣。
为了能方便的扩充页面置换算法,更好的描述置换过程,示例实验程序采用了C++语言用Replace类描述了置换算法及其属性。
2、算法设计说明如下：
1.二次机会算法描述（Clock）:
将帧表设置为循环表,由RefBit数组记录某一页是否被引用（0表示未被引用,1表示被引用）。
当访问一页时,首先从帧表中检查此页是否在实存,若在将其引用位设置为1;若不在,在循环帧表中循序查找,若某页引用位为1,则将其设置为0，然后继续查找；若某页引用位为0，将其替换。
若查找一圈，没有替换页（所有引用位均为1），则将全部引用位设置为0。
2.增强的二次机会算法（Eclock）：
将帧表设置为循环表，由RefBit数组记录某页是否被引用,ModBit数组记录某页是否被修改。
当访问一页时,首先从帧表中检查此页是否在实存,若在将引用位设置为1,并根据输入修改修改位;若不在,第一次在帧表中查找是否有属性为（0,0）的页,若有则将其替换,并修改引用位和修改位;若没有这种页,第二次查找是否有属性为（0,1）或（1,0）的页,若有将其替换,并修改引用位和修改位;若没有这种页,将所有引用位置为0,重复第二次查找操作。
3.最少使用页替换算法（Lfu）:
设置accout数组记录帧表中每一页被引用次数。
当访问一页时,首先从帧表中检查此页是否在实存,若在将其计数加1;若不在,查找计数最小的页将其替换,并将当前页的计数置为1;
4.最多使用页替换算法（Mfu）:
设置accout数组记录帧表中每一页被引用次数。
当访问一页时,首先从帧表中检查此页是否在实存,若在将其计数加1;若不在,查找计数最大的页将其替换,并将当前页的计数置为1;
3、开发调试过程：
在shell命令行下运行makevmrp
g++-w-g-cvmrp.cc
g++vmrp.o-ovmrp
$./vmrp
Pleaseinputpagenumbers:
12
Pleaseinputreferencepagestring:
123412512345
Pleaseinputpageframes:
3
运行截图如下：
附件：
vmrp.h
#include
#include
#include
usingnamespacestd;
classReplace{
public:
Replace（）;
~Replace（）;
voidInitSpace（char*MethodName）;//初始化页号记录
voidReport（void）;//报告算法执行情况
voidFifo（void）;//先进先出算法
voidLru（void）;//最近最旧未用算法
voidClock（void）;//时钟（二次机会）置换算法
voidEclock（void）;//增强二次机会置换算法
voidLfu（void）;//最不经常使用置换算法
voidMfu（void）;//最经常使用置换算法
private:
int*ReferencePage;//存放要访问到的页号
int*EliminatePage;//存放淘汰页号
int*PageFrames;//存放当前正在实存中的页号
intPageNumber;//访问页数
intFrameNumber;//实存帧数
intFaultNumber;//失败页数
int*Referencebit;
int*count;
int*Modifybit;
};
//vmrp.c
#include"vmrp.h"
Replace:
:
Replace（）{
inti;
cout<<"Pleaseinputpagenumbers:
";
cin>>PageNumber;
ReferencePage=newint[sizeof（int）*PageNumber];
EliminatePage=newint[sizeof（int）*PageNumber];
cout<<"Pleaseinputreferencepagestring:
";
for（i=0;icin>>ReferencePage[i];
cout<<"Pleaseinputpageframes:
";
cin>>FrameNumber;
PageFrames=newint[sizeof（int）*FrameNumber];
Referencebit=newint[sizeof（int）*FrameNumber];
count=newint[sizeof（int）*FrameNumber];
Modifybit=newint[sizeof（int）*FrameNumber];
}
Replace:
:
~Replace（）{
}
voidReplace:
:
InitSpace（char*MethodName）
{
inti;
cout<FaultNumber=0;
//引用还未开始,-1表示无引用页
for（i=0;iEliminatePage[i]=-1;
for（i=0;iPageFrames[i]=-1;
Referencebit[i]=0;
count[i]=0;
Modifybit[i]=0;
}
}
//分析统计选择的算法对于当前输入的页面走向的性能
voidReplace:
:
Report（void）{
//报告淘汰页顺序
cout<";
for（inti=0;EliminatePage[i]!
=-1;i++）cout<//报告缺页数和缺页率
cout<cout<cout<<"Rateofpagefaults="<<100*（float）FaultNumber/（float）PageNumber<<"%"<}
//最近最旧未用置换算法
voidReplace:
:
Lru（void）
{
inti,j,k,l,next;
InitSpace（"LRU"）;
//循环装入引用页
for（k=0,l=0;knext=ReferencePage[k];
//检测引用页当前是否已在实存
for（i=0;iif（next==PageFrames[i]）{
//引用页已在实存将其调整到页记录栈顶
next=PageFrames[i];
for（j=i;j>0;j--）PageFrames[j]=PageFrames[j-1];
PageFrames[0]=next;
break;
}
}
if（PageFrames[0]==next）{
//如果引用页已放栈顶，则为不缺页，报告当前内存页号
for（j=0;jif（PageFrames[j]>=0）cout<cout<continue;//继续装入下一页
}
else
//如果引用页还未放栈顶，则为缺页，缺页数加1
FaultNumber++;
//栈底页号记入淘汰页数组中
EliminatePage[l]=PageFrames[FrameNumber-1];
//向下压栈
for（j=FrameNumber-1;j>0;j--）PageFrames[j]=PageFrames[j-1];
PageFrames[0]=next;//引用页放栈顶
//报告当前实存中页号
for（j=0;jif（PageFrames[j]>=0）cout<//报告当前淘汰的页号
if（EliminatePage[l]>=0）
cout<<"->"<else
cout<}
//分析统计选择的算法对于当前引用的页面走向的性能
Report（）;
}
//先进先出置换算法
voidReplace:
:
Fifo（void）{
inti,j,k,l,next;
InitSpace（"FIFO"）;
for（k=0,j=l=0;knext=ReferencePage[k];
for（i=0;iif（ifor（i=0;icout<continue;
}
FaultNumber++;
EliminatePage[l]=PageFrames[j];
PageFrames[j]=next;
j=（j+1）%FrameNumber;
for（i=0;iif（PageFrames[i]>=0）cout<if（EliminatePage[l]>=0）
cout<<"->"<else
cout<}
Report（）;
}
voidReplace:
:
Clock（void）
{
intj,i,k,l,next;
InitSpace（"Clock"）;
for（k=0,j=l=0;knext=ReferencePage[k];
for（i=0;iif（next==PageFrames[i]）{
Referencebit[i]=1;
break;
}
if（ifor（i=0;icout<continue;
}
if（Referencebit[j]==1）{
Referencebit[j]==0;
}
EliminatePage[l]=PageFrames[j];
PageFrames[j]=next;
Referencebit[j]=1;
FaultNumber++;
j=（j+1）%FrameNumber;
for（i=0;iif（PageFrames[i]>=0）cout<if（EliminatePage[l]>=0）
cout<<"->"<else
cout<}
Report（）;
}
voidReplace:
:
Eclock（void）
{
intj,i,k,l,next;
InitSpace（"EClock"）;
for（k=0,j=l=0;knext=ReferencePage[k];
for（i=0;iif（next==PageFrames[i]）{
Referencebit[i]=1;
count[i]++;
if（count[i]%2==0）
Modifybit[i]=0;
else
Modifybit[i]=1;
break;
}
if（ifor（i=0;icout<continue;
}
if（Referencebit[j]==1）{
Referencebit[j]==0;
}
if（Modifybit[j]==1）{
Modifybit[j]=0;
}
intmin=10*Referencebit[j]+Modifybit[j];
intindex=j;
for（i=0;iif（10*Referencebit[i]+Modifybit[i]min=10*Referencebit[i]+Modifybit[i];
index=i;
}
}
EliminatePage[l]=PageFrames[index];
PageFrames[index]=next;
Referencebit[index]=0;
Modifybit[index]=1;
count[index]=0;
FaultNumber++;
j=（j+1）%FrameNumber;
for（i=0;iif（PageFrames[i]>=0）cout<if（EliminatePage[l]>=0）
cout<<"->"<else
cout<}
Report（）;
}
voidReplace:
:
Lfu（void）
{
intj,i,k,l,next;
InitSpace（"Lfu"）;
for（k=0,j=l=0;knext=ReferencePage[k];
for（i=0;iif（next==PageFrames[i]）{
count[i]++;
break;
}
if（ifor（i=0;icout<continue;
}
FaultNumber++;
intmin=count[0];
intindex=0;
for（i=0;iif（count[i]min=count[i];
index=i;
}
}
EliminatePage[l]=PageFrames[index];
PageFrames[index]=next;
count[index]=1;
for（i=0;iif（PageFrames[i]>=0）cout<if（EliminatePage[l]>=0）
cout<<"->"<else
cout<}
Report（）;
}
voidReplace:
:
Mfu（void）
{
intj,i,k,l,next;
InitSpace（"Mfu"）;
for（i=0;icount[i]=1;
for（k=0,j=l=0;knext=ReferencePage[k];
for（i=0;iif（next==PageFrames[i]）{
count[i]++;
break;
}
if（ifor（i=0;icout<continue;
}
FaultNumber++;
intmax=count[0];
intindex=0;
for（i=0;iif（count[i]>max）{
max=count[i];
index=i;
}
}
EliminatePage[l]=PageFrames[index];
PageFrames[index]=next;
count[index]=0;
for（i=0;iif（PageFrames[i]>=0）cout<if（EliminatePage[l]>=0）
cout<<"->"<else
cout<}
Report（）;
}
intmain（intargc,char*argv[]）{
Replace*vmpr=newReplace（）;
vmpr->Lru（）;
vmpr->Fifo（）;
vmpr->Clock（）;
vmpr->Eclock（）;
vmpr->Lfu（）;
vmpr->Mfu（）;
return0;
}
升级会员 