ch6 页面置换算法
Overviews 功能与目标 实验设置与评价方法 局部页面算法 最优页面置换算法 先进先出算法 最近最久未使用算法 时钟页面置换算法 最不常用置换算法 Belady现象 LRU FIFO Clock对比 全局页面置换算法 工作集模型 工作集页面置换算法 缺页率置换算法 功能与目标 功能 : 当缺页中断发生,需要调入新的页面而内存已满时,选择内存当中哪个物理页面被置换。 目标 : 尽可能地减少页面的换进换出次数(即缺页中断的次数)。 具体来说,把未来不再使用的或短期内较少使用的页面换出,通常只能在局部性原理指导下依据过去的统计数据来进行预测。 页面锁定 frame locking:用于描述必须常驻内存的操作系统的关键部分或时间关键(time critical)的应用进程。实现的方式是:在页表中添加锁定标记位(lock bit)。 实验设置与评价方法 实例:记录一个进程对页访问的一个轨迹 举例 : 模拟一个实验环境,记录对应的地址访问序列,虚拟地址跟踪(页号, 偏移)… (3,0) (1,9) (4,1) (2,1) (5,3) (2,0) … 而offset可以忽略(页不存在才会产生 page fault),生成的页面轨迹 3, 1, 4, 2, 5, 2, 1, …(替换为,3,1,4,2,5,2,1) 模拟一个页面置换的行为并且记录产生页缺失数的数量 更少的缺失,更好的性能 局部页面置换算法 最优页面置换算法 基本思路:当一个缺页中断发生时,对于保存在内存当中的每一个逻辑页面,计算在它的下一次访问之前,还需等待多长时间,从中选择等待时间最长的那个,作为被置换的页面。 这是一种理想情况, 在实际系统中是无法实现的, 因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问. 最优页面置换算法(Optimal Page Replacement)可用作其他算法的性能评价的依据,(在一个模拟器上运行某个程序, 并记录每一次的页面访问情况,在第二遍运行时即可使用最优算法) 在该算法中,会替换在未来最长持续时间内不会使用的页面。如下图所示有 a b c d e五个页,但是只有四个页帧。此时会产生物理页不够,会产生 Page Fault。...