页面置换-操作系统实验报告

实验二实验二 页面置换算法实现页面置换算法实现 一 实验目的一 实验目的 1 了解内存分页管理策略 2 掌握调页策略 3 掌握一般常用的调度算法 4 学会各种存储分配算法的实现方法 5 了解页面大小和内存实际容量对命中率的影响 二 实验内容二 实验内容 采用页式分配存储方案 通过分别计算不同算法的命中率来比较算法的优 劣 同时也考虑页面大小及内存实际容量对命中率的影响 设计一个虚拟存储区和 内 存工作区 并使用下述算法来模拟实现页面的置换 1 先进先出的算法 FIFO 2 最近最久未使用算法 LRU 3 最佳置换算法 OPT 实验分析 在进程运行过程中 若其所访问的页面不存在内存而需要把它们调入内存 但内存已无空闲时 为了保证该进程能够正常运行 系统必须从内存中调出一 页 程序或数据送磁盘的对换区中 但应调出哪个页面 需根据一定的算法来确定 算法的好坏 直接影响到系统的性能 一个好的页面置换算法 应该有较低的 页面更换频率 2 12 1 先进先出 先进先出 FIFOFIFO 页面置换算法 页面置换算法 当需要访问一个新的页面时 首先查看物理块中是否就有这个页面 若要 查 看的页面物理块中就有 则直接显示 不需要替换页面 如果要查看的页面物 理 块中没有 就需要寻找空闲物理块放入 若存在有空闲物理块 则将页面放入 若没有空闲物理块 则替换页面 并将物理块中所有页面 timer 2 22 2 最近久未使用最近久未使用 LRU LRU 置换算法的思路置换算法的思路 最近久未使用置换算法的替换规则 是根据页面调入内存后的使用情况来 进 行决策的 该算法赋予每个页面一个访问字段 用来记录一个页面自上次被访 问 以来所经历的时间 当需淘汰一个页面的时候选择现有页面中其时间值最大的 进 行淘汰 2 32 3 最佳 最佳 OPTOPT 置换算法的思路 置换算法的思路 其所选择的被淘汰的页面 是以后不使用的 或者是在未来时间内不再被 访 问的页面 采用最佳算法 通常可保证获得最低的缺页率 3 3 实验流程实验流程 3 13 1 系统功能图系统功能图 图 3 1 系统功能图 3 23 2 算法流程图算法流程图 1 先进先出 FIFO 页面置换算法流程图 图 3 2 先进先出页面置换算法流程图 2 最近久未使用 LRU 置换算法 图 3 3 最近久未使用置换算法流程图 3 最佳 OPT 置换算法 图 3 4 最佳置换算法流程图 4 4 源程序源程序 include include include include define L 20 页面长度最大为 20 int M 内存块 struct Pro 定义一个结构体 int num time Input int m Pro p L 打印页面走向状态 cout m if m 20 m 10 cout endl cout 页面长度必须在 10 20 之间 endl endl cout 请重新输入 L else break while 1 int i j j time NULL 取时钟时间 srand j 以时钟时间 j 为种子 初始化随机数发生器 cout endl cout 输出随机数 endl cout endl for i 0 i m i p i num rand 10 产生 0 到 9 之间的随机数放到数组 p 中 p i time 0 cout p i num cout endl 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 2 6 cout endl M if M 6 M 2 cout endl cout 物理块 m 必须在 2 6 之间 endl endl cout 请重新输入 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 endl cout 1 FIFO 页面置换2 LRU 页面置换 endl cout 3 OPT 页面置换 4 退出 endl cout 请选择页面置换算法 c if c 1 FIFO 页面置换 n 0 cout FIFO 算法页面置换情况如下 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 endl cout 缺页次数 n 缺页率 n m endl endl if c 2 LRU 页面置换 n 0 cout LRU 算法页面置换情况如下 endl 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 endl cout 缺页次数 n 缺页率 n m endl endl if c 3 OPT 页面置换 n 0 cout OPT 算法置换情况如下 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 endl cout 缺页次数 n 缺页率 n m endl endl if c 4 break while c 1 c 2 c 3 return 0 五 实验结果五 实验结果 5 15 1 程序主界面程序主界面 运行程序后 将会提示用户输入页面长度 长度在 10 到 20 之间 当用户 输入长度 以 12 为例 后 系统将会显示随机数 系统提示用户输入分配的物 理块 用户输入数据 以 3 为例 程序主界面运行图如图 5 1 所示 图 5 1 程序主界面 5 25 2 先进先出先进先出 FIFO FIFO 页面置换算法运行结果页面置换算法运行结果 选择算法 1 之后 进入算法 1 的操作 系统会显示算法的页面置换情况 先来先服务算法的运行图如图 5 2 所示 图 5 2 先进先出页面置换算法运行结果图 5 35 3 最近久未使用最近久未使用 LRU LRU 置换算法运行结果置换算法运行结果 选择算法 2 之后 进入算法 2 的操作 系统会显示算法的页面置换情况 最近久未使用的运行图如图 5 3 所示 图 5 3 最近久未使用置换算法运行结果图 4 4 最佳 最佳 OPTOPT 置换算法运行结果 置换算法运行结果 选择算法 3 之后 进入算法 3 的操作 系统会显示算法的页面置换情况 最近久未使用的运行图如图 5