操作系统实验指导书-实验二 动态分页存储的缺页率分析

PAGEPAGE1操作系统实验指导书实验二动态分页存储的缺页率分析实验名称动态分页存储的缺页率分析实验目标请求页式虚存管理是常用的虚拟存储管理方案之一。通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。本实验使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行，并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。三、实验环境要求：1.PC机。2.Dos；Windows；Linux环境。3.BorlandC++forDos；VisualC++6.0forWindows；g++forLinux。四、实验基本原理（1）先进先出页面置换算法（FIFO）FIFO算法这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。（2）最近最久未使用置换算法（LRU）最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。源代码//动态分页存储管理中的缺页率分析#include<iostream>#include<stdio.h>#include<cstring>#include<algorithm>#include<string>#include<queue>usingnamespacestd;structPage//描述页框{intn;//页框大小intindex;//用来标记最先进入的页的下标int*p;};Pagepage;//页框voidintialize(intn);//初始化页框voidFIFO(inta[],intm){intnum=0; inti;cout<<"FIFO淘汰算法"<<endl;for(i=1;i<=page.n;i++){printf("页%d",i);}cout<<endl;for(i=0;i<m;i++){printf("%d",a[i]);intflag=0;for(intj=0;j<page.n;j++){if(a[i]==page.p[j])//该页存在在页框中，不需要发生缺页中断{flag=1;break;}}if(flag==0)////当前页框中有没有要调用的页,产生缺页中断{num++;if(page.index<page.n-1)//表明页框中还有空闲页，不发生页置换{if(page.index==-1){page.p[0]=a[i];}else{for(intk=page.index;k>=0;k--){page.p[k+1]=page.p[k];}page.p[0]=a[i];}page.index++;}else//页置换{for(intk=page.n-1;k>0;k--){page.p[k]=page.p[k-1];}page.p[0]=a[i];}}for(inti=0;i<page.n;i++){printf("%6d",page.p[i]);}cout<<endl;}cout<<"共发生"<<num<<"次缺页中断，命中率为"<<(m-num)<<"/"<<m<<endl<<endl;}voidLRU(inta[],intm){intnum=0; inti;cout<<"LRU淘汰算法"<<endl;for(i=1;i<=page.n;i++){printf("页%d",i);}cout<<endl;for(i=0;i<m;i++){printf("%d",a[i]);intflag=0;for(intj=0;j<page.n;j++){if(a[i]==page.p[j])//该页存在在页框中，不需要发生缺页中断,调整顺序{flag=1;inttemp=a[i];for(intk=j;k>0;k--){page.p[j]=page.p[j-1];}page.p[0]=temp;flag=1;break;}}if(flag==0)////当前页框中有没有要调用的页,产生缺页中断{num++;if(page.index<page.n-1)//表明页框中还有空闲页，不发生页置换{if(page.index==-1){page.p[0]=a[i];}else{for(intk=page.index;k>=0;k--){page.p[k+1]=page.p[k];}page.p[0]=a[i];}page.index++;}else//页置换{for(intk=page.n-1;k>0;k--){page.p[k]=page.p[k-1];}page.p[0]=a[i];}}for(inti=0;i<page.n;i++){printf("%6d",page.p[i]);}cout<<endl;}cout<<"共发生"<<num<<"次缺页中断，命中率为"<<(m-num)<<"/"<<m<<endl<<endl;}voidintialize(intn)//初始化页框{page.n=n;for(inti=0;i<n;i++)page.p[i]=0;page.index=-1;}intmain(){int*a;intn;intm;cin>>n;//页的大小 page.p=newint[n];cin>>m;//测试数据的个数 a=newint[m];cout<<"当前页框