20092003025邓剑锐模拟页面置换过程.docx

华南师范大学综合性实验项目指导书院系 软件学院 专业 软件工程 年级 2009 班级 8 姓名 邓剑锐 学号 20092003025 实验课程名称：操作系统实验项目名称：模拟操作系统的页面置换指导教师：刘波华南师范大学计算机科学院实验课程：操作系统 实验名称：模拟操作系统的页面置换 （综合实验）第一部分 实验内容1实验目标1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。2、掌握用随机数生成满足一定条件的指令地址流的方法。3、掌握页面置换的模拟方法。2. 实验任务1、 用一种熟悉的语言，如C、PASCAL或C+等，编制程序。2、 分别采用OPT、FIFO和LRU算法对页号序列进行调度。3. 实验设备及环境PC；C/C+等编程语言。4. 实验主要步骤(1) 根据实验目标，明确实验的具体任务；(2) 编写程序实现页面置换；(3) 设计实验数据并运行程序、记录运行的结果；(4) 分析实验结果；(5) 实验后的心得体会。第二部分 问题及算法1. 问题描述（学生填）1、 模拟操作系统采用OPT、FIFO和LRU算法进行页面置换的过程。2、 设程序中地址范围为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范围内一个随机数。3、 页面大小的取值范围为1K，2K，4K，8K，16K。按照页面大小将指令地址转化为页号。对于相邻相同的页号，合并为一个。4、 分配给程序的内存块数取值范围为1块，2块，直到程序的页面数。5、 分别采用OPT、FIFO和LRU算法对页号序列进行调度，计算出对应的缺页中断率。6、 打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。7、 分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同的页面置换算法的调度性能。2.一般思路（学生填） 3. 算法实现的关键点（学生填） 1. 分析程序获得页面序列。Dn为地址，D0=1000；Dn的地址获取方法：循环随机一个数a1,1000;落在1-500，Dn=D（n-1）+1，501-750，Dn 为1D（n-1）的随机数。如果a落在751-1000，Dn为D（n-1）到所分析程序地址大小（32767）。然后根据页面大小，将各指令地址化为页面号。 /分析程序，得到指令页面序列void DistriPro(Program p)Sleep(10);srand(time(0);int a;/初始化program_list0.Address=10000;program_list0.pagenum=program_list0.Address/pagesize;/程序页面链for(int i=1;ip.StructureNum;i+)a=rand()%1000;if(a500)program_listi.Address=program_listi-1.Address+1;int ttem=program_listi.Address/pagesize;int ttem2=program_listi.Address%pagesize;if(ttem2)program_listi.pagenum=ttem;else program_listi.pagenum=ttem-1;else if(a750)program_listi.Address=1+rand()%program_listi-1.Address;int ttem=program_listi.Address/pagesize;int ttem2=program_listi.Address%pagesize;if(ttem2)program_listi.pagenum=ttem;else program_listi.pagenum=ttem-1;else if(a0)program_listi.pagenum=ttem;else program_listi.pagenum=ttem-1;coutprogram_listi.pagenumends;coutendl;2. 算法先进先出：设置缺页中断次数breaktime，当中断发生时，+1. 获取可用物理块数，根据物理块数，申请对应长度的内存块链。然后进行调度。物理块内有一项Elapsed_Time作为存在时间，每调用一次，所有物理块得存在时间+。刚被调入时间为1.当要淘汰时，比较在内存块中的各存在时间，把存在时间最大的换掉。/FIFO.物理页的存在时间，为存在时间。void FIFO() float breaktime=0;int i,pn;/生成物理页空间Physics_Page *head=new Physics_Page(-1,0);Physics_Page *p=head,*pp=head,*ppn; for(i=1;inext=np; p=np; /物理页for(i=0;iPage_Num=pn;ppn-Elapsed_Time=1; else /获取空闲页失败.置换存在时间最大的页面ppn=getlongelapsed(pp);ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在物理页中。/什么也不发生/将在内存中的页存在时间+1Physics_Page *copp,*coppn;copp=head;coppn=pp-next;while(copp!=NULL)copp-Elapsed_Time+;copp=coppn;if(copp!=NULL)coppn=copp-next;cout页面大小=pagesize 内存块数=rougenum FIFO 缺页中断率=;cout.precision(2); /输出小数点后两位coutbreaktime/struc_numnext;while(pp!=NULL)delete pp;pp=ppn;if(pp!=NULL)ppn=pp-next;pp=NULL;ppn=NULL;head=NULL;3. LRU 跟FIFO差不多，只是在固定时间内将各个物理页的存在时间归位，增加计数器，counter，每到30将所有物理页存在时间归位。并且每使用一次物理页，将是把存在时间-3这样存在时间最大的就是最久未使用的。void LRU() float breaktime=0;int i,pn;/生成物理页空间Physics_Page *head=new Physics_Page(-1,0);Physics_Page *p=head,*pp=head,*ppn; for(i=1;inext=np; p=np; /物理页int counter=0; /计数器for(i=0;i30)counter=0; /计数器归零Physics_Page *qq=head;/物理页存在时间归位while(qq!=NULL)qq-Elapsed_Time=1;qq=qq-next;pn=program_listi.pagenum; /需要载入的页号ppn=getphysage(pp,pn); / 是否存在物理页if(ppn=NULL)/ 载入的页不在物理页中/缺页中断次数+1breaktime=breaktime+1;/获取空闲页面ppn=getfreepage(pp);if(ppn!=NULL) /获取成功ppn-Page_Num=pn;ppn-Elapsed_Time=1; else /获取空闲页失败/存在时间最大的为最久未使用。因为每使用一次是-3存在时间。与FIFO相反。ppn=getlongelapsed(pp); ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在物理页中。ppn-Elapsed_Time=ppn-Elapsed_Time-3;/输出缺页中断率，调用算法等然后释放物理页。同FIFO结尾4. OPT 当页面存在时，存在时间参数不变化。当要淘汰一个页时，预读 未来50页，并用物理页的存在时间计数。然后淘汰存在时间最短的。计数方法，未来出现1次，将存在时间-3.到时候存在时间值最大的将被淘汰。 void OPT() float breaktime=0;int i,pn;/生成物理页空间Physics_Page *head=new Physics_Page(-1,0);Physics_Page *p=head,*pp=head,*ppn; for(i=1;inext=np; p=np; /物理页for(i=0;iPage_Num=pn;ppn-Elapsed_Time=1; else /获取空闲页失败/在这里增加预读未来50个页面计数。/int nextpage=i+1; /从下一页开始算。int endread=i+50;int nextpagenum;Physics_Page *temp;temp=head;/归位先。while(temp!=NULL)temp-Elapsed_Time=1;temp=temp-next;/下面预读未来页面并计数for(;(nextpageendread)&(nextpageElapsed_Time=temp-Elapsed_Time-3;ppn=getlongelapsed(pp);ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在物理页中。/在OPT中无需变化。/输出算法，页面大小，缺页中断率等。/释放物理页第三部分 实验结果与分析1. 实验数据及结果（学生填）实验测试：物理页大小：K1 2 4 8 16 物理页数目：块 1 32767/页面大小 +1 主函数如下： void main()int i=0,j=1;Program a(32767,254);for(i=1;i32;i=2*i)coutiendl;pagesize=1024*(i);coutpagesizeendl;int p=(a.AddressSize/pagesize);float tem=a.AddressSize%pagesize;if(tem)tem=1;p=p+tem;DistriPro(a);for(j=1;j=p;j+)rougenum=j; /coutjendl;FIFO();LRU();OPT();2. 实验分析及结论（学生填） 根据上述主函数得出的数据：分析与结果：1页面大小越小，物理块越少，缺页中断率越高。2当供应的物理块数达到所需最大时，不论FIFO，LRU还是OPT，缺页中断率最低并保持不变。3 在一般情况下，LRU缺页中断率低于FIFO，但OPT必定不高于前面两种置换算法。OPT算法最优。第四部分 心得与展望1. 自我评价及心得体会（学生填）依照实验要求，完成了所有功能。包括程序的页面序号生成，FIFO，LRU和OPT算法的调度。难点在于理解实验要求，其三种调度算法实现都比较简单，而且FIFO和LRU都非常类似。因为可预知程序页码序列，OPT算法也可以实现。2. 展望（学生填）通过本次实验，我掌握了计算机页面置