教学课件PPT 存储管理.ppt

1 第4章存储管理 重要内容存储器连续存储空间管理分页存储管理分段存储管理虚拟存储管理intelx86分段和分页存储结构linux虚拟存储管理windows2003虚拟存储管理 自学 2 存储管理的功能 分配和去配请求和释放主存空间抽象和映射抽象成一维数组或二维地址空间地址转换隔离和共享隔离实现存储保护功能超越隔离机制 提高主存利用率存储扩充虚拟 允许进程虚拟地址空间大于主存空间 3 4 1存储器 4 1 1存储器的层次4 1 2地址转换与存储保护 4 4 1 1存储器的层次 5 逻辑地址 虚地址 cpu所生成的地址物理地址 实地址 内存单元所看到的地址逻辑地址空间 由程序所生成的所有逻辑地址的集合物理地址空间 由逻辑地址所对应的所有物理地址的集合地址转换或重定位 把逻辑地址转换为物理地址 4 1 2地址转换与存储保护 1 6 静态重定位地址转换工作在进程执行前一次完成 无须硬件支持 易于实现 但不允许程序在执行过程中移动位置 早期单用户单任务系统动态重定位地址转换推迟到最后的可能时刻 即进程执行时才完成 允许程序在主存中移动 便于主存共享 主存利用率高 地址转换与存储保护 2 7 存储保护问题 保护操作系统不受用户进程所影响 保护用户进程不受其他用户进程所影响方法存储键保护系统将主存划分成大小相等的若干存储块 并给每个存储块都分配一个单独的保护键 锁 在程序状态字psw中设置有保护键字段 对不同的作业赋予不同的代码 钥匙 钥匙和锁相配才允许访问界限寄存器 下页图 上 下界防护 硬件为分给用户作业的连续的主存空间设置一对上 下界 分别指向该存储空间的上 下界基址 限长防护 基址寄存器存放当前正执行者的程序地址空间所占分区的始址 限长寄存器存放该地址空间的长度 地址转换与存储保护 3 8 正运行的进程是进程2 9 4 2连续存储空间管理 4 2 1固定分区存储管理4 2 2可变分区存储管理4 2 3伙伴系统4 2 4主存不足的存储管理技术 10 4 2 1固定分区存储管理 固定分区存储管理的基本思想主存空间被分成数目固定不变的分区 各分区的大小不等 每个分区只装入一个作业 固定分区存储管理的数据结构主存分配表 指出各分区的起始地址和长度 占用标志 指示此分区是否被使用 作业进入固定分区排队策略每个分区有单独的作业等待队列 所有等待处理的作业排成一个等待队列 11 固定分区的优缺点 优点能够解决单道程序运行在并发环境下不能与cpu速度匹配的问题解决了单道程序运行时主存空间利用率低的问题实现简单缺点大作业可能无法装入主存空间利用率不高 会出现内碎片扩充困难限制多道运行程序的个数 12 4 2 2可变分区存储管理 可变分区存储管理是按作业的实际大小来划分分区 且分区个数也是随机的 实现多个作业对主存的共享 进一步提高主存资源利用率 13 可变分区方式主存分配示例 操作系统 作业1 空闲区 作业2 空闲区 操作系统 作业1 空闲区 作业2 空闲区 作业3 操作系统 作业1 空闲区 作业3 14 可变分区存储管理数据结构 可变分区主存分配表可由两张表格组成 已分配区表未分配区表 15 可变分区回收算法 16 链表空闲区管理方法 空闲区开头单元存放本空闲区长度及下个空闲区起始地址 把所有空闲区都链接起来 设置第一块空闲区地址指针 让它指向第一块空闲区地址 申请空闲区 沿链查找并取一个长度能满足要求的空闲区 归还空闲区 把此空闲区链入空闲区链表的相应位置 17 可变分区管理分配算法 1 最先适应分配算法空闲区通常按地址从小到大排列 分配第一个满足长度要求的空闲区 优点 分配从低地址开始 使高地址部分比较少用 以保持一个大空闲区 有利于大作业的装入 缺点 分区利用不均衡 回收分区比较麻烦 18 2 下次适应分配算法1 的变种 每次分配时从未分配区的上次扫描结束处顺序查找 可以解决1 的缺点 3 最优适应分配算法分配能满足要求的最小区 可以将空闲区按照大小从小到大排列 查找第一个满足要求的 优点 主存利用率好 缺点 分割剩下的空闲区比较小 难以利用 查找时间比较长 19 4 最坏适应分配算法分配能满足要求的最大区 可以将空闲区按照大小从大到小排列 查找第一个满足要求的 效率大致等同于最先适应法 5 快速适应分配算法为经常用到的长度的空闲区设置单独的链表 优点 查找快速 缺点 归还时与相邻空闲区的合并即复杂又费时 20 下表为某系统中的空闲分区表 系统采用可变式分区存储管理策略 现有以下作业序列 96kb 20kb 200kb 分别使用首次适应 最佳适用和最坏适用算法来处理这个作业序列 试问哪一种算法可以满足该作业序列的请求 为什么 例题 21 4 2 3伙伴系统 伙伴原理伙伴系统是一种固定分区和可变分区折中的主存管理算法 基本原理 任何尺寸为2i的空闲块可以被分为两个尺寸为2i 1的空闲块 这两个空闲块称为伙伴 伙伴通过对大块的物理主存划分而获得假如从第0个页面开始到第3个页面结束的主存每次都对半划分 那么第一次划分获得大小为2页的伙伴 如0 1和2 3进一步划分 可以获得大小为1页的伙伴 例如0和1 2和3 0 1 2 3 22 伙伴系统原理 23 4 2 4主存不足的存储管理技术 1 移动技术 24 有关移动问题讨论 移动条件在可变分区算法中 随着进程不断的装入和撤销 导致主存中常常出现分散的小空闲区 称为碎片 当在未分配区中找不到足够大的空闲区来装入新进程时 可采用移动技术 将分散的空闲区汇集成片 移动时机进程撤销之后释放分区时 如果它不与空闲区邻接 立即实施移动 进程装入分区时 如果它不与空闲区邻接 立即实施引动 25 移动算法 假设进程a请求分配xkb主存 步骤1 查主存分配表 若有大于xkb的空闲区 转步骤4 步骤2 若空闲区总和小于xkb 则令进程a等待主存资源 步骤3 移动主存的相关分区信息 修改主存分配表的有关表项 修改被移动者的基础寄存器等信息 步骤4 分配xkb主存 修改主存分配表的有关项 设置进程a的基址寄存器 有申请者等待时予以释放 算法结束 开销非常大 极少使用 26 2 对换技术 对换的作用通过将主存和磁盘的进程移出移入 解决主存容量不足的问题 对换进程的选择选择哪个进程换出 决定把进程的哪些信息移出去 需要确定对换时机 unix对换器windows对换器 27 在任何时候只在内存中保留所需的指令和数据由用户实现 让不会同时调用的子模块共同使用同一内存区 a30k a占用bc共用def共用 3 覆盖技术 28 碎片 外部碎片 存在分区外 所有内存之和可以满足请求 但不连续内部碎片 存在分区内 但已不能满足任何请求解决外部碎片问题的方法紧缩 compaction 移动内存内容 以便所有空闲空间合并成一整块允许物理地址空间为非连续分页分段 29 4 3分页式存储管理 4 3 1分页式存储管理的基本原理4 3 2快表4 3 3分页式存储空间的分配和去配4 3 4分页式存储空间的页面共享和保护4 3 5多级页表4 3 6反置页表 30 4 3 1分页式存储管理 为什么要引进分页技术 基本原理页面 进程逻辑地址空间分成大小相等的区 页框 帧 主存物理地址空间分成大小相等的区 其大小跟页面大小相等 逻辑地址形式 页号 页内位移页表和地址转换 后面图 基本原理 1 31 基本原理 2 作业的页面与分给的页框如何建立联系呢 逻辑地址 页面 如何变换成物理地址 页框 呢 作业的物理地址空间由连续变成分散后 如何保证程序正确执行呢 使用动态重定位技术 给每个页面设立重定位寄存器 重定位寄存器的集合便称页表 页表是操作系统为每个用户作业建立的 用来记录程序页面和主存对应页框的对照表 32 0123 01234567 逻辑内存 页表 物理内存 页号帧号 帧号 物理内存和逻辑内存的分页模型 33 逻辑地址到物理地址的转换 0123 页表 例 说明 页大小为4b 页表如图所示 将逻辑地址0 3 4 13转换为相应物理地址答案 20 23 24 9 0 4 0 05 4 0 203 4 0 35 4 3 234 4 1 06 4 0 2413 4 3 12 4 1 9 34 练习 逻辑地址到物理地址的转换 说明 页大小为1024b 页表如图所示 将逻辑地址1011 2148 3000 4000 5012转换为相应物理地址 0123 页表 答案 3059 1124 1976 7072 逻辑地址非法 1011 1024 0 10112 1024 1011 30592148 1024 2 1001 1024 100 11243000 1024 2 9521 1024 952 19764000 1024 3 9286 1024 928 70725012 1024 4 916页号4不存在 35 4 3 2快表 相联存储器 翻译后备缓冲 translationlook asidebuffer tlb 关联的快速内存tlb与页表一起工作快表项包含页号及对应的页框号 当把页号交给快表后 它通过并行匹配同时对所有快表项进行比较 如果找到 立即输出页框号 并形成物理地址 如果找不到 再查找主存中的页表以形成物理地址 同时将页号和页框号登记到快表中 当快表已满且要登记新页时 系统需要淘汰旧的快表项 36 采用相联存储器的地址转换 假定访问主存时间为100毫微秒 访问相联存储器时间为20毫微秒 相联存储器为32个单元时快表命中率可达90 按逻辑地址存取的平均时间为 100 20 90 100 100 20 1 90 130比两次访问主存的时间100 2 200下降了三成多 37 4 3 3分页式存储空间的分配和去配 1 位示图法每位与一帧相对应 用0 1表示对应块为空闲 已占用 用另一专门字记录当前空闲块数 链表方法每个表项包含 进程占用区 p 还是空闲区 h 起始地址长度指向下一表项的指针 38 主存分配的位示图和链表方法 39 4 3 4分页存储空间的页面共享和保护 数据共享允许不同进程对共享的数据页用不同的页号 只要让各自页表中的有关表项指向共享的数据页框 程序共享指令包含指向其它指令或数据的地址 标志位保护方法在页表中增加标志位 指出此页的信息只读 读写 只可执行 不可访问等 键保护方法 40 4 3 5多级页表 多级页表的概念多级页表的具体做法逻辑地址结构逻辑地址到物理地址转换过程 41 多级页表的概念 系统为每个进程建一张页目录表 它的每个表项对应一个页表页 而页表页的每个表项给出了页面和页框的对应关系 页目录表是一级页表 页表页是二级页表 逻辑地址结构有三部分组成 页目录 页表页和位移 42 多级页表地址转换过程 页框号页内位移 页目录位移页表页位移页内位移 b f 进程一级页表 进程二级页表 物理地址 逻辑地址 页目录表控制寄存器 43 解决页表页占用主存空间的问题 进程运行涉及页面的页表页应放在主存 其他页表页使用时再调入 在页目录表中增加特征位 指示对应的页表页是否已调入主存 地址转换机构根据逻辑地址中的dir 去查页目录表对应表项 如未调入 应产生一个 缺页表页 中断信号 请求操作系统将页表页调入主存 44 4 3 5反置页表 1 45 反置页表 2 ipt是为主存中的每一个物理块建立一个页表并按照块号排序 该表每个表项包含正在访问该页框的进程标识 页号及特征位 哈希链指针 用来完成逻辑地址到物理地址的转换 46 反置页表 3 反置页表地址转换过程如下 逻辑地址给出进程标识和页号 用它们去比较ipt 若整个反置页表中未能找到匹配的页表项 说明该页不在主存 产生请页中断 请求操作系统调入 否则 该表项的序号便是页框号 块号加上位移 便形成物理地址 47 分页技术不会产生外部碎片 但会产生内部碎片分页的重要特点是用户观点的内存和实际的物理内存的分离分页可以共享共同代码 分页内存管理方案小结 48 4 4分段式存储管理 4 4 1程序的分段结构4 4 2分段式存储管理的基本原理4 4 3段的共享和保护4 4 4分段和分页的比较 49 4 4 1程序的分段结构 分段存储管理引入的主要原因满足用户 程序员 编程和使用上的要求 模块化程序设计的分段结构 下页图 分页存储管理 一维地址结构分段存储管理 二维地址结构 50 模块化程序设计的分段结构 51 4 4 2分段式存储管理的基本原理 1 二维逻辑地址段号 段内地址段表段表指出主存中各分段的段号 段起始地址和段长度 起到基址 限长寄存器的作用 段式存储管理的地址转换和存储保护 52 分段式存储管理的基本原理 2 53 段表 将二维的逻辑地址映射为一维物理地址段基地址 包含该段在内存中的开始物理地址段界限 指定该段的长度逻辑地址 段号s 段内偏移d逻辑地址到物理地址的转换段号与段表长度进行比较 若段号超过了段表长度 则越界 非法地址 否则转2 根据段表始址和段号计算出该段对应段表项的位置 从中读出该段在内存的起始地址 检查段内地址是否超过该段的段长 若超过则越界 非法地址 否则转3 将该段的起始地址与段内位移相加 从而得到要访问的物理地址 逻辑地址到物理地址转换 54 逻辑地址到物理地址转换例 说明 段表如表1所示 将表2所示逻辑地址转换为相应物理地址答案 见表3 表1表2表3 90 88 100 96 55 说明 段表如表1所示 将表2所示逻辑地址转换为相应物理地址答案 见表3 逻辑地址到物理地址转换练习 表1表2 表3 210 430 2350 10 500 90 1350 400 112 95 段号5不存在 56 4 4 3段的共享 多对基址 限长寄存器段的共享 是通过不同作业段表中的项指向同一个段基址来实现 几道作业共享的例行程序就可放在一个段中 只要让各道作业的共享部分有相同的基址 限长值 对共享段的信息必须进行保护 57 4 4 4分段和分页的比较 1 分段是信息的逻辑单位 由源程序的逻辑结构所决定 用户可见 段长可根据用户需要来规定 段起始地址可从任何主存地址开始 分段方式中 源程序 段号 段内位移 经连结装配后地址仍保持二维结构 58 分段和分页的比较 2 分页是信息的物理单位 与源程序的逻辑结构无关 用户不可见 页长由系统确定 页面只能以页大小的整倍数地址开始 分页方式中 源程序 页号 页内位移 经连结装配后地址变成了一维结构 59 4 5虚拟存储管理 4 5 1虚拟存储管理的概念4 5 2请求分页虚拟存储管理4 5 3请求分段虚拟存储管理4 5 4请求段页式虚拟存储管理 60 4 5 1虚拟存储管理的概念 虚拟内存 virtualmemory 允许进程的执行不必完全在内存中 程序可以比物理内存大 在许多情况下不需要将整个程序放到内存中 处理异常错误条件的代码 几乎不执行 数组 链表和表通常分配了比实际所需更多的内存程序的某些选项或特点可能很少使用能够执行只有部分在内存中的程序的好处程序不再受现有的物理内存空间限制更多程序可同时执行 cpu利用率相应增加用户程序会运行的更快 61 虚拟存储器 虚拟存储器的定义 在具有层次结构存储器的计算机系统中 采用自动实现部分装入和部分对换功能 为用户提供一个比物理主存容量大得多的 可寻址的一种 主存储器 62 虚拟存储器的概念图 63 程序的局部性原理 指程序在执行过程中的一个较短时间内 所执行的指令地址或操作数地址分别局限于一定的存储区域中 又可细分时间局部性和空间局部性 时间局部性 最近访问过的程序代码和数据很快又被访问 空间局部性 某存储单元被使用之后 其相邻的存储单元也很快被使用 64 实现虚拟存储器须解决的问题 主存辅存统一管理问题逻辑地址到物理地址的转换问题部分装入和部分对换问题 65 虚拟存储管理实现技术 请求分页虚拟存储管理请求分段虚拟存储管理请求段页式虚拟存储管理 66 4 5 2请求分页虚拟存储系统 1 请求分页虚拟存储系统的硬件支撑 1 主存管理单元mmu完成逻辑地址到物理地址的转换功能 它接受虚拟地址作为输入 物理地址作为输出 直接送到总线上 对主存单元进行寻址 67 mmu主要功能 1 管理硬件页表基址寄存器 2 分解逻辑地址 3 管理快表tlb 4 访问页表 5 发出缺页中断或越界中断 并将控制权交给内核存储管理处理 6 设置和检查页表中各个特征位 68 2 请求分页虚拟存储系统的基本原理 分页式虚存不把作业信息 程序和数据 全部装入主存 仅装入立即使用的页面 在执行过程中访问到不在主存的页面时 产生缺页中断 再从磁盘动态地装入 怎样才能发现页面不在主存中呢 怎样处理这种情况呢 采用的办法是 扩充页表的内容 增加驻留标志位和页面辅存的地址等信息 69 页式虚拟存储管理页表扩展 其它标志 访问权限位修改位 modified 引用位 renferenced 70 请求分页虚存地址转换过程 71 请求页式虚拟存储系统优缺点 优点 作业的程序和数据可按页分散存放在主存中 减少移动开销 有效解决了碎片问题 既有利于改进主存利用率 又有利于多道程序运行 缺点 要有硬件支持 要进行缺页中断处理 机器成本增加 系统开销加大 72 3 页面装入策略和页面清除策略 页面装入主存 有两种策略 请页式调度 仅调入所需页面预调式调度 使用前预先调入若干页何时把一个修改过的页面写回辅存储器 有两种策略 请页式清除 仅当一页被选中进行替换且被修改过 才写回磁盘 预清除 成批进行 所有被更改过的页面 在需要替换前把它们都写回磁盘 73 4 页面分配策略 系统为进程分配主存 需考虑因素 分给进程的空间越小 同一时间处于主存的进程就越多 至少有一个进程处于就绪态的可能性就越大 如果进程只有小部分在主存里 即使局部性很好 缺页中断率还会相当大 因程序的局部性原理 分给进程的主存超过一定限度后 再增加主存空间 不会明显降低进程的缺页中断率 74 页面分配策略 固定分配 进程保持页框数固定不变 称固定分配 进程创建时 根据进程类型和程序员的要求决定页框数 只要有一个缺页中断产生 进程就会有一页被替换 75 页面分配策略 可变分配 进程分得的页框数可变 称可变分配 进程执行的某阶段缺页率较高 说明目前局部性较差 系统可多分些页框以降低缺页率 反之说明进程目前的局部性较好 可减少分给进程的页框数 76 页面替换策略 局部替换和全局替换 如果页面替换算法的作用范围是整个系统 称全局页面替换算法 它可以在运行进程间动态地分配页框 如果页面替换算法的作用范围局限于本进程 称为局部页面替换算法 它实际上需要为每个进程分配固定的页框 77 固定分配和局部替换策略配合使用 1 进程分得的页框数不变 发生缺页中断 只能从进程的页面中选页替换 保证进程的页框总数不变 策略难点 应给每个进程分配多少页框 给少了 缺页中断率高 给多了 使主存中能同时执行的进程数减少 进而造成处理器和其它设备空闲 78 固定分配和局部替换策略配合使用 2 采用固定分配算法 系统把页框分配给进程 采用 平均分配 按比例分配 优先权分配 79 可变分配和全局替换策略配合使用 先每个进程分配一定数目页框 os保留若干空闲页框 进程发生缺页中断时 从系统空闲页框中选一个给进程 这样产生缺页中断进程的主存空间会逐渐增大 有助于减少系统的缺页中断次数 系统拥有的空闲页框耗尽时 会从主存中选择一页淘汰 该页可以是主存中任一进程的页面 这样又会使那个进程的页框数减少 缺页中断率上升 80 可变分配和局部替换配合使用 其实现要点如下 1 新进程装入主存时 根据应用类型 程序要求 分配给一定数目页框 可用请页式或预调式完成这个分配 2 产生缺页中断时 从该进程驻留集中选一个页面替换 3 不时重新评价进程的分配 增加或减少分配给进程的页框以改善系统性能 81 5 缺页中断率 页面替换当主存空间已满又必须装入新页时 选择主存中某页淘汰 页面淘汰算法选择哪页被淘汰的算法 抖动 thrashing 现象刚被淘汰的页面立即又要调用 调入不久又被淘汰 淘汰不久再被调入 如此反复 整个系统频繁调页 使得几乎无时间进行计算任务 82 影响缺页中断率的因素 1 假定作业p共计n页 系统分配给它的主存块只有m块 m n 如果作业p在运行中成功的访问次数为s 不成功的访问次数为f 则总的访问次数 为 a s f又定义 f f a称f为缺页中断率 83 影响缺页中断率的因素 2 影响缺页中断率f的因素有 1 主存页框数 2 页面大小 3 页面替换算法 4 程序特性 84 6 全局页面替换策略 1 最佳页面替换算法opt2 先进先出页面替换算法fifo3 最近最少用页面替换算法lru4 第二次机会页面替换算法scr5 时钟页面替换算法clock注 所有算法例子中采用请页时调度 即最初假设主存中没有页面 85 1 最佳替换算法 调入一页而必须淘汰一个旧页时 所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页 opt算法 optimal 可用来作为衡量各种具体算法的标准 86 opt例 可用帧数量3 引用串如下 70120304230321201701 缺页率p 9 20 45 87 2 先进先出页面替换算法 基于程序总是按线性顺序来访问物理空间这一假设 算法总是淘汰最先调入主存的那一页 或者说在主存中驻留时间最长的那一页 常驻的除外 实现技术 1 设置具有m个元素的页号表 控制换页 2 引入指针链成队列 88 fifo例 容易理解和实现 性能并不总是很好例 可用帧数量3 引用串如下 70120304230321201701 缺页率p 15 20 75 89 belady异常 页错误率随着所分配的帧数增加而增加的现象 例 可用帧数3 9次缺页 可用帧数4 10次缺页 90 3 最近最少用页面替换算法 算法淘汰的页面是在最近一段时间里较久未被访问的那页 根据程序局部性原理 那些刚被使用过的页面 可能马上还要被使用 而在较长时间里未被使用的页面 可能不会马上使用到 91 lru例 思想 置换过去最长时间没有使用的页例 可用帧数量3 引用串如下 70120304230321201701 缺页率p 12 20 60 92 lru算法实现 页面淘汰队列 队列中存放当前在主存中的页号 每当访问一页时就调整一次 使队列尾总指向最近访问的页 队列头就是最近最少用的页 发生缺页中断时总淘汰队列头所指示的页 执行一次页面访问后 需要从队列中把该页调整到队列尾 93 lru算法实现 标志位法 每页设置一个引用标志位r 访问某页时 由硬件将页标志位r置1 隔一定时间t将所有页的标志r均清0 发生缺页中断时 从标志位r为0的页中挑选一页淘汰 挑选到要淘汰的页后 也将所有页的标志位r清0 94 lru算法实现 多位计数器法 每个页面设置一个多位计数器 又叫最不常用页面替换算法lfu 每当访问一页时 就使它对应的计数器加 当发生缺页中断时 可选择计数值最小的对应页面淘汰 并将所有计数器全部清 95 lru算法实现 多位计时器法 为每个页面设置一个多位计时器 每当页面被访问时 系统的绝对时间记入计时器 比较各页面的计时器的值 选最小值的未使用的页面淘汰 因为 它是最 老 的未使用的页面 96 4 第二次机会页面替换算法 改进fifo算法 把fifo与页表中的 引用位 结合起来使用 检查fifo中的队首页面 最早进入主存的页面 如果它的 引用位 是0 这个页面既老又没有用 选择该页面淘汰 如果 引用位 是1 说明它进入主存较早 但最近仍在使用 把它的 引用位 清0 并把这个页面移到队尾 把它看作是一个新调入的页 算法含义 最先进入主存的页面 如果最近还在被使用的话 仍然有机会作为像一个新调入页面一样留在主存中 97 5 时钟页面替换算法 算法实现要点 一个页面首次装入主存 其 引用位 置0 主存中的任何页面被访问时 引用位 置1 淘汰页面时 从指针当前指向的页面开始扫描循环队列 把遇到的 引用位 是1的页面的 引用位 清0 跳过这个页面 把所遇到的 引用位 是0的页面淘汰掉 指针推进一步 扫描循环队列时 如果遇到的所有页面的 引用位 为1 指针就会绕整个循环队列一圈 把碰到的所有页面的 引用位 清0 指针停在起始位置 并淘汰掉这一页 然后 指针推进一步 98 时钟页面替换改进算法 1 把 引用位 和 修改位 结合起来使用 共组合成四种情况 1 最近没有被引用 没有被修改 r 0 m 0 2 最近被引用 没有被修改 r 1 m 0 3 最近没有被引用 但被修改 r 0 m 1 4 最近被引用过 也被修改过 r 1 m 1 99 时钟页面替换改进算法 2 步1 选择最佳淘汰页面 从指针当前位置开始 扫描循环队列 扫描过程中不改变 引用位 把遇到的第一个r 0 m 0的页面作为淘汰页面 步2 如果步1失败 再次从原位置开始 查找r 0且m 1的页面 把把遇到的第一个这样的页面作为淘汰页面 而在扫描过程中把指针所扫过的页面的 引用位 r置0 步3 如果步2失败 指针再次回到了起始位置 由于此时所有页面的 引用位 r均己为0 再转向步1操作 必要时再做步2操作 这次一定可以挑出一个可淘汰的页面 100 页置换算法练习 已知页面走向为1 2 1 3 1 2 4 2 1 3 4 且开始执行时内存中没有页面 若只给该作业分配2个物理块 当采用fifo opt lru页置换算法时缺页率为多少 假定现有一种置换算法 该算法淘汰页面的策略为当需要淘汰页面时 就把刚使用过的页面作为淘汰对象 试问就相同的页面走向 其缺页率又为多少 假如分配3个物理块呢 101 12131242134 fifo9 11 81 8 opt7 11 63 6 lru8 11 72 7 new8 11 72 7 2个物理块 102 12131242134 3个物理块 fifo5 11 45 5 opt5 11 45 5 lru6 11 54 5 new6 11 54 5 103 8 请求分页虚拟存储管理的几个设计问题 1 页面大小考虑页表大小 大页内存利用 小页 减少碎片 页读写所需时间 大页精度 小页降低页错误数量 大页分析 没有最佳答案 趋向于大页 104 2 页面交换区 替换算法要挑选页面淘汰出主存 但被淘汰出去的页面可能很快使用 又要被重新装入主存 操作系统必须保存被淘汰的页面 例如unix linux使用交换区临时保存页面 系统初始化时 保留一定盘空间作交换区 105 3 写时复制 1 写时复制 copy on write 是存储管理节省物理主存 页框 的一种页面级优化技术 已被unix和windows等采用 能减少主存页面内容的复制操作 减少相