实验报告三 虚拟内存页面置换算法参考模板

1、实验报告三 虚拟内存页面置换算法班级 学号 姓名 一、 实验目的通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。二、实验的开发环境1. 硬件设备：PC机一台2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C C+Java 等编程语言环境。三、实验设计思路 问题描述：设计程序模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, ,Pn

2、，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。四、实验内容及结果程序要求如下：1）利用先进先出FIFO，最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。3）输入：最小物理块数m，页面个数n，页面访问序列P1, ,Pn，算法选择1-FIFO，2-OPI，3-LRU。4）输出：每种算法的缺页次数和缺页率。程序源码如下：#include "iostream.h"const int DataMax=100;const int Blo

3、ckNum = 10;int DataShowBlockNumDataMax; / 用于存储要显示的数组bool DataShowEnableBlockNumDataMax; / 用于存储数组中的数据是否需要显示/int DataDataMax=4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1; / 测试数据/int N = 20; / 输入页面个数int DataDataMax; / 保存数据int BlockBlockNum; / 物理块int countBlockNum; / 计数器int N ; / 页面个数int M;/最小物理块数int ChangeT

4、imes;void DataInput(); / 输入数据的函数void DataOutput();void FIFO(); / FIFO 函数void Optimal(); / Optimal函数void LRU(); / LRU函数1 / 8/*int main(int argc, char* argv) DataInput();/ DataInput(); / FIFO(); / Optimal(); / LRU(); / return 0; int menu; while(true) cout<<endl; cout<<"* 菜单选择 *"&

5、lt;<endl; cout<<"*"<<endl; cout<<"* 1-FIFO *"<<endl; cout<<"* 2-Optimal *"<<endl; cout<<"* 3-LRU *"<<endl; cout<<"* 0-EXIT *"<<endl; cout<<"*"<<endl; cin>>menu

6、; 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>

7、;>M; cout<<"请输入页面的个数：" cin>>N; while(N > DataMax) / 大于数据个数 cout<<"页面个数超过预定值，请重新输入：" cin>>N; cout<<"请输入页面访问序列："<<endl; for(int i=0;i<N;i+) cin>>Datai;void DataOutput() int i,j; for(i=0;i<N;i+) / 对所有数据操作 cout<<Da

8、tai<<" " cout<<endl; for(j=0;j<M;j+) cout<<" " for(i=0;i<N;i+) / 对所有数据操作 if( DataShowEnableji ) cout<<DataShowji<<" " else cout<<" " cout<<endl; cout<<"缺页次数: "<<ChangeTimes<<endl; cout

9、<<"缺页率: "<<ChangeTimes*100/N<<"%"<<endl;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+) DataShowEnableji = false; / 初始化为false，表示没有要显示的数据 for(i=0;i<M;i+) counti = 0; / 大于等于BlockNum，表示块中没有

10、数据，或需被替换掉 / 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1， / 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段 for(i=0;i<N;i+) / 对有所数据操作 / 增加count for(j=0;j<M;j+) countj+; find = false; / 表示块中有没有该数据 for(j=0;j<M;j+) if( Blockj = Datai ) find = true; if( find ) continue; / 块中有该数据，判断下一个数据 / 块中没有该数据 ChangeTimes+; / 缺

11、页次数+ if( (i+1) > M ) / 因为i是从0开始记，而M指的是个数，从1开始，所以i+1 /获得要替换的块指针 temp = 0; for(j=0;j<M;j+) if( temp < countj ) temp = countj; point = j; / 获得离的最远的指针 else point = i; / 替换 Blockpoint = Datai; countpoint = 0; / 更新计数值 / 保存要显示的数据 for(j=0;j<M;j+) DataShowji = Blockj; DataShowEnablei<M?(j<=

12、i?j:i):ji = 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+) DataShowEnableji = false; / 初始化为false，表示没有要显示的数据/ for

13、(i=0;i<M;i+)/ / counti = 0 ; / / for(i=0;i<N;i+) / 对有所数据操作 find = false; / 表示块中有没有该数据 for(j=0;j<M;j+) if( Blockj = Datai ) find = true; if( find ) continue; / 块中有该数据，判断下一个数据 / 块中没有该数据，最优算法 ChangeTimes+; / 缺页次数+ for(j=0;j<M;j+) / 找到下一个值的位置 find = false; for( k =i;k<N;k+) if( Blockj = D

14、atak ) find = true; countj = k; break; if( !find ) countj = N; if( (i+1) > M ) / 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 /获得要替换的块指针 temp = 0; for(j=0;j<M;j+) if( temp < countj ) temp = countj; point = j; / 获得离的最远的指针 else point = i; / 替换 Blockpoint = Datai; / 保存要显示的数据 for(j=0;j<M;j+) DataShow

15、ji = Blockj; DataShowEnablei<M?(j<=i?j:i):ji = 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+) DataShowEnableji = false;

16、/ 初始化为false，表示没有要显示的数据 for(i=0;i<M;i+) counti = 0 ; for(i=0;i<N;i+) / 对有所数据操作 / 增加count for(j=0;j<M;j+) countj+; find = false; / 表示块中有没有该数据 for(j=0;j<M;j+) if( Blockj = Datai ) countj = 0; find = true; if( find ) continue; / 块中有该数据，判断下一个数据 / 块中没有该数据 ChangeTimes+; / 缺页次数+ if( (i+1) > M

17、 ) / 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 /获得要替换的块指针 temp = 0; for(j=0;j<M;j+) if( temp < countj ) temp = countj; point = j; / 获得离的最远的指针 else point = i; / 替换 Blockpoint = Datai; countpoint = 0; / 保存要显示的数据 for(j=0;j<M;j+) DataShowji = Blockj; DataShowEnablei<M?(j<=i?j:i):ji = true; / 设置显示数据 / 输出信息 cout<< endl; cout<<"LRU => "<< endl; DataOutput();五、实验效果六、实验总结通过这次实验我对先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。有了更多的了解。在编程过程中我也通过查阅书籍和复习以前