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

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

班级 学号 姓名

一、 实验目的

通过这次实验，加深对虚拟内存页面置换概念的理解， 进一步掌握先进先出 FIFO,最佳

置换OPI和最近最久未使用 LRU页面置换算法的实现方法。

二、 实验的开发环境

硬件设备：PC机一台

软件环境：安装 Windows操作系统或者Linux操作系统，并安装相关的程序开发环境， 如C \C++\Java等编程语言环境。

三、 实验设计思路

问题描述：

设计程序模拟先进先出 FIFO,最佳置换OPI和最近最久未使用 LRU页面置换算法的工

作过程。假设内存中分配给每个进程的最小物理块数为 m，在进程运行过程中要访问的页面

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

四、 实验内容及结果

程序要求如下：

利用先进先出FIFO，最佳置换 OPI和最近最久未使用 LRU三种页面置换算法模拟 页面访问过程。

模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。

输入：最小物理块数 m,页面个数n,页面访问序列 P1,…，Pn,算法选择1-FIFO , 2-OPI, 3-LRU。

输出：每种算法的缺页次数和缺页率。

程序源码如下：

#include "iostream.h"

const int DataMax=100;

const int BlockNum = 10;

int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组

bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示

//int Data[DataMax]={4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1}; // 测试数据

//int N = 20; //输入页面个数

int Data[DataMax]; // 保存数据

int Block[BlockNum]; // 物理块

int count[BlockNum]; // 计数器

int N ; //页面个数

int M;//最小物理块数

int ChangeTimes;

void DataInput(); //输入数据的函数

void DataOutput();

void FIFO(); // FIFO 函数

void Optimal(); // Optimal 函数

void LRU(); // LRU 函数

///*

int main(int argc, char* argv[]) {

DataInput();// DataInput();

// FIFO();

// Optimal();

// LRU();

// return 0;

int menu;

while(true)

{

cout<<endl; cout<<"*

菜单选择

cout<<"

|*******************************************************|

"<<endl;

cout<<"*

1-FIFO

cout<<"* 2-Optimal

cout<<"* 3-LRU

cout<<"*

0-EXIT

*"<<endl;

*"<<endl;

*"<<endl;

*"<<endl;

*"<<endl;

cout<<"

|*******************************************************|

"<<endl;

cin>>menu;

switch(menu)

{

case 1: FIFO();break;

case 2: Optimal();break;

case 3: LRU();break;

default: break;

}

if(menu!=1&&menu!=2&&menu!=3) break; }

}

//*/

void DataInput()

{

cout<<" 请输入最小物理块数： ";

cin>>M;

while(M > BlockNum) // 大于数据个数

{

cout<<" 物理块数超过预定值，请重新输入： " cin>>M;

}

cout<<" 请输入页面的个数： ";

cin>>N;

while(N > DataMax) // 大于数据个数

{

cout<<" 页面个数超过预定值，请重新输入： " cin>>N;

}

cout<<" 请输入页面访问序列： "<<endl; for(int i=0;i<N;i++)

cin>>Data[i];

void DataOutput()

{

int i,j;

for(i=0;i<N;i++) // 对所有数据操作

{

cout<<Data[i]<<" ";

}

cout<<endl;

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

{

cout<<" ";

for(i=0;i<N;i++) // 对所有数据操作

{

if( DataShowEnable[j][i] )

cout<<DataShow[j][i]<<" ";

else

cout<<" ";

}

cout<<endl;

}

cout<<" 缺页次数 : "<<ChangeTimes<<endl;

coutvv"缺页率："v<ChangeTimes*100/Nvv"%"vvendl;

}

void FIFO()

{

int i,j;

bool find;

int point;

int temp; // 临时变量 ChangeTimes = 0;

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

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

DataShowEnable[j][i] = false; //初始化为false，表示没有要显示的数据

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

{

count[i] = 0; // 大于等于 BlockNum ，表示块中没有数据，或需被替换掉 // 所以经这样初始化( 3 2 1)，每次替换 >=3 的块，替换后计数值置 1，

// 同时其它的块计数值加 1 ，成了( 1 3 2 )，见下面先进先出程序段

}

for(i=0;i<N;i++) // 对有所数据操作

{

// 增加 count

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

count[j]++;

find = false; // 表示块中有没有该数据

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

{

if( Block[j] == Data[i] )

{

find = true;

}

}

if( find ) continue; // 块中有该数据，判断下一个数据

// 块中没有该数据

ChangeTimes++; // 缺页次数 ++

if( (i+1) > M ) // 因为 i 是从 0 开始记，而 M 指的是个数，从 1 开始，所以 i+1 {

//获得要替换的块指针

temp = 0;

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

{

if( temp < count[j] )

{

temp = count[j];

point = j; // 获得离的最远的指针

}

}

}

else point = i;

// 替换

Block[point] = Data[i];

count[point] = 0; // 更新计数值

// 保存要显示的数据

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

{

DataShow[j][i] = Block[j];

DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据

}

}

// 输出信息

cout<< endl;

cout<<"FIFO => "<< endl;

DataOutput();

}

void Optimal()

{

int i,j,k;

bool find;

int point;

int temp; // 临时变量，比较离的最远的时候用

ChangeTimes = 0;

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

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

DataShowEnable[j][i] = false; //初始化为false，表示没有要显示的数据

// for(i=0;i<M;i++)

// {

// count[i] = 0 ; //

// }

for(i=0;i<N;i++) // 对有所数据操作

{

find = false; // 表示块中有没有该数据

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

{

if( Block[j] == Data[i] )

find = true;

}

if( find ) continue; // 块中有该数据，判断下一个数据

// 块中没有该数据，最优算法

ChangeTimes++; // 缺页次数 ++

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

{

// 找到下一个值的位置

find = false;

for( k =i;k<N;k++)

{

if( Block[j] == Data[k] )

{ find = true; count[j] = k; break;

}

}

if( !find ) count[j] = N;

}

if( (i+1) > M ) // 因为 i 是从 0 开始记，而 BlockNum 指的是个数，从 1 开始，所以 i+1 {

//获得要替换的块指针

temp = 0;

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

{

if( temp < count[j] )

{

temp = count[j];

point = j; // 获得离的最远的指针

}

}

}

else point = i;

// 替换

Block[point] = Data[i];

// 保存要显示的数据

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

{

DataShow[j][i] = Block[j];

DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据

}

}

// 输出信息

cout<< endl;

cout<<"Optimal => "<< endl;

DataOutput();

}

void LRU()

{

int i,j;

bool find;

int point;

int temp; // 临时变量 ChangeTimes = 0; for(j=0;j<M;j++) for(i=0;i<N;i++)

DataShowEnable[j][i] = false; //初始化为false，表示没有要显示的数据

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

{

count[i] = 0 ;

}

for(i=0;i<N;i++) // 对有所数据操作

{

// 增加 count

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

count[j]++;

find = false; // 表示块中有没有该数据

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

{

if( Block[j] == Data[i] )

{

count[j] = 0;

find = true;

}

}

if( find ) continue; // 块中有该数据，判断下一个数据

// 块中没有该数据

ChangeTimes++; // 缺页次数 ++

if( (i+1) > M ) // 因为 i 是从 0 开始记，而 BlockNum 指的是个数，从 1 开始，所以 i+1 {

//获得要替换的块指针

temp = 0;

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

{

if( temp < count[j] )

{

temp = count[j];

point = j; // 获得离的最远的指针

}

}

}

else point = i;

// 替换

Block[point] = Data[i];

count[point] = 0;

// 保存要显示的数据

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

{

DataShow[j][i] = Block[j];

DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据

}

//输出信息

coutvv endl;

cout?"LRU => "<< endl; DataOutput();

}

五、实验效果

六、实验总结

通过这次实验我对先进先出 FIFO ，最佳置换 OPI 和最近最久未使用 LRU 页面置换算法 的实现方法。

　有了更多的了解。

　在编程过程中我也通过查阅书籍和复习以前的课本， 对 C++ 编程语言进行了复习。

通过这个实验我也体会到思路的重要性， 一个程序如果一开始计划的好， 结构设计完善， 才 可能顺利进行。

　这次实验模拟出了优先权调度算法， 使我更加了解这一算法的调度过程。

　以 前仅限于知道这一知识点， 现在居然能用程序来实现这个过程。

　我相信这将是一个很好的学 习方法。

我希望以后能够有更多的机会来锻炼自己， 通过具体实践来提高自己编程的能力， 来进 一步掌握和理解在课堂上学到的东西，做到学以致用！总之，这次综合实验是我收益匪浅， 是我明白了实际编程和理论知识间的差异， 明白了在学习课本的基础上我们还需要很大的实 践扩充才能真正的理解并学好这门课程。