操作系统实验4虚拟内存页面置换4种算法实验报告

1、程序模拟内存置换策略操作系统实验报告实验题目： 程序模拟内存页面置换策略 学 院： 计算机学院 专业班级： 网络工程 年 级： 2011级 姓 名： 学 号： 完成时间： 2013 年 12 月 8 日指导教师： 实验项目指导教师评定成绩表学号： 姓名： 班级： 项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-3

2、5分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 年 月 日实验项目指导教师评定成绩表学号： 姓名： 班级： 项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极

3、少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 年 月 日实验项目指导教

4、师评定成绩表学号： 姓名： 班级： 项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范

5、，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 年 月 日 本科学生实验项目任务书实验题目程序模拟内存页面置换策略学院计算机学院专业网络工程年级2011级任务描述：设计程序观察四种内存页面置换策略的区别，分析不同页面置换策略的效率，理解操作系统关于进程内存的管理方法。设计要求：根据教材8.2.3节的描述，设计程序分析四种不同的内存页面置换策略。要求：1、 根据内存访问的局部性原理产生不少于1000次的页面请求序列。2、 统计在不同页框数目下的页面失效率。通过实验数据的观察和分析，验

6、证是否可以得到教材图8.17的结果，并作分析。3、 程序界面友好，操作方便。实验要求：1）以项目组形式，实现项目所要求的功能。项目组每组13人，其中项目组长1人，负责项目整体进度和协调项目组成员之间的工作，要求项目组成员分工明确，各自的工作量均衡，并在实践报告中注明每个人的分工和工作量。2）写出完整的使用帮助文档3）程序、帮助文档以及实验报告（用word文档）以附件方式提交到管理系统参考资料：p 操作系统精髓与设计原理6版，William Stallings著，机械工业出版社p 现代操作系统(原书第3版)，Tanenbaum.A.S著，机械工业出版社任务下达日期 2013 年 11月 25 日

7、完成日期 年 月 日说明：学院、专业、年级均填全称，如：计算机学院、计算机科学与技术、2011。40 报告创建时间：2013-12-8 实验报告正文1 需求分析 （1）根据内存访问的局部性原理产生不少于1000次的页面请求序列。需要从MFC界面的一个编辑框中得到一个大于1000的页面数，再根据页面数随机产生页面地址（本次试验主要将地址控制在0100）。（2）统计在不同页框数目下的页面失效率。首先，要初始化页框，再编写isExit函数，用来判断某页是否已经存在在页框中。在将FIFO作为置换策略的情况下，我们用一个Button控制该算法，在该算法下，我们设置了页框数分别为8,10,12,14的4种

8、情况。设置了4个HitNumber变量分别记录4中情况下的命中页数，用于画折线图和计算缺页率。在将OPT，LUR，COLCK作为置换策略的情况下，基本需求同FIFO。（3）在画折线图时，主要需要的就是从（1）（2）步骤里得到的页框数和HitNumber数，用CDC的MoveTO和LineTo两个函数。2 系统设计（类图、模块图等）程序主界面模块图 程序主界面输入页数edit显示页数产生页数顺 序4种算法图形比较FIFOOPTCLOCKLRU子界面显示折线图3 关键代码描述（1）初始条件产生函数1 获得由界面输入的页面数void COS4aDlg:OnBnClickedButton1()/ TO

9、DO: 在此添加控件通知处理程序代码UpdateData(true);m_e3=PageNumber;UpdateData(false);2 随机产生并输出页面访问地址void COS4aDlg:OnBnClickedButton2()/ TODO: 在此添加控件通知处理程序代码CString str;srand(time(NULL);UpdateData(true);int count=0;for(int i=0;i<PageNumber;i+)count+;CString q;PageOrderi=rand()%100; q.Format("%d",PageOrd

10、eri);if(count%8=0)str+=q+"rn"else str+=q+"_"m_e4=str;UpdateData(false);（2）4种算法的关键代码 FIFO的实现，得到4中页框数下的缺页率和命中数void COS4aDlg:OnBnClickedButton3()/ TODO: 在此添加控件通知处理程序代码UpdateData(true);int x=0; /标记最早进入内存的页面CString s2,s3,s4,s5;CString d,e,f,g,h,i,j,k,l,m,n,o;CString str1,str2,str3,str

11、4;for(int i=0;i<8;i+)Ini=PageOrderi;for(int i=8;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<8;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit1(i)=0)b="调出内存的页面是"c.Format("%d",Inx);Inx=PageOrderi;x=(x+1)%8;else b="页面命中!"c.Format("%d&

12、quot;,PageOrderi);FHitNumber1+;s2+=s1+" "+b+c+"rn"float lost1=(PageNumber-FHitNumber1)*1.0/PageNumber)*100;d.Format("%f",lost1);e.Format("%d",8);f="在页框数为"+e+"时FIFO缺页率为： "+d;str1=s2+"rn"+f;for(int i=0;i<10;i+)Ini=PageOrderi;for(

13、int i=10;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<10;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit2(i)=0)b="调出内存的页面是"c.Format("%d",Inx);Inx=PageOrderi;x=(x+1)%10;else b="页面命中!"c.Format("%d",PageOrderi);FHitNumber2+;s3+=s1+&q

14、uot; "+b+c+"rn"float lost2=(PageNumber-FHitNumber2)*1.0/PageNumber)*100;g.Format("%f",lost2);h.Format("%d",10);i="当页框数为"+h+"时FIFO缺页率为： "+g;str2=s3+"rn"+i;for(int i=0;i<12;i+)Ini=PageOrderi;for(int i=12;i<PageNumber;i+)CString s1;

15、CString a,b,c;for(int j=0;j<12;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit3(i)=0)b="调出内存的页面是"c.Format("%d",Inx);Inx=PageOrderi;x=(x+1)%12;else b="页面命中!"c.Format("%d",PageOrderi);FHitNumber3+;s4+=s1+" "+b+c+"rn"float los

16、t3=(PageNumber-FHitNumber3)*1.0/PageNumber)*100;j.Format("%f",lost3);k.Format("%d",12);l="当页框数为"+k+"时FIFO缺页率为： "+j;str3=s4+"rn"+l;for(int i=0;i<14;i+)Ini=PageOrderi;for(int i=14;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<14;j+)a.

17、Format("%d",Inj); s1+=a+"_"if(isExit4(i)=0)b="调出内存的页面是"c.Format("%d",Inx);Inx=PageOrderi;x=(x+1)%14;else b="页面命中!"c.Format("%d",PageOrderi);FHitNumber4+;s5+=s1+" "+b+c+"rn"float lost4=(PageNumber-FHitNumber4)*1.0/PageNum

18、ber)*100;m.Format("%f",lost4);n.Format("%d",14);o="当页框数为"+n+"时FIFO缺页率为： "+m;str4=s5+"rn"+o;m_e5+=str1+"rnrn"+str2+"rnrn"+str3+"rnrn"+str4+"rn"UpdateData(false);int COS4aDlg:isExit1(int i)for(int j=0;j<8;j+)i

19、f(Inj=PageOrderi)return 1;return 0; OPT的实现，获得4种情况下的缺页率和命中数void COS4aDlg:OnBnClickedButton4()/ TODO: 在此添加控件通知处理程序代码UpdateData(true);int x=0; /标记最早进入内存的页面CString s2,s3,s4,s5;CString d,e,f,g,h,i,j,k,l,m,n,o;CString str1,str2,str3,str4;for(int i=0;i<8;i+)Ini=PageOrderi;for(int i=8;i<PageNumber;i+)

20、CString s1;CString a,b,c;for(int j=0;j<8;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit1(i)=1)b="页面命中!"c.Format("%d",PageOrderi);OHitNumber1+;else b="调出内存的页面是"c.Format("%d",Inx);x=Best1(i);Inx=PageOrderi;s2+=s1+" "+b+c+"rn"

21、;float lost1=(PageNumber-OHitNumber1)*1.0/PageNumber)*100;d.Format("%f",lost1);e.Format("%d",8);f="当页框数为"+e+"时OPT缺页率为： "+d;str1=s2+"rn"+f;for(int i=0;i<10;i+)Ini=PageOrderi;for(int i=10;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<

22、10;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit2(i)=1)b="页面命中!"c.Format("%d",PageOrderi);OHitNumber2+;else b="调出内存的页面是"c.Format("%d",Inx);x=Best2(i);Inx=PageOrderi;s3+=s1+" "+b+c+"rn"float lost2=(PageNumber-OHitNumber2)*1.0

23、/PageNumber)*100;g.Format("%f",lost2);h.Format("%d",10);i="当页框数为"+h+"时OPT缺页率为： "+g;str2=s3+"rn"+i;for(int i=0;i<12;i+)Ini=PageOrderi;for(int i=12;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<12;j+)a.Format("%d",Inj); s1+=

24、a+"_"if(isExit3(i)=1)b="页面命中!"c.Format("%d",PageOrderi);OHitNumber3+;else b="调出内存的页面是"c.Format("%d",Inx);x=Best3(i);Inx=PageOrderi;s4+=s1+" "+b+c+"rn"float lost3=(PageNumber-OHitNumber3)*1.0/PageNumber)*100;j.Format("%f"

25、,lost3);k.Format("%d",12);l="当页框数为"+k+"时OPT缺页率为： "+j;str3=s4+"rn"+l;for(int i=0;i<14;i+)Ini=PageOrderi;for(int i=14;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<14;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit4(i)=1)b="页

26、面命中!"c.Format("%d",PageOrderi);OHitNumber4+;else b="调出内存的页面是"c.Format("%d",Inx);x=Best4(i);Inx=PageOrderi;s5+=s1+" "+b+c+"rn"float lost4=(PageNumber-OHitNumber4)*1.0/PageNumber)*100;m.Format("%f",lost4);n.Format("%d",14);o=&q

27、uot;当页框数为"+n+"时OPT缺页率为： "+m;str4=s5+"rn"+o;m_e5+=str1+"rnrn"+str2+"rnrn"+str3+"rnrn"+str4;UpdateData(false);int COS4aDlg:Best1(int mi)int i=0,j=0,k=0,l=0,n=0,h=0,x=0,y=0;/分别代表In0,In1,In2,等0的为最近最迟出现的页面。int lable=0;/当lable=2时，即查找到两个已存在页面后。就停止for(i

28、nt m=mi+1;m<PageNumber,lable<7;m+)/往后查找在内存中最近最迟试用到的页面返回要交换页面的下标if(PageOrderm=In0) i=1;lable+;else if(PageOrderm=In1) j=1;lable+;else if(PageOrderm=In2) k=1;lable+;else if(PageOrderm=In3) l=1;lable+;else if(PageOrderm=In4) n=1;lable+; else if(PageOrderm=In5) h=1;lable+;else if(PageOrderm=In6) x

29、=1;lable+;else if(PageOrderm=In7) y=1;lable+;if(i=0) return 0;else if(j=0) return 1;else if(k=0) return 2;else if(l=0) return 3;else if(n=0) return 4;else if(h=0) return 5;else if(x=0) return 6;else if(y=0) return 7; LUR的实现，4种情况下的得到缺页率和命中数void COS4aDlg:OnBnClickedButton5()/ TODO: 在此添加控件通知处理程序代码Updat

30、eData(true);int x=0; /标记最早进入内存的页面CString s2,s3,s4,s5;CString d,e,f,g,h,i,j,k,l,m,n,o;CString str1,str2,str3,str4;for(int i=0;i<8;i+)Ini=PageOrderi;for(int i=8;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<8;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit1(i)=1)b="

31、;页面命中!"c.Format("%d",PageOrderi);LHitNumber1+;else b="调出内存的页面是"c.Format("%d",Inx);x=LBest1(i);Inx=PageOrderi;s2+=s1+" "+b+c+"rn"float lost1=(PageNumber-LHitNumber1)*1.0/PageNumber)*100;d.Format("%f",lost1);e.Format("%d",8);f=

32、"当页框数为"+e+"时LUR缺页率为： "+d;str1=s2+"rn"+f;for(int i=0;i<10;i+)Ini=PageOrderi;for(int i=10;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<10;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit2(i)=1)b="页面命中!"c.Format("%d",Page

33、Orderi);LHitNumber2+;else b="调出内存的页面是"c.Format("%d",Inx);x=LBest2(i);Inx=PageOrderi;s3+=s1+" "+b+c+"rn"float lost2=(PageNumber-LHitNumber2)*1.0/PageNumber)*100;g.Format("%f",lost2);h.Format("%d",10);i="当页框数为"+h+"时LUR缺页率为： &qu

34、ot;+g;str2=s3+"rn"+i;for(int i=0;i<12;i+)Ini=PageOrderi;for(int i=12;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<12;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit3(i)=1)b="页面命中!"c.Format("%d",PageOrderi);LHitNumber3+;else b="调出内存的

35、页面是"c.Format("%d",Inx);x=LBest3(i);Inx=PageOrderi;s4+=s1+" "+b+c+"rn"float lost3=(PageNumber-LHitNumber3)*1.0/PageNumber)*100;j.Format("%f",lost3);k.Format("%d",12);l="当页框数为"+k+"时LUR缺页率为： "+j;str3=s4+"rn"+l;for(int

36、i=0;i<14;i+)Ini=PageOrderi;for(int i=14;i<PageNumber;i+)CString s1;CString a,b,c;for(int j=0;j<14;j+)a.Format("%d",Inj); s1+=a+"_"if(isExit4(i)=1)b="页面命中!"c.Format("%d",PageOrderi);LHitNumber4+;else b="调出内存的页面是"c.Format("%d",Inx);x

37、=LBest4(i);Inx=PageOrderi;s5+=s1+" "+b+c+"rn"float lost4=(PageNumber-LHitNumber4)*1.0/PageNumber)*100;m.Format("%f",lost4);n.Format("%d",14);o="当页框数为"+n+"时LUR缺页率为： "+m;str4=s5+"rn"+o;m_e5+=str1+"rnrn"+str2+"rnrn&quo

38、t;+str3+"rnrn"+str4;UpdateData(false);int COS4aDlg:LBest1(int mi)int i=0,j=0,k=0,l=0,n=0,h=0,x=0,y=0;/分别代表In0,In1,In2,等0的为最近最迟出现的页面。int lable=0;/当lable=2时，即查找到两个已存在页面后。就停止for(int m=mi-1;m>=0,lable<7;m-)/往后查找在内存中最近最迟试用到的页面返回要交换页面的下标if(PageOrderm=In0) i=1;lable+;else if(PageOrderm=In1)

39、 j=1;lable+;else if(PageOrderm=In2) k=1;lable+;else if(PageOrderm=In3) l=1;lable+;else if(PageOrderm=In4) n=1;lable+; else if(PageOrderm=In5) h=1;lable+;else if(PageOrderm=In6) x=1;lable+;else if(PageOrderm=In7) y=1;lable+;if(i=0) return 0;else if(j=0) return 1;else if(k=0) return 2;else if(l=0) ret

40、urn 3;else if(n=0) return 4;else if(h=0) return 5;else if(x=0) return 6;else if(y=0) return 7; CLOCK算法的实现，得到4种缺页率和命中数void COS4aDlg:OnBnClickedButton6()/ TODO: 在此添加控件通知处理程序代码UpdateData(true);CString d,e,f,g,h,i,j,k,l,m,n,o;CString str1,str2,str3,str4,str5,str6,str7,str8;for(int i=0;i<8;i+)Ini=Page

41、Orderi;for(int i=0;i<8;i+)flagi=0;for(int j=8;j<PageNumber;j+)CString s1,s2;for(int b=0;b<8;b+)CString e;e.Format("%d",Inb);s1+=e+"_"bool find=false;for(int a=0;a<8;a+)if(Ina=PageOrderj)CString b;flaga=1;find=true;CHitNumber1+;b.Format("%d",Ina);s2="命中页

42、面"+b;break;if(find=false)int count=0;for(int a=0;a<8;a+)CString b;if(flaga=0)b.Format("%d",Ina);s2="被替换掉的页面为"+b;Ina=PageOrderj;flaga=1;count+;break;if(count=0)CString b;for(int a=0;a<8;a+)flaga=0;In0=PageOrderj;flag0=1;b.Format("%d",In0);s2="被替换掉的页面为&quo

43、t;+b;str1+=s1+s2+"rn"float lost1=(PageNumber-CHitNumber1)*1.0/PageNumber)*100;d.Format("%f",lost1);e.Format("%d",8);f="当页框数为"+e+"时CLOCK缺页率为： "+d;str2=str1+"rn"+f+"rn"for(int i=0;i<10;i+)Ini=PageOrderi;for(int i=0;i<10;i+)fla

44、gi=0;for(int j=10;j<PageNumber;j+)CString s1,s2;for(int b=0;b<10;b+)CString e;e.Format("%d",Inb);s1+=e+"_"bool find=false;for(int a=0;a<10;a+)if(Ina=PageOrderj)CString b;flaga=1;find=true;CHitNumber2+;b.Format("%d",Ina);s2="命中页面"+b;break;if(find=false

45、)int count=0;for(int a=0;a<10;a+)CString b;if(flaga=0)b.Format("%d",Ina);s2="被替换掉的页面为"+b;Ina=PageOrderj;flaga=1;count+;break;if(count=0)CString b;for(int a=0;a<10;a+)flaga=0;In0=PageOrderj;flag0=1;b.Format("%d",In0);s2="被替换掉的页面为"+b;str3+=s1+s2+"rn&q

46、uot;float lost2=(PageNumber-CHitNumber2)*1.0/PageNumber)*100;g.Format("%f",lost2);h.Format("%d",10);i="当页框数为"+h+"时CLOCK缺页率为： "+g;str4=str3+"rn"+i+"rn"for(int i=0;i<12;i+)Ini=PageOrderi;for(int i=0;i<12;i+)flagi=0;for(int j=12;j<Pag

47、eNumber;j+)CString s1,s2;for(int b=0;b<12;b+)CString e;e.Format("%d",Inb);s1+=e+"_"bool find=false;for(int a=0;a<12;a+)if(Ina=PageOrderj)CString b;flaga=1;find=true;CHitNumber3+;b.Format("%d",Ina);s2="命中页面"+b;break;if(find=false)int count=0;for(int a=0;a

48、<12;a+)CString b;if(flaga=0)b.Format("%d",Ina);s2="被替换掉的页面为"+b;Ina=PageOrderj;flaga=1;count+;break;if(count=0)CString b;for(int a=0;a<12;a+)flaga=0;In0=PageOrderj;flag0=1;b.Format("%d",In0);s2="被替换掉的页面为"+b;str5+=s1+s2+"rn"float lost3=(PageNumbe

49、r-CHitNumber3)*1.0/PageNumber)*100;j.Format("%f",lost3);k.Format("%d",12);l="当页框数为"+k+"时CLOCK缺页率为： "+j;str6=str5+"rn"+l+"rn" for(int i=0;i<14;i+)Ini=PageOrderi;for(int i=0;i<14;i+)flagi=0;for(int j=14;j<PageNumber;j+)CString s1,s2;

50、for(int b=0;b<14;b+)CString e;e.Format("%d",Inb);s1+=e+"_"bool find=false;for(int a=0;a<14;a+)if(Ina=PageOrderj)CString b;flaga=1;find=true;CHitNumber4+;b.Format("%d",Ina);s2="命中页面"+b;break;if(find=false)int count=0;for(int a=0;a<14;a+)CString b;if(flaga=0)b.Format("%d",Ina);s2="被替换掉的页面为"+b;Ina=PageOrderj;flaga=1;count+;break;if(count=0)CString b;for(int a=0;a<14;a+)flaga=0;In0=PageOrderj;flag0=1;b.Format("%d",In0);s2="被替换掉的页面为"+b;str7+=s1+s2+"rn"