20102100062黄耿星页面置换算法实验报告

计算机学院操作系统实验报告项目名称：模拟操作系统的页面置换指导老师：陈红英成员：黄耿星（20102100062）一、综设计实验题目：模拟操作系统的页面置换二、中文摘要：在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。本实验通过模拟操作系统中的页面置换，比较FIFO、LRU、OPT三种页面置换算法的缺页率。关键词：缺页中断页面置换算法FIFOLRUOPT三、前言实验目的1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。2、掌握用随机数生成满足一定条件的指令地址流的方法。3、掌握页面置换的模拟方法。实验要求与内容1、采用一种熟悉的语言，如C、PASCAL或C++等，编制程序，最好关键代码采用C/C++，界面设计可采用其它自己喜欢的语言。2、模拟操作系统采用OPT、FIFO和LRU算法进行页面置换的过程。3、设程序中地址范围为0到32767，采用随机数生成256个指令地址，满足50%的地址是顺序执行，25%向前跳，25%向后跳。为满足上述条件，可采取下列方法：设d0=10000，第n个指令地址为dn，第n+1个指令地址为dn+1，n的取值范围为0到255。每次生成一个1到1024范围内的随机数a，如果a落在1到512范围内，则dn+1=dn+1。如果a落在513到768范围内，则设置dn+1为1到dn范围内一个随机数。如果a落在769到1024范围内，则设置dn+1为dn到32767范围内一个随机数。例如：srand();初始化一个随机函数。a[0]＝10*rand()/32767*255+1;a[1]=10*rand()/32767*a[0]…语句可用来产生a[0]与a[1]中的随机数。或采用以下方式：（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分C：25%的指令是均匀分布在后地址部分具体的实施方法是：A：在[0，319]的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1的指令C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m'D：顺序执行一条指令，其地址为m'+1E：在后地址[m'+2，319]中随机选取一条指令并执行F：重复步骤A-E，直到320次指令（2）将指令序列变换为页地址流设：页面大小为1K；用户内存容量4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条-第9条指令为第0页（对应虚存地址为[0，9]）第10条-第19条指令为第1页（对应虚存地址为[10，19]）………………第310条-第319条指令为第31页（对应虚存地址为[310，319]）按以上方式，用户指令可组成32页。4、页面大小的取值范围为1K，2K，4K，8K，16K。按照页面大小将指令地址转化为页号。对于相邻相同的页号，合并为一个。5、分配给程序的内存块数取值范围为1块，2块，直到程序的页面数。6、分别采用OPT、FIFO和LRU算法对页号序列进行调度，计算出对应的缺页中断率。7、打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。8、分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同的页面置换算法的调度性能。9、在上机实现该程序之后，要求写出实验报告，其中包括实验名称、实验目的、实验内容、程序的主要流程图、实验心得和主要源程序清单等。四、需求分析：置换算法内存中没有空闲页面时候被调用。它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率最低的页，将它们移出内存。所以，我们有必要通过一系列客观数据，通过三种常用的页面置换算法的优劣比较，来体会到缺页率。五、详细设计1.流程图算法设计:OPT算法:理想型淘汰算法该算法淘汰在访问传中将来再也不出现的或是在离当前最远的位置上出现的页。开始开始缺页?从访问序列中获得目标页面缺页?从访问序列中获得目标页面 NY在内存块中找出以后最迟才再次出现的一页,换出此页,换入新页。在内存块中找出以后最迟才再次出现的一页,换出此页,换入新页。访问序列空?访问序列空? N Y结束结束FIFO算法:先进先出算法FIFO算法访问序列空?在内存块中找出最早进入的一页,换出此页,换入新页。开始缺页?从访问序列中获得目标页面总是选择在内存驻留时间最长的一页淘汰访问序列空?在内存块中找出最早进入的一页,换出此页,换入新页。开始缺页?从访问序列中获得目标页面 N YY结束Y结束LRU算法:最近最久未使用页面置换算法当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页先淘汰,该算法的依据是如果某一页被访问了,则他可能马上还要被访问。结束访问序列空?在内存块中找出上次访问时间最久之前的一页,换出此页,换入新页。开始缺页?从访问序列中获得目标页面结束访问序列空?在内存块中找出上次访问时间最久之前的一页,换出此页,换入新页。开始缺页?从访问序列中获得目标页面 N Y NY2.程序源代码/*******************************************************名称：OnBtnFifo*参数：无*功能：先进先出算法FIFO*作者：hgx*日期：2012-6-6******************************************************/voidCMyDlg::OnBtnFifo(){ //TODO:Addyourcontrolnotificationhandlercodehere UpdateData(1); if(m_DataArr!=NULL) { if(m_TotalMem>=m_PageCount) { MessageBox("内存块数大于页面数量,不产生缺页中断！"); } else { //初始化避免干扰 m_ListBox.ResetContent(); m_MemArr=newint[m_TotalMem]; memset(m_MemArr,0,m_TotalMem*4);//按字节清零 m_Page_Count=0; m_Page_Rate=0.0; intpointer=0; for(inti=0;i<m_PageCount;i++) { if(!check(m_DataArr[i])) { m_Page_Count++; m_MemArr[pointer]=m_DataArr[i]; Publish(); pointer=(pointer+1)%m_TotalMem;//指针页面将要占据的内存块。 } else Publish();//存在我们继续更新 } m_Page_Rate=(double)m_Page_Count/m_PageCount; UpdateData(0); } } else MessageBox("随机页面序列尚未产生！");}/*******************************************************名称：OnBtnLru*参数：无*功能：最近最久未使用页面置换算法LRU*作者：hgx*日期：2012-6-6******************************************************/voidCMyDlg::OnBtnLru(){ //TODO:Addyourcontrolnotificationhandlercodehere UpdateData(1); if(m_DataArr!=NULL) { if(m_TotalMem>=m_PageCount) { MessageBox("内存块数大于页面数量,不产生缺页中断！"); } else { //初始化避免干扰 m_ListBox.ResetContent(); m_MemArr=newint[m_TotalMem]; memset(m_MemArr,0,m_TotalMem*4);//按字节清零 m_Page_Count=0; m_Page_Rate=0.0; //****************************************************** intpointer=0; for(inti=0;i<m_PageCount;i++) { if(check(m_DataArr[i])) { Publish();//存在我们继续更新 } else { m_Page_Count++; //有两种可能1内存未满2，内存被占满 //处理情况同FIFO一样 if(pointer<m_TotalMem) { m_MemArr[pointer]=m_DataArr[i]; Publish(); pointer++; } //内存被占满回溯 else { int*temp=newint[m_TotalMem+1];//第m_TotalMem为最近最久未使用页面的下标 memset(temp,0,4*(m_TotalMem+1)); intj=i,pos=0; while(pos<=m_TotalMem) { if(!checkexist(temp,m_DataArr[j])) { temp[pos++]=m_DataArr[j]; } j--; } replace(temp[m_TotalMem],m_DataArr[i]); Publish(); } } } m_Page_Rate=(double)m_Page_Count/m_PageCount; UpdateData(0); } } else MessageBox("随机页面序列尚未产生！");}/*******************************************************名称：OnBtnOpt*参数：无*功能：理想型淘汰算法OPT*作者：hgx*日期：2012-6-6******************************************************/voidCMyDlg::OnBtnOpt(){ //TODO:Addyourcontrolnotificationhandlercodehere UpdateData(1); if(m_DataArr!=NULL) { if(m_TotalMem>=m_PageCount) { MessageBox("内存块数大于页面数量,不产生缺页中断！"); } else { //初始化避免干扰 m_ListBox.ResetContent(); m_MemArr=newint[m_TotalMem]; memset(m_MemArr,0,m_TotalMem*4);//按字节清零 m_Page_Count=0; m_Page_Rate=0.0; //****************************************************** intpointer=0; for(inti=0;i<m_PageCount;i++) { if(check(m_DataArr[i])) { Publish();//存在我们继续更新 } else { m_Page_Count++;//肯定缺页 //有两种可能1内存未满2，内存被占满 //处理情况同FIFO一样 if(pointer<m_TotalMem) { m_MemArr[pointer]=m_DataArr[i]; Publish(); pointer++; } //内存被占满前向探索思路跟lru相差不大 else { int*temp=newint[m_TotalMem]; memset(temp,0,4*m_TotalMem); intj=i+1,pos=0; while(pos<m_TotalMem&&j<m_PageCount) { if(check(m_DataArr[j])&&(!checkexist(temp,m_DataArr[j])))//目的是求得在内存中哪一个块最久未使用 //且最久未使用放在下标为m_TotalMem-1位置 { temp[pos++]=m_DataArr[j]; } j++; } replace(temp[m_TotalMem-1],m_DataArr[i]); Publish(); delete[]temp; } } } m_Page_Rate=(double)m_Page_Count/m_PageCount; UpdateData(0); } } else MessageBox("随机页面序列尚未产生！"); }/*******************************************************名称：OnBtnRandom*参数：无*功能：产生一随机页面序列*作者：hgx*日期：2012-6-6******************************************************/voidCMyDlg::OnBtnRandom(){ //TODO:AddyourcontrolnotificationhandlercodehereUpdateData(1);//更新数据 if(0==m_PageSize||0==m_TotalMem) MessageBox("输入不合法，请重新输入！"); else{ m_Edit_Random=""; intm_temp=m_PageSize*1024;intm_Num; //采用随机数生成256个指令地址存入一队列中 queue<int>m_Queue; inta,dn=10000; //第一个指令进队列 m_Num=dn/m_temp+1;///从编号为1开始因为内存块以0表示没被占用 m_Queue.push(m_Num);srand((unsigned)time(NULL)); for(inti=0;i<255;i++) { a=1+rand()%1024; if(a<513) dn=dn+1; if((a>512)&&(a<769)) dn=1+rand()%dn; if((a>768)&&(a<1025)) { inttem=32767-dn; dn=dn+rand()%tem; } m_Num=dn/m_temp+1; if(m_Queue.back()!=m_Num) { m_Queue.push(m_Num); } } m_PageCount=m_Queue.size(); CStringCstringTemp; //初始化页面序列内存块序列两个数组以方便算法使用 m_DataArr=newint[m_PageCount]; intj=0; while(!m_Queue.empty()) { CstringTemp.Format("%d",m_Queue.front()); m_Edit_Random+=CstringTemp; m_DataArr[j++]=m_Queue.front(); m_Queue.pop(); } UpdateData(0); }}/*******************************************************名称：check*参数：intnum*功能：查询内存中是否已经有页面num*作者：hgx*日期：2012-6-6******************************************************/boolCMyDlg::check(intnum){ for(inti=0;i<m_TotalMem;i++) { if(m_MemArr[i]==num) returntrue; } returnfalse;}/*******************************************************名称：Publish*参数：无*功能：将内存块的占用情况更新在List中*作者：hgx*日期：2012-6-6******************************************************/voidCMyDlg::Publish(){CStringtemp,result=""; for(inti=0;i<m_TotalMem;i++) {temp.Format("%d",m_MemArr[i]); result+=te