请求页式存储管理.doc

精品文档 1欢迎下载1欢迎下载 软软 件件 学学 院院 操作系统实验报告操作系统实验报告 专专 业 业 软件工程软件工程 班班 级 级 RBRB 软工互软工互 152152 学学 号 号 201560160226201560160226 学生姓名 学生姓名 王泽华王泽华 指导教师 指导教师 韩新超韩新超 精品文档 2欢迎下载2欢迎下载 实验四 实验四 请求页式存储管理 一 实验目的一 实验目的 深入理解请求页式存储管理的原理 重点认识其中的地址变换 缺页中断 置换算法等实现思想 二 实验属性二 实验属性 该实验为综合性 设计性实验 三 实验仪器设备及器材三 实验仪器设备及器材 普通 PC386 以上微机 四 实验要求四 实验要求 本实验要求 4 学时完成 本实验要求完成如下任务 1 建立相关的数据结构 存储块表 页表等 2 实现基本分页存储管理 如分配 回收 地址变换 3 在基本分页的基础上实现请求分页存储管理 4 给定一批作业 进程 选择一个分配或回收模拟 5 将整个过程可视化显示出来 实验前应复习实验中所涉及的理论知识和算法 针对实验要求完成基本代 码编写并完成预习报告 实验中认真调试所编代码并进行必要的测试 记录并 分析实验结果 实验后认真书写符合规范格式的实验报告 参见附录 A 并要 求用正规的实验报告纸和封面装订整齐 按时上交 五 实验提示五 实验提示 1 本实验虽然不以前面实验为基础 但建议在其界面中继续增加请求页式 存储管理功能 2 数据结构 内存分配表 页表空间 用数组实现 修改 PCB 结构增加 页表指针 页表长度 3 存储管理 编写内存分配 内存回收算法 页面置换算法 4 主界面设计 在界面上增加一个请求分页内存分配按钮 请求分页内存 回收按钮 装入指定进程的指定页按钮 触发请求分页内存分配按钮 弹出作业大小输入框 输入后调用内存分配 函数 在内存分配表和页表中看到分配的存储块 触发请求分页内存回收按钮 弹出进程 ID 输入框 输入后调用内存回收函数 在内存分配表中看到回收后的 状态改变 5 功能测试 从显示出的内存分配表和页表 可查看操作的正确与否 六 实验步骤六 实验步骤 1 任务分析 精品文档 3欢迎下载3欢迎下载 1 最佳页面置换算法 OPT 其所选择的被淘汰页面 将是以后永不使用 的或许是在最长 未来 时间内不再被访问的页面 采用最佳置换算法 通常可 保证获得最低的缺页率 2 最近最久未使用 LRU 算法 当需要置换一页时 选择在最近一段时间 里最久没有使用过的页面予以置换 2 程序设计 程序功能模块图如下 1 在同一进程中的各个线程 都可以共享该进程所拥有的资源 这表现 在 所有线程都具有相同的地址空间 进程的地址空间 此外我们应该还要用 控制语句 控制线程的同步执行 2 这个实验是要求我们采用算法模拟分页 存储管理技术的 FIFO 和 LRU 算法 所以我们 应该先生成地址序列 有了地址 序列 我们要找到它所在的虚页 然后通过查找实页 再判断下一步动作 假 如要访问的虚页不在内存中 不命中 我们要替换实页内容 根据 FIFO 算法 直接替换最早进入内存中的那一页就可以了 所以可以设立一个循环指针 记 录那个最早进入内存中的那页 而对于 LRU 算法 我们要替换是到现在为止最 长时间没被访问的页 在这里我们可以用一个队列来表示内存 把最久没使用 的页放在队头 然后替换进去的页放在队尾就可以了 假如要访问的虚页在内 存中 明显是命中 对于 FIFO 算法 不处理 而对于 LRU 算法 我们还要把他 的权值置 0 2 系统功能流程图 N N Y Y 请求分页式储存 管理 最近 最久 未使 用算 法 先 进 先 出 算 法 开始 还有指令 开始 还有指令 精品文档 4欢迎下载4欢迎下载 Y Y N N 3 算法分析 1 先进先出 定义一个队列存放页面 头指针记录最先进入队列的页面 的位置 每次替换头指针指向的页面 2 最近最少使用 定义一个二维数组 一维用来记录页面号 一维用来 记录该页面被使用的次数 每次替换最近最少使用的页面 3 程序结果 在运行界面选择某个算法 运行结果 如图 1 图 2 所示 图 1 新页进入计算过程数组第 一 位 其余为一次下移 找到了吗 计算页号 计算命中率 结束 计算页号 找到了吗 比较现有页面计数项的大 小 新页面替换最大项页 面 计算命中率 结束 精品文档 5欢迎下载5欢迎下载 图 2 3 调试与测试 1 第一道涉及线程的题编译时总是发生错误 原来编译这类程序在原有的编 译语言后要加上 pthread 2 第二个分页算法我们在系统结构课已经做过这个实验 所以有了一定的了 解 加上一点修改就能够使用了 所以没太花功夫 七 实验总结七 实验总结 通过实现请求页式存储管理的几种基本页面置换算法 了解了虚拟存储技 术的特点 通过对页面 页表 地址转换和页面置换过程的模拟 加深对请求 调页系统的原理和实现过程的理解 也知道了几种算法的效率 也验证了 LRU 算法的命中率平均的比 FIFO 算法要高 通过本次实验 我收获了很多 我了解到编写程序不是首要任务 而是一 种实现手段 我们最重要的是如何做好需求分析和理清思路 做出正确 简介 的流程设计 这样可以达到事半功倍的效果 八 附录八 附录 include include include stdio h include include define N 16 define num 5 进程分配物理块数目 int A N 1 2 3 4 5 6 7 8 5 2 3 2 7 8 1 4 页表映像 精品文档 6欢迎下载6欢迎下载 typedef struct page int address 页面地址 struct page next page struct page head run rear void jccreat 进程分配物理块 int i 1 page p q head page malloc sizeof page p head for i 1 inext q q address 0 q next NULL p q rear p int search int n page p int i 0 p head while p next if p next address n printf Get it at the page d n i 1 run p return 1 p p next i return 0 void changeOPT int n int position int i int total 0 int flag 1 int distance num 精品文档 7欢迎下载7欢迎下载 int MAX int order 0 page p q p head next q head next for i 0 iaddress 0 flag 0 break p p next i if flag p address n printf Change the page d n i 1 else while q for i position iaddress A i distance total i position total q q next MAX distance 0 for i 0 iMAX MAX distance i order i printf Change the page d n order 1 i 0 while p if i order p address n i p p next void changeLRU int n int i 0 int flag 1 page p delect p head next while p if p address 0 flag 0 p address n printf Change the page d n i 1 break p p next i if flag 精品文档 9欢迎下载9欢迎下载 delect head next head next delect next printf Delect from the head and add new to the end n delect address n rear next delect rear delect rear next NULL float OPT int i int lose 0 float losef float percent for i 0 i N i if search A i 0 lose changeOPT A i i losef lose percent 1 losef N return percent float LRU int i int lose 0 float losef 精品文档 10欢迎下载10欢迎下载 float percent page p for i 0 inext run next p next rear next p rear p rear next NULL printf Move it to end of queue n losef lose percent 1 losef N return percent main 主函数部分 float percent int choice printf Select the arithmetic n 1 OPT n 2 LRU nyour choice is scanf d 选择页面置换算法 jccreat 创建进程 if choice 1 采用 OPT 算法置换 percent OPT 计算 OPT 时的缺页率 printf The percent of OPT is f percent else if choice 2 采用 LR