实验三 模拟操作系统的页面置换文档格式.docx

1、B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是：在0，319的指令地址之间随机选取一起点m 顺序执行一条指令，即执行地址为m+1的指令 在前地址0,m+1中随机选取一条指令并执行，该指令的地址为mD：顺序执行一条指令，其地址为m+1 E：在后地址m+2，3 19中随机选取一条指令并执行 F：重复步骤A-E，直到320次指令 （2）将指令序列变换为页地址流 设：页面大小为1K；用户内存容量4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第 0 条-第 9 条指令为第0页（对应

2、虚存地址为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、 分析页面大小和分配给程序的内存块数对缺页中断率的影响。分

3、析不同的页面置换算法的调度性能。二、中文摘要 这次实验是模拟操作系统的页面置换，分别用先进先出算FIFO、最近最久未使用算法LRU和最佳淘汰算法OPT等三种置换算法来管理管理内存块，并打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。最后对不同算法的调度性能。三、关键词 页面置换 FIFO LRU OPT四、前言 本实验的目的及要求1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。2、掌握用随机数生成满足一定条件的指令地址流的方法。3、掌握页面置换的模拟方法。五、实验设计 （一）、需求分析1、用一种熟悉的语言，如C、PASCAL或C+等，编制程序。2、分别采用OP

4、T、FIFO和LRU算法对页号序列进行调度。（二）、设计流程1、根据实验目标，明确实验的具体任务；2、编写程序实现页面置换；3、运行程序，调试；4、记录并分析实验结果。（二）、关键技术 根据实验要求，使得50%的指令地址是顺序执行，25%向前跳，25% 向后跳。可采取下列方法：开一个数组address来记录指令地址，另一个数组pagenum记录指令地址转换后所在的页，这样就得到原始程序的页面访问序列。然后将相邻相同的页号合并。（三）详细设计 1、设计算法流程图2、数据结构/程序类，指明程序地址范围和指令数class Programpublic: int AddressSize; /（0Addr

5、essSize） int StructureNum; /指令数 Program（int m,int i） AddressSize=m; StructureNum=i; ;/内存块节点类class PhysicsPageNode int have; /是否有页面占领该内存块，-1代表没有，1代表有 int Page_Num; /第几页占领该内存块 int Elapsed_Time; /内存块的存在时间 PhysicsPageNode *next; PhysicsPageNode（） have=-1; Elapsed_Time=0; /刚生成时内存块的存在时间为0 next = NULL;/模拟操

6、作系统的页面置换类class PageReplacement private: int *address; /存储所有指令的地址 int *pagenum; /存储所有指令地址所在的页 float instr_sum; int pagesize; /页面大小（字节） int mem_sum; /程序获得的内存块数 void transform（Program p）; /分析程序p，得到指令页面序列,初始化有关成员 PhysicsPageNode* getphysage（PhysicsPageNode* pp,int pn）; /检查指定页是否已在内存块中 PhysicsPageNode* ge

7、tfreepage（PhysicsPageNode* pp）; /检查是否有空的内存块 PhysicsPageNode* getlongelapsed（PhysicsPageNode* pp）; /获得最长时间没访问的内存块 void FIFO（）; /先进先出算法 void LRU（）; /最近最久未使用算法 void OPT（）; /最佳淘汰算法六、实验实现（一）、实验主要硬件软件环境 32位PC机，VC+6.0（二）、主要功能模块分析1、获得页号序列模块分析程序指令，获得页面序列。Dn为地址，D0=10000；Dn的地址获取方法：循环随机一个数a1,1024;落在1-512，Dn=D（n

8、-1）+1，513-768，Dn 为1D（n-1）的随机数。如果a落在769-1024，Dn为D（n-1）到所分析程序地址大小（32767）。然后根据页面大小，将各指令地址化为页面号。最后将相邻相同的页号合并。/*分析程序，功能：得到指令页面序列。入口参数：一个程序类，指明程序地址范围和指令数。*/void PageReplacement:transform（Program p） Sleep（10）; srand（time（0）; int a,q,r; /初始化 instr_sum=p.StructureNum; address = new int instr_sum; pagenum = n

9、ew int instr_sum; cout原程序页面链:endl; address0=10000; /指令起始地址 pagenum0=address0/pagesize; /指令地址所在的页pagenum0ends; for（int i=1;iinstr_sum;i+） a = 1 + rand（）%1024; if（a=512） /顺序执行 addressi=addressi-1+1; else if（a=768） /向前跳 addressi=1 + rand（）%（addressi-1）;=1024） /向后跳 addressi = addressi-1 + rand（）%（p.Addr

10、essSize-addressi-1）; /求得指令所在的页 q=addressi/pagesize; r=addressi%pagesize; if（r） pagenumi=q; else pagenumi=q-1; coutpagenumi /输出指令所在的页面endl /将相邻相同的页号合并 int *newpagenum = new int instr_sum; newpagenum0=pagenum0;将相邻相同的页号合并为一个后的页面链 int j=0; for（i=1;i+） if（newpagenumj != pagenumi） j+; newpagenumj=pagenumi

11、; instr_sum = j+1; /新的页面访问串的访问数（j为下标，所以加一）新的页面访问串的访问数=instr_sumnext=np; p=np; pn=pagenumi; /需要载入的页号（这里还没简化） ppn=getphysage（head,pn）; / 是否存在内存页 if（ppn=NULL） / 载入的页不在内存页中 /缺页中断次数+1 breaktimes+; /获取空闲页面 ppn=getfreepage（head）; if（ppn!=NULL） /获取成功 ppn-Page_Num=pn;Elapsed_Time=1; else /获取空闲页失败.置换存在时间最大的页面

12、 ppn=getlongelapsed（head）; else /载入的页在内存页中。 /什么也不发生 /将在内存中的页存在时间+1 PhysicsPageNode *copp=head; while（copp!=NULL） copp-Elapsed_Time+; copp=copp-next; /输出算法，页面大小，缺页中断率等。页面大小=pagesize 内存块数=mem_sum FIFO 缺页中断率=; cout.precision（2）; /输出小数点后两位breaktimes/instr_sum30） counter=0; /计数器归零 PhysicsPageNode *q=head

13、; /内存页存在时间复位 while（q! q- q=q- /需要载入的页号 if（ppn=NULL）/ 载入的页不在内存页中 else /获取空闲页失败 /存在时间最大的为最久未使用。因为每使用一次是减3个单位的存在时间。 ppn-Elapsed_Time=ppn-Elapsed_Time-3; LRU 缺页中断率=4、OPT模块最优淘汰算法OPT当页面存在时，存在时间参数不变化。当要淘汰一个页时，预读未来50页，并用内存页的存在时间计数。然后淘汰存在时间最短的。计数方法，未来出现1次，将存在时间减3个单位。到时候存在时间值最大的将被淘汰。OPT（） /缺页中断次数+1 breaktimes

14、=breaktimes+1; /在这里增加预读未来50个页面计数。 int nextpage=i+1; /从下一页开始算。 int endread=i+50; int nextpagenum; PhysicsPageNode *temp; temp=head; /先复位。 while（temp! temp- temp=temp- /下面预读未来页面并计数 for（;（nextpageendread）&（nextpageElapsed_Time=temp- / 在OPT中无需变化。 OPT 缺页中断率=5、辅助模块/检查指定页是否在已内存块中PhysicsPageNode* PageReplac

15、ement:getphysage（PhysicsPageNode* pp,int pn） PhysicsPageNode *tmp=pp; while（tmp! if（tmp-Page_Num = pn） return tmp; /找到对应的页并返回 else tmp=tmp- return NULL; /没找到，返回NULL/检查是否有空的内存块getfreepage（PhysicsPageNode* pp）have = -1） tmp-have=1; /找到空的内存块并返回/查找存在时间最长的内存块并返回getlongelapsed（PhysicsPageNode* pp） PhysicsPageNode *tmp=pp,*t=pp;Elapsed_Time t-Elapsed_Time） t=tmp; tmp=tmp- return t;七、结果及结果分析 （一）测试数据1、程序中地址范围0 327672、页面大小（k）1K，2K，4K，8K，16K3、分配给程序的内存块数1 块，2 块直到程序的页面数。4、算法OPT、FIFO 和LRU （二）测试结果记录分析以上的实验结果可知：1、一般情况下，当页面大小一定时，分配给程序的内存块数越多，缺页中断率的越小；当分配给程序的内存块数一定时，页面大小越大，缺页中