欢迎来到天天文库
浏览记录
ID:15349104
大小:135.37 KB
页数:18页
时间:2018-08-02
《页面置换算法模拟_课程设计》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、《操作系统原理与Linux》课程设计报告专业计算机科学与技术班级学号姓名指导教师完成时间成绩17目录一、设计题目2二、设计目的2三、设计要求2四、设计思想说明21.最佳置换算法(OPT)22.先进先出置换算法(FIFO)33.最近最久未使用置换算法(LRU)3五、系统结构说明31.内存信息类(MemInfo)52.访问器(MemVisitor)53.加载器(MemLoader)64.页面走向列表类(MemReqs)65.MemReplacement6六、数据结构说明61.内存信息类(MemInfo)62.访问器(MemVisitor)73.加载器(MemLo
2、ader)84.页面走向列表类(MemReqs)9七、程序清单91.访问器92.加载器103.最佳置换算法114.先进先出算法135.最近最久末使用算法13八、使用说明书14九、实验体会、建议16十、参考文献1717一、设计题目页面置换算法模拟二、设计目的1、编写页面置换算法,实现计算机中页面置换的模拟。2、通过算法模拟的实现,理解几种常用的页面置换算法的执行过程。三、设计要求1、实现OPT,LRU,FIFO三种算法并进行对比分析。2、要求界面简单,易懂,关键代码部分要注释。3、编程语言可以采用自己任意精通的语言。四、设计思想说明1.最佳置换算法(OPT)1
3、7最佳置换算法所选择的被淘汰掉的页面,将是以后永久不再使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置算法,通常可保证获得最低的缺页率。本模拟算法中,最佳页面置换算法实现所采用的思想是:循环读入每个页表项,若该页表在内存中,则读取下一个页表项。若页表不存在内存中:一种情况是内存不满,则将页表放入内存中;若内存块已满,刚分别计算内存中各个页表再次被使用的时间,并将最久不被访问的调出,放入当前读入页表项。1.先进先出置换算法(FIFO)选择先进入内存的页面予以淘汰。这是最早出现的置换算法,该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久
4、的页面予以淘汰。实现简单,但是算法与进程实际运行规律不适应,例如在进程中,有些页面是经常被访问的。2.最近最久未使用置换算法(LRU)选择最近一段时间最长时间没有被访问过的页面予以淘汰。LRU算法是根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况,采取“最近的过去”作为“最近的将来”的近似。选择最近最久未使用的页面予以淘汰。实现:赋予每个页面一个方位字段,用来记录一个页面自上次被访问以来所经历的时间T,当要淘汰一个页面的,选择现有页面中其T值最大的,即最近最久未使用的页面予以淘汰。一、系统结构说明17本次算法模拟主要产生了7个类,访问器
5、(MemVisitor)、加载器(MemLoader)、内存信息类(MemInfo)、页面走向列表类(MemReqs)、最佳置换算法类(AlgOpt)、先进先出算法类(AlgFIFO)、最近最久未使用算法类(AlgLRU)。三个算法类都从MemReplacement继承,它主要包含一个方法,用于取得下一个要淘汰页面的ID,通过这种继承实现算法类多态。而系统结构图大致如下。171.内存信息类(MemInfo)主要包含页表信息以及服务于先进先出算法的页面换入队列和服务于最近最久未使用算法的页面访问栈。2.访问器(MemVisitor)通过页面走向列表依次访问每一
6、个页面,若页面已存在内存(通过MemInfo得知),直接访问;若页面不在内存中,则调用加载器加载相应的页。171.加载器(MemLoader)通过MemInfo得知内存块是否已占满,若未占满,则将相应的页载入空闲的内存块;若内存块已满,则调用已设置的置换算法,得出最佳淘汰页。加载器将在页表中将其移出,并且将欲载入的页加载到相应的内存块中。2.页面走向列表类(MemReqs)包含页面走向列表,在应用程序中设置。3.MemReplacement是置换算法基类,它包含一个虚函数NextPage(MemInfo&info),加载器将调用此方法得到欲淘汰的页。加载器在
7、设置使用的置换算法时,必须设置它的子类。一、数据结构说明1.内存信息类(MemInfo)/*页表*主要实现是Map(C++,Java)*或Dictionary(C#)*/MemTable*pTable;/**页换入队列17*服务于先进先出算法,*由加载器管理,被换入的页即会入队**/MemQueue*pQueue;/**页访问栈*服务于最近最久未使用算法,*由访问器管理,被访问页将入栈,*或被冒至栈顶**/MemStack*pStack;/**页缺页记录*当被访问页不在内存而产生缺页时,*将增加缺页记数*/MemMap*pFailReq;/**记录信息,指示
8、本次置换的结果描述*/charnote[8];/**
此文档下载收益归作者所有