页面置换算法模拟_课程设计.doc

操作系统原理与Linux课程设计报告专 业 计算机科学与技术班 级 学 号 姓 名 指导教师 完成时间 成 绩 目录一、 设计题目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. 加载器(MemLoader)84. 页面走向列表类(MemReqs)9七、 程序清单91. 访问器92. 加载器103. 最佳置换算法114. 先进先出算法135. 最近最久末使用算法13八、 使用说明书14九、 实验体会、建议16十、 参考文献171、 设计题目页面置换算法模拟2、 设计目的1、 编写页面置换算法，实现计算机中页面置换的模拟。2、 通过算法模拟的实现，理解几种常用的页面置换算法的执行过程。3、 设计要求1、实现OPT,LRU,FIFO三种算法并进行对比分析。2、要求界面简单,易懂,关键代码部分要注释。3、编程语言可以采用自己任意精通的语言。4、 设计思想说明1. 最佳置换算法（OPT）最佳置换算法所选择的被淘汰掉的页面，将是以后永久不再使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置算法，通常可保证获得最低的缺页率。本模拟算法中，最佳页面置换算法实现所采用的思想是：循环读入每个页表项，若该页表在内存中，则读取下一个页表项。若页表不存在内存中：一种情况是内存不满，则将页表放入内存中；若内存块已满，刚分别计算内存中各个页表再次被使用的时间，并将最久不被访问的调出，放入当前读入页表项。2. 先进先出置换算法（FIFO)选择先进入内存的页面予以淘汰。这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。实现简单，但是算法与进程实际运行规律不适应，例如在进程中，有些页面是经常被访问的。3. 最近最久未使用置换算法(LRU)选择最近一段时间最长时间没有被访问过的页面予以淘汰。LRU算法是根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，采取“最近的过去”作为“最近的将来”的近似。选择最近最久未使用的页面予以淘汰。实现：赋予每个页面一个方位字段，用来记录一个页面自上次被访问以来所经历的时间T，当要淘汰一个页面的，选择现有页面中其T值最大的，即最近最久未使用的页面予以淘汰。5、 系统结构说明本次算法模拟主要产生了7个类，访问器(MemVisitor)、加载器(MemLoader)、内存信息类(MemInfo)、页面走向列表类(MemReqs)、最佳置换算法类(AlgOpt)、先进先出算法类(AlgFIFO)、最近最久未使用算法类(AlgLRU)。三个算法类都从MemReplacement继承，它主要包含一个方法，用于取得下一个要淘汰页面的ID，通过这种继承实现算法类多态。而系统结构图大致如下。1. 内存信息类(MemInfo)主要包含页表信息以及服务于先进先出算法的页面换入队列和服务于最近最久未使用算法的页面访问栈。2. 访问器(MemVisitor)通过页面走向列表依次访问每一个页面，若页面已存在内存（通过MemInfo 得知），直接访问；若页面不在内存中，则调用加载器加载相应的页。3. 加载器(MemLoader)通过MemInfo得知内存块是否已占满，若未占满，则将相应的页载入空闲的内存块；若内存块已满，则调用已设置的置换算法，得出最佳淘汰页。加载器将在页表中将其移出，并且将欲载入的页加载到相应的内存块中。4. 页面走向列表类(MemReqs)包含页面走向列表，在应用程序中设置。5. MemReplacement是置换算法基类，它包含一个虚函数NextPage(MemInfo& info)，加载器将调用此方法得到欲淘汰的页。加载器在设置使用的置换算法时，必须设置它的子类。6、 数据结构说明1. 内存信息类(MemInfo)/*页表 *主要实现是Map（C+, Java) *或Dictionary(C#) */MemTable *pTable;/*页换入队列 *服务于先进先出算法，*由加载器管理，被换入的页即会入队*/MemQueue *pQueue;/*页访问栈*服务于最近最久未使用算法，*由访问器管理，被访问页将入栈，*或被冒至栈顶*/MemStack *pStack;/*页缺页记录*当被访问页不在内存而产生缺页时，*将增加缺页记数*/MemMap *pFailReq; /*记录信息，指示本次置换的结果描述*/char note8;/*指示内存块总数*/int memoryCapa;2. 访问器(MemVisitor)/*加载器*/MemLoader *loader;/*内存信息*/MemInfo *info;/*内存*/Memory *mem;/*内存信息快照*在每次页被访问后，将执行一个内存信息*快照，以取得每一个页面走向后的内存占用情况*/MemSnapshotManager *ssManager;3. 加载器(MemLoader)/*模拟内存*/Memory *mem;/*内存信息*/MemInfo *info;/*置换算法*/MemReplacement *worker;/*模拟磁盘*/Drive *drv;4. 页面走向列表类(MemReqs)/*页面走向缓冲区*/int *pReqs;/*页面走向总数*/int count;7、 程序清单1. 访问器int MemVisitor:VisitPage(int id)if(loader != NULL);if (!Exists(id)loader-LoadPage(id);elseinfo-SetNote(命中);if (loader-GetReplacementAlg() = REPLACEMENT_ALG_LRU)/若使用最近最久未使用算法，触发辅助函数VisitedPage(id);/snapshotssManager-Add( MemSnapshotManager:GetSnapshot(info) );return 0;2. 加载器void MemLoader:LoadPage(int id)int next = 0;int loc = 0;if (Exceed()/内存块已占满/增加缺页记数info-AddFailReq(id);/得到淘汰的页IDnext = worker-NextPage(*info);/从页表中移除loc = info-RemoveLocationEntry(next);/info-SetNote(缺页);else/取得下一个空闲内存块loc = NextLocation();/info-SetNote(加载);/增加页表项info-AddPageLocation(id, loc);/装载入内存，从磁盘中mem-SetPage(drv-GetPage(id), loc);if (GetReplacementAlg() = REPLACEMENT_ALG_FIFO)/若使用先进先出算法，触发辅助函数PageLoaded(id);3. 最佳置换算法int AlgOpt:NextPage(MemInfo& info)/if(pReqs != NULL);/取得页表项数目int entSize = info.GetLocationEntryCount();/取得页面请求数目int reqsSize = pReqs-GetCount();/记录各页在页面走向中是否出现int *pVisited = new intentSize;int i, j;int trid = 0;int preret = 0, ret = 0;/initmemset(pVisited, 0, sizeof(int) * entSize);/找到未来最久才访问的页for (i = 0; i ViewAt(i);for (j = 0; j entSize; j+)if (trid = info.GetLocationEntry(j).GetPageId()& *(pVisited + j) = 0)*(pVisited + j) = 1;/走向中的页在页表中的下标preret = j;/找到未来不访问的页for (i = 0; i 0; i+) ;if (i = entSize)ret = info.GetLocationEntry(preret).GetPageId();elseret = info.GetLocationEntry(i).GetPageId();delete pVisited;return ret;4. 先进先出算法int AlgFIFO:NextPage(MemInfo& info)/将页换入队列中的队头出列/它是最先被换入的return info.QueuePop();以及辅助其完成置换工作的函数/当页被换入时触发，/参数 id 换入的页IDvoid MemLoader:PageLoaded(int id)/将换入的页的ID插入队列info-QueuePush(id);5. 最近最久末使用算法 int AlgLRU:NextPage(MemInfo& info)/将淘汰页访问栈的栈底元素/它是最近最久未使用的return info.StackRemoveAt(0);以及辅助其完成置换工作的函数/当页被访问后触发/参数 id 被访问页的IDvoid MemVisitor:VisitedPage(int id)int oid = 0, v = 0;oid = info-StackFind(id);if (oid StackPush(id);else/被访问的页在栈中，/将其移至栈顶v = info-StackRemoveAt(oid);info-StackPush(v);8、 使用说明书几种页面算法模拟主界面如下：输入相应的选项，手动输入页面走向，如上图，可执行相应的算法模拟如下：最佳算法结果：由此可看到，对于此页面项，使用最佳算法的命中次数为4，命中率为4/(10+1)=0.3636363636先进先出算法：由此可看到，对于此页面项，使用先进先出算法的命中次数为2，命中率