页面置换算法实验报告.doc

操作系统课程设计报告课程名称:操作系统课程设计课程设计题目:页面置换算法学院:计算机科学与技术学院专业:科技小组成员:庞思慧E王蒙 E姚慧乔E朱潮潮E指导老师:邱剑锋目录1 实验目的 32 实验要求 33 实验内容与步骤 34 算法思想 45 模块设计 46 程序设计 57 测试结果 78 结果分析 99 程序代码 910 课程设计小结 (1)通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。(2)掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想,并至少用三种算法来模拟实现。(3)通过对几种置换算法命中率的比较,来对比他们的优缺点。 计算并输出下述各种算法在不同内存容量下的命中率。A先进先出的算法(FIFO)B最近最少使用算法(LRU)C最佳淘汰算法(OPT)(1)通过随机数产生一个指令序列,共320条指令,具体的实施方法是:[0,319]的指令地址之间随机选取一起点M;顺序执行一条指令,即执行地址为M+1的指令;在前地址[0,M+1]中随机选取一条指令并执行,该指令的地址为M’;顺序执行一条指令,其地址为M’+1;在后地址[M’+2,319]中随机选取一条指令并执行;重复A—E,直到执行320次指令。(2)指令序列变换成页地址流页面大小为1K;用户内存容量为4页到32页;用户虚存容量为32K。在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:第0条—第9条指令为第0页(对应虚存地址为[0,9]);第10条—第19条指令为第1页(对应虚存地址为[10,19]);。。。。。。。。。。。。。。。。。。。。。第310条—第319条指令为第31页(对应虚存地址为[310,319]);(3)计算并输出上述各种算法在不同内存容量下的命中率。命中率=1-缺页次数/,若其所要访问的页面不在内存而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区中。但应将哪 个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法。一个好的页面置换算法,应具有较低的页面更换频率。从理论上讲,应将那些以后不再会访问的页面换出,或将那些在较长时间内不会再访问的页面调出。 : 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。(least recently used):算法的基本思想:当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是,如果某页被访问了,则它可能马上还被访问。或者反过来说,如果某页很长时间未被访问,则它在最近一段时间不会被访问。,或许是未来最长时间内不使用的页面,该算法可保证获得最低的淘汰率,但在实际运用中无法实现,可用来评价其他算法的命中率。,FIFO,LRU,OPT,并显示地址流、页面流、页面置换过程和命中率命中率比较结束总模块图入口产生随机数、要调入的页面、离现在处理时间最长的页面、最长的页面初始化页面情况t1<N根据选择的算法进行置换,缺页数加1计算缺页率, //内存页的结构体{intnum;//记录页面号inttime;//页面从未被利用的时间};#defineM320//定义指令条数ProP[M];//产生的随机指令数组voidInput() //产生随机数{ ints; //随机数 int i;srand(time(0));s=rand()%M; //cout<<"\n------------随机产生指令流------------\n";for(i=0;i<M;i+=4) //产生指令队列{p[i].num=s; //任选一指令访问点mp[i+1].num=p[i].num+1; //顺序执行一条指令p[i+2].num=(int)((float)p[i].num*(rand()/(RAND_MAX+))); //执行前地址指令m'p[i+3].num=p[i+2].num+1; //顺序执行一条指令s=(int)((float)(319-p[i+2].num)*(rand()/(RAND_MAX+)))+p[i+2].num;} for(i=