实验三页面置换算法模拟实验

计算机科学系 实验报告书 课 程 名 操 作 系 统 题 目 虚拟存储器管理 页面置换算法模拟实验 班 级 学 号 姓 名 评语 成绩 指导教师 批阅时间 年 月 日 操作系统 实验报告 0 一 实验目的与要求 1 目的 请求页式虚存管理是常用的虚拟存储管理方案之一 通过请求页式虚存管理中对页面置 换算法的模拟 有助于理解虚拟存储技术的特点 并加深对请求页式虚存管理的页面调度算 法的理解 2 要求 本实验要求使用 C 语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行 并在缺页中断发生时分别使用 FIFO 和 LRU 算法进行页面置换的情形 其中虚页的个数可以事 先给定 例如 10 个 对这些虚页访问的页地址流 其长度可以事先给定 例如 20 次虚页访 问 可以由程序随机产生 也可以事先保存在文件中 要求程序运行时屏幕能显示出置换过程 中的状态信息并输出访问结束时的页面命中率 程序应允许通过为该进程分配不同的实页数 来比较两种置换算法的稳定性 二 实验说明 1 1 设计中虚页和实页的表示 设计中虚页和实页的表示 本设计利用 C 语言的结构体来描述虚页和实页的结构 pn pfn time 虚页结构 实页结构 在虚页结构中 pn 代表虚页号 因为共 10 个虚页 所以 pn 的取值范围是 0 9 pfn 代表 实页号 当一虚页未装入实页时 此项值为 1 当该虚页已装入某一实页时 此项值为所装入的实 页的实页号 pfn time 项在 FIFO 算法中不使用 在 LRU 中用来存放对该虚页的最近访问时间 在实页结构中中 pn 代表虚页号 表示 pn 所代表的虚页目前正放在此实页中 pfn 代表实页 号 取值范围 0 n 1 由动态指派的实页数 n 所决定 next 是一个指向实页结构体的指针 用 于多个实页以链表形式组织起来 关于实页链表的组织详见下面第4 点 2 2 关于缺页次数的统计 关于缺页次数的统计 为计算命中率 需要统计在 20 次的虚页访问中命中的次数 为此 程序应设置一个计数器 count 来统计虚页命中发生的次数 每当所访问的虚页的 pfn 项值不为 1 表示此虚页已被装入 某实页内 此虚页被命中 count 加 1 最终命中率 count 20 100 3 3 LRULRU 算法中算法中 最近最久未用最近最久未用 页面的确定页面的确定 为了能找到 最近最久未用 的虚页面 程序中可引入一个时间计数器 countime 每当要访 问一个虚页面时 countime 的值加 1 然后将所要访问的虚页的 time 项值设置为增值后的当前 pn pfn next 操作系统 实验报告 1 countime 值 表示该虚页的最后一次被访问时间 当 LRU 算法需要置换时 从所有已分配实页的 虚页中找出 time 值为最小的虚页就是 最近最久未用 的虚页面 应该将它置换出去 4 4 算法中实页的组织 算法中实页的组织 因为能分配的实页数 n 是在程序运行时由用户动态指派的 所以应使用链表组织动态产生的多个实 页 为了调度算法实现的方便 可以考虑引入 free 和 busy 两个链表 free 链表用于组织未分配 出去的实页 首指针为 free head 初始时 n 个实页都处于 free 链表中 busy 链表用于组织已分 配出去的实页 首指针为 busy head 尾指针为 busy tail 初始值都为 null 当所要访问的一个 虚页不在实页中时 将产生缺页中断 此时若 free 链表不为空 就取下链表首指针所指的实页 并分配给该虚页 若 free 链表为空 则说明 n 个实页已全部分配出去 此时应进行页面置换 对 于 FIFO 算法要将 busy head 所指的实页从 busy 链表中取下 分配给该 虚页 然后再将该实页插 入到 busy 链表尾部 对于 LRU 算法则要从所有已分配实页的虚页中找出 time 值为最小的虚页 将 该虚页从装载它的那个实页中置换出去 并在该实页中装入当前正要访问的虚页 三 程序流程图 要求画出非常详细的流程图 输入实 页数 输入选项 FIFO法LRO法虚页顺序重置实页数 是否已输入虚页 顺序 是否已输入虚页 顺序 输入访 问次 数 和 访问顺 序 重新输 入实页 数 输出实页置换情 况 命中概率 开始 退出 No No YESYES 操作系统 实验报告 2 四 主要程序清单 动态指定实页个数的页面置换算法 包括 FIFO 和 LRU 两个算法 include include include include define M 10 10 个虚页 define N 20 20 个页面的访问序列 define L 10 最大 10 个实页 定义虚页的结构 typedef struct VirtualPage int pn int pfn int time VirtualPage 定义实页的结构 typedef struct Page int pn int pfn struct Page next Page struct Page pp M 定义一个存放 10 个实页的数组 在底下还要将其串成链表 struct VirtualPage vp M 定义存放 10 个虚页的数组 int queue N 定义一个数组 存放随机生成的 20 个数 表示访问虚页的次序 里面的数值不 能超过 9 int count 存放缺页次数 用来统计缺页率 本算法没有考虑预调页 只要该页不在内存 就认为缺页一次 int countime 用于 LRU 算法中 找出要淘汰的页 每当要访问一个虚页面时 countime 的值 加 1 然后将所要访问的虚页的 time 项值设置为增值后的当前 countime 值 int MemoryStatus L N 记录当访问每一个虚页时 内存中的 5 个实页的详细信息 操作系统 实验报告 3 int NotInMemory N 表示每次虚页访问是否在内存 struct Page Free Free head Free tail Busy Busy tail Busy head temp temp small void FIFO 先入先出算法的具体实现 int i j k currentpage 一些临时变量 for i 0 i N i 这是主循环 每次处理一个虚页访问 直到把 20 个虚页处理完为止 当前访问的虚页是哪一页 由数组 queue i 中的值表示 currentpage queue i 判断该虚页是否已经调入内存 if vp currentpage pfn 1 表示该页已经在内存中 可以直接访问 同时记录访 问该页时对应的实页信息 和前一页相同 for j 0 jnext Free Free head 操作系统 实验报告 4 将虚页 currentpage 装入 temp 指向的实页 该实页的编号为 temp pfn vp currentpage pfn temp pfn temp pn currentpage 将 temp 指向的实页插入 Busy 链表的末尾 temp next NULL if Busy NULL 如果是第一次把虚页装入实页 则 temp 就是 Busy 链表的第 一个元素 Busy temp Busy head Busy Busy tail Busy else 如果不是第一次把虚页装入实页 则将 temp 插入 Busy 链表的队尾 Busy tail next temp Busy tail temp 修改内存状态 for k 0 kpfn i currentpage 虚页 currentpage 装入了 temp pfn 表示的那个实页里 else 如果 Free 链表为空 需要置换一页出去 由于采用 FIFO 算法 故取 busy 链 表的队首元素 将其置换出去 修改信息后插入队尾 将 Busy 首元素取出 赋给 temp temp Busy Busy head Busy next Busy Busy head 操作系统 实验报告 5 将当前虚页 currentpage 装入 temp 指向的实页 修改其信息 vp temp pn pfn 1 该页被置换出去了 所以其 pfn 字段 要设置成 1 表示其已经不再内存 vp currentpage pfn temp pfn currentpage 被装入内存 更新其 pfn 字段为 temp 指向的实页 temp pn currentpage temp 指向的实页 装入了 currentpage 虚页 将 temp 指向的实页插入 Busy 链表的末尾 此时不用再考虑 Busy 是否为空了 temp next NULL Busy tail next temp Busy tail temp 修改内存状态 for k 0 kpfn i currentpage 虚页 currentpage 装入了 temp pfn 表示的那个实页里 void LRU int i j k currentpage 一些临时变量 for i 0 i N i 这是主循环 每次处理一个虚页访问 直到把 20 个虚页处理完为止 当前访问的虚页是哪一页 由数组 queue i 中的值表示 currentpage queue i countime countime 1 每次访问一个虚页 将该变量值加 1 操作系统 实验报告 6 vp currentpage time countime 设置当前访问的虚页的 time 值 判断该虚页是否已经调入内存 if vp currentpage pfn 1 表示该页已经在内存中 可以直接访问 同时记录访 问该页时对应的实页信息 和前一页相同 for j 0 jnext Free Free head 将虚页 currentpage 装入 temp 指向的实页 该实页的编号为 temp pfn vp currentpage pfn temp pfn temp pn currentpage 将 temp 指向的实页插入 Busy 链表的末尾 temp next NULL if Busy NULL 如果是第一次把虚页装入实页 则 temp 就是 Busy 链表的第 一个元素 Busy temp Busy head Busy Busy tail Busy 操作系统 实验报告 7 else 如果不是第一次把虚页装入实页 则将 temp 插入 Busy 链表的队尾 Busy tail next temp Busy tail temp 修改内存状态 for k 0 kpfn i currentpage 虚页 currentpage 装入了 temp pfn 表示的那个实页里 else 如果 Free 链表为空 需要置换一页出去 由于采用 LRU 算法 在 busy 链表 中查找到 time 值最小的那个元素 置换到链表尾部 查找 time 值最小的元素 找到后用 temp small 指针表示 temp Busy head temp small Busy head while temp next NULL if vp temp small pn time vp temp next pn time 若当前元素的 time 值比下一个元素的 time 值大 则更新 temp small 为指向下一元素 temp small temp next temp temp next 将当前虚页 currentpage 装入 temp small 指向的实页 修改其信息 vp temp small pn pfn 1 该页被置换出去了 所以其 pfn 字段要设置成 1 表示其已经不再内存 操作系统 实验报告 8 vp currentpage pfn temp small pfn currentpage 被装入内存 更 新其 pfn 字段为 temp small 指向的实页 temp small pn currentpage temp small 指向的实页 装入 了 currentpage 虚页 将 temp small 指向的实页插入 Busy 链表的末尾 if temp small Busy tail 如果 temp small 指向的那个元素就是 Busy 链 表的最后一个 则不用做任何操作 if temp small Busy head 如果 temp small 指向的那个元素是 Busy 链 表的第一个元素 则直接插入链表尾部 Busy Busy head next Busy head Busy temp small next NULL Busy tail next temp small Busy tail temp small else 如果 temp small 指向的那个元素恰好在 Busy 链表的中间 首先定位到 temp small 的前一个元素 temp Busy head while temp next temp small temp temp next 然后将 temp small 的前一个元素的 next 指针 指向 temp small 指向 的下一个元素 temp next temp small next 最后插入尾部 并更新 Busy tail 指针 temp small next NULL Busy tail next temp small Busy tail temp small 操作系统 实验报告 9 修改内存状态 for k 0 kpfn i currentpage 虚页 currentpage 装入 了 temp pfn 表示的那个实页里 void main int i j ppCount 由键盘输入实页的个数 并形成 Free 链表 printf 请输入系统能提供的物理块 即实页 的个数 数值为 2 10 之间 t scanf d if ppCount 10 ppCount 2 printf n n 输入的数值不合法 程序终止 else count 0 countime 0 初始化 10 个虚页 操作系统 实验报告 10 for i 0 ipn 1 Free head pfn 0 Free head next NULL 用一个循环生成后续的元素 并初始化后 链接成链表 for i 1 ipn 1 temp pfn i temp next NULL Free tail next temp Free tail temp 初始化 Busy 链表 Busy NULL Busy head NULL Busy tail NULL 初始化 MemoryStatus 数组 for i 0 i L i 操作系统 实验报告 11 for j 0 j N j MemoryStatus i j 1 初始化 NotInMemory 数组 for i 0 i N i NotInMemory i 1 生成 20 个