虚拟内存页面置换算法实验报告.pdf

虚拟内存页面置换算法实验报
告

LT
华侨大学计算机科学与技术学院

2
华侨大学计算机科学与技术学院

3
华侨大学计算机科学与技术学院

4
华侨大学计算机科学与技术学院

(1)输入的形式

intPageOrder[MaxNumber];//页面序列

intPageNum,LackNum=0,BlockNum;//页面个数，缺页次数，

最小物理块数

(2)输出的形式

doubleLackPageRate//缺页率

缺页个数

每次缺页时物理块中存储

(3)程序所能达到的功能

模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页

面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数

为m，在进程运行过程中要访问的页面个数为n，页面访问序列为

，分别利用不同的页面置换算法调度进程的页面访问序列，
P1,…,Pn
给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。

测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出

结果。

(4)测试数据

页面个数：20最小物理块数：3

页面序列：90120304230321201701

4、概要设计

说明本程序中用到的所有抽象数据类型的定义、主程序的流程以

5
华侨大学计算机科学与技术学院

及各程序模块之间的层次(调用)关系。

intPageOrder[MaxNumber];//页面序列

intPageCount[MaxNumber]={0};//计算内存内数据离下一

次出现的距离

intPageNum,LackNum=0,BlockNum;//页面个数，缺页次数，

最小物理块数

doubleLackPageRate=0;

boolfound=false;

5、详细设计

6
华侨大学计算机科学与技术学院

其它两个的流程一样，只是PageCount[j]>max判断条件中的max

所指含义不同，在FIFO中max是指从进入物理块到本次存在最久，在

LRU中是指从上一次访问到本次存在最久！

6、调试分析

(1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨

论和分析；

在FIFO和LRU中计算每个页面在物理块中所存在的“时间”时总是出

错，后来多次调试语句所处位置和计数方法，终于得出正确结果，并且所

有算法都没有输出物理块中发生置换后的物理块中的内容，在老师的提醒

下更改程序输出其内容。

(2)算法的性能分析(包括基本操作和其它算法的时间复杂度和

空间复杂度的分析)及其改进设想；

OPI：时间复杂度为O（n^2）空间复杂度为：O(1)

FIFO：时间复杂度为O（n^2）空间复杂度为：O(1)

7
华侨大学计算机科学与技术学院

LRU：时间复杂度为O（n^2）空间复杂度为：O(1)

(3)经验和体会。

首先要明确页面置换的原理及OPI、FIFO、LRU算法的主要思想，

画出算法流程图！这样在解决问题时更容易!

7、用户使用说明

程序的使用说明，列出每一步的操作步骤。

（1）输入页面总数

（2）输入最小物理块数

（3）输入页面访问序列

（4）选择算法

（5）得出结果

8、测试结果

8
华侨大学计算机科学与技术学院

9、心得体会

通过使用C++程序设计语言对页面置换算法进行编程设计，使我

对该算法有了更深的了解和更完整的掌握，也在编程过程中对这种算

法的优缺点有了体会，并且加强了自己的编程能力。

10、附录

程序源代码：

#include<iostream.h>

#defineMaxNumber100

9

/******************************最佳置换算法*************************************/

voidOPI(intPageOrder[MaxNumber],intPageCount[MaxNumber],

intPageNum,intLackNum,intBlockNum,doubleLackPageRate,boolfound)
{

intmodule[MaxNumber];

intsum=0;

inti,j,k,m;

for(i=0;i<BlockNum;i++)//将内存填满
{

module[i]=PageOrder[i];

sum++;

for(j=0;j<=i;j++)

cout<<endl;
}

LackNum=BlockNum;

for(i=BlockNum;i<PageNum;i++)
{

found=false;

for(j=