操作系统原理课外实验报告-虚页替换算法的仿真实现.doc

计算机操作系统原理课外上机实验报告题目：实验名称：虚页替换算法的仿真实现 组长主要任务:（1）整体程序的架构设计；（2）输出函数书写，数据结构选定；（3）LRU、OPT算法的仿真实现；（4）撰写实验报告。组员主要任务:（1）FIFO、CLOCK算法的仿真实现；（2）算法调试及测试；（3）撰写实验报告。1 实验目的1.1 通过实验掌握请求式页面替换理论与算法。1.2 通过设计友好的用户界面仿真页面替换过程。2基础原理和核心设计内容2.1 基础原理2.1.1 FIFO算法总是淘汰最先调入主存的页面，淘汰在主存中驻留时间最长的页面。2.1.2 OPT算法当要调入一页而必须淘汰掉旧页时，应该淘汰以后不再访问的页、或距现在最长时间后要访问的页面。2.1.3 LRU算法淘汰的页面是在最近一段时间内最久未被访问的那一页。2.1.4 CLOCK算法页面被访问时，引用位为1，有页面淘汰是=时，引用位为1的清零，并跳过该页面，淘汰掉引用位为0的页面。2.2 核心设计内容2.2.1 FIFO算法对应函数：void FIFO()建立一个驻留集数组（memery）、一个页面序列数组（page）、和一个进入时间数组（time），利用时间数组与驻留集数组的对应关系，记录驻留集数组中各个页面的进入时间一般为页面序号，在需要替换旧页时，对时间数组进行查找，找到时间最小的（即进入时间最早的页面），然后用新来的页面替换掉这个页面。2.2.2 OPT算法对应函数：void OPT()建立一个驻留集数组（memery）、一个页面序列数组（page）、和一个之后访问时间数组（next），利用时间数组与驻留集数组的对应关系，计算出驻留集中各个页面在还未到来的页面序列中距离下一次访问的时间，在需要替换旧页时，对时间数组进行查找，找到时间最大的（即下一次访问时间最长的页面），然后用新来的页面替换掉这个页面。2.2.3 LRU算法对应函数：void LRU()建立一个驻留集数组（memery）、一个页面序列数组（page）、和一个最近访问时间数组（flag），利用时间数组与驻留集数组的对应关系，每当一个页面进入驻留集时其他页面的最近访问时间就加1，该页面的最近访问时间清零，当需要替换旧页时，对时间数组进行查找，找到时间最大的（即距离最近访问时间最长的页面），然后用新来的页面替换掉这个页面。2.2.4 CLOCK算法对应函数：void Clock()建立一个驻留集数组（memery）、一个页面序列数组（page）、和一个引用位数组（clock），利用时间数组与驻留集数组的对应关系，任何一个页面被访问时引用位置1，当需要替换旧页时，对引用位数组进行查找，遇到引用位为1的就将其清零并且跳过该页面，找到引用位为0的页面，然后用新来的页面替换掉这个页面；如果引用位全为1则将所有的引用位都清零，然后替换掉第一个页面。2.2.5 输出函数对应函数：void print()建立二维中间数组（temp），将二维数组利用循环每行输出20个竖排输出。3数据结构及操作函数设计3.1 全局变量int mSIZE; /驻留集大小，用户手动输入int pSIZE; /页面号序列个数，用户手动输入static int memery10=0; /驻留集中的页号static int page100=0; /页面号序列，有随机生成的随机数赋值static int temp10010=0; /中间数组，用于竖着输出驻留集3.2 FIFO函数void FIFO() int time10=0; /记录进入驻留集的时间 for(i=0;ipSIZE;i+) /判断新页面号是否在驻留集中 for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /如果不在驻留集中 /计算替换次数for(k=0;kmSIZE;k+)/判断驻留集内的值是否有为零的，如果有直接替换到此页面if(memeryk=0)max=k;flag=2;if(flag!=2)/计算被替换的页面for(m=1;mmSIZE;m+)if(timemtimemax&timem!=0)max=m; memerymax=pagei; else cno+;/计算命中次数flag=0; print(count,cno); /输出3.3 LRU 函数void LRU() int flag10=0; /记录页面的访问时间 for(i=0;ipSIZE;i+) /判断新页面号是否在驻留集中 for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; else f=j;for(j=0;jmSIZE;j+)flagj=flagj+1;flagf=0; /刷新页的访问时间 if(k=mSIZE) /如果不在驻留集中 for(j=0,g=0;jmSIZE;j+) if(memeryj!=0)g+;if(g=mSIZE) /如果驻留集已满 count+;/计算替换次数 for(m=1;mflagmax) max=m; memerymax=pagei; for(j=0;jmSIZE;j+) flagj=flagj+1; flagmax=0; /刷新该页的访问时间else/如果驻留集未满 for(k=0;kmSIZE;k+)/判断驻留集内的值是否有为零的，如果有直接替换此页面 if(memeryk=0) max2=k; memerymax2=pagei; for(j=0;jflagmax) max=m;选择出最近访问时间最大的那个页面，将其替换memerymax=pagei，然后赋值给二维数组tempij=memeryj;；之后循环对下一个页面进行判断，直到完成所有的。3.4 OPT 函数void OPT() int next10=0; /记录下一次访问时间 for(i=0;ipSIZE;i+) /判断新页面号是否在驻留集中 for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /如果不在驻留集中 for(j=0,g=0;jmSIZE;j+) if(memeryj!=0) g+; if(g=mSIZE)/如果驻留集已满for(a=0;amSIZE;a+)for(b=i+1;bpSIZE;b+)if(memerya=pageb)nexta=b;/将距离放入对应的距离数组 for(m=1;mnextmax) max=m;memerymax=pagei; count+; /计算替换次数 else/如果驻留集未满 for(k=0;knextmax) max=m;选择出距离最大的那个页面，将其替换memerymax=pagei，然后赋值给二维数组tempij=memeryj;；之后循环对下一个页面进行判断，直到完成所有的。3.5 CLOCK 函数void Clock() int clock10=0; /引用位for(i=0;ipSIZE;i+) /判断新页面号是否在驻留集中 for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+;elsemax=j; if(k=mSIZE) /如果不在驻留集中 max=11;count+;for(k=0;kmSIZE;k+)/判断驻留集内的值是否有为零的，如果有直 /接替换到此页面if(memeryk=0)max=k;flag=2;if(flag!=2)/判断驻留集中各页的引用位情况for(l=0;lmSIZE-1)/驻留集各页的引用位全为1for(l=1;lmSIZE;l+)clockl=0;max=0;memerymax=pagei;clockmax=1; else clockmax=1; cno+; /计算命中次数 flag=0; print(count,cno); /输出3.6 主函数void main() for(i=0;ipSIZE;i+) pagei=rand()%(int)(9-1+1)+1; /随机生成页面号序列（19之间的整数） switch(code) case 1: FIFO();break; /进入FIFO替换算法 case 2: LRU();break; /进入LRU替换算法 case 3: OPT();break; /进入OPT替换算法case 4: Clock();break; /进入Clock替换算法 case 5:system(cls);exit(0); /退出页面替换算法程序替换算法default:printf(错误，请重新输入：); /switch语句选择需要执行的页面替换算法 while (code!=5); /退出后就不再继续执行操作类型FIFOLRUOPTClock退出输入驻留集大小1342输入页面序列大小随机生成页面序列5输出说明：根据选择的不同操作数跳转到不同的算法4测试运行及结果分析4.1 FIFO算法4.1.1 运行4.1.2 分析用户输入驻留集大小为4，页面序列号个数为13，按任意键进入算法选择界面，选择1 FIFO替换算法。第一个页面号为9，驻留集中无内容，直接放入；第二个页面号为7，驻留集中无匹配内容，驻留集未满，直接放入；第三个页面号为6，驻留集中无匹配内容，驻留集未满，直接放入；第四个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第五个页面号为4，驻留集中无匹配内容，驻留集未满，直接放入；第六个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第七个页面号为9，驻留集中有匹配内容9，命中，驻留集不变；第八个页面号为5，驻留集中无匹配内容，最先进入的页面9被替换掉；第九个页面号为6，驻留集中有匹配内容6，命中，驻留集不变；第十个页面号为8，驻留集中无匹配内容，最先进入的页面7被替换掉；第十一个页面号为2，驻留集中无匹配内容，最先进入的页面6被替换掉；第十二个页面号为7，驻留集中无匹配内容，最先进入的页面4被替换掉；第十三个页面号为3，驻留集中无匹配内容，最先进入的页面5被替换掉；这时候已经没有页面了，按任意键继续执行。4.2 LRU算法4.2.1 运行4.2.2 分析用户输入驻留集大小为4，页面序列号个数为13，按任意键进入算法选择界面，选择2LRU替换算法。第一个页面号为9，驻留集中无内容，直接放入；第二个页面号为7，驻留集中无匹配内容，驻留集未满，直接放入；第三个页面号为6，驻留集中无匹配内容，驻留集未满，直接放入；第四个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第五个页面号为4，驻留集中无匹配内容，驻留集未满，直接放入；第六个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第七个页面号为9，驻留集中有匹配内容9，命中，驻留集不变；第八个页面号为5，驻留集中无匹配内容，最近没有被使用的6被替换掉；第九个页面号为6，驻留集中无匹配内容，最近没有被使用的4被替换掉；第十个页面号为8，驻留集中无匹配内容，最近没有被使用的7被替换掉；第十一个页面号为2，驻留集中无匹配内容，最近没有被使用的9被替换掉；第十二个页面号为7，驻留集中无匹配内容，最近没有被使用的5被替换掉；第十三个页面号为3，驻留集中无匹配内容，最近没有被使用的6被替换掉；这时候已经没有页面了，按任意键继续执行。4.3 OPT算法4.1.1 运行4.3.2 分析用户输入驻留集大小为4，页面序列号个数为13，按任意键进入算法选择界面，选择3 OPT替换算法。第一个页面号为9，驻留集中无内容，直接放入；第二个页面号为7，驻留集中无匹配内容，驻留集未满，直接放入；第三个页面号为6，驻留集中无匹配内容，驻留集未满，直接放入；第四个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第五个页面号为4，驻留集中无匹配内容，驻留集未满，直接放入；第六个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第七个页面号为9，驻留集中有匹配内容9，命中，驻留集不变；第八个页面号为5，驻留集中无匹配内容，之后没有被使用的9被替换掉；第九个页面号为6，驻留集中有匹配内容6，命中，驻留集不变；第十个页面号为8，驻留集中无匹配内容，之后没有被使用的5被替换掉；第十一个页面号为2，驻留集中无匹配内容，之后没有被使用的8被替换掉；第十二个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第十三个页面号为3，驻留集中无匹配内容；这时候已经没有页面了，按任意键继续执行。4.4 CLOCK算法4.4.1 运行4.4.2 分析用户输入驻留集大小为4，页面序列号个数为13，按任意键进入算法选择界面，选择3 OPT替换算法。第一个页面号为9，驻留集中无内容，直接放入；第二个页面号为7，驻留集中无匹配内容，驻留集未满，直接放入；第三个页面号为6，驻留集中无匹配内容，驻留集未满，直接放入；第四个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第五个页面号为4，驻留集中无匹配内容，驻留集未满，直接放入；第六个页面号为7，驻留集中有匹配内容7，命中，驻留集不变；第七个页面号为9，驻留集中有匹配内容9，命中，驻留集不变；第八个页面号为5，驻留集中无匹配内容，标志位全1替换掉第一个9；第九个页面号为6，驻留集中有匹配内容6，命中，驻留集不变；第十个页面号为8，驻留集中无匹配内容，7标志位为0被替换掉；第十一个页面号为2，驻留集中无匹配内容，4标志位为0被替换掉；第十二个页面号为7，驻留集中无匹配内容，标志位全1替换掉第一个5；第十三个页面号为3，驻留集中无匹配内容，8标志位为0被替换掉；这时候已经没有页面了，按任意键继续执行。4.5 算法之间的比较用户输入驻留集大小为4，页面序列号个数为139 7 6 7 4 7 9 5 6 8 2 7 命中次数/次替换次数/次命中率/%替换率/%FIFO453038LRU362346OPT543830Clock453038用户输入驻留集大小为5，页面序列号个数为167 5 7 4 5 1 4 8 3 4 3 9 3 8 7 9 命中次数/次替换次数/次命中率/%替换率/%FIFO835018LRU835018OPT921230Clock835018用户输入驻留集大小为5，页面序列号个数为192 7 4