ppt份示范之虚拟内存.ppt

纯请求页面调度 备份仓库 缺页 页表 OS 内部帧表 缺页率低 = 性能可接受 * 页置换算法 FIFO Belady异常 最优 LRU（最近最少使用） 计数器 最不经常使用 (LFU) * 帧分配策略 固定 (i.e. equal share) 按比例(to program size) 优先级 工作集模型 局部 颠簸 如果一个进程工作集未获得足够内存，将引起颠簸 * 作业 2, 4, 5, 8, 11, 17,18, 20 * 内存访问地址顺序:0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 页大小100B，页码序列:1, 4, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1 引用串:1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 * * 给定引用串:1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 如果有三帧: 3 次缺页 如果只有一帧: 11 次缺页 FIFO算法: 可以创建一个FIFO 队列来管理内存中的所有页 调入页时，将它加到队列的尾部 当必须置换一页时，将选择最旧的页 * 总共 15 次缺页 引用串: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 帧 4帧 FIFO 置换算法 – Belady异常 期望: 增加帧数 ? 降低缺页率 * 1 2 3 1 2 3 4 1 2 5 3 4 9 page faults 1 2 3 1 2 3 5 1 2 4 5 10 page faults 4 4 3 * 被置换的页将是最长时间不被使用的页 很难实现，因为需要引用串的未来知识 4帧的例子 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5最优页置换的作用：用来衡量你的算法的效率 * 1 2 3 4 6 page faults 4 5 * total 9 page faults LRU置换为每个页记录该页最后的使用时间 当必须进行页置换时，LRU选择最近最长未被使用的页。 * 引用串: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 计数器的实现 每一个页表项 有一个计数器，每次页通过这个表项被访问，把记录拷贝到计数器中 当一个页需要改变是，查看计数器来觉得改变哪一个页0 * 1 2 3 5 4 4 3 5 8 page faults * total 12 page faults 计数器 每个页表项都关联一个使用时间域 需要一个逻辑时钟或计数器，对每次内存引用，计数器都会增加。 每次内存引用时，时钟寄存器的内容都会复制到相应页表项的使用时间域内 进行页置换时，选择具有最小时间（或者计数器值）的页 问题 需要有哪些信誉好的足球投注网站页表 每次内存访问都需要写页表项的使用时间域 上下文切换时需要维护页表 需要考虑时钟溢出 * 栈 –在一个双链表中保留一个记录页数目的栈 被访问的页 : 移到栈顶 最坏情况下需要改变6个指针 无需为置换进行查找 * * 引用位 每个页都与一个位相关联，初始值位0 当页被访问时，将该页的引用位设为1 如果存在的话置换位为0的页。然而我们并不知道这个置换顺序 一些通过引用位实现的LRU近似页置换算法 附加引用位算法 二次机会法 增强型二次机会法 * 附加引用位算法 在规定时间间隔里（如100ms）记录引用位 操作系统把每个页的引用位转移到其8bit字节的高位，而将其它位右移 选择具有最小值的页进行置换 * 二次机会算法 FIFO+引用位 所有帧形成一个循环队列 每次内存访问，需将访问页的引用位置1 检查当前帧 如果引用位为1，则置为0，并跳到下一帧 如果引用位为0，则置换该页 假如某个页被频繁访问，那么它就不会被置换出去 * * 增强型二次机会算法 一个FIFO循环队列 引用位 修改位 四种类型（引用位，修改位）： (0, 0)最近没有使用也没有修改过 (0, 1) 最近没有使用但曾经被修改过 (1, 0)最近使用过，但没有被修改过 (1, 1)最近使用过并且修改过 当需要置换时，检查页属于哪一类型 置换在最低非空类型中所碰到的页 缺点: 需要多次有哪些信誉好的足球投注网站整个循环队列 * 用一个计数器记录对每一个页的访问次数。 最不经常使用页置换算法（LFU） 替换具有最小计数的页 定期将计数右移一位，以形成指数衰减的平均使用次数 最常使用页置换算法 (MFU) 基于如下理论：具有最小次数的页可能刚刚被置换进来，