实验三 模拟操作系统的页面置换.doc

院 系：计 算 机 学 院实验课程： 操作系统实验项目：模拟操作系统的页面置换指导老师： 陈红英老师 开课时间：2011 2012年度第 2学期专 业：网络工程班 级：10级学 生：yuth学 号：*华南师范大学教务处一、综合设计实验题目 模拟操作系统的页面置换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(); 初始化一个随机函数。 a0 10*rand()/32767*255+1;a1=10*rand()/32767*a0语句可用来产生a0与a1中的随机数。或采用以下方式：（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在0，319的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址0,m+1中随机选取一条指令并执行，该指令的地址为m D：顺序执行一条指令，其地址为m+1 E：在后地址m+2，3 19中随机选取一条指令并执行 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、 分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同的页面置换算法的调度性能。 二、中文摘要 这次实验是模拟操作系统的页面置换，分别用先进先出算FIFO、最近最久未使用算法LRU和最佳淘汰算法OPT等三种置换算法来管理管理内存块，并打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。最后对不同算法的调度性能。三、关键词 页面置换 FIFO LRU OPT四、前言本实验的目的及要求1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。 2、掌握用随机数生成满足一定条件的指令地址流的方法。 3、掌握页面置换的模拟方法。 五、实验设计 （一）、需求分析1、 用一种熟悉的语言，如C、PASCAL或C+等，编制程序。2、 分别采用OPT、FIFO和LRU算法对页号序列进行调度。（二）、设计流程1、 根据实验目标，明确实验的具体任务；2、 编写程序实现页面置换；3、 运行程序，调试；4、 记录并分析实验结果。（二）、关键技术根据实验要求，使得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 范围内一个随机数。开一个数组address来记录指令地址，另一个数组pagenum记录指令地址转换后所在的页，这样就得到原始程序的页面访问序列。然后将相邻相同的页号合并。（三）详细设计 1、设计算法流程图2、数据结构/程序类，指明程序地址范围和指令数class Programpublic:int AddressSize; /（0AddressSize） int StructureNum; /指令数public:Program(int m,int i)AddressSize=m;StructureNum=i; ;/内存块节点类class PhysicsPageNode public:int have; /是否有页面占领该内存块，-1代表没有，1代表有int Page_Num; /第几页占领该内存块int Elapsed_Time; /内存块的存在时间PhysicsPageNode *next; public:PhysicsPageNode()have=-1;Elapsed_Time=0; /刚生成时内存块的存在时间为0next = NULL;/模拟操作系统的页面置换类class PageReplacement private:int *address; /存储所有指令的地址 int *pagenum; /存储所有指令地址所在的页float instr_sum; /指令数public:int pagesize; /页面大小(字节)int mem_sum; /程序获得的内存块数public:void transform(Program p); /分析程序p，得到指令页面序列,初始化有关成员PhysicsPageNode* getphysage(PhysicsPageNode* pp,int pn); /检查指定页是否已在内存块中PhysicsPageNode* getfreepage(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-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 = new int instr_sum;cout原程序页面链:endl;address0=10000; /指令起始地址pagenum0=address0/pagesize; /指令地址所在的页coutpagenum0ends;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);else if(a=1024) /向后跳addressi = addressi-1 + rand()%(p.AddressSize-addressi-1);/求得指令所在的页q=addressi/pagesize;r=addressi%pagesize; if(r)pagenumi=q;else pagenumi=q-1;coutpagenumiends; /输出指令所在的页面coutendlendl;/将相邻相同的页号合并int *newpagenum = new int instr_sum; newpagenum0=pagenum0;cout将相邻相同的页号合并为一个后的页面链endl; int j=0; for(i=1;iinstr_sum;i+)if(newpagenumj != pagenumi)j+;newpagenumj=pagenumi; instr_sum = j+1; /新的页面访问串的访问数(j为下标，所以加一) cout新的页面访问串的访问数=instr_sumendl;for(i=0;iinstr_sum;i+) pagenumi = newpagenumi; coutpagenumiends; /输出指令所在的页面coutendlendl;2、FIFO模块先进先出算法：设置缺页中断次数breaktimes，当中断发生时，+1. 获取可用内存块数，根据内存块数，申请对应长度的内存块链。然后进行调度。内存块内有一项Elapsed_Time作为存在时间，每调用一次，所有内存块得存在时间+。刚被调入时间为1.当要淘汰时，比较在内存块中的各存在时间，把存在时间最大的换掉。/内存页的存在时间，为存在时间。void PageReplacement:FIFO() float breaktimes=0;int i,pn;/生成内存页空间PhysicsPageNode *head = new PhysicsPageNode();PhysicsPageNode *p=head,*ppn=NULL; for(i=1;inext=np;p=np; for(i=0;iPage_Num=pn;ppn-Elapsed_Time=1; else /获取空闲页失败.置换存在时间最大的页面ppn=getlongelapsed(head);ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在内存页中。 /什么也不发生/将在内存中的页存在时间+1PhysicsPageNode *copp=head; while(copp!=NULL)copp-Elapsed_Time+;copp=copp-next;/输出算法，页面大小，缺页中断率等。cout页面大小=pagesize 内存块数=mem_sum FIFO 缺页中断率=;cout.precision(2); /输出小数点后两位coutbreaktimes/instr_sumendl;3、LRU模块最近最久未使用页面置换算法（LRU）LRU在固定时间内将各个内存页的存在时间复位，增加计数器counter，每到30将所有内存页存在时间复位。并且每使用一次内存页，将是把存在时间减3个单位，这样存在时间最大的就是最久未使用的。void PageReplacement:LRU() float breaktimes=0;int i,pn;/生成内存页空间PhysicsPageNode *head=new PhysicsPageNode();PhysicsPageNode *p=head,*ppn; for(i=1;inext=np;p=np;int counter=0; /计数器for(i=0;i30)counter=0; /计数器归零PhysicsPageNode *q=head;/内存页存在时间复位while(q!=NULL)q-Elapsed_Time=1;q=q-next;pn=pagenumi; /需要载入的页号ppn=getphysage(head,pn); / 是否存在内存页if(ppn=NULL)/ 载入的页不在内存页中/缺页中断次数+1breaktimes+;/获取空闲页面ppn=getfreepage(head);if(ppn!=NULL) /获取成功ppn-Page_Num=pn;ppn-Elapsed_Time=1; else /获取空闲页失败/存在时间最大的为最久未使用。因为每使用一次是减3个单位的存在时间。 ppn=getlongelapsed(head); ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在内存页中。 ppn-Elapsed_Time=ppn-Elapsed_Time-3;/输出算法，页面大小，缺页中断率等。cout页面大小=pagesize 内存块数=mem_sum LRU 缺页中断率=;cout.precision(2); /输出小数点后两位coutbreaktimes/instr_sumendl;4、OPT模块最优淘汰算法OPT当页面存在时，存在时间参数不变化。当要淘汰一个页时，预读未来50页，并用内存页的存在时间计数。然后淘汰存在时间最短的。计数方法，未来出现1次，将存在时间减3个单位。到时候存在时间值最大的将被淘汰。 void PageReplacement:OPT() float breaktimes=0;int i,pn;/生成内存页空间PhysicsPageNode *head=new PhysicsPageNode();PhysicsPageNode *p=head,*ppn=NULL; 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;PhysicsPageNode *temp;temp=head;/先复位。while(temp!=NULL)temp-Elapsed_Time=1;temp=temp-next;/下面预读未来页面并计数for(;(nextpageendread)&(nextpageElapsed_Time=temp-Elapsed_Time-3;ppn=getlongelapsed(head);ppn-Page_Num=pn;ppn-Elapsed_Time=1;else /载入的页在内存页中。 /在OPT中无需变化。 /输出算法，页面大小，缺页中断率等。cout页面大小=pagesize 内存块数=mem_sum OPT 缺页中断率=;cout.precision(2); /输出小数点后两位coutbreaktimes/instr_sumPage_Num = pn)return tmp; /找到对应的页并返回elsetmp=tmp-next;return NULL; /没找到，返回NULL/检查是否有空的内存块PhysicsPageNode* PageReplacement:getfreepage(PhysicsPageNode* pp)PhysicsPageNode *tmp=pp;while(tmp!=NULL)if(tmp-have = -1)tmp-have=1;return tmp; /找到空的内存块并返回el