山东大学操作系统实验七内存页面置换算法问题.doc

计算机科学与技术学院操作系统实验报告实验题目：内存页面置换算法问题 假请在以上示例实验程序中补充“增强二次机会”等置换算法的模拟程序。输入不同的内存页面引用串和实存帧数,观察并分析其页面置换效果和性能,并将其与 LRU 和FIFO 算法进行比较。改进以上示例实验程序,使之能够随机的产生内存页面引用串,以便能动态的观测各种置换算法的性能。实验目的：加深对于存储管理的了解,掌握虚拟存储器的实现原理;观察和了解重要的页面置换算法和置换过程。练习模拟算法的编程技巧,锻炼分析试验数据的能力。硬件环境： Inter(R)Core(TM)i5-3210M CPU 2.50GHz 内存：4GB 硬盘：500G软件环境： XUbuntuLinux 操作系统 Gnome 桌面 2.18.3 BASH_VERSION=3.2.33(1)-release gcc version 4.1.2 gedit 2.18.2 OpenOffice 2.3 实验步骤： 1、问题分析:示例实验程序中模拟两种置换算法:LRU 算法和 FIFO 算法能对两种算法给定任意序列不同的页面引用串和任意帧实内存块数的组合测试,显示页置换的过程。能统计和报告不同置换算法情况下依次淘汰的页号、缺页次数(页错误数)和缺页率。比较两种置换算法在给定条件下的优劣。为了能方便的扩充页面置换算法,更好的描述置换过程,示例实验程序采用了 C+语言用 Replace 类描述了置换算法及其属性。2、算法设计说明如下：1.二次机会算法描述(Clock):将帧表设置为循环表,由RefBit数组记录某一页是否被引用(0表示未被引用,1表示被引用)。当访问一页时,首先从帧表中检查此页是否在实存,若在将其引用位设置为1;若不在,在循环帧表中循序查找,若某页引用位为1,则将其设置为0，然后继续查找；若某页引用位为0，将其替换。若查找一圈，没有替换页（所有引用位均为1），则将全部引用位设置为0。 2.增强的二次机会算法（Eclock）：将帧表设置为循环表，由RefBit数组记录某页是否被引用,ModBit数组记录某页是否被修改。当访问一页时,首先从帧表中检查此页是否在实存,若在将引用位设置为1,并根据输入修改修改位;若不在,第一次在帧表中查找是否有属性为(0,0)的页,若有则将其替换,并修改引用位和修改位;若没有这种页,第二次查找是否有属性为(0,1)或(1,0)的页,若有将其替换,并修改引用位和修改位;若没有这种页,将所有引用位置为0,重复第二次查找操作。 3.最少使用页替换算法(Lfu):设置accout数组记录帧表中每一页被引用次数。当访问一页时,首先从帧表中检查此页是否在实存,若在将其计数加1;若不在,查找计数最小的页将其替换,并将当前页的计数置为1;4.最多使用页替换算法(Mfu):设置accout数组记录帧表中每一页被引用次数。当访问一页时,首先从帧表中检查此页是否在实存,若在将其计数加1;若不在,查找计数最大的页将其替换,并将当前页的计数置为1;3、开发调试过程：在shell命令行下运行make vmrpg+ -w -g -c vmrp.ccg+ vmrp.o -o vmrp$ ./vmrpPlease input page numbers :12Please input reference page string :1 2 3 4 1 2 5 1 2 3 4 5Please input page frames :3 运行截图如下：附件：vmrp.h#include #include #include using namespace std;class Replacepublic:Replace();Replace();void InitSpace(char * MethodName); /初始化页号记录void Report(void); / 报告算法执行情况void Fifo(void); /先进先出算法void Lru(void); /最近最旧未用算法void Clock(void); /时钟(二次机会）置换算法void Eclock(void); /增强二次机会置换算法void Lfu(void); /最不经常使用置换算法void Mfu(void); /最经常使用置换算法private:int * ReferencePage ; /存放要访问到的页号int * EliminatePage ; /存放淘汰页号int * PageFrames ; /存放当前正在实存中的页号int PageNumber; /访问页数int FrameNumber; /实存帧数int FaultNumber; /失败页数int * Referencebit;int * count;int * Modifybit;/vmrp.c#include vmrp.hReplace:Replace() int i; cout PageNumber; ReferencePage = new intsizeof(int) * PageNumber; EliminatePage = new intsizeof(int) * PageNumber; cout Please input reference page string :; for (i = 0; i ReferencePagei; cout FrameNumber; PageFrames = new intsizeof(int) * FrameNumber; Referencebit=new intsizeof(int) * FrameNumber; count=new intsizeof(int)*FrameNumber; Modifybit=new intsizeof(int)*FrameNumber;Replace:Replace()void Replace:InitSpace(char * MethodName) int i; cout endl MethodName endl; FaultNumber=0;/引用还未开始,-1表示无引用页 for (i = 0; i PageNumber; i+) EliminatePagei = -1; for(i = 0; i FrameNumber; i+) PageFramesi = -1; Referencebiti=0; counti=0; Modifybiti=0; /分析统计选择的算法对于当前输入的页面走向的性能void Replace:Report(void)/报告淘汰页顺序 cout endl Eliminate page:; for(int i=0; EliminatePagei!=-1; i+) cout EliminatePagei ;/报告缺页数和缺页率 cout endl Number of page faults = FaultNumber endl; cout setw(6) setprecision(3) ; cout Rate of page faults = 100*(float)FaultNumber/(float)PageNumber %endl;/最近最旧未用置换算法void Replace:Lru(void) int i,j,k,l,next; InitSpace(LRU);/循环装入引用页 for(k=0,l=0; k PageNumber; k+) next=ReferencePagek;/检测引用页当前是否已在实存 for (i=0; i0;j-) PageFramesj = PageFramesj-1; PageFrames0=next; break; if(PageFrames0 = next)/如果引用页已放栈顶，则为不缺页，报告当前内存页号 for(j=0; j=0) cout PageFramesj ; cout 0;j-) PageFramesj= PageFramesj-1; PageFrames0=next; /引用页放栈顶/报告当前实存中页号 for(j=0; j=0) cout PageFramesj =0) cout EliminatePagel+ endl; else cout endl; /分析统计选择的算法对于当前引用的页面走向的性能 Report();/先进先出置换算法void Replace:Fifo(void) int i,j,k,l,next; InitSpace(FIFO); for(k=0,j=l=0; k PageNumber; k+) next=ReferencePagek; for (i=0; iFrameNumber; i+) if(next=PageFramesi) break; if (iFrameNumber) for(i=0; iFrameNumber; i+) cout PageFramesi ; cout endl; continue; FaultNumber+; EliminatePagel= PageFramesj; PageFramesj=next; j = (j+1)%FrameNumber; for(i=0; i=0) cout PageFramesi =0) cout EliminatePagel+ endl; else cout endl; Report();void Replace:Clock(void) int j,i,k,l,next; InitSpace(Clock); for(k=0,j=l=0; k PageNumber; k+) next=ReferencePagek; for (i=0; iFrameNumber; i+) if(next=PageFramesi) Referencebiti=1; break; if (iFrameNumber) for(i=0; iFrameNumber; i+) cout PageFramesi ; cout endl; continue; if(Referencebitj=1) Referencebitj=0; EliminatePagel=PageFramesj; PageFramesj=next; Referencebitj=1; FaultNumber+; j=(j+1)%FrameNumber; for(i=0; i=0) cout PageFramesi =0) cout EliminatePagel+ endl; else cout endl; Report(); void Replace:Eclock (void) int j,i,k,l,next; InitSpace(EClock); for(k=0,j=l=0; k PageNumber; k+) next=ReferencePagek; for (i=0; iFrameNumber; i+) if(next=PageFramesi) Referencebiti=1; counti+; if(counti%2=0) Modifybiti=0; else Modifybiti=1; break; if (iFrameNumber) for(i=0; iFrameNumber; i+) cout PageFramesi ; cout endl; continue; if(Referencebitj=1) Referencebitj=0; if(Modifybitj=1) Modifybitj=0; int min=10*Referencebitj+Modifybitj; int index=j; for(i=0;iFrameNumber;i+) if(10*Referencebiti+Modifybitimin) min=10*Referencebiti+Modifybiti; index=i; EliminatePagel=PageFramesindex; PageFramesindex=next; Referencebitindex=0; Modifybitindex=1; countindex=0; FaultNumber+; j=(j+1)%FrameNumber; for(i=0; i=0) cout PageFramesi =0) cout EliminatePagel+ endl; else cout endl; Report(); void Replace:Lfu(void)int j,i,k,l,next; InitSpace(Lfu); for(k=0,j=l=0; k PageNumber; k+) next=ReferencePagek; for (i=0; iFrameNumber; i+) if(next=PageFramesi) counti+; break; if (iFrameNumber) for(i=0; iFrameNumber; i+) cout PageFramesi ; cout endl; continue; FaultNumber+; int min=count0; int index=0; for(i=0;iFrameNumber;i+) if(countimin) min=counti; index=i; EliminatePagel= PageFramesindex; PageFramesindex=next; countindex=1; for(i=0; i=0) cout PageFramesi =0) cout EliminatePage