页面置换算法实验报告

页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告一、实验目的：设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比较。二、实验内容：虚拟内存页面总数为N，页号从0到N-1物理内存由M个物理块组成页面访问序列串是一个整数序列，整数的取值范围为0到N-1。页面访问序列串中的每个元素p表示对页面p的一次访问页表用整数数组或结构数组来表示符合局部访问特性的随机生成算法1.确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p+1），以及一个范围在0和1之间的值t；2.生成m个取值范围在p和p+e间的随机数，并记录到页面访问序列串中；3.生成一个随机数r，0≤r≤1；4.如果rt，则为p生成一个新值，否则p=(p+1)modN；5.如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。三、实验环境：操作系统：Windows7软件：VC++6.0四、实验设计：本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的数据结构实现，而是根据不同算法的特点用不同的数据结构来实现：1、最佳置换和随机置换所需操作不多，用整数数组模拟内存实现；2、先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内存来实现；3、CLOCK置换和改进的CLOCK置换具有循环队列的特性，故用循环队列模拟内存实现；4、所有算法都是采用整数数组来模拟页面访问序列。页面置换算法实验报告五、数据结构设计：//页面访问序列数组：intref[ref_size];//内存数组：intphy[phy_size];//队列数据结构定义：typedefstructQNode//定义队列数据结构{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//头指针QueuePtrrear;//尾指针}LinkQueue;//定义链表数据结构typedefstructLNode//定义循环链表数据结构{intdata;intflag;//访问位intmodify;//修改位structLNode*next;}LNode,*LinkList;页面置换算法实验报告六、主要函数说明：1、voidset_rand_num()//产生具有局部特性的随机数列；2、intExchange_LNode(LinkList&L,inte,inti)//将链表L中序号为i的结点替换为内容为e的结点；3、boolSearch_LinkList(LinkList&L,inte,int&i)//找到链表L中内容为e的结点，并用i返回其位置，i=1表示第一个非头结点，依次类推；4、voidSearch_LL_Flag(LinkList&L,int&i)//用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点，以此类推；5、voidSet_LL_Flag(LinkList&L,inti)//设置链表L中的序号为i的结点的flag标志为1；6、intSearch_LL_ModifyClock(LinkList&L,int&modify_num)//找到改进的CLOCK算法所需要淘汰的页，用modify_num返回其位置；此函数根据书上给的思路，第一遍扫描A=0且M=0的页面予以淘汰，若失败，则进行第二轮扫描A=0且M=1的页面，第二轮扫描时将所有访问过的页面的访问位A置0；若失败则重复上述两部；7、voidSet_LL_modify(LinkList&L,inti)//设置链表L中的序号为i的结点的modify标志为1；8、boolSearchQueue(LinkQueue&Q,inte,int&i)//寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置；页面置换算法实验报告9、intgetnum(inta,intb)//用b返回元素a在被引用数列中的下一个位置10、voidORA()//实现最佳置换算法，包括判断页面是否在内存中、页面进内存、输出内存状态等内容；11、voidRAND()//随机置换算法12、voidFIFO()//先进先出算法13、voidLRU()//最近最久未使用算法实现最近最久未使用算法的思想是：判断待进入内存的页面，如果与内存中的第一个页面相同，则将它移到最后一个，即标志为最近使用的页；如果与内存中的第二个页面相同，则将它删除，并在队列尾部添加相同元素，即标志为最近使用的页；14、voidCLOCK()//实现CLOCK算法15、voidModified_Clock()//实现改进的CLOCK算法16、intmain()//主函数，调用实现各算法的6个主要函数，并输出各算法的缺页率。七、实验问题回答：1、FIFO算法是否比随机置换算法优越？答：FIFO算法比随机置换算法优越，但优势并不明显。2、LRU算法比FIFO算法优越多少？答：LRU算法FIFO算法的效率要高5%-10%，有理论知识可知，页面访问序列具有局部性，而FIFO算法并不符合实际情况。3、LRU算法和Optimal算法有何差距？答：LRU算法是所有算法中效率最接近Optimal算法的算法，由理论知识可知，Optimal算法是理想的算法，现实中几乎不可能实现，只能作为一种测评标准，LRU算法是效率较高的可实现置换算法，但其硬件要求较高，如果规模较小，则略显麻烦。4、Clock算法和LRU算法有何差距？答：Clock算法和LRU算法从结果看来差距不大，Clock算法是使用软件的方式实现LRU算法中硬件的功能，从而在执行效率上会稍逊色些。八、实验过程结果截图：实验结果截图测评一：页面置换算法实验报告测评二：测评三：页面置换算法实验报告实验过程截图（注：只截取第三次测评，蓝色字体表示产生缺页中断）页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告页面置换算法实验报告九、实验结果分析：1、最佳置换算法效果最佳不论在那组数据中，最佳置换算法的效果都是最好的，且都会比其它算法的性能高出不少。但通过课堂上的学习，我们知道这只是一种理想化算法，但实际上却难于实现，故主要用于算法评价参照。2、随机算法的性能总是最不好的这是由于随机算法每次总是从所有页面中随机挑一个置换出去，但我们知道页面的访问存在着局部性的原理，并不是随机的，因此它的性能较差。3、最近最久未使用算法的性能较好相较于先进先出和两种clock算法，最近最久未使用算法的性能略好，我们测试的数据规模相对较小，相信如果采用更大规模的数据，其优势会更加明显。当从课堂上我们知道要想在实际的应用中实现本算法，用软件的方法速度太慢，影响程序执行效率，如果采用硬件方法实现，则需要增加大量的硬件设备。4、先进先出与clock算法的性能基本相同这是由于两种clock算法遍历链表采用的就是FIFO的方法，而改进的clock算法相比于简单clock算法的优势主要体现在会根据是否被修改进行选择，以减少写回所花费的时间。页面置换算法实验报告十、实验总结：这次实验总体难度不是很大，需要实现的算法数目虽然不少，但基本思路较为相似，因此实现起来也并不是十分困难。通过完成这次实验，除了加深了我对几种策略的理解，锻炼了我的编程能力，另一个巨大的收获就是了解了一些生成测试数据的方法。为了使我们的测试数据更贴近现实，我们引入了工作集的概念，并根据实际使用情况的特点设计出尽可能符合实际情况的随机数生成方案。通过阅读课件再加上自己的理解，我了解了老师的设计思路，感觉这个思路极其巧妙，设计中用到的方法和体现出的很多思想值得我们学习。十一、程序清单：#includeiostream#includewindows.h#includetime.h#includemalloc.h#includeconio.husingnamespacestd;#defineref_size20#definephy_size3intref[ref_size];floatinterrupt[6]={0.0};//intref[ref_size]={0};intphy[phy_size];//////////////////////////////////////////////////////////////////voidset_rand_num()//产生具有局部特性的随机数列{cout页面访问序列：endl;intp=12;inte=4;intm=4;inti=0;intj=0;intn=0;doublet=0.6;inttemp;for(i=0;im;i++,j++){Sleep(1000*i);页面置换算法实验报告srand(time(NULL));temp=rand()%e+p;ref[j]=temp;coutref[j];}for(n=0;n4;n++){Sleep(1000*n);srand(time(NULL));doubler=(double)(rand()%10)/10.0;//coutrendl;if(rt)p=p+int(10*r);elsep=(p+1)%20;for(i=0;im;i++,j++){Sleep(1000*i);srand(time(NULL));temp=rand()%e+p;ref[j]=temp;coutref[j];}}coutendl;}////////////////////////////////////////////////////////////////typedefstructQNode//定义队列数据结构{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//头指针QueuePtrrear;//尾指针}LinkQueue;//定义链表结点typedefstructLNode//定义循环链表数据结构{intdata;intflag;//访问位intmodify;//修改位structLNode*next;页面置换算法实验报告}LNode,*LinkList;//////////////////////////////////////////////////////////////////////////对循环链表的一些操作intCreatList(LinkList&L)//创建循环带有头结点的链表{L=(LinkList)malloc(sizeof(LNode));if(!L)exit(-1);L-next=L;L-flag=0;return1;}intExchange_LNode(LinkList&L,inte,inti)//将链表L中序号为i的结点替换为内容为e的结点{if(L-next==L)exit(-1);LinkListp,q;intj=0;p=(LinkList)malloc(sizeof(LNode));q=(LinkList)malloc(sizeof(LNode));q-data=e;p=L;for(j=0;ji;j++)//使p为待更换结点的前一个结点，故应保证，删除第一个非头结点时i=0，以此类推p=p-next;q-next=p-next-next;p-next=q;q-flag=1;//设置新结点的访问位为1q-modify=0;//设置新结点的修改位为0return1;}intInsert_LNode(LinkList&L,inte)//在循环链表中插入新的结点，从L头结点开始依次向后插入{LinkListp,q;