页面置换算法的模拟实现二

页面置换算法的模拟实现二页面置换算法的模拟实现二 专业班级 计算机 学生姓名 张三 学 号 指导教师 日 期 0 目录 一 设计目的 2 二 设计题目 2 2 1 设计内容 2 2 2 设计要求 2 三 相关知识 2 四 设计过程 3 4 1 OPT 最佳置换算法 3 4 2 LFU 4 五 设计思想 5 六 完整代码 5 7 实验结果 12 八 总结 14 九 参考文献 14 1 一 设计目的一 设计目的 操作系统是计算机教学中最重要的环节之一 也是计算机专业学生的一门 重要的专业课程 操作系统质量的好坏 直接影响整个计算机系统的性能和用 户对计算机的使用 一个精心设计的操作系统能极大地扩充计算机系统的功能 充分发挥系统中各种设备的使用效率 提高系统工作的可靠性 由于操作系统 涉及计算机系统中各种软硬件资源的管理 内容比较繁琐 具有很强的实践性 要学好这门课程 必须把理论与实践紧密结合 才能取得较好的学习效果 进一步巩固和复习操作系统的基础知识 培养学生结构化程序 模块化程序设计的方法和能力 提高学生调试程序的技巧和软件设计的能力 提高学生分析问题 解决问题以及综合利用C 语言进行程序设计的能力 二 设计题目二 设计题目 页面置换算法模拟程序页面置换算法模拟程序 2 1 设计内容设计内容 根据设计要求实现对页面置换算法的模拟 2 2 设计要求设计要求 设计一个虚拟存储区和内存工作区 编程序演示下述算法的具体实现过程 并计算访问命中率 用C 语言实现 要求设计主界面以灵活选择某算法 且以 下算法都要实现 1 最佳淘汰算法 OPT 2 最少访问页面算法 LFU 三 相关知识 三 相关知识 3 1 虚拟存储器的引入 虚拟存储器的引入 局部性原理 程序在执行时在一较短时间内仅限于某个部分 相应的 它所 访问的存储空间也局限于某个区域 它主要表现在以下两个方面 时间局限性 和空间局限性 3 2 虚拟存储器的定义 虚拟存储器的定义 虚拟存储器是只具有请求调入功能和置换功能 能从逻辑上对内存容量进行 扩充的一种存储器系统 3 3 虚拟存储器的实现方式 虚拟存储器的实现方式 分页请求系统 它是在分页系统的基础上 增加了请求调页功能 页面置换 功能所形成的页面形式虚拟存储系统 请求分段系统 它是在分段系统的基础上 增加了请求调段及分段置换功能 后 所形成的段式虚拟存储系统 2 四四 设计过程设计过程 4 14 1 OPTOPT 最佳置换算法 最佳置换算法 设计原理 需要进行页面置换 把内存中以后一段时间都不使用或是使用时间 离现在最远的页面换出 流程图 开始 页面走向存入数组 p 中 内 存块用 page 表示初始化为 0 当前 p 中第 i 个元 素是否已在内存 Page 是否有空 把 p i 的内容直接 装入最上面一个 空内存块 i 把 page 中以后一段时间都不使用 或是使用时间离现在最远的换出 i 输出当前内存块状态 结束 N Y i Y N 3 4 2 LFU 页面置换算法 开开始始 内内存存数数据据初初始始化化 物物理理 块块0 0 m m 5 50 0 将将页页面面p p n n 调调入入内内存存 比比较较物物理理块块中中页页面面在在之之 前前的的5 50 0次次调调用用中中出出现现的的 次次数数 将将页页面面p p n n 调调入入 使使用用最最少少的的页页面面占占用用的的 物物理理块块 n n 3 32 20 0 结结束束 按按照照L LR RU U页页面面置置换换算算 法法调调入入页页面面 n n Y Y N N Y Y N N 4 五 设计思想 五 设计思想 选择置换算法 先输入所有页面号 为系统分配物理块 依次进行置换 OPT 基本思想 基本思想 是用一维数组 page pSIZE 存储页面号序列 memery mSIZE 是存储装入 物理块中的页面 数组 next mSIZE 记录物理块中对应页面的最后访问时间 每当发生缺页时 就从物理块中找出最后访问时间最大的页面 调出该页 换 入所缺的页面 特别声明特别声明 若物理块中的页面都不再使用 则每次都置换物理块中第一个位置的页面 若物理块中的页面都不再使用 则每次都置换物理块中第一个位置的页面 LFU 基本思想 基本思想 LFU 即最不经常使用页置换算法 要求在页置换时置换引用计数最小的页 因 为经常使用的页应该有一个较大的引用次数 但是有些页在开始时使用次数很 多 但以后就不再使用 这类页将会长时间留在内存中 因此可以将引用计数 寄存器定时右移一位 形成指数衰减的平均使用次数 六 完整代码六 完整代码 include include include 全局变量 int queye 0 记录缺页次数 int mSIZE 物理块数 int pSIZE 页面号引用串个数 static int memery 10 0 物理块中的页号 static int page 100 0 页面号引用串 static int temp 100 10 辅助数组 载入数据 void download printf nFinish n 载入成功 按任意键进入置换算法选择界面 getch 显示设计者信息 void designBy printf 课题 页面置换算法 n printf 学号 20111202075 n 5 printf 姓名 周涛 n void begin for int i 0 i 100 i for int j 0 j 10 j memery j 1 temp i j 1 void print unsigned int t int i j p for p 0 p pSIZE p printf d page p printf n for j 0 j mSIZE j for i 0 i pSIZE i if temp i j 1 printf else printf d temp i j printf n printf n printf 缺页次数 d t t queye printf 缺页率 d d n queye pSIZE printf 置换次数 d t t t printf 访问命中率 d n pSIZE queye 100 pSIZE printf n 最佳置换算法 void OPT begin 6 queye 0 int next 10 0 记录下一次访问时间 int i j l m int t 1 n 1 int max 记录换出页 int count 0 记录置换次数 for i 0 i pSIZE i for j 0 j mSIZE j 找到一个空闲物理块 找到后跳出循环 if memery j 1 t j break for j 0 j mSIZE j 找到进程相同标号 if memery j page i 找到相同物理块 n j if t 1 说明没有空闲物理块找到 得到物理快中各页下一次访 问时间 for m 0 m mSIZE m for l i 1 l next 1 0 1 for m 2 mnext max max m 7 if n 1 没有相同物理块 if t 1 而且有空闲物理块 memery t page i t 1 for j 0 j mSIZE j temp i j memery j queye else 没有空闲物理块 memery max page i count for j 0 j mSIZE j temp i j memery j queye else 有相同物理块 n 1 print count 函数分界线 void LFU begin queye 0 int flag 10 0 记录页面的访问次数 int i j m int t 1 n 1 int min int count 0 记录置换次数 for i 0 i pSIZE i 8 for j 0 j mSIZE j 找到一个空闲物理块 找到后跳出循环 if memery j 1 t j break for j 0 j mSIZE j 找到进程相同标号 if memery j page i 找到相同物理块 n j flag j if t 1 说明没有空闲物理块找到 min flag 0 flag 1 1 0 for m 2 mflag m min m if n 1 if t 1 而且有空闲物理块 memery t page i t 1 for j 0 j mSIZE j temp i j memery j queye else 9 memery min page i count for j 0 j getch system cls system color 0B do printf 请输入物理块的个数 M10 mSIZE 0 printf 输出错误 请重新输入 n flag1 1 while flag1 1 do 10 printf 请输入页面号引用串的个数 P 100 scanf d flag2 0 if pSIZE100 printf 输出错误 请重新输入 n flag2 1 while flag2 1 printf 请依次输入页面号引用串 n for i 0 i pSIZE i scanf 1d download system cls system color 0E do puts 输入的页面号引用串为 for k 0 k getch system cls while code 4 getch 七七 实验结果实验结果 运行环境运行环境 VisualVisual C C 6 06 0 1 1 按任意键进行初始化 按任意键进行初始化 2 2 载入数据 载入数据 12 3 3 进入置换算法选择界面 进入置换算法选择界面 4 4 两种算法演示结果 两种算法演示结果 13 8 总结总结 14 通过这次课程设计 不仅让我了解了两种页面置换算法 即 OPT 最 佳置换 算法 LFU 最不经常使用 算法 同时使我对操作系统这门课程有 了更深入的研