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

院系：计算机学院实验课程：操作系统实验项目：模拟操作系统的页面置换指导老师：陈红英老师开课时间：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到327672范围内一个随机数。例如：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、分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同的页面置换算法的调度性能。二、中文摘要这次实验是模拟操作系统的页面置换，分别用先进先出算FIFO、最近最久未使用算法LRU和最佳淘汰算法OPT等三种置换算法来管理管理内存块，并打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。最后对不同算法的调度性能。3三、关键词页面置换FIFOLRUOPT四、前言本实验的目的及要求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、设计算法流程图4程序，提供程序的地址范围和指令数获取页面大小将程序分页获取程序可用内存块数选择算法进行页面调度Programpagesizevoidtransform(Programp);mem_sumFIFO()LRU()OPT()开始结束endstart2、数据结构//程序类，指明程序地址范围和指令数classProgram{public:intAddressSize;//（0~AddressSize）intStructureNum;//指令数public:Program(intm,inti){AddressSize=m;StructureNum=i;}};//内存块节点类classPhysicsPageNode{5public:inthave;//是否有页面占领该内存块，-1代表没有，1代表有intPage_Num;//第几页占领该内存块intElapsed_Time;//内存块的存在时间PhysicsPageNode*next;public:PhysicsPageNode(){have=-1;Elapsed_Time=0;//刚生成时内存块的存在时间为0next=NULL;}};//模拟操作系统的页面置换类classPageReplacement{private:int*address;//存储所有指令的地址int*pagenum;//存储所有指令地址所在的页floatinstr_sum;//指令数public:intpagesize;//页面大小(字节)intmem_sum;//程序获得的内存块数public:voidtransform(Programp);//分析程序p，得到指令页面序列,初始化有关成员PhysicsPageNode*getphysage(PhysicsPageNode*pp,intpn);//检查指定页是否已在内存块中PhysicsPageNode*getfreepage(PhysicsPageNode*pp);//检查是否有空的内存块PhysicsPageNode*getlongelapsed(PhysicsPageNode*pp);//获得最长时间没访问的内存块voidFIFO();//先进先出算法voidLRU();//最近最久未使用算法voidOPT();//最佳淘汰算法};六、实验实现（一）、实验主要硬件软件环境32位PC机，VC++6.0（二）、主要功能模块分析61、获得页号序列模块分析程序指令，获得页面序列。Dn为地址，D0=10000；Dn的地址获取方法：循环随机一个数a[1,1024];落在1-512，Dn=D（n-1）+1，513-768，Dn为1~D（n-1）的随机数。如果a落在769-1024，Dn为D（n-1）~到所分析程序地址大小（32767）。然后根据页面大小，将各指令地址化为页面号。最后将相邻相同的页号合并。/*分析程序，功能：得到指令页面序列。入口参数：一个程序类，指明程序地址范围和指令数。*/voidPageReplacement::transform(Programp){Sleep(10);srand(time(0));inta,q,r;//初始化instr_sum=p.StructureNum;address=newint[instr_sum];//存储所有指令的地址pagenum=newint[instr_sum];cout原程序页面链:endl;address[0]=10000;//指令起始地址pagenum[0]=address[0]/pagesize;//指令地址所在的页coutpagenum[0]ends;for(inti=1;iinstr_sum;i++){a=1+rand()%1024;if(a=512)//顺序执行address[i]=address[i-1]+1;elseif(a=768)//向前跳address[i]=1+rand()%(address[i-1]);elseif(a=1024)//向后跳address[i]=address[i-1]+rand()%(p.AddressSize-address[i-1]);//求得指令所在的页q=address[i]/pagesize;r=address[i]%pagesize;if(r)pagenum[i]=q;elsepagenum[i]=q-1;7coutpagenum[i]ends;//输出指令所在的页面}coutendlendl;//将相邻相同的页号合并int*newpagenum=newint[instr_sum];newpagenum[0]=pagenum[0];cout将相邻相同的页号合并为一个后的页面链endl;intj=0;for(i=1;iinstr_sum;i++){if(newpagenum[j]!=pagenum[i]){j++;newpagenum[j]=pagenum[i];}}instr_sum=j+1;//新的页面访问串的访问数(j为下标，所以加一)cout新的页面访问串的访问数=instr_sumendl;for(i=0;iinstr_sum;i++){pagenum[i]=newpagenum[i];coutpagenum[i]ends;//输出指令所在的页面}coutendlendl;}2、FIFO模块先进先出算法：设置缺页中断次数breaktimes，当中断发生时，+1.获取可用内存块数，根据内存块数，申请对应长度的内存块链。然后进行调度。内存块内有一项Elapsed_Time作为存在时间，每调用一次，所有内存块得存在时间++。刚被调入时间为1.当要淘汰时，比较在内存块中的各存在时间，把存在时间最大的换掉。//内存页的存在时间，为存在时间。voidPageReplacement::FIFO(){floatbreaktimes=0;8inti,pn;//生成内存页空间PhysicsPageNode*head=newPhysicsPageNode();PhysicsPageNode*p=head,*ppn=NULL;for(i=1;imem_sum;i++)//mem_sum:程序获得的内存块数{PhysicsPageNode*np=newPhysicsPageNode();p-next=np;p=np;}for(i=0;iinstr_sum;i++){pn=pagenum[i];//需要载入的页号(这里还没简化)ppn=getphysage(head,pn);//是否存在内存页if(ppn==NULL)//载入的页不在内存页中{//缺页中断次数+1breaktimes++;//获取空闲页面ppn=getfreepage(head);if(ppn!=NULL)//获取成功{ppn-Page_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){