模拟页式储存管理的页面置换算法.doc-资料库

hhz174628-9698223-4744302542863937263.doc.pdf-第1页.png

第1页 / 共6页

hhz174628-9698223-4744302542863937263.doc.pdf-第2页.png

第2页 / 共6页

hhz174628-9698223-4744302542863937263.doc.pdf-第3页.png

第3页 / 共6页

hhz174628-9698223-4744302542863937263.doc.pdf-第4页.png

第4页 / 共6页

hhz174628-9698223-4744302542863937263.doc.pdf-第5页.png

第5页 / 共6页

hhz174628-9698223-4744302542863937263.doc.pdf-第6页.png

第6页 / 共6页

操作系统第二次讨论课报告模拟页式储存管理的页面置换算法学生所在学院：信息科学与工程学院班级及小组号：计算机科学与技术 3 班 18 组小组成员：_薄玉昌、李辰倩 _赵向春、王琛指导教师：何海涛

模拟页式储存管理的页面置换算法 1 概述 1.1 设计要求通过使用程序设计语言设计一个程序，模拟页式存储管理中 FIFO、LRU、LFU、OPT 四页面置换算法运行的过程。基本要求如下：（1）输入一个逻辑页面访问序列和随机产生逻辑页面访问序列，由四个线程同时完成每个算法；（2）能够设定驻留内存页面的个数、内存的存取时间、缺页中断的时间、快表的时间，并提供合理省缺值，可以暂停和继续系统的执行；（3）能够随机输入存取的逻辑页面的页号序列；（4）能够随机产生存取的逻辑页面的页号序列；（5）能够设定页号序列中逻辑页面个数和范围；（6）能够设定有快表和没有快表的运行模式；（7）提供良好图形界面，同时能够展示四个算法运行的结果；（8）给出每种页面置换算法每个页面的存取时间，同时给出缺页率；（9）能够将每次的实验输入和实验结果存储起来，下次运行时或以后可查询；（10）完成多次不同设置的实验，总结实验数据，看看能得出什么结论。 1.2 目的通过本次操作系统讨论课，了解计算机软件技术，深化计算机操作系统技术。这次讨论使我们能够进一步掌握页面置换的方法，并借此机会提高自己的问题抽象能力、解决问题能力，以及自主学习能力和归纳总结能力。 1.3 预使用开发工具使用 mac 系统下的 Xcode 开发工具进行界面和程序的开发。 1.4 主要解决的问题（1）4 个页面置换算法的设计（有无块表）；（2）学习固定语言下多道程序线程的使用；（3）总程序流程的设计；（4）学习界面的开发。 2 使用的基本概念和原理 2.1 4 个页面置换算法操作系统在进行虚拟内存向主存调入“页”时，如果主存可存在页数已达上限，此时必须将主存中的某一页的调出，再将需要调入的页调入。而选择将主存中已存在的哪个页面调

出的算法，即为页面置换算法。下面讨论 4 种页面置换算法：FIFO 算法，LRU 算法，LFU 算法，Optimal 算法。（1）先进先出算法（FIFO） FIFO 的核心思想是如果一个数据最先进入内存中，则应该最早淘汰掉。基于这个思想，操作系统可以在页表中给每一个进入内存的页添加一个进入内存的时间的度量值；当一个页需要从内存中调出时，扫描页表找到最早进入的页的信息并从内存中调出，再将需要调入的页面调入即可。（2）最近最久未使用算法（LRU） LRU 的思想是“如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小”。LRU 算法在实现时需要操作系统在页表中给每个页添加一个此页最后一次调度的时间到当前时间间隔的度量值；当一个页面需要从内存中调出时，扫描页表找到时间间隔度量最大的页的信息并将其调出，再将需要调入的页面调入即可。（3）最少使用算法（LFU） LFU 基于的是“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思想。如果操作系统使用 LFU，则操作系统需要在页表中给每个页建立一个在一段时间（由操作系统决定）内，这个页的使用次数的度量值；当一个页需要从内存中调出时，扫描页表找到度量值最小的页的信息并将其调出，再将需要调入的页面调入即可。（4）最优置换算法（Optimal） Optimal 的思想是最理想化的思想：“选择在以后永远不进入或在最长时间内不进入内存的页，将其淘汰”。基于这个思想，不是一般性的得出，Optimal 是最好的页面置换算法。但是由于操作系统在进行页面调度时，不知道后面要进入内存的页的序列信息，故此算法虽然最好，但只是理论上可行，实际上无法实现的算法。 2.2 进程和线程进程和线程的关系就如同一个车间内任务的加工和车间内许多加工器材任务的加工，即进程包含多个线程。进程是系统资源分配和调度的基本单位。线程是程序运行的基本单位。一个进程内可以有多个线程同时并发或并行地运行。 2.3 快表操作系统在进行页面信息匹配时，每次需要在页表中查询。页表属于内存的一部分，查询页表相当于访问一次内存。当页面切换非常频繁的时候，在很短的时间内可能需要查询多次内存，使系统反应时间变慢。因此系统在设计的时加入了快表，将访问频率很高的页的信息存入其中；由于快表是硬件体系，查询时间很短，所以那些访问频率很高的页可以很快的查询出来，这样就能节省大量查询页的位置的时间，总体减少了系统反应时间。 2.4 访问一个页面的时间设访问一次内存的时间（内存的存取时间）为 MTime，查询一次快表的时间为 FTime，缺页中断的时间为 BTime。

在没有快表的情况下，访问一个页面的时间为 2xMTime（页在内存中）或 3xMTime+BTime （页不在内存中）。在有快表的情况下，我们假设操作系统是快表和页表是同时查询的。此时访问一个页面的时间为 FTime+MTime（页在快表）或 2xMTime（页不在快表但在内存）或 3xMTime+BTime （页不在内存）。 3 总体设计 3.1 确定基本技术路线使用 Swift 这种面向对象语言，采用 MVC 设计理念管理界面程序和逻辑程序之间的关系。 3.2 确定软件总体框架 3.2.1 MVC MVC 设计理念即将可视化界面程序分为 Model（模型），View（视图），Controller（控制器）三个方面。其中模型负责软件中逻辑运算部分；视图负责软件的界面显示；而控制器的功能则是将模型和视图联系起来。另外控制器还有接收用户输入的功能。 3.2.2 各模块内容 M：进程全局变量设计，4 个有无快表页面置换算法，随机生成逻辑页面序列，保存结果，查看结果。 V：显示程序界面和执行结果。 C：接收用户输入，线程的创建和执行，进程的挂起和唤醒。 3.2.3 软件总体流程 3.2.4 每个页面访问流程图 1 软件总体流程图图 2 每个页面的访问流程

4 详细设计 4.1 全程变量缺省值的设置内存页面数 mSize 逻辑页面数 lSize = = 3 8 内存存取时间 mTime 快表存取时间 fTime 缺页中断时间 bTime 是否有快表 existFT = = = = 5 1 20 true 逻辑页面数组 lArray[] 并发队列 queue 4.2 主要函数 4.2.1 4 个页面置换算法的设计首先说明 3 个局部变量： 1. 缺页率 rate 2. 总时间 allTime 3. 结果数组 resultArray[] 下面将介绍 4 个页面置换算法，首先是执行 FIFO 并返回结果算法： doFIFO(lArray[],mSize,existFT,3xTime)->(rate,allTime,resultArray[]){} 算法过程中模拟页面置换时不用使用辅助数组，仅在内存数组中操作即可。具体过程为设内存数组为 A[n]，每次向内存中调入页面放到下标最小的位置；如果内存数组已满，则淘汰 A[0]，并将其他数据向前移动一个位置，从而保证 A[0]处的页总是最先进入内存的，此时再将需要调入的页放入 A[n-1]中，实现页面置换。下面是 LRU 并返回结果算法： doLRU(lArray[],mSize,existFT,3xTime)->(rate,allTime,resultArray[]){} 算法过程中模拟页面置换也不用使用辅助数组。具体过程为设内存数组为 A[n]，每次访问一个页面就将此页面放到数组下标最小的位置（注意和 FIFO 的区别），即如果需要访问的页面没有在内存中，直接将此页面放到数组最小下标处；如果访问的页面在内存中，则将此页放到数组最小下标处，其后边的页的位置向前移动一位。如果内存已满，则淘汰 A[0]，并将其他数据向前移动一个位置（同 FIFO），此时再将页面调入到 A[n-1]中，实现页面置换。 LFU 并返回结果算法： doLFU(lArray[],mSize,existFT,3xTime)->(rate,allTime,resultArray[]){} 算法过程中模拟页面置换需要使用一个和内存大小相同的数组 B[n]，用来记录此页面

在一定时间内的调度次数（实现时可以直接设定为从算法执行开始到当前时间此页面的调动次数），当需要页面置换时，扫描 B[n]，取其中最小值 B[x]，将其对应的 A[x]淘汰，再将页面调入 A[x]，完成页面置换。最后是 Optmial 并返回结果算法： doOPT(lArray[],mSize,existFT,3xTime)->(rate,allTime,resultArray[]){} 算法过程中不需要辅助数组，仅需要一个算法来计算当前内存中的所有页面中哪个页面是后续逻辑页面队列中永远不进入内存或最长时间不进入内存的，并将其调出，再将所需页面调入，完成页面置换。 4.2.2 Swift 线程的使用 let queue: NSOperationQueue //创建一个线程队列 let operation1 = NSBlockOperation{ //第一个任务的具体步骤 } let operation2 = NSBlockOperation{ //第二个任务的具体步骤 } let operation3 = NSBlockOperation{ //第三个任务的具体步骤 } ... queue.addOperations{ [operation1, operation2, operation3, ...]，false} 4.2.2 Swift 文件管理（或使用 coredata 即本地数据库保存） //并发执行这几个任务 storeResult( rate, allTime, resultArray[]){} readResult( rate, allTime, resultArray[] ){} 5 总结通过对四种页面置换算法的模拟，小组明白了四种页面置换算法的特点，其中 FIFO 是最容易编程实现的，因为不需要额外的空间来保存中间结果。OPT 是最理想的实现方法，可以保证缺页率最小。LRU 需要确定最近一段时间访问最少的页号，用数组来保存，将每次新访问的页号存入第一个元素。根据局部性原理，可以有效地减小缺页率。LFU 将最少使用次数的页面调出内存，但是由于硬件移位时间的限制，不能准确的记录访问次数。目前对四种算法比较的实现已有大体思路，相信可以在编程实现的过程中，对四种算法有更深的体会。

资料库

模拟页式储存管理的页面置换算法.doc

相关推荐

课程资源

热门标签

最新资料