实验五虚拟内存页面置换算法.docx
《实验五虚拟内存页面置换算法.docx》由会员分享，可在线阅读，更多相关《实验五虚拟内存页面置换算法.docx（46页珍藏版）》请在冰点文库上搜索。
实验五虚拟内存页面置换算法
.
实验五虚假内存页面置换算法
一、需求解析2
1.输入的形式和输入值的范围3
2.输出的形式4
3.程序所能达到的功能4
4.测试数据5
二、大纲设计6
1.抽象数据种类的定义6
2.主程序的流程7
3.程序各模块之间的层次（调用）关系8
三、详细设计8
1.voidFIFO（）8
2.voidOPI（）10
3.voidLRU（）13
四、调试解析16
1.发现的问题16
2.算法的性能解析（包括基本操作和其他算法的时间复杂度和空间复杂度的解析）及其改
进设想；16
3.解决方法16
4.经验和领悟..............................................................................................................................17
.
五、用使用明17
六、果17
七．附19
一、需求解析
需求
在程运行程中，若其所的面不在内存而需把它入内存，但内存已无
空空，了保程能正常运行，系必从内存出一程序或数据送
磁的区中。
但将哪个面出，需依照必然的算法来确定。
平时，把
出面的算法称面置算法。
置算法的利害，将直接影响到系的性能。
一个好的面置算法，拥有低的更好率。
从理上，将那些今后不再
的面出，或把那些在内不再的面出。
目的
通次，加深虚内存面置看法的理解，
一步掌握先先出
FIFO、
最正确置
OPI
和近来最久未使用
LRU
面置算法的方法
。
内容
程序模先先出FIFO、最正确置OPI和近来最久未使用LRU面置算
法的工作程。
假内存中分配每个程的最小物理数m，在程运行
程中要的面个数n，面序列P1,⋯,Pn，分利用不相同的面置
算法度程的面序列，出面序列的置程，算每种算法缺
.
次数和缺率。
程序要求
1）利用先先出FIFO、最正确置OPI和近来最久未使用LRU三种面置算法
模面程。
2）模三种算法的面置程，出每个面的内存分配情况。
3）入：
最小物理数m，面个数n，面序列P1,⋯,Pn，算法1-FIFO，
2-OPI，3-LRU。
4）出：
每种算法的缺次数和缺率。
1.输入的形式和输入值的范围
从dos控制台界面依照入提示入数据（色的数字即入的内容）
：
物理（LackNum）
：
3
号数（PageNum
）：
20
面序列（PageOrder）：
701203042303
212
0
1
7
0
1
程的最大号数100，物理、面序列的int型的范。
.
2.输出的形式
入数据后，按出程序模先先出
ENTER即可在FIFO、最正确置
dosOPI
控制台界面获取果。
依照要求分
和近来最久未使用LRU面置算法的
工作程。
果以下：
首行是算法的名称，第二行是号序列，接下来的3行数字是模拟物理的情况，
着看才是正确的果，此示的是3物理内存占用情况。
此后示缺次
数和缺率。
3.程序所能达到的功能
程序模先先出FIFO、最正确置OPI和近来最久未使用LRU面置算法的工作
程。
假内存中分配每个程的最小物理数m，在程运行程中要的
面个数n，面序列P1,⋯,Pn，分利用不相同的面置算法度程的
面序列，出面序列的置程，算每种算法缺次数和缺率。
.
4.测试数据
.
二、大纲设计
1.抽象数据种类的定义
程序中进度调换时间变量描述以下：
constintMaxNumber=100;
intPageOrder[MaxNumber];
intSimulate[MaxNumber][MaxNumber];
intPageCount[MaxNumber];
intPageNum,LackNum;
doubleLackPageRate;
boolfound;
主要函数：
voidprint（）;
voidinit（）;
voidoriginal（）;
voidFIFO（）;
voidOPI（）;
voidLRU（）;
2.主程序的流程
Init（）
输入a
.
初始化全局变量：
最小物理块数，页面个数，页
面接见序列
输出缺页次数和缺页
率及模拟过程
a=1
是
FIFO（）
否
否
a=2
是
OPI（）
否
a=3
是
LRU（）
否
a=4
是
结束
.
3.程序各模块之间的层次（调用）关系
FIFO（）Print（）
1
main（）调用Init（）2OPI（）Print（）
3
LRU（）Print（）
三、详细设计
1.voidFIFO（）
original（）;
Simulate[0][0]=PageOrder[0];
inttemp=0,flag=0;
for（i=1;i
{
//判断该页面可否存在内存中
for（j=0;j
{
if（PageOrder[i]==Simulate[flag][j]）
.
break;
}
if（j==BlockNum）
{//该页面不在内存中
for（k=0;k
{//模拟置换过程
if（Simulate[flag][k]==NULL）
break;
else
Simulate[i][k]=Simulate[flag][k];
}
//裁汰最先进入内存的页面
temp++;
temp=temp%BlockNum;
Simulate[i][temp]=PageOrder[i];
LackNum++;
flag=i;
}//该页面在内存中
else
.
continue;
}
2.voidOPI（）
original（）;
Simulate[0][0]=PageOrder[0];
inttemp,flag=0;//flag表示上一个模拟内存的下标
for（i=1;i
{
//判断该页面可否存在内存中
for（j=0;j
{
if（PageOrder[i]==Simulate[flag][j]）
break;
}
//j!
=BlockNum表示该页面已经在内存中
if（j!
=BlockNum）
continue;
.
//模拟置换过程
for（k=0;k
{
if（Simulate[flag][k]==NULL）
break;
else
Simulate[i][k]=Simulate[flag][k];
}
//内存中页面进行选择
//两种情况：
内存已满和内存未满
for（j=0;j
{
if（Simulate[i][j]==NULL）
{
Simulate[i][j]=PageOrder[i];
LackNum++;
flag=i;
break;
}
}
.
if（j!
=BlockNum）//内存未满
continue;
//内存已满
temp=0;//temp表示要置换的页面内存下标
for（j=0;j
{//采用要置换的页面内存下标
for（k=i+1;k
{//最长时间内不被接见的页面
if（Simulate[i][j]==PageOrder[k]）
{
PageCount[j]=k;
break;
}
}
if（k==PageNum）//此后没有进行对该页面的接见
PageCount[j]=PageNum;
if（PageCount[temp]
{
.
temp=j;
}
}
Simulate[i][temp]=PageOrder[i];
LackNum++;
flag=i;
}
3.voidLRU（）
original（）;
Simulate[0][0]=PageOrder[0];
inttemp,flag=0;//flag表示上一个模拟内存的下标
PageCount[0]=0;//近来的页面下标
for（i=1;i
{
//判断该页面可否存在内存中
for（j=0;j.
{
if（PageOrder[i]==Simulate[flag][j]）
{
PageCount[j]=i;
break;
}
}
//j!
=BlockNum表示该页面已经在内存中
if（j!
=BlockNum）
continue;
//模拟置换过程
for（k=0;k
{
if（Simulate[flag][k]==NULL）
break;
else
Simulate[i][k]=Simulate[flag][k];
}
//内存中页面进行选择
.
//两种情况：
内存已满和内存未满
for（j=0;j
{
if（Simulate[i][j]==NULL）
{//内存未满
Simulate[i][j]=PageOrder[i];
PageCount[j]=i;
LackNum++;
flag=i;
break;
}
}
if（j!
=BlockNum）
continue;
//内存已满
temp=0;//temp表示要置换的页面内存下标
for（j=0;j
{//近来最久时间内不被接见的页面
if（PageCount[temp]>PageCount[j]）
temp=j;
}
.
Simulate[i][temp]=PageOrder[i];
PageCount[temp]=i;
LackNum++;
flag=i;
}
}
四、调试解析
1.发现的问题
在编写程序的最先，界面不是很好，看着很乱。
最后求的缺页率也不是
用百分数表示。
2.算法的性能解析（包括基本操作和其他算法的时间复杂度和空间复杂度的解析）及其改进设想；
该程序的的时间复杂度还算理想，是O（m*n）,空间复杂度也是相同，复杂
度为O（m*n）,均不需要再改进了。
3.解决方法
界面使用空格填充，使各行各列对齐。
.
对于输出百分数，将缺页率乘以100，后加%输出。
4.经验和领悟
经过二次编程，又一次加深了对先进先出（FIFO）页面置换算法，最正确
（OPI）置换算法，近来最久未使用（LRU）置换算法的理解。
同时，也掌握了一些使界面输出看起来更工整的方法。
还有，在平时做作业的时候，总是默认为物理块数是3，其实可是比较
常用而已，其实不是每次都是3.这个在编程中有表现，在今后做题中会更注意。
五、用户使用说明
（1）用户依照提示输入物理块数
（2）输入页面个数
（3）依次输入页面接见个数
（4）依照提示选择算法，输入对应的数字。
六、测试结果
列出测试结果，包括输入和输出。
.
.
七．附录
#include
#include
usingnamespacestd;
constintMaxNumber=100;
int
PageOrder[MaxNumber];//
面序列
P1,
⋯,Pn，
int
int
Simulate[MaxNumber][MaxNumber];//PageCount[MaxNumber];//
模面置程
int
PageNum,LackNum;//
面数，缺数
doubleLackPageRate;//boolfound;
缺率
.
intBlockNum;
inti,j,k;
voidprint（）;
voidinit（）;
voidoriginal（）;
voidFIFO（）;
voidOPI（）;
voidLRU（）;
voidmain（）{
//cout<（2）<<"";
init（）;
boold=true;
while（d）
{
cout<<"
算法选择\nFIFO:
输入'1'\n
OPI:
输入
'2'\n
LRU:
输入
'3'\nexit:
输入'4'\n";
intc;
cin>>c;
switch（c）{
.
case1:
cout<\n";
FIFO（）;
print（）;
break;
case2:
cout<\n";
OPI（）;
print（）;
break;
case3:
cout<\n";
LRU（）;
print（）;
break;
case4:
d=false;
break;
default:
cout<<"你的输入有问题请重新输入！
\n";
break;
}
.
}
}
voidinit（）{
cout<<"物理数m:
";
cin>>BlockNum;
cout<<"面个数n:
";
cin>>PageNum;
cout<<"面序列P1,⋯,Pn\n";
for（i=0;i
cin>>PageOrder[i];
}
voidoriginal（）{
for（i=0;i
for（j=0;j
Simulate[i][j]=NULL;
LackNum=1;
}
.
voidprint（）{
//模拟三种算法的页面置换过程，
//给出每个页面接见时的内存分配情况
//每种算法的缺页次数和缺页率。
LackPageRate=（double）LackNum/PageNum;
for（i=0;i
cout<
for（i=0;i
cout<
for（i=0;i
cout<
for（j=0;j
{
//for（i=0;i
//cout<
for（i=0;i
if（Simulate[i][j]==NULL）
cout<
else
cout<
cout<.
}
//cout<
cout<<"缺页次数:
"<
率:
"<
}
voidFIFO（）{
//先进先出:
最早出现的置换算法，总是裁汰最先进入内存的页面。
original（）;
Simulate[0][0]=PageOrder[0];
inttemp=0,flag=0;
for（i=1;i
{
//判断该页面可否存在内存中
for（j=0;j
{
if（PageOrder[i]==Simulate[flag][j]）
break;
}
.
if（j==BlockNum）
{//该页面不在内存中
for（k=0;k
{//模拟置换过程
if（Simulate[flag][k]==NULL）
break;
else
Simulate[i][k]=Simulate[flag][k];
}
//裁汰最先进入内存的页面
temp++;
temp=temp%BlockNum;
Simulate[i][temp]=PageOrder[i];
LackNum++;
flag=i;
}//该页面在内存中
else
continue;
}
}
voidOPI（）{
.
//最正确置换:
选择的被裁汰的页面都是今后永不使用也许在最长（未来）时间内不被接见的页面。
original（）;
Simulate[0][0]=PageOrder[0];
inttemp,flag=0;//flag表示上一个模拟内存的下标
for（i=1;i
{
//判断该页面可否存在内存中
for（j=0;j
{
if（PageOrder[i]==Simulate[flag][j]）
break;
}
//j!
=BlockNum表示该页面已经在内存中
if（j!
=BlockNum）
continue;
//模拟置换过程
for（k=0;k.
{
if（Simulate[flag][k]==NULL）
break;
else
Simulate[i][k]=Simulate[flag][k];
}
//内存中页面进行选择
//两种情况：
内存已满和内存未满
for（j=0;j
{
if（Simulate[i][j]==NULL）
{
Simulate[i][j]=PageOrder[i];
LackNum++;
flag=i;
break;
}
}
if（j!
=BlockNum）//内存未满
continue;
.
//内存已满
temp=0;//temp表示要置换的页面内存下标
for（j=0;j
{//采用要置换的页面内存下标
for（k=i+1;k
{//最长时间内不被接见的页面
if（Simulate[i][j]==PageOrder[k]）
{
PageCount[j]=k;
break;
}
}
if（k==PageNum）//此后没有进行对该页面的接见
PageCount[j]=PageNum;
if（PageCount[temp]
{
temp=j;
}
}
.
Simulate[i][temp]=PageOrder[i];
LackN
升级会员 