页面置换算法.ppt

4 3 4页面置换算法 1 最优算法 OPT算法 2 先进先出算法 FIFO算法 3 最久未使用页面置换算法 LRU算法 4 LRU近似算法 下一页 1 最优算法 Optimal算法 它是一种理想化的算法 性能最好 但在实际上难于实现 即选择那些永不使用的 或者是在最长时间内不再被访问的页面置换出去 但是要确定哪一个页面是未来最长时间内不再被访问的 目前来说是很难估计的 所以该算法通常用来评价其它算法 例 假定系统为某进程分配了三个物理块 并考虑有以下的页面号引用串 7 0 l 2 0 3 0 4 2 3 0 3 2 l 2 0 l 7 0 1 如下图所示 进程运行时先将7 0 1三个页面装入内存 当进程访问页面2时 产生缺页中断 此时OS根据最佳置换算法 页面7将在第18次才被访问 是三页中将最久不被访问的页面 所以被淘汰 接着访问页面0时 发现已在内存中 而不会产生缺页中断 以此类推 从图可以看出 采用最佳置换算法 只发生了6次页面置换 下一页 2 先进先出算法 FIFO算法 这种算法的基本思想是 总是先淘汰那些驻留在内存时间最长的页面 即先进入内存的页面先被置换掉 理由是 最先进入内存的页面不再被访问的可能性最大 下一页 图4 20先进先出算法存储分块表构造 下一页 3 最久未使用页面置换算法 LRU LeastRecentlyUsed算法 这种算法的基本思想是 如果某一页被访问了 那么它很可能马上又被访问 反之 如果某一页很长时间没有被访问 那么最近也不太可能会被访问 这种算法考虑了程序设计的局部性原理 其实质是 当需要置换一页时 选择在最近一段时间最久未使用的页面予以淘汰 实现这种算法可通过周期性地对 引用位 进行检查 并利用它来记录一页面自上次被访问以来所经历的时间t 淘汰时选择t最大的页面 下一页 4 LRU近似算法 这种算法 只要在存储分块表 或页表 中设一个 引用位 当存储分块表中的某一页被访问时 该位由硬件自动置1 并由页面管理软件周期性把所有引用位置0 这样 在一个时间周期T内 某些被访问过的页面其引用位为1 而未被访问过的页面其引用位为0 因此 可根据引用位的状态来判别各页面最近的使用情况 当需要置换一页面时 选择其引用位为0的页 如图4 21所示的算法 图4 22是这种近似算法的一个例子 下一页 图4 21LRU近似算法 下一页 图4 22LRU近似算法举例 返回本节 4 3 5请求式分页存储管理性能分析举例 1 程序设计的质量2 页面的大小3 分配的内存块数4 页面置换算法性能 下一页 例1 主存块数m 3 置换算法采用FIFO算法 缺页中断次数及缺页率如图4 23所示 在图4 23中 P行表示页面走向 M行表示在主存中的页面号 其中带有 的表示新调入页面 在M行的各列按调入的顺序排列 带有圆圈的数字表示下一时刻将被淘汰页面 F行表示是否引起缺页中断 带 号的表示引起缺页中断 从图4 23可以看出 缺页中断页数为9次 缺页率f 9 12 75 下一页 图4 23FIFO算法性能分析 m 3 下一页 例2 设m 4 仍采用FIFO算法 缺页中断次数及缺页率如图4 24所示 可以算出 在分配给该作业的内存块数增加到4时 缺页中断由图4 23的9次反而增加到了10次 缺页率由75 增加到10 12 83 这就是FIFO算法的一种异常现象 随着分配的主存块数的增加 缺页中断次数不但没有降低 反而增加了 这与该算法定全不考虑程序的动态特征有关 下一页 图4 24FIFO算法性能分析 m 4 下一页 例3 设m 3 采用LRU算法 缺页中断次数及缺页率如图4 25所示