页面置换算法模拟程序-附代码.doc

目 录 1 问题问题的提出的提出 1 1 1 关于页面置换算法模拟程序问题的产生 1 1 2 任务分析 1 2 需求分析 需求分析 1 3 方案 方案设计设计 2 4 总总体体设计设计 3 4 1 程序 N S 图 3 4 2 主要的函数 3 4 3 主要流程图及代码 4 4 3 1 FIFO 先进先出 4 4 3 2 LRU 最近最久未使用 5 4 3 3 OPT 最佳置换算法 7 4 4 实现结果 10 5 程序 程序测试测试 14 5 1 设计测试数据 14 5 2 测试结果及分析 15 摘 要 随着计算机的普及人们的物质生活得到了极大的满足 人们在精神生活方面同样也需要 精品资料 提高 所以越来越多的人进行着各种各样的学习 操作系统是计算机教学中最重要的 环节之一 也是计算机专业学生的一门重要的专业课程 操作系统质量的好坏 直接影 响整个计算机系统的性能和用户对计算机的使用 一个精心设计的操作系统能极大地扩 充计算机系统的功能 充分发挥系统中各种设备的使用效率 提高系统工作的可靠性 由于操作系统涉及计算机系统中各种软硬件资源的管理 内容比较繁琐 具有很强的实 践性 要学好这门课程 必须把理论与实践紧密结合 才能取得较好的学习效果 本课程设计是学生学习完 操作系统教程 课程后 进行的一次全面的综合训练 通过课程设计 让学生更好地掌握操作系统的原理及实现方法 加深对操作系统基础理 论和重要算法的理解 加强学生的动手能力 熟悉页面置换算法及其实现 引入计算机系统性能评价方法的概念 关关键词键词 编制页面置换算法模拟程序 打印页面 FIFO 页面算法 LRU 页面置换算法 OPT 页面置换算法 精品资料 引 言 1 问题问题的提出的提出 1 1 关于关于页页面置面置换换算法模算法模拟拟程序程序问题问题的的产产生生 在各种存储器管理方式中 有一个共同的特点 即它们都要求将一个作业全 部装入内存方能运行 但是有两种情况 1 有的作业很大 不能全部装入内存 致使作业无法运行 2 有大量作业要求运行 但内存容量不足以容纳所有这些 作业 而虚拟内存技术正式从逻辑上扩充内存容量 将会解决以上两个问题 从内存中调出一页程序或数据送磁盘的对换区中 通常 把选择换出的页面的算 法称为页面置换算法 Page Replacement Algorithms 进而页面置换算法模拟程 序能客观的将其工作原理展现在我们面前 1 2 任任务务分析分析 首先 定义宏变量 设置所占最大内存长度 编辑以时间为种子 初始化随 即发生器 进行相关页面输入程序的编写以及页面的打印 尔后 寻找最近最近 最久未使用的页面 记录当前内存块中页面离下次使用间隔长度等相关程序的 代码编写 最后 进行 FIFO LRU OPT 三种算法的编写 2 需求分析需求分析 1 用随机数方法产生页面走向 页面走向长度为 L 2 根据页面走向 分别采用 FIFO 和 LRU 算法进行页面置换 统计缺页率 精品资料 为简化操作 在淘汰一页时 只将该页在页表中抹去 而不再判断它是否 被改写过 也不将它写回到辅存 3 假定可用内存块和页表长度 作业的页面数 分别为 m 和 k 初始时 作业 页面都不在内存 随机数产生程序 int i j j time NULL 取时钟时间 srand j 以时钟时间 x 为种子 初始化随机数发生器 cout 输出随机数 for i 0 i m i p i num rand 10 1 产生 1 到 10 之间的随即数放到数组 p 中 p i time 0 cout p i num 上述随机数发生函数产生的随机数为 0 0 1 0 稍另变化就可得到 0 n 1 之间的随机数 程序开始时 应对变量 Seed 实型 赋初值 根据页面置换算法的理论操作及要求 首先要进行页面长度的确定 定义结 构体用以储存数据 进行主界面代码及 FIFO LRU OPT 页面置换算法代码的编 写 精品资料 3 方案 方案设计设计 首先 定义宏变量 设置所占最大内存长度 编辑以时间为种子 初始化随即 发生器 进行相关页面输入程序的编写以及页面的打印 其次 寻找最近最近最久未使用的页面 记录当前内存块中页面离下次使用 间隔长度等相关程序的代码编写 最后 进行 FIFO LRU OPT 三种算法的编写 程序运行平台 VC 6 0 具体操作如下 在 VC 6 0 的环境下准备用时钟函数调用库函数 include 取时钟时间并存入 t 调用库函数 t time NULL 用时间 t 初始化 随机数发生器调用 库函数 srand t 返回一个 1 10 之间的随机数 x rand 10 1 编写三种算法 4 总总体体设计设计 4 1 程序程序 N S 图图 程序开始 输入选择项 进行判断 页面存在进入下一部操作此项不存 在 输入要输出的结果 输出结果 结束 精品资料 4 2 主要的函数主要的函数 Input int m Pro p L 打印页面走向状态 void print Pro page1 打印当前的页面 int Search int e Pro page1 寻找内存块中与 e 相同的块号 int Max Pro page1 寻找最近最长未使用的页面 int Count Pro page1 int i int t Pro p L 记录当前内存块中页面离下次使用 间隔长度 int main 主函数 随机数发生器 include include 准备用时钟函数调用库函数 t time NULL 取时钟时间并存入 t 调用库函数 srand t 用时间 t 初始化随机数发生器调用库函数 x rand 10 1 返回一个 1 10 之间的随机数 4 3 主要流程主要流程图图及代及代码码 4 3 1 FIFO 先 先进进先出 先出 设计原理 需要进行页面置换 即把内存中装入最早的那个页面淘汰 换入当前的页面 算法流程图 开始 页面走向存入数组 p 中 内存块用 page 表示初 始化为 0 精品资料 Y N N Y 图 4 1FIFO 算法流程图 代码 if c 1 FIFO 页面置换 n 0 cout endl cout endl cout FIFO 算法页面置换情况如下 endl cout endl cout endl while i 0 当前页面在内存中 cout p i num 输出当前页 p i num 当前 p 中第 i 个 元素是否已在内 存中 Page 是否有空 把 page 中最先装入的页 面置换出去 i 把 p i 的内容直接 装入最上面一个 空内存块 i 输出当前内存块状态 结束 i 精品资料 cout 不缺页 endl i i 加 1 else 当前页不在内存中 if t M t 0 else n 缺页次数加 1 page t num p i num 把当前页面放入内存 中 cout p i num print page 打印当前页面 t 下一个内存块 i 指向下一个页面 cout 缺页次数 n 缺页率 n m endl 4 3 2 LRU 最近最久未使用 最近最久未使用 设计原理 当需要淘汰某一页时 选择离当前时间最近的一段时间内 最久没有使用过的页先淘汰该算法的主要出发点是 如果某页被访问了 则它可 能马上还要被访问 或者反过来说如果某页很长时间未被访问 则它在最近一段 时间也不会被访问 算法流程图 开始 精品资料 Y N Y N 图 4 2 LRU 算法流程图 代码 if c 2 LRU 页面置换 n 0 cout endl cout endl cout LRU 算法页面置换情况如下 endl cout endl 页面走向存入数组 p 中 内 存块用 page 表示初始化为 0 当前 p 中第 i 个元 素是否已在内存 Page 是否有空 把 page 中最近最久未使 用的页面置换出去 i 把 p i 的内容直接 装入最上面一个 空内存块 i 输出当前内存块状态 结束 i 精品资料 cout endl while i 0 如果已在内存块中 page t time 0 把与它相同的内存块的时间置 0 for a 0 a M a if a t page a time 其它的时间加 1 cout p i num cout 不缺页 endl else 如果不在内存块中 n 缺页次数加 1 t Max page 返回最近最久未使用的块号赋 值给 t page t num p i num 进行替换 page t time 0 替换后时间置为 0 cout p i num print page for a 0 a M a if a t page a time 其它的时间加 1 i cout 缺页次数 n 缺页率 n m endl 精品资料 4 3 3 OPT 最佳置 最佳置换换算法 算法 设计原理 需要进行页面置换 把内存中以后一段时间都不使用或是 使用时间离现在最远的页面换出 流程图 Y N Y N 开始 页面走向存入数组 p 中 内 存块用 page 表示初始化为 0 当前 p 中第 i 个元 素是否已在内存 Page 是否有空 把 page 中以后一段时间都不使用 或是使用时间离现在最远的换出 i 把 p i 的内容直接 装入最上面一个 空内存块 i 输出当前内存块状态 i 精品资料 图 4 3 OPT 流程图 代码 if c 3 OPT 页面置换 n 0 cout endl cout endl cout OPT 算法置换情况如下 endl cout endl cout endl while i 0 如果已在内存块中 cout p i num cout 不缺页 endl i else 如果不在内存块中 int a 0 for t 0 t M t if page t num 0 a 记录空的内存块数 if a 0 有空内存块 结束 精品资料 int q M for t 0 tt q t 把空内存块中块号 最小的找出来 page q num p i num n cout p i num print page i else int temp 0 s for t 0 t M t 寻找内存块中下次使用离 现在最久的页面 if temp Count page i t p temp Count page i t p s t 把找到的块号赋给 s page s num p i num n cout p i num print page i cout 缺页次数 n 缺页率 n m endl 精品资料 4 4 实现结实现结果果 程序在运行的情况下 进入主界面输入菜单 如图 3 3 所示 输入 14 图 4 5 输入 14 后的输出图 输入 25 图 5 6 输入数据 25 后输出图 输入数据 18 图 5 7 输入数据 18 后的输出图 输入数据 精品资料 图 5 8 输出图 选 1 进入 FIFO 页面置换 图 5 9 FIFO 的输出图 选 2 进入 LRU 页面置换 精品资料 图 5 10 LRU 的输出图 输入 3 进入 OPT 页面置换 精品资料 图 5 11 OPT 的输出图 5 程序 程序测试测试 5 1 设计测试设计测试数据数据 A 14 25 18 2 6 4 B 1 C 2 D 3 精品资料 5 2 测试结测试结果及分析果及分析 1 测试 A 结果及分析 进入主菜单后输入 14 25 显示输入不满足要求 输入 18 显示相关信息 输入 2 6 不满足要求 输入 4 显示出相关信息 2 测试结果及分析 显示出 FIFO 页面置换算法的缺页信息及缺页率 3 测试 C 结果及分析 显示出 LRU 页面置换算法的缺页信息及缺页率 4 测试 D 结果及分析 显示出 OPT 页面置换算法的缺页信息及缺页率 精品资料 结 论 通过这次课程设计 不仅让我了解了页面置换算法 开始我一味的进行调 试 急切的想侥幸调试出来 但由于没有进行深入的考虑 我调试了很久都没没 有成功 我仔细的分析题目 分析材料 在原由的基础上我进行了改正 我最后 还是调试成功了 还是经过了一翻努力 这次操作系统实习 不仅让我对操作系 统这门课程有了更深入的研究 对很多重要的概念有了巩固和掌握 通过努力 三个页面置换算法程序都已经完成 此时此刻 我心里多了些成就感 虽然自己所做的很少也不够完善 但毕竟也是努力的结果 主要有以下几点收获 1 通过对上网和看书查阅相关资料 使自己对 VC 语言的基本框架有新的 了解 加深了对可视化程序的认识 2 在使用 VC 语言来实现功能时 不像以往用的其他语言 它比较简练 更 容易理解 实用性很强 3 先进先出页面置换和 LRU 以及 OPT 算法各有特点 但是实践起来却很大 使自己对页面置换算法有了新的认识 一周半的课程设计就要结束了 不但对专业知识有了更深的理解 更使的自己认 识到实践的重要性 理论 实践相结合才能达到很好的学习效果 特别是程序语 言的学习 精品资料 致 谢 本次课程设计能顺利完成 感谢学校的大力支持 感谢数学与计算机学院为 我们提供实练的机会 感谢老师的细心教导 此次的课程设计收获很多 虽然经过了一段漫长而又痛苦的过程 但是自己 还是完成了 这是与自己的努力是分不开的 但是自己在调试过程当中遇到的一 些问题 自己仍然不懂 是在同学 老师的帮助下完成的 在这里还要再次对他 们的付出表示崇高的敬意 精品资料 参考文献参考文献 面向对象程序设计与 VisualC 6 0 教程 陈天华编著 C 程序设计 第三版 谭浩强编著 C 入门经典 面向对象程序设计与 C 实现 刘晋萍编著 计算机操作系统教程 徐甲同等编著 操作系统 罗宇等编著 操作系统实验教程 张丽芬 刘利雄 王全玉编著 计算机操作系统 梁红兵 哲风屏 汤子瀛 编著 操作系统教程 陈向群 杨芙清 编著 代码 include 精品资料 include include include define L 20 页面走向长度最大为 20 int M 内存块 struct Pro 定义一个结构体 int num time Input int m Pro p L 打印页面走向状态 cout 请输入实际页面走向长度 L 15 L m if m 20 m 15 cout 实际页面长度须在 15 20 之间 请重新输入 L else break while 1 int i j j time NULL 取时钟时间 srand j 以时钟时间 x 为种子 初始化随机数发生器 cout 输出随机数 for i 0 i m i p i num rand 10 1 产生 1 到 10 之间的随即数放到数组 p 中 p i time 0 cout p i num cout endl return m void print Pro page1 打印当前的页面 Pro page new Pro M page page1 for int i 0 i M i cout page i num cout endl int Search int e Pro page1 寻找内存块中与 e 相同的块号 Pro page new Pro M page page1 精品资料 for int i 0 i M i if e page i num return i 返回 i 值 return 1 int Max Pro page1 寻找最近最长未使用的页面 Pro page new Pro M page page1 int e page 0 time i 0 while i M 找出离现在时间最长的页面 if e page i time e page i time i for i 0 i M i if e page i time return i 找到离现在时间最长的页面返回其块号 return 1 int Count Pro page1 int i int t Pro p L 记录当前内存块中页面离下次使用间隔长度 Pro page new Pro M page page1 int count 0 for int j i j L j if page t num p j num break 当前页面再次被访问时循环结束 else count 否则 count 1 return count 返回 count 的值 int main int c int m 0 t 0 float n 0 Pro p L m Input m p 调用 input 函数 返回 m 值 cout M if M 5 M 3 cout 内存块 m 须在 3 5 之间 请重新输入 m else break while 1 Pro page new Pro M do for int i 0 i M i 初试化页面基本情况 page i num 0 page i time m 1 i i 0 cout 1 FIFO 页面置换 endl cout 2 LRU 页面置换 endl cout 3 OPT 页面置换 endl cout 按其它键结束程序 c system cls if c 1 FIFO 页面置换 n 0 cout endl cout endl cout FIFO 算法页面置换情况如下 endl cout endl cout endl while i 0 当前页面在内存中 cout p i num 输出当前页 p i num cout 不缺页 endl i i 加 1 else 当前页不在内存中 if t M t 0 else 精品资料 n 缺页次数加 1 page t num p i num 把当前页面放入内存中 cout p i num print page 打印当前页面 t 下一个内存块 i 指向下一个页面 cout 缺页次数 n 缺页率 n m endl if c 2 LRU 页面置换 n 0 cout endl cout endl cout LRU 算法页面置换情况如下 endl cout endl cout endl while i 0 如果已在内存块中 page t time 0 把与它相同的内存块的时间置 0 for a 0 a M a if a t page a