页面置换 实验 操作系统9页.doc

一、实验名称：模拟操作系统的页面置换二、实验目的：1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。 2、掌握用随机数生成满足一定条件的指令地址流的方法。 3、掌握页面置换的模拟方法。三、实验内容：1、用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 范围内一个随机数。4、 页面大小的取值范围为 1K，2K，4K，8K，16K。按照页面大小将指令地址转化为页号。对于相邻相同的页号，合并为一个。 5、 分配给程序的内存块数取值范围为 1块，2块，直到程序的页面数。 6、 分别采用 OPT、FIFO 和 LRU 算法对页号序列进行调度，计算出对应的缺页中断率。 7、 打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。 8、 分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同的页面置换算法的调度性能。 四、程序主要流程图：实验源程序：主要程序清单：void CMyDlg:run(int start,int end,int* add,int k)/模拟应用程序运行过程int m,m1,m2;while(320!=k)m=rand()%(end-1); /选取地址起点m+;/顺序执行一条指令addk+=m;m1=rand()%m;/在前地址0,m+1中选取一条指令并执行addk+=m1;m1+;/顺序执行一条指令addk+=m1;m2=rand()%(end-m1)+m1; /在后地址m1+1,319中随机选取一条指令并执行addk+=m2;int CMyDlg:addresstopage(int* add,int* pag,int k,int size) /地址序列转换成页流for(int i=0;i320;i+)if(addi/(10*size)!=(addi-1/(10*size)pagk+=addi/(10*size); return k;int CMyDlg:fifo(int *num,int size,int &count,int len) /先来先服务int m32,flag=0;for(int i=0;ilen;i+)if(isize)mi=numi;count+;else bool exist=false;for(int j=0;jsize;j+)if(mj=numi)exist=true;break;if(!exist)if(flagsize)mflag+=numi;count+;elseflag=0;mflag+=numi;count+;return count;int CMyDlg:lru(int *num,int size,int &count,int len) /最近最久未使用置换算法int m32,m232,max,mark;for(int i=0;ilen;i+)if(isize)mi=numi;count+;for(int k=0;k=0;j-)if(mk=numj)m2k=i-j;break;max=-1;for(k=0;ksize;k+)if(maxm2k)max=m2k;mark=k;bool exist=false;for(int j=0;jsize;j+)if(mj=numi)exist=true;break;if(!exist)mmark=numi;count+;return count;int CMyDlg:opt(int *num,int size,int &count,int len) /最佳置换算法int m32,m232,max,mark;for(int i=0;ilen;i+)if(isize)mi=numi;count+;for(int k=0;ksize;k+)for(int j=i;jlen;j+)if(mk=numj)m2k=j-size+1;break;max=-1;for(k=0;ksize;k+)if(maxm2k)max=m2k;mark=k;bool exist=false;for(int j=0;jsize;j+)if(mj=numi)exist=true;break;if(!exist)mmark=numi;count+;return count;void CMyDlg:OnReadme() / TODO: Add your control notification handler code hereCString warn;warn= 如果想分析结果正确,请确保遵守如下原则：n在内存块数和页面大小相同的前提下，至少选择两种及以上的算法来测试，或者在算法相同的前提下，改变内存块数或页面的大小来测试,结果分析中是一个静态的分析;AfxMessageBox(warn);void CMyDlg:OnAnalyse() / TODO: Add your control notification handler code here m_static.SetWindowText( 当内存块数和页面大小一定,而只改变算法时,可以看到：OPT算法的缺页率较小,FIFO次之,LRU最差);五、实验中遇到的问题和实验中的重点1. 利用随机数产生一个指令序列，共320条指令满足程序要求：50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分；使用语句M1=rand()%m;通过循环语句进行指令序列设置初始化。2. 指令序列变换成页地址流，着重于对不同页面大小时对于页面的地址换算。3 FIFO先进先出的算法，LRU最近最少使用算法，OPT最佳淘汰算法的理解对于程序的实现影响很大RAND算法：用软硬件的随面数产生主存中要被替换页的页号。FIFO算法：选择最早装入主存的页作为被替换的页。这种算法实现方便，但不一定正确反映出程序的局部性。LRU算法：选择近期最少访问的页作为被替换页。OPT算法：根据未来实际使用情况将未来的近期里不用的页替换出去。六、实验心得：只有基于对FIFO先进先出的算法，LRU最近最少使用算法，OPT最佳淘汰算法的充分的理解才能在程序设计中掌握其设计思路。在课堂上算算老师出的题目是简单的事情但是当实际动手操作将算法通过程序表达出来并且设计出其对应的缺页中断率。并通过实验结果对于各种算法性能进行分析。就成了一件很富杂的事情。在反复上网查找资料和同学交流程序设计的框架中获得了很多宝贵的解决问题思路