页面置换算法实验报告.docx
- 文档编号:17163172
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:16
- 大小:120.20KB
页面置换算法实验报告.docx
《页面置换算法实验报告.docx》由会员分享,可在线阅读,更多相关《页面置换算法实验报告.docx(16页珍藏版)》请在冰点文库上搜索。
页面置换算法实验报告
操作系统课程设计报告
课程名称:
操作系统课程设计
课程设计题目:
页面置换算法
学院:
计算机科学与技术学院
专业:
科技
小组成员:
庞思慧E01114081
王蒙E01114161
姚慧乔E01114349
朱潮潮E01114408
指导老师:
邱剑锋
Notableofcontentsentriesfound.
页面置换算法模拟设计
1.实验目的
(1)通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。
(2)掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想,并至少用三种算法来模拟实现。
(3)通过对几种置换算法命中率的比较,来对比他们的优缺点。
2.实验要求
计算并输出下述各种算法在不同内存容量下的命中率。
A先进先出的算法(FIFO)
B最近最少使用算法(LRU)
C最佳淘汰算法(OPT)
3.实验内容与步骤
(1)通过随机数产生一个指令序列,共320条指令,具体的实施方法是:
A.[0,319]的指令地址之间随机选取一起点M;
B.顺序执行一条指令,即执行地址为M+1的指令;
C.在前地址[0,M+1]中随机选取一条指令并执行,该指令的地址为M’;
D.顺序执行一条指令,其地址为M’+1;
E.在后地址[M’+2,319]中随机选取一条指令并执行;
F.重复A—E,直到执行320次指令。
(2)指令序列变换成页地址流
A.页面大小为1K;
B.用户内存容量为4页到32页;
C.用户虚存容量为32K。
在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
第0条—第9条指令为第0页(对应虚存地址为[0,9]);
第10条—第19条指令为第1页(对应虚存地址为[10,19]);
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
第310条—第319条指令为第31页(对应虚存地址为[310,319]);
(3)计算并输出上述各种算法在不同内存容量下的命中率。
命中率=1-缺页次数/页地址流长度
4.算法思想
在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区中。
但应将哪 个页面调出,须根据一定的算法来确定。
通常,把选择换出页面的算法称为页面置换算法。
一个好的页面置换算法,应具有较低的页面更换频率。
从理论上讲,应将那些以后不再会访问的页面换出,或将那些在较长时间内不会再访问的页面调出。
1.先进先出算法FIFO:
这是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。
2.最近最久未使用算法LRU(least recently used):
算法的基本思想:
当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。
该算法的主要出发点是,如果某页被访问了,则它可能马上还被访问。
或者反过来说,如果某页很长时间未被访问,则它在最近一段时间不会被访问。
3.最佳淘汰算法OPT
其所选择的被淘汰的页面将是以后永不使用,或许是未来最长时间内不使用的页面,该算法可保证获得最低的淘汰率,但在实际运用中无法实现,可用来评价其他算法的命中率。
5.模块设计
总模块图
主程序图
6.程序设计
structProum=s;um=p[i].num+1;um=(int)((float)p[i].num*(rand()/(RAND_MAX+));um=p[i+2].num+1;um)*(rand()/(RAND_MAX+))+p[i+2].num;
}
for(i=0;i { p[i].time=0; } } intSearch(inte,Pro*page1,intN)um) returni; } return-1; } intMax(Pro*page1,intN)ime,i=0; while(i { if(e 选中算法,输入内存数点击计算 点击命中率按钮 点击退出按钮 8.结果分析 理论上,四种替换算法的命中率由高到底排列应该是OPT>LRU>CLOCK>FIFO。 实际上,在内存页面数较少(4~5页面)时,3种算法的命中率差别不大,可是50%左右。 在内存页面为7~25个页面之间时,3种算法的访内命中率大致在52%至87%之间变化。 在内存页面为25~32个页面时,由于用户进程的所有指令基本上都已装入内存,从而命中率已较大。 从而算法之间的差别不大。 9.程序代码 " #include"页面置换算法模拟设计" #ifdef_DEBUG #definenewDEBUG_NEW #undefTHIS_FILE staticcharTHIS_FILE[]=__FILE__; #endif Theframeworkdoesthisautomatically ForMFCapplicationsusingthedocument/viewmodel, voidCMyDlg: : OnPaint() { if(IsIconic()) { CPaintDCdc(this);HCURSORCMyDlg: : OnQueryDragIcon() { return(HCURSOR)m_hIcon; } #include<> #include #include #defineM320 intN; structProum=s;um=p[i].num+1;um=(int)((float)p[i].num*(rand()/(RAND_MAX+));um=p[i+2].num+1;um)*(rand()/(RAND_MAX+))+p[i+2].num; } for(i=0;i { p[i].time=0; } /*p[0].num=10;p[1].num=22;p[2].num=33;p[3].num=44;p[4].num=50; p[5].num=13;p[6].num=32;p[7].num=22;um) returni; } return-1; } intMax(Pro*page1,intN)ime,i=0; while(i { if(e str1+=tmp1; k++; if(k%16==0) { str1+="\n\r\n\r\n\r"; } } (_T(str1)); um/10); str2+=tmp2; k++; if(k%16==0) { str2+="\n\r\n\r\n\r"; } } (_T(str2)); Pro*page=newPro[N]; for(intj=0;j page[j].time=j; } if(m_iFifo==0)um,page,N)>=0)++i;um=p[i].num/10;um==-1) { ("%s",""); str3+=tmp3; } else { ("%-4d",page[i].num); str3+=tmp3; } str3+="\n\r\n\r\n\r"; (_T(str3)); um,page,N); if(k>=0) { page[k].time=0; for(p2=0;p2 { if(p2! =k) page[p2].time++; } } else { if(t1 {n++; page[t].num=p[i].num/10;ime=0; um==-1) { ("%s",""); str3+=tmp3; } else { ("%-4d",page[i].num); str3+=tmp3; } str3+="\n\r\n\r\n\r"; (_T(str3)); um=p[i].num/10; page[t].time=0; um==-1) { ("%s",""); str3+=tmp3; } else { ("%-4d",page[i].num); str3+=tmp3; } str3+="\n\r\n\r\n\r"; (_T(str3)); ime++; } } i++; } MZL=1-n/M; } if(m_iFifo==2)um,page,N)>=0)i++; else { if(t1 {n++; page[t].num=p[i].num/10;um==-1) { ("%s",""); str3+=tmp3; } else { ("%-4d",page[i].num); str3+=tmp3; } str3+="\n\r\n\r\n\r"; (_T(str3)); um=p[i].num/10; n++; um==-1) { ("%s",""); str3+=tmp3; } else { ("%-4d",page[i].num); str3+=tmp3; } str3+="\n\r\n\r\n\r"; (_T(str3)); etEventMask() um=-1; page[j].time=j; } intt1=0; inti1=0; floatn1=0; floats1,s2,s3; um,page,N)>=0)++i1;um=p[i1].num/10;um=-1; page[j].time=0; } while(i2 { intk; k=Search(p[i2].num,page,N); if(k>=0) { page[k].time=0; for(p2=0;p2 { if(p2! =k) page[p2].time++; } } else { if(tt { n2++; page[t2].num=p[i2].num/10;ime=0; } else { n2++; t2=Max(page,N); page[t2].num=p[i2].num/10; page[t2].time=0; } for(p2=0;p2 { if(p2! =t2) page[p2].time++; } } i2++; } s2=1-n2/M; um=-1; page[j].time=j; } while(i3 { if(Search(p[i3].num,page,N)>=0) i3++; else { if(ttt {n3++; page[t3].num=p[i3].num/10;um=p[i3].num/10; n3++; i3++; } elsebreak; } } s3=1-n3/M; CStringst,kg,bt; st=""; kg=""; bt="FIFO,LRU,OPT命中率分别为: "; ("%s%s%-4f%s%-4f%s%-4f",bt,kg,s1,kg,s2,kg,s3); MessageBox(st,"命中率比较"); UpdateData(false); } 10.课程设计小结 这次实验相对于以前来说比较不一样的是对于界面的制作,是一个比较新奇的体验。 整体来说的话还算是比较简单,需要注意的是在编写程序之前要将课程设计的要求及解决思路。 通过此次实验,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储和页面置换有了一定的了解。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 页面 置换 算法 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)