实验报告三 虚拟内存页面置换算法
班级 学号 姓名
一、 实验目的
通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。
二、实验的开发环境
1. 硬件设备：PC机一台
2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C \\C++\\Java 等编程语言环境。
三、实验设计思路 问题描述：
设计程序模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。
四、实验内容及结果
程序要求如下：
1）利用先进先出FIFO，最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。
2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。
3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。
4）输出：每种算法的缺页次数和缺页率。 程序源码如下：
#include \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<
void DataInput() {
cout<<\请输入最小物理块数：\ cin>>M;
while(M > BlockNum) // 大于数据个数 {
cout<<\物理块数超过预定值，请重新输入：\ cin>>M; }
cout<<\请输入页面的个数：\ cin>>N;
while(N > DataMax) // 大于数据个数 {
cout<<\页面个数超过预定值，请重新输入：\ cin>>N; }
cout<<\请输入页面访问序列：\ for(int i=0;i
void DataOutput() {
int i,j;
for(i=0;i cout< cout< for(j=0;j cout<<\ for(i=0;i if( DataShowEnable[j][i] ) cout< cout<<\ \ } cout< cout<<\缺页次数: \ cout<<\缺页率: \} void FIFO() { int i,j; bool find; int point; int temp; // 临时变量 ChangeTimes = 0; for(j=0;j DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据 for(i=0;i count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉 // 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1， // 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段 } for(i=0;i // 增加count for(j=0;j find = false; // 表示块中有没有该数据 for(j=0;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 if( temp < count[j] ) { temp = count[j]; point = j; // 获得离的最远的指针 } } } else point = i; // 替换 Block[point] = Data[i]; count[point] = 0; // 更新计数值 // 保存要显示的数据 for(j=0;j DataShow[j][i] = Block[j]; DataShowEnable[i // 输出信息 cout<< endl; cout<<\ DataOutput(); } void Optimal() { int i,j,k; bool find; int point; int temp; // 临时变量，比较离的最远的时候用 ChangeTimes = 0; for(j=0;j DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据 // for(i=0;i // count[i] = 0 ; // // } for(i=0;i find = false; // 表示块中有没有该数据 for(j=0;j { if( Block[j] == Data[i] ) find = true; } if( find ) continue; // 块中有该数据，判断下一个数据 // 块中没有该数据，最优算法 ChangeTimes++; // 缺页次数++ for(j=0;j // 找到下一个值的位置 find = false; for( k =i;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 if( temp < count[j] ) { temp = count[j]; point = j; // 获得离的最远的指针 } } } else point = i; // 替换 Block[point] = Data[i]; // 保存要显示的数据 for(j=0;j DataShow[j][i] = Block[j]; DataShowEnable[i // 输出信息 cout<< endl; cout<<\ DataOutput(); } void LRU()
实验报告三 虚拟内存页面置换算法
