操作系统实验八-请求页

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

实验八请求页【基本信息】姓名:谌浩旗学号:71109424日期:2010/06/10【实验内容】编写程序实现LRU算法及其近似算法,并分析各算法的时间复杂度、空间复杂度和实现难度;通过随机生成页面访问序列,测试所实现算法的的页错误率,并加以比较和分析。【实验目的】通过实验,理解LRU页面置换算法的算法思想及其实现方法,比较各种实现算法的复杂度和实现难度,体会LRU算法与各种近似算法间的区别,并进而加深对虚拟内存概念的理解。【设计思路】1.为了比较各个算法的对于同一测试数据的结果,我们将每个测试函数都设置参数RandSeed,作为rand()函数的种子,这样通过随机获取的数据可以相同,各个函数同时还都有参数MaxMemoryFrames,是模拟的内存最大的页数,和TestNum,指测试实例数,他们的返回值为出错数。2.为了使测试数据一样,还必须设置请求页的范围,这里设置全局变量MaxFrames,使用rand()%MaxFrames所获得请求页帧的值将在0~MaxFrames-1范围内。3.在判断某页是否在内存中时,由于是模拟场景,因此这里只是简单的遍历查找,各个函数的时复杂度都最小为O(n),因此通过比较运行时间来评价这些函数性能在此处不合适。4.对于附加引用算法中,需要在规定时间间隔内定时产生中断,然后将引用位转移到8位字节的最高位。这里没用用多线程来模拟,而是将规定时间间隔模拟为经过一定测试实例数后,更新引用。切这里是设定为每测10次更新,这种办法虽然更系统的中断机制有所差别,但放在此处却还是比较合理的,因为每次请求帧的处理时间基本相同,这些函数只能比较出错率,无法比较运行时间。【主要数据结构及其说明】#includecstdio#includecstring#includecstdlib#includectimeusingnamespacestd;intLRU_Counter(intMaxMemoryFrames,intTestNum,unsignedintRandSeed);intLRU_Stack(intMaxMemoryFrames,intTestNum,unsignedintRandSeed);intAdditionalReferenceBits(intMaxMemoryFrames,intTestNum,unsignedintRandSeed);intSecondChance(intMaxMemoryFrames,intTestNum,unsignedintRandSeed);intMaxFrames;//全局变量,限制了请求帧值的范围intmain(){intMaxMemoryFrames,TestNum;printf(请输入可能出现页帧的数目:);scanf(%d,&MaxFrames);intErrNum[4];while(true){printf(请输入最大内存帧数:);scanf(%d,&MaxMemoryFrames);printf(请输入数据测试数目:);scanf(%d,&TestNum);intRandSeed=time(0);//获取种子ErrNum[0]=LRU_Counter(MaxMemoryFrames,TestNum,RandSeed);ErrNum[1]=LRU_Stack(MaxMemoryFrames,TestNum,RandSeed);ErrNum[2]=AdditionalReferenceBits(MaxMemoryFrames,TestNum,RandSeed);ErrNum[3]=SecondChance(MaxMemoryFrames,TestNum,RandSeed);printf(ErrorRate:LRU_CounterLRU_StackAddRefBitsSecChance\n);printf(%11.2lf%9.2lf%10.2lf%9.2lf\n,(double)ErrNum[0]/TestNum,(double)ErrNum[1]/TestNum,(double)ErrNum[2]/TestNum,(double)ErrNum[3]/TestNum);}return0;}intLRU_Counter(intMaxMemoryFrames,intTestNum,unsignedintRandSeed){int*Frames=newint[MaxMemoryFrames];int*Counter=newint[MaxMemoryFrames];intErrNum=0,//出错帧数TimeCounter=0,//LRU计数器法的计数器frames,//请求的帧值i,min;//记下计数器值最小的帧的位置memset(Counter,0,sizeof(int)*MaxMemoryFrames);memset(Frames,-1,sizeof(int)*MaxMemoryFrames);srand(RandSeed);//下种子while(TestNum--){++TimeCounter;frames=rand()%MaxFrames;//随机获取请求帧min=0;//通过遍历查找请求帧是否在内存中,同时更新minfor(i=0;iMaxMemoryFrames;++i){if(Frames[i]==frames)break;if(Counter[i]Counter[min])min=i;}//请求帧在内存中,更新Counterif(iMaxMemoryFrames)Counter[i]=TimeCounter;//请求帧不再内存中,跟新出错数,置换页,计数器更新else{++ErrNum;Frames[min]=frames;Counter[min]=TimeCounter;}}delete[]Counter;delete[]Frames;returnErrNum;}intLRU_Stack(intMaxMemoryFrames,intTestNum,unsignedintRandSeed){int*Frames=newint[MaxMemoryFrames];int*pre=newint[MaxMemoryFrames];int*post=newint[MaxMemoryFrames];inthead=0,rear=MaxMemoryFrames-1,ErrNum=0,i,frames;for(i=0;iMaxMemoryFrames;++i){Frames[i]=-1;pre[i]=i-1;post[i]=i+1;}srand(RandSeed);while(TestNum--){frames=rand()%MaxFrames;for(i=0;iMaxMemoryFrames;++i)if(Frames[i]==frames)break;if(i==MaxMemoryFrames){++ErrNum;i=rear;Frames[i]=frames;}if(i==head)head=post[i];elsepost[pre[i]]=post[i];if(i==rear)rear=pre[i];elsepre[post[i]]=pre[i];post[i]=head;pre[head]=i;pre[i]=-1;head=i;}delete[]Frames;delete[]pre;delete[]post;returnErrNum;}intAdditionalReferenceBits(intMaxMemoryFrames,intTestNum,unsignedintRandSeed){intErrNum=0,i,frames,min,count=0;int*Frames=newint[MaxMemoryFrames];int*TmpReference=newint[MaxMemoryFrames];//临时引用位__int8*HisReference=new__int8[MaxMemoryFrames];//8为历史引用位memset(Frames,-1,sizeof(int)*MaxMemoryFrames);memset(TmpReference,0,sizeof(int)*MaxMemoryFrames);memset(Frames,0,sizeof(__int8)*MaxMemoryFrames);srand(RandSeed);while(TestNum--){++count;frames=rand()%MaxFrames;min=0;for(i=0;iMaxMemoryFrames;++i){if(frames==Frames[i])break;if(HisReference[i]HisReference[min])min=i;}if(iMaxMemoryFrames)TmpReference[i]=1;else{++ErrNum;TmpReference[min]=1;HisReference[min]=0;Frames[min]=frames;}//每10次更形8位历史引用位if(count==10){count=0;for(i=0;iMaxMemoryFrames;++i)HisReference[i]=(HisReference[i]1)+(TmpReference[i]7);memset(TmpReference,0,sizeof(int)*MaxMemoryFrames);}}delete[]Frames;delete[]TmpReference;delete[]HisReference;returnErrNum;}intSecondChance(intMaxMemoryFrames,intTestNum,unsignedintRandSeed){intErrNum=0,cur=0,i,frames;int*Frames=newint[MaxMemoryFrames];int*Reference=newint[MaxMemoryFrames];memset(Frames,-1,sizeof(int)*MaxMemoryFrames);memset(Reference,0,sizeof(int)*MaxMemoryFrames);srand(RandSeed);while(TestNum--){frames=rand()%MaxFrames;for(i=0;iMaxMemoryFrames;++i)if(Frames[i]==frames)break;if(iMaxMemoryFrames)Reference[i]=1;else{++ErrNum;while(Reference[cur]!=0){Reference[cur]=0;cur=(++cur)%MaxMemoryFrames;}Frames[cur]=frames;}}delete[]Frames;delete[]Reference;returnErrNum;}【程序运行时的初值和运行结果】从实验结果可以看到,当测试实例数比较大时,LRU近似算法跟LRU算法的出错率基本相同。【实验体会】同过该实验,更加深入的了解了LRU页置换算法及其近似算法的算法思想及其实现方法,对于虚拟内存的概念更加的清晰起来。

1 / 5
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功