第04章_存储器管理

1 第四章存储器管理 4 1存储器的层次结构4 2程序的装入和链接4 3连续分配方式4 4基本分页存储管理方式4 5基本分段存储管理方式4 6虚拟存储器的基本概念4 7请求分页存储管理方式4 8页面置换算法4 9请求分段存储管理方式 2 4 1存储器的层次结构 4 1 1多级存储器结构1 存储器功能合理 安全 有效地保存数据2 存储器发展方向接口更新以硬盘为例 ESDI IDE EIDE ATA SATA SATA2 SCSI IEEE1394 USB 高速性以USB为例 USB1 1是12Mbps USB2 0是480Mbps USB3 0理论上是5Gbps 存储密度越来越高 体积越来越小1 7Mb 平方英寸 20Mb 平方英寸 1 43Gb 平方英寸 135Gb 平方英寸 620Gb 平方英寸 1Tb 平方英寸 3 4 容量越来越大 价格越来越低以下是近年来关于硬盘价格的趣味数字1995年200MB 400MB大于4000元 GB1996年1 2GB 2 1GB1500元 2000 GB1998年1 2GB 2 1GB200元 250元 GB2000年4 3GB 6 4GB40元 GB2002年10GB 20GB20元 GB2004年40GB 80GB6 9元 GB2005年80GB 160GB4 5元 GB2006年80GB 250GB3 8元 GB2008年160GB 1TB1 6元 GB2009年500GB 2TB0 8元 GB2010年500GB 2TB0 6元 GB 5 3 存储器层次结构 6 4 存储管理功能存储分配与回收本章主要内容 讨论其算法和数据结构地址变换可执行文件生成中的链接技术 程序装入时的重定位技术 进程运行时的地址变换技术和机构 软件 硬件 存储共享和保护代码和数据共享 对地址空间的访问权限 读 写 执行 存储器扩充由用户应用程序控制 覆盖Overlay由OS控制 交换Swapping 请求调入和预调入OnDemand OnPrefetch 7 4 1 2主存储器与寄存器1 主存储器主存储器 简称内存或主存 是计算机系统中一个主要部件 用于保存进程运行时的程序和数据 也称可执行存储器 材质以DRAM为主 由于主存储器的访问速度远低于CPU执行指令的速度 为缓和这一矛盾 在计算机系统中引入了寄存器和高速缓存 8 2 寄存器寄存器访问速度最快 完全能与CPU协调工作 但价格却十分昂贵 因此容量不可能做得很大 寄存器的长度一般以字 word 为单位 寄存器的数目 对于当前的微机系统和大中型机 可能有几十个甚至上百个 而嵌入式计算机系统一般仅有几个到几十个 寄存器通常用于加速存储器的访问速度 如用寄存器存放操作数 或用作地址寄存器加快地址转换速度等 9 4 1 3高速缓存和磁盘缓存1 高速缓存高速缓存是现代计算机结构中的一个重要部件 其容量大于或远大于寄存器 而比内存约小两到三个数量级左右 从几十KB到几MB 访问速度快于主存储器 根据程序执行的局部性原理 即程序在执行时将呈现出局部性规律 在一较短的时间内 程序的执行仅局限于某个部分 将主存中一些经常访问的信息存放在高速缓存中 减少访问主存储器的次数 可大幅度提高程序执行速度 10 2 磁盘缓存由于目前磁盘的I O速度远低于对主存的访问速度 因此将频繁使用的一部分磁盘数据和信息 暂时存放在磁盘缓存中 可减少访问磁盘的次数 11 4 2程序的装入和链接 在多道程序环境下 要使程序运行 必须先为之创建进程 而创建进程的第一件事 便是将程序和数据装入内存 如何将一个用户源程序变为一个可在内存中执行的程序 通常都要经过以下几个步骤 首先是要编译 由编译程序 Compiler 将用户源代码编译成若干个目标模块 ObjectModule 其次是链接 由链接程序 Linker 将编译后形成的一组目标模块 以及它们所需要的库函数链接在一起 形成一个完整的装入模块 LoadModule 最后是装入 由装入程序 Loader 将装入模块装入内存 图4 2示出了这样的三步过程 本节将扼要阐述程序 含数据 的链接和装入过程 12 图4 2对用户程序的处理步骤 编译Compile 若干目标模块 OBJ 源程序 C 链接Link 库函数Lib 装入模块 EXE 装入Load CPU 13 4 2 1程序的链接链接 若干目标模块 库函数 可装入模块根据链接时间的不同 可把链接分成如下三种 1 静态链接 在程序运行之前 先将各目标模块及它们所需的库函数 链接成一个完整的装配模块 以后不再拆开 我们把这种事先进行链接的方式称为静态链接方式 2 装入时动态链接 这是指将用户源程序编译后所得到的一组目标模块 在装入内存时 采用边装入边链接的链接方式 3 运行时动态链接 这是指对某些目标模块的链接 是在程序执行中需要该 目标 模块时 才对它进行的链接 14 1 静态链接方式 StaticLinking 在生成可装入模块时 也就是在程序装入运行前 完成的链接 见图4 4特点 一次链接 n次运行得到完整的可装入模块 不可再拆不灵活 不管有用与否的模块都将链接到装入模块 同时导致内存利用率较低不利于模块的修改和升级 15 16 2 装入时动态链接 Load timeDynamicLinking 用户源程序经编译后所得的目标模块 是在装入内存时边装入边链接的 即在装入一个目标模块时 若发生一个外部模块调用事件 将引起装入程序去找出相应的外部目标模块 并将它装入内存 还要按照图4 4所示的方式来修改目标模块中的相对地址 17 3 运行时动态链接 Run timeDynamicLinking 装入时动态链接是将所有可能要运行到的模块都全部链接在一起并装入内存 显然这是低效的 因为往往会有些目标模块根本就不运行 比较典型的例子是作为错误处理用的目标模块 如果程序在整个运行过程中都不出现错误 则显然就不会用到该模块 运行时动态链接方式是对装入时链接方式的一种改进 这种链接方式是将对某些模块的链接推迟到程序执行时才进行链接 亦即 在程序执行过程中 当发现一个被调用模块尚未装入内存时 才立即由OS去找到该模块并将之装入内存 把它链接到调用者模块上 凡在本次执行过程中未被用到的目标模块 都不会被调入内存和被链接到装入模块上 这样不仅可加快程序的装入过程 而且可节省大量的内存空间 18 4 动态链接方式的优点便于共享多个进程可共用一个DLL模块 节省了内存 为部分装入提供了条件 运行时动态链接 一个进程可由若干DLL模块构成 按需装入 便于模块的修改和升级只要被修改模块的接口不变 则该模块的修改不会引发其它模块的重新编译 改善了程序的可移植性可面向不同的应用环境开发同一功能模块的不同版本 根据当前的环境载入匹配的模块版本 19 5 动态链接方式的缺点增加了程序执行时的链接开销 每次运行都需链接 模块数量众多 增加了模块的管理开销 20 4 2 2程序的装入装入 可装入模块 EXE 内存进程1 绝对装入方式 AbsoluteLoadingMode 在编译后 装入前已产生了绝对地址 内存地址 装入时不再作地址重定位 即 装入内存前的虚拟地址 装入内存后的物理地址 绝对地址的产生 1 由编译器完成 2 由程序员编程完成 优点 装入过程简单 无需地址映射 缺点 不适于多道程序系统 过于依赖硬件结构 不易修改 不灵活 21 2 可重定位装入方式 RelocationLoadingMode 可装入模块在被装入到内存中时 由装入程序来完成程序虚拟地址 内存物理地址的变换 22 如果不进行地址变换 那么这条指令将无法取到正确的数值 365 所以该指令中的地址应该重定位为 LOAD1 12500 静态地址重定位 指令或数据的内存地址MA 该指令或数据的虚拟地址VA 该程序在内存中的首地址BA 23 可重定位装入的优缺点 优点 适用于多道程序系统 提高了内存利用率 由于地址映射规则简单 故在地址变换过程中无需硬件变换机构的支持 缺点 任何进程都要求连续的内存空间 必须将全部模块都装入且装入后不能再移动位置 因为无法实现动态重定位 不支持虚拟存储器技术 不易实现共享 24 3 动态运行时装入方式 DynamicRun timeLoading 出于实际情况 程序在运行过程中的内存位置可能经常要改变 此时就应采用动态运行时装入的方式 程序装入内存后并不立即进行地址变换 而是等到真正要执行时才由硬件地址变换机构来完成地址变换 从而得到内存物理地址 25 动态地址重定位 指令或数据的内存地址MA 该指令或数据的虚拟地址VA 重定位基址寄存器BR 26 动态运行时装入的优缺点 优点OS可将一个进程的不同部分分散存放在不连续的内存空间 可移动进程在内存中的位置 由重定位基址寄存器反映移动情况 提供了实现虚拟存储器技术的基础 可实现部分模块装入 有利于实现模块共享 缺点动态重定位需要硬件变换机构的支持 实现较复杂 27 4 3连续分配方式 连续分配方式是指一个进程在内存中必须占用连续的存储空间 典型的连续分配方式主要有 单一连续分配 固定分区分配 动态分区分配 动态重定位分区分配等 4 3 1单一连续分配把内存分为系统区和用户区两部分 系统区仅提供给OS使用 用户区是指除系统区以外的全部内存空间 提供给用户使用 优点 简单 易于管理缺点 只能用于单用户单任务OS 内存利用率低 毫无共享性可言 早已淘汰 28 引入 分区存储管理原理将内存分为一些大小相等或不等的分区 Partition 每个进程可占用一个分区 适于多道程序系统 支持多个进程并发执行 出现了碎片问题内碎片 被占用分区的尾部未被利用的空间 外碎片 在两个被占用分区之间的难以利用的小空闲分区 分区管理的数据结构 分区表或分区链表 内存紧凑 Compaction 将各个已占用分区向内存某端移动 从而使分散的各个小空闲分区能相邻 进而合并为一个稍大的空闲分区 29 4 3 2固定分区分配1 把内存划分为若干个固定大小的分区 分区的总数以及各个分区的大小都是恒定值 各分区大小相等不灵活 对于小进程而言 内存利用率低 内碎片严重 对于大进程而言 分区大小可能无法满足需要 导致无法装入 各分区大小不等小分区 中等分区 大分区 适应性较强 可以有效提高内存利用率 30 2 固定分区的内存分配为了便于内存分配 通常将分区按大小进行排队 并为之建立一张分区使用表 其中各表项包括每个分区的起始地址 大小及状态 是否已分配 见图4 5 a 所示 当有一用户程序要装入时 由内存分配程序检索该表 从中找出一个能满足要求的 尚未分配的分区 将之分配给该程序 然后将该表项中的状态置为 已分配 若未找到大小足够的分区 则拒绝为该用户程序分配内存 存储空间分配情况如图4 5 b 所示 31 32 3 固定分区分配的优缺点优点由于各分区大小固定 故易于实现 管理开销小 缺点内碎片的问题不可避免 较大程序不易装入 故内存利用率较低 分区数目固定也限制了进程的并发度 33 4 3 3动态分区分配在动态分区分配方式中 各个分区的大小会在OS的管理下发生改变 分区总数也会相应地发生变化 1 分区分配中的数据结构 1 空闲分区表 记录所有空闲分区情况的二维表 34 2 空闲分区链 将所有的空闲分区链接成一个双向链 如图4 6所示 图4 6空闲链结构 35 2 分区分配算法1 首次适应FF算法 FirstFit 空闲分区链以地址递增的次序链接 在每次分配时 都从链首开始顺序查找 直至找到第一个大小能满足要求的空闲分区为止 然后再按照程序的大小 从该分区中划出一块内存空间分配给请求者 余下的空闲分区仍留在空闲链中 若从链首直至链尾都不能找到一个能满足要求的分区 则此次内存分配失败 返回 特点 简单 高址内存可保留较大的空闲分区 但低址内存会产生很多碎片分区 查找开销大 36 2 循环首次适应NF算法 NextFit 该算法是由首次适应FF算法演变而成的 分配空间不再是每次都从链首开始查找 而是从上次找到的空闲分区的下一个空闲分区开始查找 如果达到链尾则回到链首继续 特点 查找开销小 空闲分区分布更均匀 但较大分区难以保留 37 3 最佳适应BF算法 BestFit 空闲分区链表以容量递增为序组织 每次分配时从链首查找 将第一个满足空间要求的分区分配出去 特点 最接近按需分配原则 较大的分区容易保留 但会产生很多难以利用的小碎片分区 4 最坏适应WF算法 WorstFit 空闲分区链表以容量递减为序组织 每次分配时从链首查找 将第一个满足空间要求的分区分配出去 特点 小碎片分区的问题得到了有效的解决 但大分区也不易保留 最坏适应算法与前面所述的首次适应 循环首次适应 最佳适应算法一起 统称为顺序搜索法 38 5 快速适应QF算法 QuickFit 该算法又称为分类搜索法 是将空闲分区根据其容量大小进行分类 对于每一类具有相同容量的所有空闲分区 单独设立一个空闲分区链表 这样 系统中存在多个空闲分区链表 同时在内存中设立一张管理索引表 该表的每一个表项对应了一种空闲分区类型 并记录了该类型空闲分区链表表头的指针 空闲分区的分类是根据进程常用的空间大小进行划分 优点 查找效率高 不会对任何分区产生分割 所以能保留大的分区 也不会产生内存碎片 缺点 分区归还主存的算法复杂 系统开销较大 多样化的链表造成管理开销大 39 3 分区分配操作1 分配内存系统应利用某种分配算法 从空闲分区链 表 中找到所需大小的分区 设请求的分区大小为u size 表中每个空闲分区的大小可表示为m size 若m size u size size size是事先规定的不再切割的剩余分区的大小 说明多余部分太小 可不再切割 将整个分区分配给请求者 否则 即多余部分超过size 从该分区中按请求的大小划分出一块内存空间分配出去 余下的部分仍留在空闲分区链 表 中 然后 将分配区的首址返回给调用者 图4 7示出了分配流程 40 41 2 回收内存 1 回收区与插入点的前一个空闲分区F1相邻接 见图4 8 a 此时应将回收区与插入点的前一分区合并 不必为回收分区分配新表项 而只需修改其前一分区F1的大小 2 回收分区与插入点的后一空闲分区F2相邻接 见图4 8 b 此时也可将两分区合并 也不必分配新表项 用回收区的首址作为新空闲区的首址 大小为两者之和 3 回收区同时与插入点的前 后两个分区邻接 见图4 8 c 此时将三个分区合并 使用F1的表项 F1的首址不变 F1的大小为三者之和 删除F2的表项 4 回收区既不与F1邻接 又不与F2邻接 见图4 8 d 这时应为回收区单独建立一新表项 填写回收区的首址和大小 并根据其首址插入到空闲链中的适当位置 42 合并 改F1大小 合并 改F1大小和首址 合并 改F1大小 删除F2表项 建立一新表项 43 例 假设最佳适应法 如果改为首次适应算法 44 4 3 4伙伴系统 自学内容 固定分区和动态分区方式都有不足之处 固定分区方式限制了活动进程的数目 当进程大小与空闲分区大小不匹配时 内存空间利用率很低 动态分区方式算法复杂 回收空闲分区时需要进行分区合并等 系统开销较大 伙伴系统方式是对以上两种内存方式的一种折衷方案 伙伴系统规定 无论已分配分区或空闲分区 其大小均为2的k次幂 k为整数 l k m 其中 21表示分配的最小分区的大小 2m表示分配的最大分区的大小 通常2m是整个可分配内存的大小 45 假设系统的可利用空间容量为2m个字 则系统开始运行时 整个内存区是一个大小为2m的空闲分区 在系统运行过程中 由于不断的划分 可能会形成若干个不连续的空闲分区 将这些空闲分区根据分区的大小进行分类 对于每一类具有相同大小的所有空闲分区 单独设立一个空闲分区双向链表 这样 不同大小的空闲分区形成了k 0 k m 个空闲分区链表 46 当需要为进程分配一个长度为n的存储空间时 首先计算一个i值 使2i 1 n 2i 然后在空闲分区大小为2i的空闲分区链表中查找 若找到 即把该空闲分区分配给进程 否则 表明长度为2i的空闲分区已经耗尽 则在分区大小为2i 1的空闲分区链表中寻找 若存在2i 1的一个空闲分区 则把该空闲分区分为相等的两个分区 这两个分区称为一对伙伴 其中的一个分区用于分配 而把另一个加入分区大小为2i的空闲分区链表中 若大小为2i 1的空闲分区也不存在 则需要查找大小为2i 2的空闲分区 若找到则对其进行两次分割 第一次 将其分割为大小为2i 1的两个分区 一个用于分配 一个加入到大小为2i 1的空闲分区链表中 第二次 将第一次用于分配的空闲区分割为2i的两个分区 一个用于分配 一个加入到大小为2i的空闲分区链表中 若仍然找不到 则继续查找大小为2i 3的空闲分区 以此类推 由此可见 在最坏的情况下 可能需要对2k的空闲分区进行k次分割才能得到所需分区 47 与一次分配可能要进行多次分割一样 一次回收也可能要进行多次合并 如回收大小为2i的空闲分区时 若事先已存在2i的空闲分区时 则应将其与伙伴分区合并为大小为2i 1的空闲分区 若事先已存在2i 1的空闲分区时 又应继续与其伙伴分区合并为大小为2i 2的空闲分区 依此类推 在伙伴系统中 其分配和回收的时间性能取决于查找空闲分区的位置和分割 合并空闲分区所花费的时间 与前面所述的多种方法相比较 由于该算法在回收空闲分区时 需要对空闲分区进行合并 所以其时间性能比前面所述的分类搜索算法差 但比顺序搜索算法好 而其空间性能则远优于前面所述的分类搜索法 比顺序搜索法略差 48 4 3 5哈希算法哈希算法就是利用哈希快速查找的优点 以及空闲分区在可利用空间表中的分布规律 建立哈希函数 构造一张以空闲分区大小为关键字的哈希表 该表的每一个表项记录了一个对应的空闲分区链表表头指针 当进行空闲分区分配时 根据所需空闲分区大小 通过哈希函数计算 即得到在哈希表中的位置 从中得到相应的空闲分区链表 实现最佳分配策略 49 4 3 6可重定位分区分配1 动态重定位的引入在连续分配方式中 必须把一个系统或用户程序装入一连续的内存空间 如果在系统中只有若干个小的分区 即使它们容量的总和大于要装入的程序 但由于这些分区不相邻接 也无法把该程序装入内存 例如 图4 9 a 中示出了在内存中现有四个互不邻接的小分区 它们的容量分别为10KB 30KB 14KB和26KB 其总容量是80KB 但如果现在有一程序到达 要求获得40KB的内存空间 由于必须为它分配一连续空间 故此程序无法装入 这种不能被利用的小分区称为 零头 或 碎片 50 图4 9紧凑的示意 现在有4个空闲分区 如果有一个大小为40KB的程序要求进入内存 如何处理 解决办法 紧凑 紧凑 通过移动一些内存分区 将原本离散的一些内存小碎片变得相邻 进而可以合并为一个稍大的空闲分区的技术 51 2 动态重定位的实现经过紧凑后 某些用户程序在内存中的位置发生了变化 此时若不对程序和数据的地址加以修改 变换 则程序必将无法执行 为此 在每次 紧凑 后 都必须对移动了的程序或数据进行地址重定位 增设 重定位寄存器 每当系统对内存进行了 紧凑 而使若干程序从内存的某处移至另一处时 不需对程序做任何修改 只要实时更新 重定位寄存器 的值即可 52 动态地址重定位 指令或数据的内存地址MA 该指令或数据的虚拟地址VA 重定位基址寄存器BR 53 3 动态重定位分区分配算法动态重定位分区分配算法与动态分区分配算法基本上相同 差别仅在于 在这种分配算法中 增加了紧凑的功能 通常 在找不到足够大的空闲分区来满足用户需求时进行紧凑 图4 11示出了动态重定位分区分配算法 54 55 4 3 7有关分区管理的讨论1 分区存储管理的特点优点 实现了多个进程对内存的共享 有助于多道程序系统 提高了资源利用率 要求的硬件支持少 管理简单 实现容易 缺点 内存利用率仍然不高 小碎片多 进程大小受分区大小的限制 不能部分装入 难以实现各分区间的信息共享 无法实现虚存 56 2 关于虚存的实现虚存 用户进程所需内存容量只受内存和外存容量之和的限制的存储器技术 单纯的分区管理是无法实现虚存的 覆盖Overlay由程序员提供一个清晰的覆盖结构 从而实现进程内部不同模块之间的覆盖 例 某进程由A F六段组成 如图 覆盖结构 Total 110K 缺点 编程复杂度过大 且进程模块大小仍受限于分区大小 已淘汰 57 对换Swapping换出Swap out 将内存中阻塞且优先级最低的进程 程序 数据 换到外存交换区 修改其PCB并回收相应内存 换入Swap in 将外存交换区中静止就绪且被换出时间最久的进程 程序 数据 换入内存并修改其PCB 对换分类 进程对换 整体对换 部分对换 页面或分段对换 真正意义上实现虚存对换的三个关键操作 换出 换入 对换空间 pagefile sys 的管理 对换缺点 换入换出开销大 58 关于地址变换和内存保护地址变换 不实现紧凑时可采用 静态可重定位装入 方式 实现紧凑时必须采用 运行时动态可重定位装入 方式 内存保护 硬件法 为每个进程设置一对上 下界寄存器 或利用分区的基址寄存器和限长寄存器 若越界则产生地址保护中断并转错误处理 软件法 保护键法 为被保护分区设置保护键开关字段 针对不同的进程赋予不同的开关代码 通过检查两者是否匹配来实现读 写保护 软硬结合法 59 4 4基本 静态 分页存储管理方式 4 4 1页式管理的基本原理回顾分区分配法 碎片问题严重 内存利用率不高 由于要求连续存放 导致进程的大小仍受分区大小和内存可用空间的限制 不利于共享 无法实现虚存 引入页式管理的目的 为了减少碎片 为了实现换入 换出而采用离散存储 提高内存利用率 分页存储管理 将一个进程的逻辑地址空间分成若干个大小相等的片 称为页面或页 并为各页加以编号 从0开始 如第0页 第1页等 相应地 也把内存空间分成与页面相同大小的若干个存储块 称为 物理 块或页框 frame 也同样为它们加以编号 如0 块 1 块等等 在为进程分配内存时以块为单位 将进程中的若干个页分别装入到多个可以不相邻接的物理块中 由于进程的最后一页经常装不满一块而形成了不可利用的碎片 称之为 页内碎片 60 1 页面一个进程的虚拟空间被划分为若干个长度相等的页面 page 通常几KB 几十KB为一页 故进程的虚地址 逻辑地址 可由页号P与页内地址W所组成 假设这是某系统的分页地址结构 则该系统页长为210 1024B即1KB 页 一个进程最长允许有214 16384页即16384KB 61 与进程逻辑空间的分页结构类似 物理内存空间也被划分为与页面相等大小的若干物理块 在为进程分配内存时 将进程的N个页面 必定连续 装入到N个内存物理块 不一定连续 即 连续的N个页面对应装入不连续的N个物理块 页式管理特点 无外碎片的概念 且内碎片必定小于一个物理块 实现了非连续 离散 方式存储 为虚存的实现提供了基础 但管理开销增大 关键问题 如何将页面逻辑地址变换为内存物理地址 页表 硬件地址变换机构 62 2 页表 PageMappingTable 由于在分页系统中 允许将进程的n个连续页离散地存储在内存不连续的n个物理块中 为此 系统又为每个进程建立了一张页面映像表 简称页表 在进程地址空间内的所有页 0 n 依次在页表中有一页表项 其中记录了相应页在内存中对应的物理块号 见图4 12的中间部分 在配置了页表后 进程执行时 通过查找该表 即可找到每页在内存中的物理块号 可见 页表的作用是实现从页号到物理块号的地址映射 63 说明 页表负责记录逻辑页面与内存物理块的一一对应关系每个进程都有自己的一张页表页表的长度由进程大小和页面大小共同决定 比如一进程为4765B 若页面大小为1KB 页 则该进程包含5页 第0页 第4页 即该进程的页表包含5个表项 64 思考几个问题页面大小一般为2n字节 但具体n有多大 过小怎样 过大怎样 过小 则页表过长 换入 换出效率低 使用和维护的开销大 过长 页内碎片大 已知逻辑地址和页面大小 如何计算页号及页内地址 页号 逻辑地址 页面大小 整除运算 页内地址 逻辑地址 页面大小 求余运算 例 已知页面大小为1KB 页 现有一数据的逻辑地址为2148 问 该数据在哪页的哪个位置 页号 2148 1024 2 页内地址 2148 1024 100 即 该数据在该进程的第2页的相对地址100处 65 3 静态页式管理 基本页式管理 必须将一个进程的所有页面全部装入到内存物理块 无法实现虚存 4 动态页式管理允许将一个进程的一部分页面装入到内存物理块 采用 请求调页 或 预调页 技术实现了内外存存储器的统一管理即对换技术 内存中只存放那些经常被执行或将要被执行的页面 而不常被执行或近期内不会执行的页面则存放在外存 待需要时再按请求式调入 5 分页管理的重点逻辑地址 物理地址的地址变换 页表 硬件地址变换机构 页面的动态置换技术 66 4 4 2地址变换机构1 基本的地址变换机构地址映射 连续的N个页面对应于不连续的N个物理块逻辑页号 物理块号 查页表页内地址 块内地址 两者相等从成本和容量上来考虑 采用寄存器来存储页表是不现实的 因此 页表大多驻留在内存中 而在系统中只设置一个页表寄存器PTR Page TableRegister 在其中存放该进程的页表在内存的始址和页表的长度 平时 进程未执行时 页表的始址和页表长度存放在本进程的PCB中 当调度程序调度到某进程时 才将这两个数据装入页表寄存器中 因此 在单处理机环境下 虽然系统中可以运行多个进程 但只需一个页表寄存器 67 地址变换算法当某进程被调度执行时 将其PCB中记录的页表始址S和页表长度L取出来放到 页表寄存器 中 同时 分页地址变换机构会自动将逻辑地址划分为页号P和页内地址W 然后用页号P与页表长度L比较 若P L则越界中断 否则合法 再以页号P去检索页表 查得该页P对应的物理块号 进而算得该块在内存的起始地址B 最后B与页内地址W 即块内地址 相加就得到了要访问的物理地址 这样便完成了从逻辑地址到物理地址的变换 图4 13示出了分页系统的地址变换机构 68 69 例 已知页面长度为1KB 页 某进程的页表如图所示 现有逻辑地址为100的一条指令LOADR1 2500 问 试说明该指令的取指过程 试说明该指令的取数过程 70 逻辑地址为100的指令的取指过程 页号 逻辑地址 页长 100 1024 0页内地址 逻辑地址 页长 100 1024 100物理地址 物理块号 块长 块内地址 2 1024 100 2148 71 逻辑地址为100的指令的取数过程 该数的逻辑地址为2500 页号 逻辑地址 页长 2500 1024 2页内地址 逻辑地址 页长 2500 1024 452物理地址 物理块号 块长 块内地址 8 1024 452 8644 72 2 具有 快表 的地址变换机构引入 快表 前 完成一次取指或取数操作都至少要访问2次内存 第1次是通过访问内存页表 计算并获得指令或数据的物理地址 第2次是根据该物理地址去访问内存并取得想要的指令或数据 如何加快访问速度 解决方法 方法一 将进程的整张页表放在大量寄存器阵列中而不是放在内存中 该方法成本过于昂贵 不可取 方法二 在地址变换机构中加入一个高速联想存储器 俗称快表 73 引入 快表 后 快表中始终存放最近访问过或访问频率最高的若干页表项 在进行取指或取数操作时 地址变换机构先将页号拿到快表中检索 若找到对应物理块号则立即结合块内地址形成物理地址 此为命中Cache 若未找到才去访问内存中完整的页表从而得到物理块号 此为未命中Cache 与此同时将该页表项从内存更新至快表 命中Cache的情况下 取指或取数只需访问一次内存 未命中Cache的情况下 取指或取数仍需访问二次内存 74 图4 14具有快表的地址变换机构 75 例 已知检索一次快表的时间为20ns 访问一次内存的时间为100ns 问 在分页式系统中 1 若不使用快表机制 存取一个数据需多少时间 2 若使用快表机制 再假定快表命中率分别为0 50 80 90 98 时 存取一个数据各需要多少时间 解 若不使用快表 则存取一个数据需200ns若使用快表 则存取一个数据需要的时间T T 命中率 1次访问快表 1次访存 1 命中率 1次访问快表 2次访存 命中率 20 100 1 命中率 20 100 100 思考 从本例来看 能否画出命中率和存取时间之间的曲线关系 能否推测出Cache容量和命中率之间的曲线关系 76 4 4 3两级和多级页表现代的大多数计算机系统 都支持非常大的逻辑地址空间 232 264 在这样的环境下 页表就变得非常大 要占用相当大的内存空间 例如 对于一个具有32位逻辑地址空间的分页系统 规定页面大小为4KB即212B 则在每个进程页表中的页表项可达1兆个 220 之多 又因为每个页表项占用一个字节 故每个进程仅仅其页表就要占用1MB的内存空间 而且还要求是连续的 显然这是不现实的 我们可以采用下述两个方法来解决这一问题 1 两级页表 采用离散分配方式来存储页表 即对页表进行分页 见下页图 先查外层页表得知内层页表地址 再根据内层页表找到块号 2 请求调页表 预调页表 只将当前需要的部分页表项调入内存 其余的页表项仍驻留在磁盘上 需要时再调入 77 图4 15两级页表结构 78 图4 16具有两级页表的地址变换机构 79 2 多级页表对于32位的机器 采用两级页表结构是合适的 但对于64位的机器 采用两级页表是否仍可适用的问题 须做以下简单分析 如果页面大小仍采用4KB即212B 那么还剩下52位 假定仍按物理块的大小 212位 来划分页表 则将余下的42位用于外层页号 此时在外层页表中可能有4096G个页表项 要占用16384GB的连续内存空间 这样的结果显然是不能令人接受的 因此必须采用多级页表 将外层页表再进行分页 也就是将各分页离散地装入到不相邻接的物理块中 再利用第2级的外层页表来映射它们之间的关系 80 4 5基本分段存储管理方式 段式管理的基本思想 把一个程序按功能或过程函数关系划分成若干个段 Segment 每个段都有自己的名字且大小不等 段式存储管理以段为单位分配内存 一个段装入一个内存分区 同一程序的N个段对应的N个分区可以不连续 然后通过段表和硬件地址映射机构把段式二维虚拟地址转换成实际的内存物理地址 81 4 5 1引入分段存储管理方式的原因方便编程和编译程序是按照逻辑功能来划分段 每个段的虚拟地址都是从0开始有利于信息共享页无独立功能和逻辑意义 不便共享 段则相反 有利于信息保护同上适于动态增长页长固定不变 不利于动态增长 而段长可变 适于动态链接分段管理更适合于请求调入和预调入机制 82 4 5 2静态分段系统的基本原理1 分段一个程序的地址空间按逻辑功能被划分为N个段 有大有小 分别载入N个内存分区中 段内的数据连续 不同段之间的数据离散 例如 有主程序段MAIN 子程序段X 数据段D及栈段S等 如图4 17所示 每个段都有自己的名字 为了实现简单起见 通常可用一个段号来代替段名 每个段都从0开始编址 并采用一段连续的地址空间 逻辑地址由段号 段名 和段内地址所组成 在左图的地址结构中 每个程序最多被分为215即32K个段 每个段最长为217即128KB 83 如何才能完成逻辑地址到物理地址的地址变换 84 2 段表请回顾页式管理中 页表 的作用 在段式管理中 系统中为每个进程建立一张段映射表 SegmentMappingTable 简称 段表 每个段在段表中占有一个表项 其中记录了该段在内存中的起始地址 又称为 基址 和段的长度 请尝试画出该进程的内存分布示意图 85 图4 17利用段表实现地址映射 86 3 地址变换机构当某进程被调度执行时 将其PCB中记录的段表始址和段表长度取出来放到 段表寄存器 中 当进行地址变换时 系统将逻辑地址中的段号与段表长度比较 若段号 段表长度则越界中断 否则合法 再以段号去检索段表 查得该段在内存中的起始地址和段长 然后 再比较段内地址与段长 如果段内地址 段长则越界 否则合法 最后将该段起始地址与段内地址相加 即可得到最终要访问的内存物理地址 这样便完成了从逻辑地址到物理地址的变换 87 88 例 已知某进程的段表如图所示 现有段号为2 段内地址为128的一条指令 请说明该指令的取指过程 89 段号为2 段内地址为128的指令的取指过程 物理地址 段基址 段内地址 8192 128 8320 90 4 添加 快表 存放最近访问过或访问频率最高的若干段表项 其原理与页式管理中的快表相同 由于段表的规模通常远小于页表 所以在段式管理中采用快表的效果要优于页式管理 91 5 静态分页与静态分段的比较相同点 都是采用离散存储方式 都需硬件地址变换机构 都需整体装入 提供了实现虚存的部分基础 不同点 页以定长划分 系统需要 段不定长且以逻辑功能划分 用户和程序员需要 段具备逻辑意义 更适于共享和动态链接 页式管理中的逻辑地址是一维的 段式管理中的逻辑地址是二维的 通常段长比页长大 故段表比页表短 可缩短查找时间 提高访问速度 页式管理的碎片问题轻于段式管理 92 4 5 3信息共享分段系统相比分页系统的优点之一是共享性 例 一个多用户系统 最多同时接纳40个用户 每个用户都会用到一个文本编辑程序 TextEditor 它分为160KB的代码段和40KB的数据段 问最多需要多少内存空间 不考虑共享 40 160 40 KB 8000KB段式共享 160KB 40 40KB 1760KB如果采用页式管理 假设页长为4KB 页 93 图4 19分页系统中共享editor的示意图 94 图4 20分段系统中共享editor的示意图 95 可重入代码 纯代码PureCode 允许多个进程同时访问 读 执行 但不允许任何进程修改的内存共享代码段 最常见的是DLL模块 一般来说 DLL是一种磁盘文件 以 dll drv fon sys和许多以 exe为扩展名的系统文件都可以是DLL 操作 c windows system32 tasklist m 96 4 5 4段页式存储管理方式1 基本原理页式 碎片少 内存利用率高段式 面向用户 更利于共享和保护 可动态链接 可动态增长 段页结合式 将程序划分成若干个段 再把每段分成若干个页 思考 段页结合式的逻辑地址应该是什么样的 97 图4 22利用段表和页表实现地址映射 98 2 地址变换过程在段页式系统中 为了便于实现地址变换 须配置一个段表寄存器 其中存放段表始址和段表长TL 进行地址变换时 首先利用段号S 将它与段表长TL进行比较 若S TL 表示未越界 于是基于段表始址用段号去查段表 从而得到该段的页表始址 并利用逻辑地址中的段内页号P去查该段的页表 从中读出该页所在的物理块号b 再利用块号b和页内地址 即块内地址 来构成物理地址 图4 23示出了段页式系统中的地址变换机构 99 图4 23段页式系统中的地址变换机构 100 思考 在段页式系统中 完成一次取指或取数操作需要访问几次内存 答案 3次 第1次 根据段号去访问段表 得到页表始址第2次 根据段内页号去访问页表 获得物理块号后再结合页内地址计算出物理地址第3次 根据物理地址去访问内存 完成取指或取数操作结论 更应该采用 快表 来提高内存访问效率 101 4 6虚拟存储器的基本概念 背景 静态分页和静态分段都要求将程序的整体载入内存后才能运行 这将导致大程序无法运行或大量程序无法载入内存的情况 如何解决 从物理上扩充内存 需要 不在OS的讨论范畴 从逻辑上扩充内存 虚拟存储器技术的作用 102 4 6 1虚拟存储器的引入1 常规存储器管理方式的特征 1 一次性 程序必须一次性整体装入内存 2 驻留性 程序必须一次性整体卸出内存 程序在执行中途不会部分撤出内存 想想 对于程序执行来说 这两个特征是必需的吗 这两个特征的存在使得内存利用率很低 导致系统吞吐量变小 103 2 局部性原理在一小段时间内 程序的执行仅局限于某个段落 且它所访问的存储空间也局限于某个区域 时间局部性 刚访问过的马上会再度被访问 递归调用 循环结构 空间局部性 刚访问过某处 马上会访问邻近的区域 顺序存储结构 104 3 虚拟存储器的定义指具有请求调入功能和置换功能 能从逻辑上对内存容量加以扩充的一种存储器系统 其逻辑容量由内存容量和外存容量之和决定 其运行速度慢于内存 而单位成本又接近于外存 由此可见 虚拟存储器技术是一种以时间来换取空间的技术 105 4 引入虚存技术的好处可在较小的可用内存中执行较大的用户程序可在内存中容纳更多的程序来实现并发执行不必影响编程时的程序结构提供给用户可用的虚拟内存空间大于实际物理内存容量 106 4 6 2虚拟存储器的实现方法1 分页请求系统在静态分页系统的基础上 增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统 它允许只装入少数页面的程序及数据 便启动运行 以后 再通过调页功能及页面置换功能 陆续地把暂不运行的页面换出到外存上 同时把即将要运行的页面调入内存 置换是以页为单位进行的 为了实现请求调页和置换功能所必需的硬件和软件支持 1 硬件支持 缺页中断机构 地址变换机构 2 软件支持 请求分页的页表机制 实现请求分页和页面置换的软件 107 2 请求分段系统在静态分段系统的基础上 增加了请求调段及分段置换功能后所形成的段式虚拟存储系统 它允许只装入少数段 而非所有的段 的用户程序和数据 即可启动运行 以后再通过调段功能和段的置换功能将暂不运行的段调出 同时调入即将运行的段 置换是以段为单位进行的 为了实现请求分段所必需的硬件和软件支持 1 硬件支持 缺段中断机构 地址变换机构 2 软件支持 请求分段的段表机制 实现请求分段和段置换的软件 108 4 6 3虚拟存储器的特征1 离散性一个进程在内存中非连续存放 是下面2 3 4的基础2 多次性一个程序被分成多次调入内存运行3 对换性同一进程的不同部分之间换入换出频繁4 虚拟性用户感觉的内存容量远大于物理内存容量 109 4 6 4虚拟存储器的种类动态 请求 页式管理动态 请求 段式管理动态 请求 段页式管理 110 4 7请求分页存储管理方式 请求分页存储管理 动态分页式管理 部分装入 动态置换4 7 1请求分页中的硬件支持1 页表机制在请求分页系统中所需要的主要数据结构是页表 其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址 由于只将应用程序的一部分调入内存 还有一部分仍在盘上 故须在页表中再增加若干项 供程序 数据 在换进 换出时参考 在请求分页系统中的每个页表项如下页所示 111 记录该页是否已在内存中 记录该页已被访问次数的计数器或未被访问时间的计时器 记录该页在内存中是否被修改过 以决定该页被换出时是否需要重写回外存 记录该页在外存对应的物理块号 思考 在上面6个字段中 哪些是所有页都有的 哪些是内存页才会有的 所有页都有的字段 内存页才有的字段 112 2 缺页中断机构缺页 在指令执行期间 一旦发现要访问的页面当前不在内存 则称为一次缺页 必将引发一次缺页中断 缺页中断机构用于确保缺页中断及时 有效 安全地进行 注意区别 缺页 与 置换 的概念 缺页中断作为中断 它们同样需要经历诸如保护CPU环境 分析中断原因 转入缺页中断处理程序进行处理 恢复CPU环境等几个步骤 但缺页中断又是一种特殊的中断 它与一般的中断相比 有着明显的区别 1 缺页中断是在指令执行期间产生和处理的 2 一条指令在执行期间可能产生多次缺页中断 3 地址变换机构 113 图4 25请求分页中的地址变换过程 114 4 7 2内存分配策略和分配算法1 最小物理块数的确定这里所说的最小物理块数 是指能保证进程正常运行所需的最少物理块数 115 2 物理块的分配策略1 固定分配 局部置换 FixedAllocation LocalReplacement 为各进程分配固定不变的物理块数 缺页时只能选择本进程的某页来置换 分析 这种方式难以准确确定一个进程所需的物理块数 分配太少会导致频繁缺页 降低吞吐量 分配太多则限制了系统并发度 使资源利用率降低 116 2 可变分配 全局置换 VariableAllocation GlobalReplacement 为各进程分配若干物理块数 OS自身设置一个公共空闲物理块队列 某进程缺页时就从公共空闲物理块队列中选择一个物理块以调入缺页 若公共队列的空闲块用完则由OS选择任一进程的某页调出 从而腾出一个空闲块以载入缺页 117 3 可变分配 局部置换 VariableAllocation LocalReplacement 为各进程分配一定数额的物理块数 缺页时只能选择本进程的某页来置换 但若系统发现某进程的缺页中断过于频繁 则由系统为该进程一次性再追加若干物理块以缓解缺页率 若系统发现某进程的缺页中断过于稀少 则由系统从该进程一次性回收若干物理块 118 3 物理块分配算法1 平均分配算法各进程等分所有物理块 极不合理 2 按比例分配3 考虑优先权的分配算法按比例分配 优先权策略 119 4 7 3调页策略 When Where How 1 何时调入页面 When1 请求调页策略要用到某页但发现不在内存时 再去申请调入 被调入的页必定会立即使用 但每次都只调入一页 不断启动I O使得系统开销大 2 预调页策略预测哪些页将很快被访问到 从而预先调入这些页 准确率不够高 120 2 确定从何处调入页面 Where对换区采用连续分配方式 I O速度快 适合于存放对速度要求高的进程或存放被修改过的换出页面 文件区采用离散分配方式 I O速度慢 适合存放大型进程或不会被修改的页面 121 3 页面调入过程 How每当程序所要访问的页面未在内存时 便向CPU发出一缺页中断 中断处理程序首先保留CPU环境 分析中断原因后转入缺页中断处理程序 该程序通过查找页表 得到该页在外存的物理块 如果此时内存能容纳新页 则启动磁盘I O将所缺之页调入内存 然后修改页表 如果内存已满 则须先按照某种置换算法从内存中选出一页准备换出 如果该页未被修改过 可不必将该页写回磁盘 但如果此页已被修改 则必须将它写回磁盘 然后再把所缺的页调入内存 并修改页表中的相应表项 置其存在位为 1 并将此页表项写入快表中 在缺页调入内存后 利用修改后的页表 去形成所要访问数据的物理地址 再去访问内存数据 整个页面的调入过程对用户是透明的 122 4 8页面置换算法 页面淘汰算法 页面置换算法的好坏极大地影响着系统性能 抖动 Thrashing 由于页面置换算法选择不当而导致系统的页面置换调度非常频繁 如刚换出的页立即又被换入 使访问外存时间和I O处理时间大大增加 反而造成CPU因等待数据而空转 导致系统性能大大下降的现象 正确的置换出发点 未来永远不再使用的页面 未来长期不会使用的页面 过去短期内较少使用的页面 123 4 8 1最佳置换算法和先进先出置换算法1 最佳 Optimal 页面置换算法 OPT算法 最久不会再用到的页