资源描述：
《操作系统实验八-请求页复习过程.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、操作系统实验八-请求页精品文档实验八请求页【基本信息】姓名：谌浩旗学号：71109424日期：2010/06/10【实验内容】编写程序实现LRU算法及其近似算法，并分析各算法的时间复杂度、空间复杂度和实现难度；通过随机生成页面访问序列，测试所实现算法的的页错误率，并加以比较和分析。【实验目的】通过实验，理解LRU页面置换算法的算法思想及其实现方法，比较各种实现算法的复杂度和实现难度，体会LRU算法与各种近似算法间的区别，并进而加深对虚拟内存概念的理解。【设计思路】1.为了比较各个算法的对于同一测试数据的结果，我们将每个测试函数都设置参数RandSeed，作为rand()函数的种子，这样通过随
2、机获取的数据可以相同，各个函数同时还都有参数MaxMemoryFrames，是模拟的内存最大的页数，和TestNum,指测试实例数，他们的返回值为出错数。2.为了使测试数据一样，还必须设置请求页的范围，这里设置全局变量MaxFrames，使用rand()%MaxFrames所获得请求页帧的值将在0～MaxFrames-1范围内。3.在判断某页是否在内存中时，由于是模拟场景，因此这里只是简单的遍历查找，各个函数的时复杂度都最小为O(n)，因此通过比较运行时间来评价这些函数性能在此处不合适。4.对于附加引用算法中，需要在规定时间间隔内定时产生中断，然后将引用位转移到8位字节的最高位。这里没用用多
3、线程来模拟，而是将规定时间间隔模拟为经过一定测试实例数后，更新引用。切这里是设定为每测10次更新，这种办法虽然更系统的中断机制有所差别，但放在此处却还是比较合理的，因为每次请求帧的处理时间基本相同，这些函数只能比较出错率，无法比较运行时间。【主要数据结构及其说明】#include#include#include#includeusingnamespacestd;intLRU_Counter(intMaxMemoryFrames,intTestNum,unsignedintRandSeed);intLRU_Stack(intMa
4、xMemoryFrames,intTestNum,unsignedintRandSeed);intAdditionalReferenceBits(intMaxMemoryFrames,intTestNum,unsignedintRandSeed);intSecondChance(intMaxMemoryFrames,intTestNum,unsignedintRandSeed);intMaxFrames;//全局变量，限制了请求帧值的范围intmain(){intMaxMemoryFrames,TestNum;printf("请输入可能出现页帧的数目：");scanf("%d",&MaxFr
5、ames);收集于网络，如有侵权请联系管理员删除精品文档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]=Addition
6、alReferenceBits(MaxMemoryFrames,TestNum,RandSeed);ErrNum[3]=SecondChance(MaxMemoryFrames,TestNum,RandSeed);printf("ErrorRate:LRU_CounterLRU_StackAddRefBitsSecChance");printf("%11.2lf%9.2lf%10.2lf%9.2lf",(double)ErrNum[0]/TestNum,(double)ErrNum[1]/TestNum,(double)ErrNum[2]/TestNum,(double)ErrNum
7、[3]/TestNum);}return0;}intLRU_Counter(intMaxMemoryFrames,intTestNum,unsignedintRandSeed){int*Frames=newint[MaxMemoryFrames];int*Counter=newint[MaxMemoryFrames];intErrNum=0,//出错帧数TimeCounter=0,//LRU计数器法的计数器f
