实验五虚拟内存页面置换算法Word下载.docx
《实验五虚拟内存页面置换算法Word下载.docx》由会员分享,可在线阅读,更多相关《实验五虚拟内存页面置换算法Word下载.docx(46页珍藏版)》请在冰点文库上搜索。
平时,把
出面的算法称面置算法。
置算法的利害,将直接影响到系的性能。
一个好的面置算法,拥有低的更好率。
从理上,将那些今后不再
的面出,或把那些在内不再的面出。
目的
通次,加深虚内存面置看法的理解,
一步掌握先先出
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
1
7
程的最大号数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()
main()调用Init()2OPI()Print()
3
LRU()Print()
三、详细设计
1.voidFIFO()
original();
Simulate[0][0]=PageOrder[0];
inttemp=0,flag=0;
for(i=1;
i<
PageNum;
i++)
{
//判断该页面可否存在内存中
for(j=0;
j<
BlockNum;
j++)
if(PageOrder[i]==Simulate[flag][j])
break;
}
if(j==BlockNum)
{//该页面不在内存中
for(k=0;
k<
k++)
{//模拟置换过程
if(Simulate[flag][k]==NULL)
else
Simulate[i][k]=Simulate[flag][k];
//裁汰最先进入内存的页面
temp++;
temp=temp%BlockNum;
Simulate[i][temp]=PageOrder[i];
LackNum++;
flag=i;
}//该页面在内存中
continue;
2.voidOPI()
inttemp,flag=0;
//flag表示上一个模拟内存的下标
//j!
=BlockNum表示该页面已经在内存中
if(j!
=BlockNum)
//模拟置换过程
//内存中页面进行选择
//两种情况:
内存已满和内存未满
if(Simulate[i][j]==NULL)
Simulate[i][j]=PageOrder[i];
=BlockNum)//内存未满
//内存已满
temp=0;
//temp表示要置换的页面内存下标
{//采用要置换的页面内存下标
for(k=i+1;
{//最长时间内不被接见的页面
if(Simulate[i][j]==PageOrder[k])
PageCount[j]=k;
if(k==PageNum)//此后没有进行对该页面的接见
PageCount[j]=PageNum;
if(PageCount[temp]<
PageCount[j])
temp=j;
3.voidLRU()
PageCount[0]=0;
//近来的页面下标
PageCount[j]=i;
{//内存未满
{//近来最久时间内不被接见的页面
if(PageCount[temp]>
PageCount[temp]=i;
四、调试解析
1.发现的问题
在编写程序的最先,界面不是很好,看着很乱。
最后求的缺页率也不是
用百分数表示。
2.算法的性能解析(包括基本操作和其他算法的时间复杂度和空间复杂度的解析)及其改进设想;
该程序的的时间复杂度还算理想,是O(m*n),空间复杂度也是相同,复杂
度为O(m*n),均不需要再改进了。
3.解决方法
界面使用空格填充,使各行各列对齐。
对于输出百分数,将缺页率乘以100,后加%输出。
4.经验和领悟
经过二次编程,又一次加深了对先进先出(FIFO)页面置换算法,最正确
(OPI)置换算法,近来最久未使用(LRU)置换算法的理解。
同时,也掌握了一些使界面输出看起来更工整的方法。
还有,在平时做作业的时候,总是默认为物理块数是3,其实可是比较
常用而已,其实不是每次都是3.这个在编程中有表现,在今后做题中会更注意。
五、用户使用说明
(1)用户依照提示输入物理块数
(2)输入页面个数
(3)依次输入页面接见个数
(4)依照提示选择算法,输入对应的数字。
六、测试结果
列出测试结果,包括输入和输出。
七.附录
#include<
iostream>
iomanip>
usingnamespacestd;
int
PageOrder[MaxNumber];
//
面序列
P1,
⋯,Pn,
Simulate[MaxNumber][MaxNumber];
//PageCount[MaxNumber];
模面置程
PageNum,LackNum;
面数,缺数
//boolfound;
缺率
intBlockNum;
inti,j,k;
voidmain(){
//cout<
<
setw
(2)<
"
"
;
init();
boold=true;
while(d)
cout<
算法选择\nFIFO:
输入'
1'
\n
OPI:
输入
'
2'
LRU:
3'
\nexit:
4'
\n"
intc;
cin>
>
c;
switch(c){
case1:
endl<
先进先出FIFO页面置换算法:
\n"
FIFO();
print();
case2:
最正确页面OPI置换算法:
OPI();
case3:
近来最久未使用LRU置换算法:
LRU();
case4:
d=false;
default:
你的输入有问题请重新输入!
voidinit(){
物理数m:
面个数n:
面序列P1,⋯,Pn\n"
for(i=0;
PageOrder[i];
voidoriginal(){
Simulate[i][j]=NULL;
LackNum=1;
voidprint(){
//模拟三种算法的页面置换过程,
//给出每个页面接见时的内存分配情况
//每种算法的缺页次数和缺页率。
LackPageRate=(double)LackNum/PageNum;
setw(4)<
----"
//for(i=0;
'
Simulate[i][j];
endl;
缺页次数:
LackNum<
缺页
率:
LackPageRate*100<
%"
voidFIFO(){
//先进先出:
最早出现的置换算法,总是裁汰最先进入内存的页面。
voidOPI(){
//最正确置换:
选择的被裁汰的页面都是今后永不使用也许在最长(未来)时间内不被接见的页面。
LackN