存储管理讲义-南京大学.ppt

虚拟存储管理 请求分页式存储管理 典型的页面替换算法 时钟页面替换算法 当发生缺页中断时，检查指针指向位置的页面： 1）当页面引用位为0时，替换该页面； 2）当页面引用位非0时，对该引用位置0，指针累进 虚拟存储管理 请求分页式存储管理 典型的页面替换算法 时钟页面替换算法的改进 把”引用位”和”修改位”结合起来使用，共组合成四种情况： 最近没有被引用,没有被修改(r=0,m=0) 最近被引用,没有被修改(r=1,m=0) 最近没有被引用,但被修改(r=0,m=1) 最近被引用过,也被修改过(r=1,m=1) 虚拟存储管理 请求分页式存储管理 典型的页面替换算法 最近最少用页面替换算法 总是淘汰在最近一段时间里较久未被访问的页面。 实现：维护一个页面淘汰队列，队尾总是指向最近访问的页面，队头是最近最少使用的页面。 特点：缺页率低，但实现代价高 近似的方法实现：（时间信息更新周期t，较难设定） 设置标志位，最近没有使用页面替换算法(NUR) 多位寄存器，“老化算法” 多位计数器，最不常用页面替换算法(LFU) 多位计时器 Figure 3-18. The aging algorithm simulates LRU in software. Shown are six pages for five clock ticks. The five clock ticks are represented by (a) to (e). Aging - Simulating LRU in Software NFU - Simulating LRU in Software NFU (Not Frequently Used) A counter associated with each page At each clock interrupt, add the value of R bit(0/1) to each page’s counter When a page fault occurs, the page with the lowest counter is chosen for replacement. 虚拟存储管理 请求分页式存储管理 典型的页面替换算法 最近最少用页面替换算法示例： 给某作业分配3个页框，作业依次访问页号：4,3,0,4,1,1,2 访问页号 页面淘汰序列 被淘汰页面 4 4 3 4,3 0 4,3,0 4 3,0,4 1 0,4,1 3 1 0,4,1 2 4,1,2 0 虚拟存储管理 请求分页式存储管理 典型的全局页面替换算法： 全局最佳页面替换算法 工作集模型和工作集置换算法 模拟工作集替换算法 缺页频率替换算法 虚拟存储管理 请求分页式存储管理 全局最佳页面替换算法 进程在 t 时刻发生缺页，则把该页面装入一个空闲页框。每次访问，均检查在内存中的所有页面引用情况，如果页面在时间间隔(t, t+τ)内未被引用，则移出该页面。 全局最佳页面替换算法例 t 0 1 2 3 4 5 6 7 8 9 10 P4 P3 P3 P4 P2 P3 P5 P3 P5 P1 P4 P1 - - - - - - - - - √ - P2 - - - - √ - - - - - - P3 - √ √ √ √ √ √ √ - - - P4 √ √ √ √ - - - - - - √ P5 - - - - - - √ √ √ - - Int P3 P2 P5 P1 Outt P4 P2 P3 P5 P1 P4 is preloaded, and T = 3 虚拟存储管理 请求分页虚拟存储管理的实现 工作集模型 工作集，为确保每个进程每一时刻能够执行下去，在物理存储器中必须有的最少页面集合。(Denning, 1968) 根据工作集的大小分配主存块，以保证工作集所需要的页面能够进入主存。（可变分配） 为避免系统发生抖动，应该限制系统内的作业数量，使它们的工作集总尺寸不超过主存块总数。 虚拟存储管理 请求分页式存储管理 工作集替换算法 进程在 t 时刻发生缺页，则把该页面装入一个空闲页框。每次访问，均检查在内存中的所有页面引用情况，如果页面在时间间隔(t -T, t)内未被引用，则移出该页面。 通过页面被引用的历史情况来预估未来。 t 0 1 2 3 4 5 6 7 8 9 10 P1 P3 P3 P4 P2 P3 P5 P3 P5 P1 P4 P1 √ √ √ √ - - - - - √ √ P2 - - - - √ √ √ √ - - - P3 - √ √ √ √ √ √ √ √ √ √ P4 √ √ √ √ √ √ √ - -