操作系统存储器管理中的命中率问题实验

1、实验四存储器管理中的命中率问题!1!r:、实验名称存储器页式分配管理算法的模拟实现二、实验目标提高存储器的使用效率是操作系统研究的重要课题之一。虚拟存取技术是用 来扩大主存容量的一种重要方法。本实验要求学生应用高级程序设计语言编写儿个常用的存储器页面置换算 法，并设计一个存储管理的模拟程序，能对各种页面置换算法进行分析、比较, 评测其性能优劣，从而加深对这些算法的了解。三、实验环境要求Windows+Visual C+ 6.0：I、实验基本原理本实验采用页式分配存储管理方案，并通过分析、计算不同页面淘汰算法情 况下的访问命中率来比较各种算法的优劣。先进先出算法(FIFO)： FIFO算法认为先

2、调度内存的页不再被访问的可能 性要比其它页大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个 己经分配的页面按分配时间顺序链接起来，组成FIFO队列。置换时将队列头页 换出，把换入的页链接到FIFO队列尾部。最佳淘汰算法(OPT)：这是一种理想的算法，可用来作为衡量其他算法 优劣的依据，在实际系统中是难以实现的。该算法的准则是淘汰己满页表中以后 不再访问或是最迟访问的页。这就要求将页表中的页逐个与后继指令访问的所有 页比较，如后继指令不再访问该页，则把此页淘汰，否则要找出后继指令中最迟访问的页面予以淘汰。最近最少使用算法(LRU)：该算法的思想是，当需要淘汰某一页时, 选择离当前时间

3、最近的一段时间内最久没有使用过的页先淘汰。五、数据结构设计六、流程图图1页面置换算法流程图七、源代码#iiicludedefine NUM 3 using namespace std;/定义全局变量mt Ye100=0; 存储页面走向mt Length=O;页面走向的长度mtDealNUM=0; 存储相关的处理mt num=O; 计算缺页中断次数/ 全局变量定义完/自定义函数/初始化全局变量/void init()fbr(int i=0;i0;i-)ai=ai-l;a0=m;在第一个元素插入相应的数据m/判断一个数是否在数组中/bool test(iiit a.iiit n.mt m)fbr(

4、int i=0;in;i-H-)if(ai=m)return tme;return false;/显示/void display()fbr(int i=0;iNUM;i+)if(Deali=O)coutH ”；elsecoutDealin H; coutendl;/先进先出算法/void FIFO()coutMFIFOHendl;coutHynizx yl y2 y3Hendl;fbr(int i=O;iLength;i+)coutM -YeiH”；谊! test(DeaLNUM.Ye i)(Move(DeaLNUM.Ye 国)； num+;)elsei+；displayQ;cout共发生次中

5、断。”endl; /把对应的数移到第一个位置/void MoveFirst(iiit a,iiit m)fbr(int i=0;iO;j-)硕=如-1;a0=m;/最近最少使用算法/void LRU()coutMLRUHendl;coutHynizx yl y2 y3Hendl;fbr(int i=O;iLength;i+)coutM -YeiH H;谊! test(DeaLNUM.Ye i)(Move(DeaLNUM.Ye 国)； num+;elseMoveFirst(DeaLNUM,Yei);displayQ;coutM共发生,num,t次中断。Hendl:/求数组中每个元素到下次遇到时的

6、间隔/void Next(int ajnt flag,mt m,mt k)fbr(int i=0;im;i-H-)j=k+1 jLength;j+)if(ai=Yej)break;if(j=Length)(flagi=j-k;fbr(int j=O;jLength;j-H-)!f(ai=Ye|j)break:if(jLength)flagi=flagi+j;elseflagi=-l;elseflagi=j-k;/求最后遇到的数/mt Latest(iiit flag4nt n)fbr(int i=0 ,max=O ;iflagmax) max=i;return max;/理想页面置换算法/vo

7、id OPT0coutMOPT-endl;coutHynizx yl y2 y3Hendl;fbr(int i=0;iLength:i-H-)coutM HYeiH ”；iR! test(DeaLNUM.Ye i)(if(DealNUM-l=0)Move(DeaLNLTM,Yei);else(hit flagNUM=0;Next(DeaLflag.NUMj);hit max=Latest(flag.NUM);Move(DeaLniax.Yei);num-H-;)elsei+；displayQ;coutM共发生,numM次中断。Hendl: /自定义函数结束/主函数mt mam()mput();

8、/ FIFO。； LRUQ；OPT()；/* int flag3=0;inta3=(2,5,4);Next(a,fbg,3,10);fbr(int i=0;i3;i+)coutflagin H;coutendl; */retuin 0;八、运行结果请输人页面走向：432143543215 入ZFIFOC先进先出 ynax112 344 12334 1112 5共发“9次中断。LRU单近本少使用ynaxy3Press any key to continue九、结果分析先进先出(FIFO)算法输出数据分析：页面置换按先进先出的方式，相当于 一个队列，调入的页面按时间排好队，等待被置换。最近最少使用(LRU)算法输出数据分析：当有页面要被置换时，系统根 据己被调入的页面最近一次被使用的时间排序，最早的将被置换。十、本次实验体会通过本次实验，进一步