操作系统实验五报告虚拟内存页面置换算法.doc
操作系统实验报告实验五虚拟内存页面置换算法学号：班级：姓名：【实验目的】 通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出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）输出：每种算法的缺页次数和缺页率。实现提示：用C+语言实现提示：1）程序中变量定义参考（根据需要可添加）如下：const int MaxNumber=100;int PageOrderMaxNumber;int SimulateMaxNumberMaxNumber;int PageCountMaxNumber;int PageNum,LackNum;double LackPageRate;bool found;2）页面置换的实现过程如下：Ø 变量初始化；Ø 接收用户输入最小物理块数m，页面个数n，页面序列P1, ,Pn，选择算法1-FIFO，2-OPI，3-LRU；Ø 根据用户选择的算法进行页面的分配和置换，输出页面置换算法的模拟过程；Ø 计算选择算法的缺页次数和缺页率；Ø 输出选择算法的缺页次数和缺页率。实验要求：1) 上机前认真复习页面置换算法，熟悉FIFO，OPI，LRU三种页面分配和置换算法的过程；2) 上机时独立编程、调试程序；3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。【源程序】头文件FIFO.h#include<iostream>#include "iostream.h"const int MaxNumber=100;const int BlockNum=10;typedef struct Page_struct /定义页面结构快int PageOrderMaxNumber; /保存作业的页面访问序列int SimulateBlockNumMaxNumber; /保存页面int BlockBlockNum; /物理块int PageCountMaxNumber; /页面计数int PageNum,LackNum; /页面个数、缺页次数double PageRate; /缺页率bool found; Page;Page p;bool PageShowEnableBlockNumMaxNumber; /用于存储数组中的数据是否需要显示int N; /页面个数int M; /最小物理块数int LackCount; /缺页计数void FIFO(); /FIFO函数void FIFO()int i,j;int point;int temp; /临时变量LackCount=0;for(j=0;j<M;j+)for(i=0;i<N;i+)PageShowEnableji=false; /初始化为false,表示没有要显示的数据for(i=0;i<M;i+)p.PageCounti=0; for(i=0;i<N;i+)for(j=0;j<M;j+)p.PageCountj+;p.found=false; /表示块中有没有该数据for(j=0;j<M;j+)if(p.Blockj = p.PageOrderi)p.found=true;if(p.found)continue; /块中有该数据，判断下一个数据LackCount+; /块中没有该数据,缺页次数加1if(i+1)>M) temp=0;for(j=0;j<M;j+)if(temp<p.PageCountj)temp=p.PageCountj;point=j; /获得离得最远的指针elsepoint=i; p.Blockpoint=p.PageOrderi;/替换p.PageCountpoint=0; /更新计数值for(j=0;j<M;j+)/保存要显示的数据p.Simulateji=p.Blockj;PageShowEnablei<M?(j<=i?j:i):ji=true; /设置显示数据cout<<endl;/输出信息cout<<"先进先出FIFO页面置换算法:"<<endl;Poutput();头文件Optimal.h#include<iostream>void Optimal(); /Optimal函数void Optimal()int i,j,k;int point;int temp; /临时变量,比较离得最远的时候用LackCount=0;for(j=0;j<M;j+)for(i=0;i<N;i+)PageShowEnableji=false; /初始化为false,表示没有要显示的数据for(i=0;i<N;i+)p.found=false; /表示块中有没有该数据for(j=0;j<M;j+)if(p.Blockj = p.PageOrderi)p.found=true;if(p.found)continue; LackCount+; /块中没有该数据，缺页次数加1for(j=0;j<M;j+)p.found=false;/找到下一个值的位置for(k=i;k<N;k+)if(p.Blockj = p.PageOrderk)p.found=true;p.PageCountj=k;break;if( !p.found )p.PageCountj=N;if(i+1)>M) temp=0;/获得要替换的块指针for(j=0;j<M;j+)if(temp<p.PageCountj)temp=p.PageCountj;point=j; /获得离得最远的指针elsepoint=i;p.Blockpoint=p.PageOrderi; /替换p.PageCountpoint=0; /更新计数值for(j=0;j<M;j+) /保存要显示的数据p.Simulateji=p.Blockj;PageShowEnablei<M?(j<=i?j:i):ji=true; /设置显示数据cout<<endl; /输出信息cout<<"最佳Optimal页面置换算法:"<<endl;Poutput();头文件LRU.h#include<iostream.h>void LRU()int i,j;int point;int temp; /临时变量LackCount=0;for(j=0;j<M;j+)for(i=0;i<N;i+)PageShowEnableji=false; /初始化为false,表示没有要显示的数据for(i=0;i<M;i+)p.PageCounti=0; for(i=0;i<N;i+) /对有所数据操作for(j=0;j<M;j+)/增加countp.PageCountj+;p.found=false; /表示块中有没有该数据for(j=0;j<M;j+)if(p.Blockj = p.PageOrderi)p.PageCountj=0;p.found=true;if(p.found)continue; LackCount+; /块中没有该数据,缺页次数加1if(i+1)>M) temp=0;for(j=0;j<M;j+)if(temp<p.PageCountj)temp=p.PageCountj;point=j; /获得离得最远的指针elsepoint=i;p.Blockpoint=p.PageOrderi;/替换p.PageCountpoint=0; /更新计数值for(j=0;j<M;j+)/保存要显示的数据p.Simulateji=p.Blockj;PageShowEnablei<M?(j<=i?j:i):ji=true; /设置显示数据cout<<endl; /输出信息cout<<"最近最久未使用LRU页面置换算法:"<<endl;Poutput();主程序Main.cpp#include<iostream>#include "FIFO.h"#include "Optiaml.h"#include "LRU.h"int Pinput(); /进程参数输入int Poutput(); /调度结果输出int main(int argc,char *argv)Pinput(); /数据输入int option; while(true)cout<<endl;cout<<"请选择算法：1-FIFO，2-OPL，3-LRU，0-EXIT"<<endl;cout<<"请输入你选择的算法的序号:"<<endl;cin>>option;switch(option)case 1:FIFO();break;case 2:Optimal();break;case 3:LRU();break;default:break;if(option != 1 && option != 2 && option != 3)break;return 0;void Pinput()cout<<"*虚拟内存页面置换算法*"<<endl;cout<<"请输入最小物理块数："cin>>M;while(M > BlockNum) /大于数据个数cout<<"物理块数超过预定值，请重新输入："cin>>M;cout<<"请输入页面的个数："cin>>N;while(N > MaxNumber) /大于数据个数cout<<"页面个数超过预定值，请重新输入："cin>>N;cout<<"请输入页面访问序列："<<endl;for(int i=0;i<N;i+)cin>>p.PageOrderi;void Poutput()int i,j;for(i=0;i<N;i+)cout<<p.PageOrderi<<" "cout<<endl;for(j=0;j<M;j+)cout<<" "for(i=0;i<N;i+)if(PageShowEnableji)cout<<p.Simulateji<<" "elsecout<<" "cout<<endl;cout<<"缺页次数："<<LackCount<<endl;cout<<"缺页率："<<LackCount*100/N<<"%"<<endl;【实例运行结果截图】先进先出页面置换算法（FIFO）最佳页面置换算法（Optimal）最近最久未使用页面置换算法（LRU）
