实验六 请求分页存储管理.doc

实验六 实验六 请求分页存储管理 一 实验目的一 实验目的 深入理解请求页式存储管理的基本概念和实现方法 重点认识其中的 地址变换 缺页中断 置换算法等实现思想 二 实验属性二 实验属性 该实验为综合性 设计性实验 三 实验仪器设备及器材三 实验仪器设备及器材 普通 PC386 以上微机 四 实验要求四 实验要求 本实验要求 2 学时完成 本实验要求完成如下任务 1 建立相关的数据结构 页表 页表寄存器 存储块表等 2 指定分配给进程的内存物理块数 设定进程的页面访问顺序 3 设计页面置换算法 可以选择 OPT FIFO LRU 等 并计算 相应的缺页率 以比较它们的优劣 4 编写地址转换函数地址转换函数 实现通过查找页表完成逻辑地址到物理地 址的转换 若发生缺页则选择某种置换算法 OPT FIFO LRU 等 完成页面的交换 5 将整个过程可视化显示出来 实验前应复习实验中所涉及的理论知识和算法 针对实验要求完成基 本代码编写并完成预习报告 实验中认真调试所编代码并进行必要的测试 记录并分析实验结果 实验后认真书写符合规范格式的实验报告 参见附 录 A 并要求用正规的实验报告纸和封面装订整齐 按时上交 三 设计过程 3 1 算法原理分析 OPT 算法是未来最远出现 当当前内存中没有正要访问的页面时 置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的 页面 FIFO 算法是先进先出 当当前内存中没有正要访问的页面时 置 换出最先进来的页面 LRU 算法是最近最久未使用 当当前内存中没有正要访问的页面时 置换出在当前页面中最近最久没有使用的页面 3 2 数据定义 int length num page count seed length 记录访问串的长度 num page 页面 数 count 记录缺页次数 int result 20 30 order 30 a 10 result 记录结果 order 存储访问串 a 存 储当前页面中的值 int pos1 flag1 flag2 flag3 pos1 位置变量 flag1 等为标志变量 char result1 30 记录缺页数组 void opt 最佳 void fifo 先进先出 bool search int n 查找当前内存中是否已存在该页 3 3 流程图与运行截图 否 是 是 否 开始 得到执行的指令 指令是否在内存中 最先存入指 令被淘汰 下面是否还有指令 结束 得出命中率 图 6 1 FIFO 函数流程图 开始 输入内存中分配页 数 据第一个访问页初始化第一列值 还有请求访问页 直接复制前一列内容 内存中是否已存在 内存有空页 直接插入 替换内存中将来不出现或离当前最 远的页 输出全部页面变 化情况 结束 否 是 否 是 否 是 图 2 2 OPT 算法流程图 四 小结 本次课程设计目的是通过请求页式管理中页面置换算法模拟设计 了解虚拟存储技术的特点 掌握请求页式存储管理的页面置换算法 要求设计随机页面产生程序 并说明随机的性能和其性能可能对算法 的影响 对随机性要有一定的参数控制能力 计算并输出 FIFO 及 LRU 算法在不同内存容量下的命中率 由于上学期做过页面置换的实验 内容包括先进先出算法 FIFO 最近最久未使用页面置换算法 LRU 和理想淘汰算法 OPT 3 种算法思想简单明确 选好数据结构 思路清晰便基本没 问题了 所以相对来说 这次操作系统的课程设计容易许多 只是在 之前实验基础上 要附加设计随机页面产生程序 对随机性要有一定 的参数控制能力 对于随机页面产生程序 我们之前没做过 在网上 查阅资料 使用了库函数 srand 和 rand 实现了简单的随机页 面产生程序 功能基本完成 我们知识所限 没有使用漂亮可视化界 面编程实现功能 用简单的 C 语言编程实现的 不管怎么样 最终还 是实现的本次课程设计要求的 五 源程序 include include using namespace std int length num page count seed int result 20 30 order 30 a 10 int pos1 flag1 flag2 flag3 char result1 30 void init memset a 1 sizeof a int i cout length cout seed srand seed cout 产生的随机访问串 for i 0 i length i order i rand 10 cout order i endl cout num page void print int i j cout 表示缺页 endl for j 0 j length j printf 2d order j cout endl for i 0 i num page i for j 0 j length j if result i j 1 printf else printf 2d result i j cout endl for j 0 j length j printf 2c result1 j cout endl cout 缺页率 count length printf 1lf count 1 0 length 1 0 100 cout endl bool search int n 查找当期内存是否已存在 int i for i 0 i num page i if a i n return true return false void opt 最佳 int i pos 10 flag 10 while 1 flag1 flag2 0 for i 0 i length i if search order i count result1 i if a num page 1 1 表示当前页面已满要淘汰一个 memset pos 1 sizeof pos memset flag 0 sizeof flag int j k for j i j length j 找出当前页中的值在将 来访问串中对应的最近位置 for k 0 k num page k if order j a k flag k 1 cout endl int max 10 max pos for k 0 k num page k 找出位置最远的那个值 if pos k 1 未出现则跳出 替换该值 max pos k break else if max pos k max pos k max pos k a max pos order i else 还有空页 for int j 0 j num page j if a j 1 a j order i break else result1 i for int j 0 j num page j result j i a j print if flag1 0 void fifo 先进先出 int i thisn 0 while 1 count 0 flag1 flag2 0 for i pos1 i num page thisn 0 else for int j 0 j num page j if a j 1 a j order i break else result1 i for int j 0 j num page j result j i a j print if flag1 0 void main 主函数 int m printf 1