操作系统实验八-请求页

实验八请求页【基本信息】姓名：谌浩旗学号：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页置换算法及其近似算法的算法思想及其实现方法，对于虚拟内存的概念更加的清晰起来。