操作系统实验报告2

Nachos 虚存 06 级软件 4 班 许小颖 200630556148 Nachos 虚存实验报告虚存实验报告 一 实验名称 实验名称 Nachos 虚存 二 实验目的实验目的 本实验牵涉到 Nachos 虚存子系统的部分实现 也是第一次用到 Nachos 的虚拟机 测 试代码是一组覆盖了绝大部分虚存空间的数组操作 该虚存空间被映射到 20 个物理页中 地址转换和页表结构已给出 本实验的目的是要实现缺页处理程序 这需要在适当的 时候将某些页面替换出 入 为了减少缺页和将页面从内存淘汰到磁盘的次数 要求实现以 下五种页面替换算法 NRU Not Recently Used 算法 SC Second Chance 算法 Clock 算法 Working Set 算法 Aging 算法 三 三 实验步骤实验步骤 1 预备预备 1 素材 本实验的源代码是 home nachos mp3 tar 文件 复制到本地目录后解包 要在 userprog 子目录下工作 也需阅读文件 filesys filesys h filesys openfile h machine translate h machine timer h 和 bin noff h 本实验需修改文是 memmanager h 和 memmanager cpp 2 分析代码 每个地址空间都有相应的页表 页表中的每一项称为页表条目 在本实验中 我们会 牵涉到其中的三个主要字段 USE DIRTY 和 VALID 它们在 machine translate h 中有详细 描述 AddrSpace 结构包含了 Nachos 进程地址空间的所有信息 页表 页表长度等 以及操作地 址空间的函数 当创建了一个新的进程时 该结构也就随之产生并初始化 所提供的代码 已实现了页面调度机制 在该机制中 仅在一个执行进程访问页面时 才将它从可执行的 源文件中读入物理内存 所以 在进程刚创建时 页表中的所有条目都是初始化为无效的 所有页表条目的有效位都置为 false 然而 访问这样的页面 不属于任何程序段 一 般来说是不合法的 当初始化一个页表时 要生成一个报告 该报告说明哪些页面的访问 是合法的 而哪些页面的访问是不合法的 Legal 字段 每个可执行程序都以一个头开始 它指定程序中所有程序段的虚存范围 Nachos 虚存 06 级软件 4 班 许小颖 200630556148 开始时 调用 AddrSpace ReadSourcePage 函数来从可执行文件中读一个页面到物理内 存 注意 该函数仅在进程第一次访问虚页时调用 至于后续的访问 如果页面不在物理 内存中 则搜索替换文件而不是源文件 替换文件由类似与 MainMemory 的内存帧组成 只不过它们存储在磁盘上 一组称为 SwapOwners 的 TranslationEntry 指针用来跟踪指向 替换文件中页面的页表条目 一个类似的结构 CoreOwners 则用来跟踪指向内存中页面 的页表条目 在执行阶段 仿真程序将在 TranslationEntrys 中设置适当的位 如 当出现写操作时 置 DIRTY TRUE 当出现写或读操作时置 USE TRUE 如果仿真器处理了这样一个 TranslationEntry 中的存储器请求 LEGAL TRUE 但 VALID FALSE 它将自陷到 MemManager faultIn 中去 这就是你要实现的地方 给定缺页的 TranslationEntry 用 PageIn PageOut 以及你要实现的将适当的缓冲页面调入物理页的方法 更新 TranslationEntry 并将控制权返回给虚拟机 阅读代码 MemManager PageFaultExceptionHandler 它由 ExceptionHandler 在接收到一个 缺页异常时调用 关于如何实现 MemManager faultIn 的一些细节和几点提示都以注释的 方式在 MemManager PageFaultExceptionHandler 中给出 注意 在此函数中 程序计数器 的值不应加一 在处理完异常且控制权返回给缺页进程后 引起缺页的那条指令将重新执 行 2 页面替换算法的实现页面替换算法的实现 本次实验对页面替换算法的实现主要是通过一个 MemManagerr 类来实现的 类中主 要的函数有以下几个 faultIn 是 handler 而其它各种方法则聚合成了重要的功能 PageOut 负责将页面写到备份存储中 它只处理脏页 因为其它的页面已在备份 存储中或是与原始状态相比没有变化 所以其它的页面可以覆盖它 PageIn 负责将页面读入指定的物理页 若该页不在备份存储中 则从原始文件中 装载 MakeFreeFrame 负责在没有空闲页时用适当的页面替换算法来选择一个牺牲页 doUpdation 是一个定时中断处理程序 在 memmanager cc 文件中 它修改 translationEntries 中适当的位来更新历史信息 整个实验修改的代码如下所示 红色部分为修改的代码 int MemManager makeFreeFrame victim is the number of the physical page to be swapped out int victim 0 switch policy case PAGEREPL NRU 4 4 2 Not Recently Used ifdef CHANGE int i Nachos 虚存 06 级软件 4 班 许小颖 200630556148 bool find false for i 0 i NumPhysPages i if coreOwners i use find true for i 0 i NumPhysPages i if coreOwners i use find true for i 0 i NumPhysPages i if coreOwners i use find true endif break case PAGEREPL FIFO 4 4 3 FIFO int ptr fifoList Remove victim ptr ifdef CHANGE if ptr NULL delete ptr endif break case PAGEREPL SC 4 4 4 Second Chance ifdef CHANGE int ptr fifoList Remove Nachos 虚存 06 级软件 4 班 许小颖 200630556148 while coreOwners ptr use coreOwners ptr use false fifoList Append ptr ptr fifoList Remove victim ptr if ptr NULL delete ptr endif break case PAGEREPL CLOCK 4 4 5 Clock ifdef CHANGE while coreOwners clock hand use coreOwners clock hand use false clock hand clock hand 1 NumPhysPages victim clock hand clock hand clock hand 1 NumPhysPages endif break case PAGEREPL WS 4 4 8 Working Set int v timestamp stats totalTicks ifdef CHANGE for int i 0 i NumPhysPages i if coreOwners i timeStamp timeStamp victim i endif break case PAGEREPL AGING 4 4 7 Aging Nachos 虚存 06 级软件 4 班 许小颖 200630556148 unsigned int v bitmask 0 xFFFF ifdef CHANGE for int i 0 i NumPhysPages i if history i Test i coreOwners i use false endif break case PAGEREPL AGING Aging Section 4 4 7 ifdef CHANGE for i 0 i NumPhysPages i if coreFreeMap Test i Nachos 虚存 06 级软件 4 班 许小颖 200630556148 history i history i 1 if coreOwners i use history i history i 1 use FALSE endif break the following don t use the timer interrupt case PAGEREPL FIFO not used case PAGEREPL SC not used case PAGEREPL CLOCK not used case PAGEREPL WS not used default break end switch return void MemManager pageIn TranslationEntry PTEntry int physFrame MP3 you need to make changes to the history keeping algorithms here FIFO and Second Chance have been implemented for you switch policy case PAGEREPL FIFO 4 4 3 FIFO case PAGEREPL SC 4 4 4 SC int ptr new int ptr physFrame fifoList Append ptr break case PAGEREPL AGING 4 4 7 AGING ifdef CHANGE history physFrame bitmask endif Nachos 虚存 06 级软件 4 班 许小颖 200630556148 break case PAGEREPL NRU 4 4 2 NRU case PAGEREPL CLOCK 4 4 5 CLOCK case PAGEREPL WS 4 4 8 WS default break return 1 NRU 算法的实现 算法的实现 此算法是用 R 位和 M 位来构造的 R 位在每次时间中断是被清零 以区别最近没有被 访问和被访问的页面 在系统中 R 位和 M 位分别对应 TranslationEntrys 中的 use 和 dirty 字段 每次中断时 系统会调用 doUpdation 来进行中断处理 因此我们必须在 doUpdation 中将内存中所有页面的 R 位清零 也就是将 use 字段设为 false 具体实现是在 switch 语句 中的 case PAGEREPL NRU 中加入 int i for i 0 i NumPhysPages i if coreFreeMap Test i coreOwners i use false 要注意的是 在设置use字段时 如果此时coreOwners i 指向的内存页面为空就会发 生严重的错误 所以我们必须在设置之前加入一个判断语句if coreFreeMap Test i 通 过测试空闲位图的第i位 0为空 1为非空 来判断此页是否为空 当页面发生失效时 根据页面的R位和M位将其分为4类 第0类 use false dirty false 第1类 use false dirty true 第2类 use true dirty false 第3类 use true dirty true 我们将从最小编号的非空类中 选择第一个页面将其淘汰 具体实现是在makeFreeFrame 中switch语句的case PAGEREPL NRU中加入3个for循环 int i bool find false for i 0 i NumPhysPages i if coreOwners i use find true for i 0 i NumPhysPages i if coreOwners i use find true for i 0 i NumPhysPages i if coreOwners i use find true 这三个 for 循环依次寻找第 0 1 2 类页面 如果找到符合条件的页面 victim 的值 被置为 i 即符合条件的页面号 此页面将被置换掉 同时将 find 变量置为 true 之后的 循环便不再执行 当三个 for 循环执行完后 仍未找到符合条件的页面 那么所有页面都 属于第 3 类 victim 的值是默认的 0 即第一个页面 在实现这个算法的过程中 我曾考虑过用两个循环来实现 第一个循环检查每一类中 是否有符合条件的页面 第二个循环在最小类中寻找一个符合条件的页面 由于在第一个 循环中 无论编号较小的类中是否有页面 循环都必须继续 平均代价比三个 for 循环更 大 所以最终决定用三个 for 循环来实现 2 SC 算法的实现 算法的实现 SC 算法只是对 FIFO 算法进行简单的修改 检查最老页面的 use 字段 如果为 false 就置换此页面 如果为 true 就将它置为 false 并将此页面放到 FIFO 列表的末端 具体实现是在 makeFreeFrame 中 switch 语句的 case PAGEREPL SC 中加入 int ptr fifoList Remove while coreOwners ptr use coreOwners ptr use false fifoList Append ptr ptr fifoList Remove victim ptr if ptr NULL delete ptr Nachos 虚存 06 级软件 4 班 许小颖 200630556148 我们用 fifoList Remove 取出 FIFO 链表头的页面号 即最老的页面号 用一个 int 指针指向该页面号 并判断该页面的 use 字段 如果为 true 就将它置为 false 并就调用 fifoList Append ptr 函数将此页面号插入到 FIFO 链表的末端 继续取下一个链表头的页 面号 如果为 false 就将此页面号赋给 victim 将此页面置换掉 最后将 ptr 指针指向的 内存区域清空 3 CLOCK 算法的实现 算法的实现 Clock 算法和 SC 算法的区别仅是实现上的不同 它将所有页面保存在一个类似钟面 的环形链表中 用一个指针指向最老的页面 以减少 SC 算法在链表中移动页面的代价 我们用 coreOwners 数组和求模操作来模拟环形链表 用一个 clock hand 的正型变量来模 拟表针 具体实现是在 makeFreeFrame 中 switch 语句的 case PAGEREPL CLOCK 中加 入 while coreOwners clock hand use coreOwners clock hand use false clock hand clock hand 1 NumPhysPages victim clock hand clock hand clock hand 1 NumPhysPages clock hand 的值初始化为 0 我们先判断第一个页面的 use 字段 如果 true 表示它 最近被使用到 将 use 设为 false 并将 clock hand 的值置为 clock hand 1 NumPhysPages 进入下一次循环 这里的求模操作是一个关键 它保证了 clock hand 的值在 0 到 NumPhysPages 之间循环 类似于一个表针 如果 clock hand 所指的页面 use 字段为 false 循环结束 将 victim 的值赋为 clock hand 此页面将被置换掉 并将 表针向前移动一格 也就是将 clock hand 的值设为 clock hand 1 NumPhysPages 4 Working Set 算法的实现 算法的实现 这个算法中 我们认为最早被访问的那个页面不在工作集中 将它置换出去 也就是 说 我们要在内存中寻找最后一次访问时间最小的那个页面 页面中与最后访问时间相对 应的是 timeStamp 字段 每次访问一个页面时 timeStamp 都会被更新为访问时的时间 具体实现是在 makeFreeFrame 中 switch 语句的 case PAGEREPL WS 中加入 for int i 0 i NumPhysPages i if coreOwners i timeStamp timeStamp victim i v timestamp 的初始值是当前系统时间 所有页面的最后访问时间都小于当前系统时 间 所以可以将 v timestamp 作为一个临时变量 在遍历所有页面的时候储存最小的最后 访问时间 我们用一个 for 循环遍历内存中的所有页面 并将每个页面的 timeStamp 与 Nachos 虚存 06 级软件 4 班 许小颖 200630556148 v timestamp 比较 如果小于 v timestamp 就将 v timestamp 的值设为当前页面的 timeStamp 并将 victim 的值置为当前页面号 这样 当遍历完所有页面时 v timestamp 值为所有页面的 timeStamp 的最小值 而 victim 的值也恰好是最小 timeStamp 值对应的 页面 此页面将被置换出去 5 Aging 算法的实现 算法的实现 在此算法中 每一个内存页面都分配了一个特定位数的计数器 每次时钟中断时 将 所有计数器值右移一位 然后将计数器的最高位设为 R 位的值 发生页面失效时 淘汰计 数器值最小的页面 用一个无符号整形变量来表示一个计数器 无符号整形数组 history 的 每一项代表一个页面的计数器 我们需要在调入页面的时候初始化计数器的值 具体实现 是在 pageIn 的 switch 语句的 case PAGEREPL AGING 中加入 history physFrame bitmask 整形变量 bitmask 的值为 1 Test i history i history i 1 if coreOwners i use history i history i 1 use FALSE 我们用一个 for 循环遍历内存的每个页面 在对计数器修改之前 要先判断页面是否 为空 如果为空 我们并不需要修改它的计数器 如果不为空 我们用 history i history i 1 将其计数器的值右移一位 然后 我们继续判断该页面的 use 字段 如果为 false 无 需改变 因为右移一位后 最高位自然变为 0 如果为 true 就必须将其计数器的最高位 设为 1 我们的做法是将 histo