虚拟内存页面置换算法实验报告材料.docx
《虚拟内存页面置换算法实验报告材料.docx》由会员分享，可在线阅读，更多相关《虚拟内存页面置换算法实验报告材料.docx（15页珍藏版）》请在冰点文库上搜索。
虚拟内存页面置换算法实验报告材料
虚拟内存页面置换算法
学生姓名:
学生学号:
专业班级:
指导老师：
2013年6月20日
1、实验目的：
通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。
2、问题描述：
假设有n个进程分别在T1,…,Tn时刻到达系统，它们需要的服务时间分别为S1,…,Sn。
分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
3、需求分析
通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。
通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面置换的缺页次数和缺页率，及每次缺页时物理块中存储！
（1）输入的形式
intPageOrder[MaxNumber];//页面序列
intPageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数
（2）输出的形式
doubleLackPageRate//缺页率
缺页个数
每次缺页时物理块中存储
（3）程序所能达到的功能
模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。
假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1,…,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。
测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。
（4）测试数据
页面个数：
20最小物理块数：
3
页面序列：
90120304230321201701
4、概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。
intPageOrder[MaxNumber];//页面序列
intPageCount[MaxNumber]={0};//计算内存内数据离下一次出现的距离
intPageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数
doubleLackPageRate=0;
boolfound=false;
5、详细设计
其它两个的流程一样，只是PageCount[j]>max判断条件中的max所指含义不同，在FIFO中max是指从进入物理块到本次存在最久，在LRU中是指从上一次访问到本次存在最久！
6、调试分析
（1）调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析；
在FIFO和LRU中计算每个页面在物理块中所存在的“时间”时总是出错，后来多次调试语句所处位置和计数方法，终于得出正确结果，并且所有算法都没有输出物理块中发生置换后的物理块中的内容，在老师的提醒下更改程序输出其内容。
（2）算法的性能分析（包括基本操作和其它算法的时间复杂度和空间复杂度的分析）及其改进设想；
OPI：
时间复杂度为O（n^2）空间复杂度为：
O
（1）
FIFO：
时间复杂度为O（n^2）空间复杂度为：
O
（1）
LRU：
时间复杂度为O（n^2）空间复杂度为：
O
（1）
（3）经验和体会。
首先要明确页面置换的原理及OPI、FIFO、LRU算法的主要思想，画出算法流程图！
这样在解决问题时更容易!
7、用户使用说明
程序的使用说明，列出每一步的操作步骤。
（1）输入页面总数
（2）输入最小物理块数
（3）输入页面访问序列
（4）选择算法
（5）得出结果
8、测试结果
9、心得体会
通过使用C++程序设计语言对页面置换算法进行编程设计，使我对该算法有了更深的了解和更完整的掌握，也在编程过程中对这种算法的优缺点有了体会，并且加强了自己的编程能力。
10、附录
程序源代码：
#include
#defineMaxNumber100
/******************************最佳置换算法*************************************/
voidOPI（intPageOrder[MaxNumber],intPageCount[MaxNumber],
intPageNum,intLackNum,intBlockNum,doubleLackPageRate,boolfound）
{
intmodule[MaxNumber];
intsum=0;
inti,j,k,m;
for（i=0;i{
module[i]=PageOrder[i];
sum++;
for（j=0;j<=i;j++）
cout<cout<}
LackNum=BlockNum;
for（i=BlockNum;i{
found=false;
for（j=0;j{
if（module[j]==PageOrder[i]）
{
found=true;
break;
}
}
if（found==false）//缺页，选择替换
{
for（j=0;j{
PageCount[j]=0;
for（k=i+1;k{
if（module[j]!
=PageOrder[k]）
PageCount[j]++;
else
break;
}
}
intmax=PageCount[0];
intkind=0;
for（j=0;j{
if（PageCount[j]>max）
{
max=PageCount[j];
kind=j;
}
}
module[kind]=PageOrder[i];
LackNum++;
for（m=0;m<3;m++）
cout<cout<}
}
LackPageRate=（LackNum*1.0）/PageNum;
cout<<"该算法缺页次数为:
"<cout<<"该算法缺页率为:
"<}
/******************************先进先出置换算法*************************************/
voidFIFO（intPageOrder[MaxNumber],intPageCount[MaxNumber],
intPageNum,intLackNum,intBlockNum,doubleLackPageRate,boolfound）
{
intmodule[MaxNumber];
intsum=0;
inti,j,m;
for（i=0;i{
module[i]=PageOrder[i];
sum++;
PageCount[i]=3-i;
for（j=0;j<=i;j++）
cout<cout<}
LackNum=BlockNum;
for（i=BlockNum;i{
found=false;
for（j=0;j{
if（module[j]==PageOrder[i]）
{
found=true;
break;
}
}
if（found==false）//缺页，选择替换
{
intmax=PageCount[0];
intkind=0;
for（j=0;j{
if（PageCount[j]>max）
{
max=PageCount[j];
kind=j;
}
}
for（intk=0;k{
if（k!
=kind）
PageCount[k]++;
}
module[kind]=PageOrder[i];
PageCount[kind]=0;//替换之后已经查询的次数改为0
LackNum++;
for（m=0;m<3;m++）
cout<cout<}
}
LackPageRate=（LackNum*1.0）/PageNum;
cout<<"该算法缺页次数为:
"<cout<<"该算法缺页率为:
"<}
/******************************最近最久未使用置换算法*************************************/
voidLRU（intPageOrder[MaxNumber],intPageCount[MaxNumber],
intPageNum,intLackNum,intBlockNum,doubleLackPageRate,boolfound）
{
intmodule[MaxNumber];
intsum=0;
inti,j,m;
for（i=0;i{
module[i]=PageOrder[i];
sum++;
PageCount[i]=3-i;
for（j=0;j<=i;j++）
cout<cout<}
LackNum=BlockNum;
for（i=BlockNum;i{
found=false;
for（j=0;j{
if（module[j]==PageOrder[i]）
{
found=true;
PageCount[j]=0;//查询后，更改次数
for（intk=0;k{
if（k!
=j）
PageCount[k]++;
}
break;
}
}
if（found==false）//缺页，选择替换
{
intmax=PageCount[0];
intkind=0;
for（j=0;j{
if（PageCount[j]>max）
{
max=PageCount[j];
kind=j;
}
}
for（intk=0;k{
if（k!
=kind）
PageCount[k]++;
}
module[kind]=PageOrder[i];
PageCount[kind]=0;//替换之后未查询的次数改为0
LackNum++;
for（m=0;m<3;m++）
cout<cout<}
}
LackPageRate=（LackNum*1.0）/PageNum;
cout<<"该算法缺页次数为:
"<cout<<"该算法缺页率为:
"<}
voidmain（）
{
intPageOrder[MaxNumber];//页面序列
intPageCount[MaxNumber]={0};//计算内存内数据离下一次出现的距离
intPageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数
doubleLackPageRate=0;
boolfound=false;
intchioce1=0,chioce2,chioce3;
inti=0;
while（chioce1==0）
{
cout<<"是否重新输入数据；0:
不输入，1：
重新输入：
";
cin>>chioce2;
if（chioce2==1）
{
cout<<"请输入页面个数：
";
cin>>PageNum;
cout<<"请输入最小物理块数";
cin>>BlockNum;
cout<<"请输入页面序列：
"<for（i=0;icin>>PageOrder[i];
}
cout<<"请选择算法：
1-FIFO，2-OPI，3-LRU:
";
cin>>chioce3;
if（chioce3==1）
FIFO（PageOrder,PageCount,PageNum,LackNum,BlockNum,LackPageRate,found）;
else
{
if（chioce3==2）
OPI（PageOrder,PageCount,PageNum,LackNum,BlockNum,LackPageRate,found）;
else
LRU（PageOrder,PageCount,PageNum,LackNum,BlockNum,LackPageRate,found）;
}
cout<<"*****************************************************************"<cout<<"请选择继续还是结束：
0：
继续，1：
结束";
cin>>chioce1;
}
}
升级会员 