操作系统原理 第四章 存储器管理.ppt

2007 8 1515 2615 26 操作系统 存储器管理 1 第四章存储器管理 存储管理的机制分区管理分页管理分段管理虚拟存储器的概念请求页式管理页面置换算法请求段式管理 2007 8 1515 2615 26 操作系统 存储器管理 2 4 1存储管理概述 存储管理的目的主存的分配和回收记住内存每个位置的状态 在系统程序或用户作业提出申请时 实施分配 并修改分配记录 接受系统或用户释放的存储区 或主动收回不再用的存储区 并相应地修改分配记录表 2007 8 1515 2615 26 操作系统 存储器管理 3 提高内存利用率 扩充 内存容量信息保护 4 1存储管理概述 2007 8 1515 2615 26 操作系统 存储器管理 4 内外存数据传输的控制用户程序控制操作系统控制交换 S 由OS把那在内存中处于等待状态的进程换出内存 就绪进程换入内存 请求调入 Ondemand 和预调入 Onprefetch 4 1存储管理概述 2007 8 1515 2615 26 操作系统 存储器管理 5 内存管理的内容分配结构 放置策略 交换策略 调入策略 回收策略 4 1存储管理概述 2007 8 1515 2615 26 操作系统 存储器管理 6 内存信息的共享与保护上下界保护法保护键法为每个被保护存储块分配一个单独的保护键 在程序状态字中设置相应的开关字段 不同的进程值不一样 匹配时 方可进行访问 界限寄存器与CPU的用户态和核心态工作方式相结合用户态进程只能访问在界限寄存器所规定范围内的内存部分 而核心态进程则可访问整个内存地址空间 4 1存储管理概述 2007 8 1515 2615 26 操作系统 存储器管理 7 4 2程序的装入和链接 2007 8 1515 2615 26 操作系统 存储器管理 8 程序的装入绝对装入方式 AbsoluteLoadingMode 编译程序产生绝对地址目标代码 由装入程序根据装入模块中的地址 将程序和数据装入内存 2007 8 1515 2615 26 操作系统 存储器管理 9 2 可重定位装入方式 RelocatableLoadingMode 重定位 在装入时对目标程序中的指令和数据地址的修改过程 4 2程序的装入和链接 Load1 12500 2007 8 1515 2615 26 操作系统 存储器管理 10 静态地址重定位 是指作业在装入时随即进行的地址变换方式 这一工作由装配程序完成 优点 无需增加硬件地址变换机构 实现简单 缺点 程序经地址定位后就不能再移动了 程序在存储空间中只能连续分配 多个用户难以共享存于内存中的同一程序 4 2程序的装入和链接 2007 8 1515 2615 26 操作系统 存储器管理 11 3 动态运行时装入方式 DynamicRun TimeLoading 程序执行过程中 当访问指令或数据时 才进行的地址变换方法 称为动态重定位 靠硬件地址变换机构实现的 基地址寄存器 重定位寄存器 BR程序虚地址寄存器VR地址MA BR VR 优点 可对内存进行非连续分配 提供了实现虚存的基础 有利于程序段的共享 4 2程序的装入和链接 2007 8 1515 2615 26 操作系统 存储器管理 12 4 2程序的装入和链接 2007 8 1515 2615 26 操作系统 存储器管理 13 程序的链接静态链接 将各模块及库函数链接成一个装配模块 以后不再拆开 装入时动态链接 各目标模块装入内存时 边装入边链接 运行时动态链接 对模块的链接 是在程序执行中 才进行链接 4 2程序的装入和链接 2007 8 1515 2615 26 操作系统 存储器管理 14 4 3连续分配存储管理方式 单一连续分配存储区的分配内存分配和回收策略优点管理简单 不要求专用的硬件支持 为防止破坏OS 设置界限寄存器 易于实现 2007 8 1515 2615 26 操作系统 存储器管理 15 缺点存储器利用率低缺乏灵活性 程序所需应小于内存 否则提供覆盖 某些系统中安全性差 信息不共享CPU利用率低 周转时间长 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 16 固定分区工作原理在系统生成时 将内存划分为若干各分区 每个分区的大小可以不等 一经划分 不能更改 系统对内存的管理和控制通过分区说明表说明各区的区号 大小 起始地址及状态 特点可使多个作业共享内存 但管理简单 内存利用率太低 对工作负荷明确的作业比较合适 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 17 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 18 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 19 动态分区工作原理存储空间的划分是在装入作业时进行的 且使分区大小正好适应作业的需要 数据结构空闲分区表 序号 大小 起址 状态空闲分区链 在每个分区中附上一个表格信息 状态 0 1 大小 指针 空白分区才有 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 20 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 21 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 22 分区管理算法首次适应算法 FirstFit 每个空白区按地址递增的顺序链接在一起 特点 尽量使用低端地址 以保持高址部分的大空闲区 低址部分有很多小空白区 增加查找时间开销 循环首次适应算法从上次查找的位置的下一个空闲空闲分区开始查找 空闲分区分布均匀 查找时间缩短 但系统会缺少大的空闲分区 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 23 最佳适应算法空白区按大小递增的顺序链在一起 变量FREE中的始端指针总指向最小的空白区 特点 平均而言 查找时间较少 选择最适合的空白区 形成很多小碎片 找一个大空白区时较慢 回收时费时 先拼接 再把该区插入适当位置 最差适应算法空白区按容量递减次序排列 特点 分配时间快 剩下的空白分区仍可用 各空白区比较均匀地减少 工作一段时间后 就不能满足大空白区的要求 回收麻烦 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 24 算法分析特点 有助于多道程序设计 只需要界限地址寄存器 用于存储保护 算法简单 易于实现 但会产生碎片 降低存储器的利用效率 分区的大小 受内存容量限制 几种算法比较 搜索速度 释放速度 空闲区的利用 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 25 分区的分配在未分配表中找出一个足够大的空白分区 如比进程要求的大 则分为两部分 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 26 分区的回收检查回收的分区是否与空白区邻接 如有则加以合并 上邻接 下邻接 上下邻接 2007 8 1515 2615 26 操作系统 存储器管理 27 伙伴系统 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 28 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 29 可重定位分区分配 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 30 原理 内存紧凑地址映射地址空间 在编译后 一个目标程序所限定的地址 即地址空间仅仅是指程序用来访问信息所用的一系列地址单元的集合 这些单元编号称为逻辑地址 相对地址 存储空间 指主存中一系列存储信息的物理单元的集合 这些单元的编号称为物理地址或绝对地址 实现动态重定位技术 访问指令或数据时 通过重定位寄存器来自动修改访问存储器的地址 2007 8 1515 2615 26 操作系统 存储器管理 31 2007 8 1515 2615 26 操作系统 存储器管理 32 动态重定位分区分配算法 2007 8 1515 2615 26 操作系统 存储器管理 33 内存紧凑两种时机在某个分区被回收时 如不与空白区邻接 则立即进行内存紧凑 在为作业分配而找不到足够大的空白区时再进行内存紧凑 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 34 对换技术对换 S 把内存中的暂不运行的进程或暂不使用的数据 换出到外存 把已具备运行条件的进程 或进程所需要的数据和程序 换入内存 并将控制转给它 整体对换 进程对换 用于分时系统 解决内存紧张问题 部份对换 页面对换 分段对换 以请求分页和请求分段存储管理为基础 用于支持虚拟存储系统 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 35 交换空间的管理文件区 离散分配 提高存储空间的利用率 对换区 连续分配 提高交换速度 对换空间的分配与回收 注意空闲区的拼接交换区分配算法 首次适应算法 循环适应算法和最佳适应算法 2007 8 1515 2615 26 操作系统 存储器管理 36 换入和换出消息m中有 分区号i 基址basei 长度sizei 方向和外存交换区中分区始址 SWAPINBeginlocalmm base basei m ceiling basei sizei m direction in m source backupstorebasei send m i devicequeue end 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 37 S i Beginlocalmm base basei m ceiling basei sizei m direction out m destination baseoffreeareaons backupstorebasei m destination send m i devicequeue end 4 3连续分配存储管理方式 2007 8 1515 2615 26 操作系统 存储器管理 38 4 4基本分页存储管理 基本原理实现方法各进程的地址空间分成大小相等的页 把内存的存储空间也分成与页大小相同的片 称为物理块 在分配存储空间时 以块为单位来分配 页面大小 2i 1K 2K 4K等 2007 8 1515 2615 26 操作系统 存储器管理 39 2007 8 1515 2615 26 操作系统 存储器管理 40 分页管理存储地址结构 页号P 位移量W 0 12 11 31 若逻辑空间地址为A 页面大小为L 则 页号P 页内地址d 2007 8 1515 2615 26 操作系统 存储器管理 41 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 42 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 43 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 44 2007 8 1515 2615 26 操作系统 存储器管理 45 地址变换页表采用动态重定位技术 为作业的每页设置一个重定位寄存器 这些寄存器组成一组 称为页表 其中一个表目为该页在主存中的块号 在主存中专门分配一些存储单元来存放页表 页表始址和长度存放在控制寄存器中 页表的大小页表始址的选择为了快速地根据页表始址和页号找到所需相应表目 页表的始址应为2的幂 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 46 地址变换页号P页内地址W3112110找到地址变换 P W B W 实际地址 在开始执行 或恢复执行 一个作业时 由系统把页表始址和页表长度放入控制寄存器中 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 47 地址映射机制 页号块号存取控制 页描述符 如果页号 页表长度 则中断 否则继续 如果访问非法 则中断 否则继续 页号位移量 虚拟地址LA 块号位移量 物理地址 页表始址长度 页表寄存器PTR 页表 块号存取控制 页描述子 页号01 块号 位移量 2007 8 1515 2615 26 操作系统 存储器管理 48 根据页表的得到逻辑地址100的物理地址 该指令地址 2 1024 100 2148执行 2500 2048 452P 2W 452B 82500单元的物理地址 1024 8 452 8644 4 4请求分页存储管理 例 一个三页长的进程 每页长1K 页号页框号 块号 021328指令 100LOAD1 2500的地址变换过程为 2007 8 1515 2615 26 操作系统 存储器管理 49 快表 采用联想存储器加快查表速度在地址变换机构中 加入一个高速 小容量 具有并行查询能力的联想存储器 构成快表 存放正运行的进程的当前页号和块号 在快表中找到 直接进行地址转换 未找到 则在主存页表继续查找 并把查到的页号和块号放入联想存储器的空闲单元中 如没有 淘汰最先装入的页号 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 50 在缓存中查找页描述子 找到了则提取 快表的命中率可高达80 90 利用页描述子和位移量计算物理地址 2 在缓存中未找到 从页表中读取 并存入缓存 利用页描述子和位移量计算物理地址 页号位移量 虚拟地址 275382 超高速缓存 页表 01234 首先访问高速缓存 确定需要的页描述子是否在其中 如果没有发现 再访问存储器中的页表 同时将从页表中读出的页描述子更新高速缓存中旧的页描述子 具有超高速缓冲存储器的地址变换过程 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 51 分页存储管理算法管理表目作业表 JT 整个系统一张 每个进程对应一个表目内容 页表长度 页表始址 状态存储分块表 MBT 整个系统一张表示方式 链表 位示图页表 PT 每个进程一张分页存储分配算法 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 52 多级页表两级页表引入两级页表的结构外层页号P1内层页号P2页内地址D222112110地址变换多级页表结构 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 53 4 4基本分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 54 假设一分页存储系统的页面大小为4K 页表结构如下 外层页号10位 外层页内地址10位 页内地址12位 在逻辑地址空间中 有逻辑单元的地址为0 x7FFFFFFB 请给出该地址的外层页号 内层页内地址 页内地址 十进制表示 页内地址 0 x7FFFFFFBMOD0 x1000 FFB 4091内层页内地址 0 x7FFFFMOD0 x400 3FF 1023外层页号 INT 0 x7FFFF 0 x400 1FF 511 2007 8 1515 2615 26 操作系统 存储器管理 55 分页存储管理方案的评价优点有效解决存储器的零头问题 能在更高的程度上进行多道程序设计 从而相应提高了存储器和CPU的利用率 缺点采用动态地址变换为增加计算机成本和降低CPU的速度 表格占内存空间 管理表格要付出时间 存在页内碎片 作业动态的地址空间受内存容量限制 2007 8 1515 2615 26 操作系统 存储器管理 56 4 6分段存储管理 分段存储管理 方便编程 分段共享 分段保护 动态增长和动态链接 基本思想把程序按内容或过程 函数 关系分成段 每段有自己的名字 段式管理程序以段为单位分配内存 然后通过地址映射机构把段式虚地址转换成实际的内存物理地址 2007 8 1515 2615 26 操作系统 存储器管理 57 实现原理段式虚存空间进程的虚地址空间为二维的 段长不固定 每个段定义一组逻辑上完整的程序或数据 段号S段内地址W3116150例 CALL X LOAD1 A STORE1 B 2007 8 1515 2615 26 操作系统 存储器管理 58 2007 8 1515 2615 26 操作系统 存储器管理 59 内存的分配和回收内存的分配内存中有足够的空闲区满足该段的要求分配算法 最先适应算法 最佳适应 最差适应算法 不满足所有空闲区之和是否满足 如满足则合并 内存的回收 2007 8 1515 2615 26 操作系统 存储器管理 60 段式管理的地址变换段表 SegmentMappingTable 段号始址长度存取方式动态地址变换当进程执行时 管理程序把其段表始址和段表长度放入段表控制寄存器中 以段号为索引 查段表 对内存二次以上访问 可采用高速联想寄存器 加快查找速度 2007 8 1515 2615 26 操作系统 存储器管理 61 分段系统的地址变换过程 2007 8 1515 2615 26 操作系统 存储器管理 62 分段与分页的区别 页是信息的物理单位 分页是为了提高内存的利用率 段是信息的逻辑单位 分段是为了更好满足用户的需要 页的大小固定 逻辑地址的划分由机器硬件实现 段的大小取决于用户 由编译程序进行划分 分页的作业地址空间是一维的 分段是二维的 标识一个地址时 要同时给出段名 段号 和段内地址 2007 8 1515 2615 26 操作系统 存储器管理 63 信息共享 分页系统中的共享 2007 8 1515 2615 26 操作系统 存储器管理 64 分段系统中的共享 2007 8 1515 2615 26 操作系统 存储器管理 65 性能评价优点便于程序模块化处理和处理变化的数据结构 便于共享分段便于动态链接 缺点地址变换费时 管理表格 硬件支持 使OS复杂 为满足段的动态增长和减少碎片 要用拼接技术 段长不定 管理困难 段长受内存可用区的限制 2007 8 1515 2615 26 操作系统 存储器管理 66 基本思想将用户程序分成若干段 再用分页方法对每一段进行分配和管理实现原理地址构成段号S段内页号P页内地址W有效地址长度决定作业地址空间的范围程序的分段 由程序员或编译程序按信息的逻辑结构划分 分页由OS自动完成 4 7段页式存储管理 2007 8 1515 2615 26 操作系统 存储器管理 67 2007 8 1515 2615 26 操作系统 存储器管理 68 2007 8 1515 2615 26 操作系统 存储器管理 69 段表和页表段表 每个进程一张 管理内存分配与释放 存储保护和地址变换等 页表 每个段一张 管理页面保护 页表始址 页表长度 段表与页表的关系动态地址变换过程三次访问内存 1 利用段获得页表始址 2 利用页表获得物理块地址 3 根据物理地址真正获得指令或数据 为提高地址转换速度 设置快速联想寄存器 存放当前最常用的段号 页号和对应的内存页面与其它控制用栏目 2007 8 1515 2615 26 操作系统 存储器管理 70 评价优点保留了请求页式和分段存储管理的全部优点 有效利用内存 为组织多道程序运行提供了方便 缺点增加硬件成本 系统的复杂性和管理上的开销 仍有碎片 各种表格要占用内存 2007 8 1515 2615 26 操作系统 存储器管理 71 4 6虚拟存储器的基本概念 虚拟存储器的引入程序的分段执行局部性原理在执行中的程序 某一段时间内 CPU总是集中地访问程序中的某一部分 时间局限性 指令在一段时间内的多次执行 产生的原因是程序中存在大量的循环操作 空间局限性 程序在一定时间所访问的地址可能集中在某一段指令范围内 2007 8 1515 2615 26 操作系统 存储器管理 72 虚拟存储器的定义在程序运行之前 仅将那些当前要运行的页 或段 先装入内存 其余暂留外存 在运行过程中 利用请求调入和交换技术 将内存中暂时不用的页调至外存上 将要访问的页调入内存 使大的程序可在较小的内存中运行 虚拟存储器 具有请求调入和置换功能 能从逻辑上对内存容量进行扩充的一种存储系统 其逻辑容量为内存和外存 对换区 容量之和 2007 8 1515 2615 26 操作系统 存储器管理 73 虚存容量在多道程序环境下 系统可分为每个用户建一个虚存 其容量可为内存与外存的容量之和 或由计算机地址结构和寻址方式确定 基础条件有相当容量的外存 要有一定容量的内存 地址变换机构 4 6虚拟存储器的基本概念 2007 8 1515 2615 26 操作系统 存储器管理 74 虚拟存储器的实现方式请求分页系统在分页系统的基础上 增加了请求调页和页面置换功能所形成的页式虚拟存储系统 请求分页的页表机制缺页中断机构地址变换机构请求分段系统请求分段的段表机制缺段中断机构地址变换机构 4 6虚拟存储器的基本概念 2007 8 1515 2615 26 操作系统 存储器管理 75 虚拟存储器的特征离散性多次性对换性虚拟性 4 6虚拟存储器的基本概念 2007 8 1515 2615 26 操作系统 存储器管理 76 4 7请求分页存储管理 请求页式管理和预调入页式管理请求页式管理当需要执行的指令或访问的数据不在内存时 产生缺页中断 系统将外存中相应的页面调入内存 预调入页式管理系统对那些在外存中的页进行调入顺序计算 估计出这些页中的指令和数据的执行和被访问的顺序 并按此顺序将它们调入和调出内存 2007 8 1515 2615 26 操作系统 存储器管理 77 实现原理要访问的虚页在不在内存扩充页表功能由动态地址变换机构产生缺页中断 页面的调入调出调入 有无空白页 是否淘汰一页 修改页表 调出 淘汰 处理过程 当传输进程某页时 阻塞 系统调度另一进程 4 7请求分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 78 请求分页中的硬件支持页表机制缺页中断机构处理过程 保护CPU现场 分析中断原因和转入中断处理程序 特点 页面访问位A 0页面不在内存1页面在内存 0页面未被访问1页面已被访问 0页面未被修改1页面已被修改 判断缺页中断 影响页面置换策略 是否重写外存 页面存在位P 页面修改位M 4 7请求分页存储管理 地址变换过程 缺页中断处理 有空页框吗 Y 4 7请求分页存储管理 装入新页 地址变换过程 2007 8 1515 2615 26 操作系统 存储器管理 80 例 某操作系统采用请求页式存储管理机制 用户进程有7个页面 系统为其分配了5个物理块 每页大小为1K 页表和快表如下表所示 分别对三个虚地址说明系统处理过程 0X5C 0X85C 0X185C 2007 8 1515 2615 26 操作系统 存储器管理 81 解答0X5C的地址转换过程 逻辑地址 5C H 0101 1100 B页号 0 B快表没有命中 查页表 P 1表示在内存 得到物理块号 1000 B物理地址 10 0000 0101 1100 B 205C H2 0X85C的地址转换过程 逻辑地址 85C H 1000 0101 1100 B页号 10 B查快表命中 得到物理块号 100 B物理地址 1 0000 0101 1100 B 105C H3 0X185C的地址转换过程 逻辑地址 185C H 1 1000 0101 1100 B页号 110 B查快表没有命中 查页表 P 0 表示不在内存 产生缺页中断 2007 8 1515 2615 26 操作系统 存储器管理 82 页面分配最小物理块数 能保证一个进程正常运行所需的最小物理块数 页面分配和置换策略分配策略 固定和可变置换策略 全局和局部固定分配局部置换可变分配全局置换可变分配局部置换 4 7请求分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 83 分配算法平均分配算法按比例分配算法考虑优先权的分配算法将内存分为两部分 一部分按比例分配 另一部分根据优先级增加分配的物理块 4 7请求分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 84 对换区的管理对换空间充足 全部从对换区换入 对换空间不够 分为修改和不修改两种方法 UNIX方式 未运行过的 从文件区调入 运行过并被换出的 从交换区调入 4 7请求分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 85 性能评价优点有效地解决了碎片问题虚存的实现缺点要求相应的硬件支持增加系统开销请求调页的算法选择不当 可能产生抖动现象 没有彻底消除碎片问题 4 7请求分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 86 思考与作业请求分页存储管理需要怎样的硬件支持 讨论三种页面分配和置换策略的优缺点 作业Page142 2 6 12 14 4 7请求分页存储管理 2007 8 1515 2615 26 操作系统 存储器管理 87 内容回顾虚拟存储器管理概念请求页式存储管理的原理缺页中断的过程及特点请求页式存储管理的地址变换过程 2007 8 1515 2615 26 操作系统 存储器管理 88 4 8页面置换算法 一个置换算法的效能是和作业运行过程中访问地址空间的变化规律 即程序的动态特征 紧密相关的 而这个变化规律是难以预测的 最佳置换算法OPT OptimalReplacementAlgorithm 被淘汰的页面是永远不使用的页面 或是在最长时间内不再被访问的页面 2007 8 1515 2615 26 操作系统 存储器管理 89 例 一个有5个页面的进程 在内存为它分配3个物理块 其页面访问顺序如下 OTP算法 页面置换次数 3 4 8页面置换算法 特点 高效但不可行 2007 8 1515 2615 26 操作系统 存储器管理 90 先进先出算法 FIFO 原理 选择在内存驻留时间最长的一页将其淘汰 实现方法按页调入内存顺序建立一队列表Q 0 Q m 1 和一替换指针 指针指向最早调入内存的一页 把这个队列表建立在存储分块表中 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 91 例 一个有5个页面的进程 在内存为它分配3个物理块 其页面访问顺序如下 FIFO算法 页面置换次数 6 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 92 算法效率这种算法只有在按线性顺序访问地址空间时才理想 否则效率不高 Belady现象在使用FIFO算法时 未给进程或作业分配足够的页面数时 有时会出现分配的页面数增多 缺页次数反而增加 原因在于它根本没考虑程序执行的动态特征 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 93 最近最久未用页面置换算法LRU LeastRecentlyUsed 原理 当需要置换一页时 选择在最近一段时间内最久未用的页予以淘汰实现通过周期性地对 引用位 进行检查 并利用它来记录一个页面自上次被访问以来所经历的时间T 淘汰时 选择T为最大的页 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 94 例 一个有5个页面的进程 在内存为它分配3个物理块 其页面访问顺序如下 LRU算法 页面置换次数 4 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 95 硬件支持寄存器法为每个页面配置一个移位寄存器 当访问到某物理块时 将相应寄存器的RN 1位置成1 每隔一段时间将寄存器右移一位 淘汰寄存器值最小的页面 R实页 R7R6R5R4R3R2R1R0 110100000200001000310000000401000000 101010000210001000301000000400100000 110101000201000100300100000400010000 101010100210100010300010000400001000 4 8页面置换算法 例 页面访问顺序为2125 2007 8 1515 2615 26 操作系统 存储器管理 96 栈利用一个特殊的栈来保存当前使用的各个页面的页面号 每当进程访问某页面时 便将该页面的页面号从栈中移出 将它压入栈顶 则栈底为最近最久为使用页面的页面号 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 97 Clock置换算法最近没使用算法NRU原理 淘汰最近一段时间内未被访问的一页 实现 设置访问位A 0最近未被访问A 1最近被访问步骤 特点 简单 实现容易 但时间周期T选择不易确定 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 98 2007 8 1515 2615 26 操作系统 存储器管理 99 2007 8 1515 2615 26 操作系统 存储器管理 100 例 一个有5个页面的进程 在内存为它分配3个物理块 其页面访问顺序如下 Clock算法 页面置换次数 5 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 101 NRU改进算法A 访问位M 修改位1类 A 0 M 0 最近既未被访问 又未被修改 4 8页面置换算法 2类 A 0 M 1 最近既未被访问 但已被修改 3类 A 1 M 0 最近被访问 未被修改 4类 A 1 M 1 最近被访问 且被修改 2007 8 1515 2615 26 操作系统 存储器管理 102 步骤 扫描循环队列 找出一类页面 找到则淘汰该页 未找到 开始第二轮扫描 找第二类页面 找到淘汰该页 并将所有经过的页面的访问位置0 都失败 重复 1 2 直到找到淘汰页面 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 103 2007 8 1515 2615 26 操作系统 存储器管理 104 其它置换算法最少使用 LeastFrequentlyUsed 置换算法淘汰访问次数最少的一页 在页表中增加访问计数 设置移位寄存器 每一页 高位置1 定时右移 页面缓冲算法 PageBufferingAlgorithm 置换算法采用FIFO 淘汰的页面挂在下列两个链表的尾部 空闲页面链表和已修改页面链表 当修改页面达到一定数量 再写回磁盘 4 8页面置换算法 2007 8 1515 2615 26 操作系统 存储器管理 105 例 一个进程的大小为5个页面 为它分配了四个物理块 当前每个块的情况如下表所示 都为十进制数 且从0开始计数 时间单位为 秒 当虚页4发生缺页时 使用下列的页面置换算法 哪一个物理块将被换出 并解释原因 若每块的大小为1K 请计算100F单元的物理地址 页号块号加载时刻访问时刻访问位R修改位M20601610111130160000226162103520163111 FIFO算法2 LRU算法3 CLOCK算法 2007 8 1515 2615 26 操作系统 存储器管理 106 解答逻辑地址 100F H 1000000001111 B1 FIFO算法 第5号物理块将被换出 因为最早被装入 页号 100 B块号 101 B物理地址 1010000001111 B 140F H2 LRU算法 第1号物理块将被换出 因为最久没被访问 页号 100 B块号 001 B物理地址 0010000001111 B 40F HCLOCK算法 第1号物理块将被换出 因为最近既没被访问又没被修改过 页号 100 B块号 001 B物理地址 0010000001111 B 40F H 2007 8 1515 2615 26 操作系统 存储器管理 107 linux的页面置换机制Linux描述页面的数据结构pagelinux使用LRU算法作为其页面交换的核心算法 linux所使用的LRU交换算法已经与存储管理 进程管理 文件系统有关机制结合成一个整体 定期地 特别是在系统相对空闲的时候 挑选一些页面预先换出 使系统始终维持一定的空闲页面供应量 4 11Linux存储管理 2007 8 1515 2615 26 操作系统 存储器管理 108 空闲页面 活跃页面 不活跃且修改的页面 不活跃且没修改的页面 页面状态和实现方法 内存空间 4 11Linux存储管理 2007 8 1515 2615 26 操作系统 存储器管理 109 思考与作业思考题一 一个进程的大小占5个页面 每页的大小为1K 系统为它分配了3个物理块 当前进程的页表如图所示 块号存在位P访问位R修改位M 1 有那些页面不在内存 2 请分别计算进程中虚地址为0 x3B7 0 x12A5 0 x1432单元的物理地址 用十六进制表示 思考题二 比较各种页面置换算法的性能和实现代价 思考题三 想一想是否还有其它的页面置换算法 作业Page142 23 27 2007 8 1515 2615 26 操作系统 存储器管理 110 4 9系统抖动 抖动现象指系统页面置换频繁 大量CPU时间花在来回进行页的调度上 小部分时间用于实际运算 一个较优的算法应尽可能避免出现抖动现象 一旦引起了这种局面 系统应能立即采取措施加以排除 2007 8 1515 2615 26 操作系统 存储器管理 111 预防抖动问题 减少缺页中断次数 程序设计质量 程序的局部化程度分配适当的内存工作集 在某段时间内 进程实际访问的页面的集合 实验证明 对所有的程序来说 要使其有效的工作 它在内存中的页面数应不低于总页面数的一半 L S准则产生缺页的平均时间等于系统处理进程缺页的平均时间 4 9系统抖动 2007 8 1515 2615 26 操作系统 存储器管理 112 4 9系统抖动 2007 8 1515 2615 26 操作系统 存储器管理 113 解决抖动问题的办法改进算法在进行淘汰或置换时 一般总是把缺页进程锁住不让其换出 而调入的页或段总是占据那些暂时得不到执行的进程所占有的内存区域 从而扩大缺页进程的工作集挂起若干进程 4 9系统抖动 4 10请求分段存储管理 硬件支持地址及段表 其中 增补位 0该段未增长过1该段进行过动态增长 段表结构 地址结构 请求分段地址变换过程 访问 S W W 段长 分段越界中断处理 符合存取方式 N Y Y 分段保护中断处理 段S在主存 N 缺段