[工学]4第四章-存储器管理.ppt

第四章第四章 存储器管理存储器管理 存储管理是指存储器资源（主要指内存并涉及外 存）的管理。 q 存储器资源的组织（如内存的组织方式） q 地址变换（逻辑地址与物理地址的对应关系 维护） q 虚拟存储的调度算法 1 存储 管理 q本章的目的是了解各种存储器管理的方式和它 们的实现方法。 q本章学习重点： q1.两种具体的存储管理方式：动态重定位的可 变分区管理和虚拟分页存储管理。 2.两类主要的算法：内存分配算法和页面淘汰 算法 3.三对概念的区别：实存与虚存，分页与分段 ，连续分配与离散分配 2 存储 管理第四章 存储管理 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 3 存储 管理 一.存储器 存储器 主存(内部存储器，磁芯存储器） 辅存 （外存）磁盘、 磁带、软盘 高速缓冲存储器 主存 系统区 （存放OS程序和数据） 用户区 （存放用户程序、数据） 由于系统开工期间，OS程序与其他程序一起共享主存，为安全 起见，多道程序系统常由OS把内存初始化为： 4 存储 管理 高速缓存器 内 存 外 存存储器容量 减少 每位存储器 成本增加 存储器存取 速度增加 存储器存取 时间减少 程序和数据 可以被CPU 直接存取 程序和数据必 须先移到内存， 才能被CPU访问 三级存储器结构 返回 5 存储 管理 4.1.1 多级存储器结构 容量愈来愈大 访问数据的速度愈来愈慢 价格愈来愈便宜 6 存储 管理 4.2 程序的装入和链接 7 存储 管理 4.2 程序的装入和链接 在多道程序环境下，要使 程序运行，必须创建进程，而 创建进程第一件事就是将程序 和数据装入内存。 一个用户源程序 要变为在内存中可执行的程序 ，通常要进行以下处理：（1 ）编译：由编译程序 将用户源程序编译成若干 个目标模块； （2）链接：由链接程序将 目标模块和相应的库函数 链接成装入模块； （3）装入：由装入程序 将装入模块装入内存。 库 目标程序块1 目标程序块2 第一步 链接程序 装入模块 第二步 装入程序 第三步 用户源程序 编译程序 内存 8 存储 管理 1. 绝对装入方式 q如果在编译时，事先知用户程序在内存的驻留位 置，则编译程序在编译时就产生绝对地址的目标 代码。装入程序就直接把装入模块中的程序和数 据装入到指定的位置，（不需进行地址转换）。 q程序中所使用的绝对地址，既可在编译或汇编时 给出， 也可由程序员直接赋予。 但在由程序员直 接给出绝对地址时， 不仅要求程序员熟悉内存的 使用情况，而且一旦程序或数据被修改后，可能 要改变程序中的所有地址。因此，通常是宁可在 程序中采用符号地址，然后在编译或汇编时，再 将这些符号地址转换为绝对地址。 4.2.1 程序的装入 9 存储 管理 1.名空间、地址空间和存储空间 n在我们用汇编语言或高级语言编写程序时，总是通 过符号名来访问某一单元。我们把程序中由符号名 组成的空间称为名空间。 n源程序经过汇编或编译形成的程序，通常是以0为基 址进行顺序编址，这样的地址表示形式称为相对地 址,也叫做逻辑地址或虚地址，把该程序逻辑地址组 成的集合叫做程序的逻辑地址空间(简称地址空间) 。 n存储器中每个具体存储单元都有不同的编号，每个 编号就是一个物理地址，整个程序在内存中存储后 所占用的物理地址的集合形成程序的物理地址空间( 简称存储空间)。 2. 重定位（地址映射）装入方式 10 存储 管理 可重定位装入方式 把在装入时对目标程序中指令和数据的 修改过程称为重定位，又因为地址变换 通常是在装入时一次完成的，以后不再 改变，故称为静态重定位。 11 存储 管理 优缺点 优点：不需要硬件的支持。 缺点：程序必须占用连续的内存空间； 一旦程序装入后不能移动。 静态重定位 12 存储 管理 3. 动态运行时装入方式 动态运行时的装入程序，在把装入模块装入内 存后，并不立即把装入模块中的相对地址转换为绝 对地址，而是把这种地址转换推迟到程序真正要执 行时才进行。因此， 装入内存后的所有地址都仍是 相对地址。 13 存储 管理 映射方法 最简单的硬件机构是重定位寄存器。 在地址重定位机构中，有一个基地址寄 存器BR和一个程序地址寄存器VR，一 个内存地址寄存器MR。 动态重定位 14 存储 管理 0 3456 . . . . . . LOAD 1 200 . . . . . . 0 100 200 300 . . . . . . . . . LOAD 1 200 3456 逻辑地址空间 1100 1200 1300 物理地址空间 200 有效地址 + 1000 BR 1000 15 存储 管理 4.2.2 程序的链接 一种事先链接方式，即在程序运行之前，先将各目 标模块及它们所需的库函数，链接成一个完整的装入模 块(执行文件)，以后不再拆开。 实现静态链接应解决: 1）相对地址的修改 2）变换外部调用符号 存在问题： 1）不便于对目标模块 的修改和更新。 2）无法实现对目标模 块的共享。 模块A CALL B; RETURN; 模块B CALL C; RETURN; 模块C RETURN; 0 L-1 0 M-1 0 N-1 目标模块 0 L-1 L L+M-1 L+M L+M+N-1 模块C Return； 模块B JSR“L+M” Return； 模块A JSR“L” Return； 装入模块 1. 静态链接方式 16 存储 管理 指将一组目标模块在装入内存时，边装入边链接的 方式。具有便于修改和更新、便于实现对目标模块的共 享。 存在问题： 由于程序运行所有可能用的目标模块在装入时均全部链 接在一起，所以将会把一些不会运行的目标模块也链接 进去。如程序中的错误处理模块。 2. 装入时动态链接方式 在程序运行中需要某些目标模块时，才对它们进行 链接的方式。具有高效且节省内存空间的优点。 3. 运行时动态链接方式 17 存储 管理 单一用户(连续)分配是一种简单的存储分配方案，主 要用于单用户单任务操作系统。它的实现方案如下： (1) 内存分配：整个内存划分为系统区和用户区。系统区 是操作系统专用区，不允许用户程序直接访问，一道 用户程序独占用户区. 4.3.1 单一用户存储管理方案 注意: 我们所涉及的内存分配 与回收一般都指用户区 的分配与回收。 进程1 OS系统区 用户区 4.3 连续分配方式 18 存储 管理 (3) 内存保护：通过基址寄存器保证用户程序不会从系统区 开始；另外系统需要一个界限寄存器，里边存储程序逻 辑地址范围，若需要进行映射的逻辑地址超过了界限寄 存器中的值，则产生一个越界中断信号。 (2) 地址映射：物理地址=用户区基地址+逻辑地址。 单一连续分配方案的优点是方法简单，易于实现；缺 点是它仅适用于单道程序，因而不能使处理机和内存得到 充分利用。 19 存储 管理 例： 一个容量为256KB的内存，操作系统占用32KB， 剩下224KB全部分配给用户作业，如果一个作业 仅需64KB，那么就有160KB的存储空间被浪费。 操作系统统 作业业 0KB 32KB 96KB 256KB-1 分配给用 户的空间 20 存储 管理 4.3.2-4 分区存储管理 分区存储管理是把主存储器中的用户区 作为一个连续区或分成若干个连续区进行管 理，每个连续区中可装入一个作业。 多道程序系统一般都采用多个分区的存 储管理，具体可分为固定分区和可变分区两 种方式。 21 存储 管理 1、固定分区存储管理 区号分区长度起始地 址 状态 1l1Ka0 2l2Kbjob2 3l3Kc0 OS 0 a b c d 空 job2 把主存中可分配的用户区域预先划分成若干个连续的分区 ，每个连续区的大小可以相同，也可以不同。但是，一旦划分 好分区之后，主存中分区的个数就固定了，且每个分区的大小 也固定不变。这是一种静态分区法。 22 存储 管理 80K 操作系统 作业1 作业2 作业3 0 20K 45K 130K 200K 分区1 分区2 分区3 分区4 （未分配） 分区 号 大小（ K） 开始 地址 状态 12520正使用 23545正使用 35080正使用 470130未使用 固定分区 分区说明表 23 存储 管理 在固定分区方式管理下，每个分区用来装入一个作 业。由于主存中有多个分区，就可同时在每个分区 中装入一个作业。所以，这种存储管理方式适用于 多道程序系统。 等待进入主存的作业排成一个作业队列。当主存中 有空闲的分区时，依次从作业队列中选择一个能装 入该分区的作业。当所有的分区都已装有作业，则 其他的作业暂时不能再装入，绝对不允许在同一分 区中同时装入两个或两个以上的作业。已经装入主 存的作业在获得处理机运行时，要限定它只能在所 占的分区中执行。 24 存储 管理 0 40K 256K 操作 系统 作业1 作业2 作业3 100K 200K 230K 0 40K 256K 操作 系统 作业1 作业2 结束 作业3 100K 200K 230K 装入 作业 4 0 40K 256K 操作 系统 作业1 作业3 100K 200K 230K 170K 作业4 0 40K 256K 操作 系统 作业3 100K 200K 230K 170K 作业4 作业1 结束 0 40K 256K 操作 系统 作业3 100K 200K 230K 170K 作业4 50K 作业5 25 存储 管理2内存空间的分配与释放 为了管理主存空间的使用，必须设置一张“主存分配表”，以 说明各分区的分配情况。主存分配表中应指出各分区的起始地 址和长度，并为每个分区设一个标志位。当标志位为“0”时 ，表示对应的分区是空闲分区，当标志位为非“0”时，表示 对应的分区已被某作业占用。空闲分区可以用来装作业。 区号 分区大小 起始地址 标志位 0 32k 0k 1 1 8k 32k 1 2 16k 40k 0 3 32k 56k 1 4 64k 88k 0 OS 作业A(6k) 作业B(28k) 0 32k 40k 56k 88k 26 存储 管理 当作业队列中有作业要装入主存时，存储管理可采 用“顺序分配算法”进行主存空间的分配。 顺序查看主存分配表，找到一个标志为“0”的并且长度大 于或等于欲装入作业的地址空间长度的分区，则把此分区 分配给该作业，相应表目的标志位改成作业名的标识；若 找不到一个这样的空闲分区，则该作业暂时不能装入主存 。 主存空间的释放很简单。某作业执行结束后必须归还所占 的分区，这时存储管理根据作业名查看主存分配表，找到 相应的表目后，把其中的标志位重新置成“0”即可。 27 存储 管理 内存空间利用率低，如 图。5道进程大小总和 为250 KB，但是所占5 个分区总容量却达到 1000 KB，内存空间利 用率仅达到25%。 解决办法： 采用可变分区存储管理 28 存储 管理 4.3.2 固定分区分配总结 作业装入之前，内存就被划分成若干个分区。 划分工作可以由系统管理员完成或由操作系统实现。 一旦划分完成，在系统运行期间不再重新划分，即分 区的个数不可变，分区的大小不可变，且每个分区装 一个且只能装一个作业。 可将内存的用户区域划分成大小相等或不等的分区。 v分区大小相等：只适合于多个相同程序的并发执行（ 处理多个类型相同的对象）。 v分区大小不等：多个小分区、适量的中等分区、少量 的大分区。根据程序的大小，分配当前空闲的、适当 大小的分区。 系统有一张分区说明表，每个表目说明一个分区的大 小、起始地址和是否已分配的使用标志。 29 存储 管理 内存管理的可变分区模式，又称变长分区模式。 与固定分区的区别就是：动态的划分分区。 克服固定分区管理的“内碎片”问题。 4.3.3 动态（可变）分区分配 30 存储 管理 作业装入内存时，从可用的内存中划出一块连续的区域 分配给它，且分区大小正好等于该作业的大小。 可变式分区中分区的大小和分区的个数都是可变的，而 且是根据作业的大小和多少动态地划分。 在分配时，首先找到一个足够大的空闲分区，即这个空 闲区的大小比作业要求的要大，系统则将这个空闲分区 分成两部分：一部分成为已分配的分区，剩余的部分仍 作为空闲区。 在回收撤除作业所占领的分区时，要检查回收的分区是 否与前后空闲的分区相领接，若是，则加以合并，使之 成为一个连续的大空间。 常用的数据结构有内存分配表（由已分配区表和空闲区 表组成）和空闲分区链两种。 31 存储 管理 0 20K 256K 操作系统 216K 作业需要内存 大小（K ） 运行 时间 13210 2145 36420 41008 55015 内存初始情况和作业队列 1主存空间的分配与释放 32 存储 管理 33 存储 管理 34 存储 管理 OS P1 P3 OS P1 P3 OS P4 例子：一计算机系统有2560KB内存，采用某种模式管理， OS占低地址的400KB空间，用户内存为2160KB。 P1 OS P1 P2 OS P1 P2 P3 P2 35 存储 管理 分区分配算法：寻找某个空闲分区，其大小需 大于或等于程序的要求。若是大于要求，则将 该分区分割成两个分区，其中一个分区为要求 的大小并标记为“占用”，而另一个分区为余下 部分并标记为“空闲”。分区的先后次序通常是 从内存低端到高端。 2 2 动态分区分配算法动态分区分配算法 36 存储 管理 目前常用分配算法有： q首次适应算法 q循环首次适应算法 q最佳适应算法 q最坏适应算法 q快速适应法 37 存储 管理 首次适应算法（最先适应算法 ） =1.空闲分区表的表目按相应分区的地址大小以递 增顺序排列。 =2.顺序查找各个空闲区，把第一个找到能容纳申请要求的 内存区分配给申请者.（若空闲区比作业长度大，则分割该 空闲区。一部分分配给作业一部分空闲。若等大？） =3.调整相应的空闲表和已分配表。 38 存储 管理 区号大小起址 132k20k 28k52k 3120k60k 4331k180k 空闲分区表 解：按首次适应算法， 申请作业100k，分配3号分区，剩下分区为20k，起始地址160K ； 申请作业30k，分配1号分区，剩下分区为2k，起始地址50K ； 申请作业7k，分配2号分区，剩下分区为1k，起始地址59K ； 其内存分配图及分配后空闲分区表如下： 例 ：系统中的空闲分区表如下，现有三个作业分配申 请内存空间100K、30K及7K。给出按首次适应算法 的内存分配情况及分配后空闲分区表。 39 存储 管理 区号大小起址 12k50k 21k59k 320k160k 4331k180k (2)该算法分配后的空闲分区表 0k 20k 50k 52k 59k 60k 160k 180k 511k (1)内存分配图 v首次适应算法的特点 优先利用内存低地址部分的空闲分区,从而保留 了高地址部分的大空闲区。但由于低地址部分不断被 划分,致使低地址端留下许多难以利用的很小的空闲 分区(碎片或零头),而每次查找又都是从低地址部分 开始,这无疑增加了查找可用空闲分区的开销。 40 存储 管理 循环首次适应算法 算法要求 又称为下次适应算法，由首次适应算法演 变而来。在为作业分配内存空间时,不再每次从 空闲分区表/链首开始查找,而是从上次找到的 空闲分区的下一个空闲分区开始查找,直到找到 第一个能满足其大小要求的空闲分区为止。然 后，再按照作业大小，从该分区中划出一块内 存空间分配给请求者，余下的空闲分区仍留在 空闲分区表/链中。 41 存储 管理 区号大小起址 132k20k 28k52k 3120k60k 4331k180k 空闲分区表 解：按循环首次适应算法， 申请作业100k，分配3号分区，剩下分区为20k,起始地址160K； 申请作业30k，分配4号分区，剩下分区为301k，起始地址210K ； 申请作业7k，分配1号分区，剩下分区为25k，起始地址27K ； 其内存分配图及分配后空闲分区表如下: 例 ：系统中的空闲分区表如下，现有三个作业分配申 请内存空间100K、30K及7K。给出按循环首次适应 算法的内存分配情况及分配后空闲分区表。 42 存储 管理 区号大小起址 12k27k 21k52k 320k160k 4131k210k (2)该算法分配后的空闲分区表 v算法特点 使存储空间的利用更加均衡，不致使小的空闲区集 中在存储区的一端，但这会导致缺乏大的空闲分区。 0k 20k 27k 52k 60k 160k 180k 210k 511k (1)内存分配图 43 存储 管理 最佳适应算法： 搜索整个空闲区以找出满足要求的最小空闲区。搜索整个空闲区以找出满足要求的最小空闲区。 思想： 1.空闲分区表的表目按相应分区的大小以递增顺序排 列。 2.在进行内存分配时，从空闲分区表/链的首开始顺序查找， 直到找到第一个满足其大小要求的空闲分区为止。 先使用小的空闲区，将大的空闲区留给大作业，所以它总 是试图找出最接近实际需要的空闲区。 44 存储 管理 例 ：系统中的空闲分区表如下，现有三个作业分配申 请内存空间100K、30K及7K。给出按最佳适应算法 的内存分配情况及分配后空闲分区表。 区号大小起址 18k52k 232k20k 3120k60k 4331k180k 分配前的空闲分区表 内存分区 0k 20k 52k 60k 180k 511k 2 1 3 4 45 存储 管理 解：按最佳适应算法，分配前的空闲分区表如上表。 申请作业100k，分配3号分区，剩下分区为20k,起始地址160K； 申请作业30k， 分配2号分区，剩下分区为2k，起始地址50K ； 申请作业7k， 分配1号分区，剩下分区为1k，起始地址59K ； 其内存分配图及分配后空闲分区表如下： 区号大小起址 18k52k 320k160k 232k20k 4331k180k 作业100K分配后的空闲分区表 区号大小起址 22k50k 18k52k 320k160k 4331k180k 作业30K分配后的空闲分区表 区号大小起址 11k59k 22k50k 320k160k 4331k180k 作业7K分配后的空闲分区表 46 存储 管理(2)该算法分配后的空闲分区表 0k 20k 52k 60k 180k 511k (1)内存分配图 50K 59K 160K 180K 区号大小起址 11k59k 22k50k 320k160k 4331k180k v算法特点 若存在与作业大小一致的空闲分区,则它必然被选中， 若不存在与作业大小一致的空闲分区，则只划分比作业稍 大的空闲分区，,从而保留了大的空闲分区,但空闲区一般 不可能正好和它申请的内存空间大小一样,因而将其分割 成两部分时,往往使剩下的空闲区非常小,从而在存储器中 留下许多难以利用的小空闲区（碎片或零头）。 47 存储 管理 最坏适应算法 1.空闲分区表的表目按相应分区的大小以递 减顺序排列。 2.总是搜索整个链表以找到够用的最大的空 闲区，使分裂出来的小空闲区比较大，因 而可以继续使用。 48 存储 管理 区号大小起址 1331k180k 2120k60k 332k20k 48k52k 空闲分区表 例 ：系统中的空闲分区表如下，现有三个作业分配申 请内存空间100K、30K及7K。给出按最坏适应算法 的内存分配情况及分配后空闲分区表。 49 存储 管理 区号大小起址 1231k280k 2120k60k 332k20k 48k52k 作业100K分配后的空闲分区表 区号大小起址 1201k310k 2120k60k 332k20k 48k52k 作业30K分配后的空闲分区表 区号大小起址 1194k317k 2120k60k 332k20k 48k52k 解：按最坏适应算法，分配前的空闲分区表如上表。 申请作业100k，分配1号分区，剩下分区为231k,起始地址280K； 申请作业30k，分配1号分区，剩下分区为201k，起始地址310K ； 申请作业7k，分配1号分区，剩下分区为194k，起始地址317K ； 其内存分配图及分配后空闲分区表如下： 50 存储 管理 区号大小起址 1194k317k 2120k60k 332k20k 48k52k (2)该算法分配后的空闲分区表 3 0k 20k 52k 60k 180k 511k (1)内存分配图 20K 52K 60K 280K 310K 317K v算法特点 总是挑选满足作业要求的最大的分区分配给作业。这 样使分给作业后剩下的空闲分区也较大，可装下其它作业 。但由于最大的空闲分区总是因首先分配而划分，当有大 作业到来时，其存储空间的申请往往会得不到满足。 51 存储 管理 快速适应算法（分类搜索法 ） 算法要求 将空闲分区根据其容量大小进行分 类，每一类相同容量的所有空闲分区， 单独设立一个空闲分区链表，同时在内 存中设立一张管理索引表，每一表项对 应了一种空闲分区类型，并记录头指针 。进程根据自己的长度，寻找能容纳它 的最小空闲区链表，取下第一块进行分 配即可。 52 存储 管理 最先适应法：按分区的先后次序，从头查找，找到符 合要求的第一个分区 该算法的分配和释放的时间性能较好，空闲较大的分 区可以被保留在内存高端。 但随着低端分区不断划分而产生较多小分区，每次分 配时查找时间开销会增大。 最佳适应法：找到其大小与要求相差最小的空闲分区 从个别来看，外碎片较小，但从整体来看，会形成较 多外碎片。较大的空闲分区可以被保留。 最坏适应法：找到最大的空闲分区 基本不留小空闲分区，但较大的空闲分区不被保留。 几种分配算法的比较 53 存储 管理 例题：分区存储管理算法题 假定主存中按地址顺序依次有五个空闲区。空闲区大小 依次为：32k,10k,15k,228k,100k.现有五个作业 J1,J2,J3,J4,J5。他们各需要主存1k,10k,128k,28k,115k。 判断用最先适应分配算法，最坏适应分配算法，最佳分 配适应算法能否将这五个作业顺序装入？ 54 存储 管理 OS 32K 10K 15K 228K 100K 示意图： 55 存储 管理 起始地址 长度 标志位 100K 32K 0 200K 10K 0 300K 15K 0 400K 228K 0 700K 100K 0 起始地址 长度 标志位 30K 70K ZS 已分配 区表 空闲区 表 56 存储 管理 最先适应分配算法 (空闲区按地址递增顺序排列) 作业依次请求空间1k,10k,128k,28k,115k。 32K228K10K100K15K 空闲链 首指针 (1)作业J1请求1K空间 31K228K10K100K15K 空闲链 首指针 (2)作业J2请求10K空间 21K100K10K100K15K 空闲 (3)作业J3请求128K空间 (4)作业J4请求28K空间 (5)作业J5请求115K空间 所有空间均不能满足作业J5请求 57 存储 管理 最坏适应分配算法 (空闲区按长度递减顺序排列) 作业依次请求空间1k,10k,128k,28k,115k。 228K15K100K10K32K 空闲链 首指针 (1)作业J1请求1K空间 227K15K100K10K32K 空闲链 首指针 (2)作业J2请求10K空间 217K15K100K10K32K 空闲链 首指针 100K15K89K10K32K 空闲链 首指针 89K15K72K10K32K 空闲链 首指针 (3)作业J3请求128K空间 (4)作业J4请求28K空间(5)作业J5请求115K空间 所有空间均不能满足作业J5请求58 存储 管理 最优适应分配算法 (空闲区按长度递增顺序排列) 作业依次请求空间1k,10k,128k,28k,115k。 10K100K15K228K32K 空闲链 首指针 (1)作业J1请求1K空间 9K100K15K228K32K 空闲链 首指针 (2)作业J2请求10K空间 5K100K9K228K32K 空闲链 首指针 5K100K9K100K32K 空闲链 首指针 4K100K5K100K9K 空闲链 首指针 (3)作业J3请求128K空间 (4)作业J4请求28K空间(5)作业J5请求115K空间 所有空间均不能满足作业J5请求 59 存储 管理 （2）回收内存 当作业执行结束时，应回收已使用完毕的分区。系统 根据回收分区的大小及首地址，在空闲分区表中检查是否 有邻接的空闲分区，如有，则合成为一个大的空闲分区， 然后修改有关的分区状态信息。 回收分区与已有空闲分区的相邻情况有以下四种： 1）回收分区上邻接一个空闲分区,合并后首地址为空闲分区 的首地址,大小为二者之和。 2）回收分区下邻接一个空闲分区,合并后首地址为回收分 区的首地址,大小为二者之和。 3）回收分区上下邻接空闲分区,合并后首地址为上空闲分 区的首地址,大小为三者之和。 4）回收分区不邻接空闲分区，这时在空闲分区表中新建一 表项，并填写分区大小等信息。 60 存储 管理 (a) M1、M2都非空(b) M1为空、M2非空 (c) M1为非空、M2空(d) M1、M2都为空 回收内存空间，关键是修改两个表。 61 存储 管理 在动态分区分配中，消除 了固定分区管理造成的“ 内碎片”，但是不可避免 的在内存空间造成“外碎 片”。多个无法利用的小 分区所形成的“碎片”是一 种很大的资源浪费。 如图（a）所示，空闲分区 之和为10 KB，但是无法 装入一个8 KB的程序。 62 存储 管理 v内存扩充 消除了固定分区管理造成的“内碎片”，但 是不可避免的在内存空间造成“外碎片”。 采用移动（紧缩）技术。定时的或在内存 紧张时，将内存中所有作业移到内存的一 端，使其相邻。 63 存储 管理 经过紧缩后的进程在内存中的位置发生了变化 ，若不对程序和数据的地址进行修改，在进程 就无法运行。 要使其运行，必须进行“动态重定位” 64 存储 管理 4.3.6 可重定位分区分配 1. 动态重定位的引入 在分区存储管理方式中，必须把作业装入到 一片连续的内存空间。如果系统中有若干个小 的分区，其总容量大于要装入的作业，但由于 它们不相邻接，也将致使作业不能装入内存。 例 ：如图所示系统中有四个小空闲分区，不相 邻，但总容量为90KB，如果现有一作业要求分 配40KB的内存空间，由于系统中所有空闲分区 的容量均小于40KB，故此作业无法装入内存。 这种内存中无法被利用的存储空间称为“零 头”或“碎片”。根据碎片出现的情况分为以下两 种： 操作系统统 作业业A 20KB 作业业B 30KB 作业业C 15KB 作业业D 25KB 65 存储 管理 系统中的碎片 os 用 户 程 序 p4 p1 p2 0k 20k 56k 65k 125k 135k 内部碎片 内部碎片 内部碎片 25KB 作业D 15KB 作业C 30KB 作业B 20KB 作业A 操作系统 外部碎片 外部碎片 外部碎片 外部碎片 内部碎片 外部碎片 n内部碎片：指分配给作业的存储空间中未被利用的部 分。如固定分区中存在的碎片。 n外部碎片：指系统中无法利用的小的空闲分区。 如动态分区中存在的碎片。 66 存储 管理 碎片问题的解决方法 拼接或紧凑或紧缩技术 将内存中所有作业移到内存一端（作业 在内存中的位置发生了变化，这就必须对 其地址加以修改或变换即称为重定位）， 使本来分散的多个小空闲分区连成一个大 的空闲区。如图所示。这种通过移动作业 从把多个分散的小分区拼接成一个大分区 的方法称为拼接或紧凑或紧缩。 拼接时机：分区回收时；当找不到足 够大的空闲分区且总空闲分区容量可以满 足作业要求时。 操作系统统 作业业A 作业业B 作业业C 作业业D 20KB 30KB 90KB 15KB 25KB 67 存储 管理 2. 动态重定位的实现 动态重定位可使程序不加任何修改就装入内存，但 是它需要硬件重定位寄存器的支持。对每一个有效地 址都要加上重定位寄存器中的内容，以形成绝对地址。 0 3456 . . . . . . LOAD 1 200 . . . . . . 0 100 200 300 . . . . . . . . . LOAD 1 200 3456 逻辑地址空间 1100 1200 1300 物理地址空间 200 有效地址 + 1000 BR 1000 68 存储 管理 动态重定位分区分配算法流程图 有大于x的 空闲分区吗？ 返回分区号 空闲分区 总和大于x吗？ 拼接并修改 相应数据结构 返回 修改有关 数据结构 按动态分区 分配方式进行分配 Y Y N N 无法分配，返回 请求分配一个 大小为x的分区 3. 动态重定位分区分配算法 在动态分区分配算法中增加拼接功能，在找不到足够 大的空闲分区来满足作业要求，而系统中总空闲分区容量 可以满足作业要求时，进行拼接。 69 存储 管理 可重定位分区分配方式主要特点 可以充分利用存储区中的“零头/碎片”， 提高主存的利用率。 但若 “零头/碎片”过多 ，则拼接频率过高会使系统开销加大。 70 存储 管理 4.3.7 覆盖技术与交换技术 1.覆盖技术 n引入：其目标是在较小的可用内存中运行较大的程序。常用 于多道程序系统，与分区存储管理配合使用。 n原理：一个程序的几个代码段或数据段，按照时间先后来占 用公共的内存空间。 将程序的必要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存 放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相 互覆盖。(即不同时用的模块可共用一个分区) n缺点： 编程时必须划分程序模块和确定程序模块之间的覆盖关系 ，增加编程复杂度。 从外存装入覆盖文件，以时间延长来换取空间节省。 71 存储 管理 A 20K D 20K E 40K C 30K B 50K F 30K 作业X的调用结构 作业X的常驻区 A（20K） 覆盖区0 （50K） 覆盖区1 （40K） BC D E F 注：另一种覆盖方法：(100K) A(20K)占一个分区：20K； B(50K)、D(20K)和E(40K)共用一个分区：50K； F(30K)和C(30K)共用一个分区：30K； Total:190K Total:110K 72 存储 管理 2. 交换技术 n引入：多个程序并发执行，可以将暂时不能执行的程 序送到外存中，从而获得空闲内存空间来装入新程序 ，或读入保存在外存中而目前到达就绪状态的进程。 交换单位为整个进程的地址空间。常用于多道程序系 统或小型分时系统中，与分区存储管理配合使用。又 称作“对换“或“滚进/滚出(roll-in/roll-out)“； 程序暂时不能执行的可能原因：处于阻塞状态，低 优先级（确保高优先级程序执行）； n原理：暂停执行内存中的进程，将整个进程的地址空 间保存到外存的交换区中（换出swap out），而将外 存中由阻塞变为就绪的进程的地址空间读入到内存中 ，并将该进程送到就绪队列（换入swap in）。 返回 73 存储 管理 n优点：增加并发运行的程序数目，并且给用户提供适当 的响应时间；编写程序时不影响程序结构 n缺点：对换入和换出的控制增加处理机开销；程序整个 地址空间都进行传送，没有考虑执行过程中地址访问的 统计特性。 n考虑的问题： 程序换入时的重定位； 减少交换中传送的信息量，特别是对大程序； 对外存交换区空间的管理：如动态分区方法； 74 存储 管理 4.4 基本分页存储管理方式 分页存储管理是解决存储零头的一种方法。 动态重定位是解决存储器零头问题的一种途径， 但要移动大量信息花去不少处理机时间,代价比较高, 这是因为这种分配要求把作业必须安置在一连续存储 区内的缘故,而分页存储管理正是要避开这种连续性 要求。 分为：实分页存储管理和虚分页存储管理 75 存储 管理 一、分页式存储管理 实存模式下的页式存储管理 1.基本原理 假设一个大型饭店，所有的客房都是标准的双人间，部 分客房已经住进客人，现在又有一个旅游团要求入住。接待 员统计了一下，对旅游团领队说：“贵团全体成员都能住下 ，两人一个房间，但是不能住在同一楼层了，因为每层空着 的客房不够，更没有几个挨着的。请原谅！”。对于这样的 安排，一般人不会感到奇怪。因为旅游团本来就是由一位位 个人或夫妻等组成的，而饭店的客房本来也是两人一间的， 两人一组正好可住在一个客房里；另外，饭店几乎每天都有 入住的和退房的客人，想在同一楼层找几间挨着的客房实在 不容易。 76 存储 管理 满 满 满 满 满 1楼 2楼 满 满 满 满 满 满 满 满 满 满 77 存储 管理 基本思想 将整个系统的内存空间划分成一系列大小相等的 块，每一块称为一个物理块、物理页或实页，页架 或页帧（frame），可简称为块（block）。所有的 块按物理地址递增顺序连续编号为0、1、2、。 这里的块相当于饭店的客房，系统对内存分块 相当于饭店把大楼所有的客房都设计成标准的双人 间。 78 存储 管理 每个作业的地址空间也划分成一系列与内存块一 样大小的块，每一块称为一个逻辑页或虚页，也有 人叫页面，可简称为页（page）。所有的页按照逻 辑地址递增顺序连续编号为0、1、2、。 这里，对作业地址空间分页就相当于把旅游团成 员分成两人一组。 79 存储 管理 一个作业，只要它的总页数不大于内存中的可用 块数，系统就可以对它实施分配。系统装入作业时 ，以页为单位分配内存，一页分配一个块，作业所 有的页所占的块可以不连续。系统同时为这个作业 建立一个页号与块号的对照表，称为页表页表。 这好象饭店有个记录客户入住情况的客户登记 表一样。另外，饭店安排客户入住是要查看全部客 房的使用情况一览表，相应地系统给作业分配内存 时要查看主存分配表或者内存块说明表。 80 存储 管理 每个块的大小是固定的，一般是个1/2KB 8KB之间的数值（请读者思考：块尺寸为 什么太大或太小都不好），而且必须是个2 的幂次。 对块尺寸这样规定相当于饭店规定客房 是双人间。可以设想一下，如果上例中饭店 所有的客房都是十人间的话，效益肯定不如 全是双人间的好 81 存储 管理 页面(或块)的大小由系统硬件地址结构规定，通常是2 的幂，例如1 KB、2 KB、4 KB等。这样的规定可以使地址 映射容易实现，后面的例子可以帮助我们理解这个问题。 页面不能过大，也不能过小。过小会造成页面过多，页表 过长，页表又会占用较大的内存空间，而且在虚拟存储中 增加了页面换入换出次数，增加了系统开销；过大又会造 成页内碎片太大，内存利用率不高。早期的页面大小一般 都在512 B4 KB，随着计算机性能的提高，现在一般在2 KB8 KB，甚至有的系统支持多种页面大小，比如 Solaris就有4 KB和8 KB两种页面。 82 存储 管理 满 满 满 满 满 1楼 2楼 满 满 满 满 满 满 满 满 满 满 83 存储 管理 概括：实模式下分页存储管理的基本原理 ： 系统自动地将作业的地址空间分页，将系 统的主存空间分块，页与块等大小，在作 业运行时，一次性把作业的全部页面装入 内存，各个页所占的内存块可以不连续。 这实际是个把作业从地址空间映射到存储 空间的过程 84 存储 管理 2.地址结构 页面的划分完全是一种系统硬件的行为 ，一个逻辑地址放到这种地址结构，自 然就分成了页号和页内单元号两部分。 页 号页内地址 31 12 11 0 页面大小为：4KB 0 1 2 3 4 5 作业1 85 存储 管理地址结构及页面大小设置 页面的划分完全是一种系统硬件的行为。 地址结构如下： 页内地址页号 31 12 11 0 若给定某一个逻辑地址（或相对地址），通过下面式 子可以得出页号和页内偏移量： 页号=逻辑地址 DIV 页面大小 页内偏移量=逻辑地址 MOD 页面大小 逻辑地址=逻辑页首址+页内地址（页内偏移量） =逻辑页号*4K+页内地址（页内偏移量） 86 存储 管理 例如页面大小为4 KB的系统中，若逻辑地址为28024 由上式求得28024 div 4096=6（页号） 28024 mod 4096=3448（页内偏移量） 0000 0000 0000 0000 0110 1101 0111 1000 28024 页号6 页内地址3448 87 存储 管理 3、页表 若把他分页后装入到不相邻的 物理块中，要保证系统仍能正 确运行，就要实现从进程的逻 辑地址变换为内存的物理地址 。 所以，系统为每个进程建立一 张页面映射表，简称页表。 满 满 满 满 满 满 满 满 满 满 88 存储 管理 0页 1页 2页 3页 4页 N页 页号 块号 0 4 1 7 2 3 3 5 4 2 页表 用户 程序 内存 通过页表实现页面映射 0 1 2 89 存储 管理 4、地址映射 在系统中设置地址变换机构，能将用户进程地址空间中的 逻辑地址变为内存空间中的物理地址。 由于页面和物理块的大小相等，页内偏移地址和块内偏移 地址是相同的。无须进行从页内地址到块内地址的转换。 地址变换机构的任务，关键是将逻辑地址中的页号转换为 内存中的物理块号。物理块号内的偏移地址就是页内偏移 地址。 页表的作用就是从页号到物理块号的转换，所以地址变换 的任务借助于页表来完成的。 90 存储 管理 通过页表实现地址映射， 设页长为P 内存 1 2 3 4 5 6 7 8 作业线性 地址空间 0 1 A L 0页 1页 2页 3页 4页 分页后 地址空间 页表 块号 4 7 3 5 6 页号 0 1 2 3 4 若逻辑地址为A，则有： A所对应的物理地址=块号M*页长P+页内地址D A/P= 商 为页号N 余数为页内地址D 91 存储 管理 地址映射： 由于页面和物理块的大小相等，故页内偏移地址和块内偏移地 址是相同的。将逻辑地址中的页号转换为内存中的物理块号可 通过查表完成。 0000 0000 0000 0000 0110 1101 0111 1000 逻辑地址28024 页号6 页内地址3448 物理地址85368 0000 0000 0000 0001 0100 1101 0111 1000 举例 设页长 为4096 块号20 块内地址3448 0000 0000 0000 0001 0100 0000 0000 0000 即将逻辑地址中页号替换为块号。 92 存储 管理 【例4-1】 考虑一个由8个页面，每页1K字节组成的逻辑 空间，把它映射到由32个物理块组成的存储器 ，试问逻辑地址和物理地址各有多少位？ 分析：解此题的关键是要知道在分页管理中， “页”（Page）和“块”（Block）是一样大小的， 这样才知道物理存储器是32K。 答案：逻辑地址有13位，物理地址有15位。 93 存储 管理 【例4-2】 在例1的基础上，若其页 表如右图所示，求逻辑 地址0A6D(16)，06637(8)的 物理地址分别为多少（ 用十六进制表示）？ 分页管理下的地址转换 方法（即块号取代页号 ，页内地址直接复制） 010 18 212 320 416 515 627 714 页号 块号 逻辑地址页号页内地址 所在块号 对应物理地址 0A6D(16)2(10)26D(16)12(10)326D(16) 06637(8)3(10)19F(16)20(10)519F(16) 94 存储 管理 分页系统地址转换过程 95 存储 管理 图4-13 分页式地址变换过程 96 存储 管理 5.内存的分配与回收 在页式存储方式中，由于内存块等长，故常用三种方式记录内存 物理页面空闲情况。 位示图 用一个二进制位（bit）表示内存中一个物理页面的状 态。规定其值为0时，表示该物理块空闲；其值为1时，表示该块被 占用。所有位组成字位映像图，见图。并设置一个计数器以记录系 统当前的空闲块数。 1111100011110001 0111100000001111 0000000001111110 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 n 块号=字号*字长+位号97 存储 管理 空闲页面表 系统将连续的 若干空闲页面作为一组登记在 空闲页面表中，如图。 起始块号 块数 5 2 10 5 20 15 50 1 空闲页面表 当作业申请x个内存页时， 可查找空闲页面表，从第 一表项开始查找，同时累 计空闲块数满x时分配给作 业，这样可以让作业在内 存中尽量占据连续的空间 。 回收时，系统将归还的空闲块按空闲块的编号插 入到空闲页面表中，若有相邻的空闲块还要合并 ，类似于可变分区方式下的空闲区管理。 98 存储 管理 空闲页面链表 将所有空闲页面组成一个链表，每 一个空闲页面设有指向下一个页面的指针，系统保 留空闲链表的头指针。作业请求分配时，系统就从 空闲链表头开始依次摘取若干页面给用户进程，回 收时，将归还的空闲块插入到表头即可。 freelist 99 存储 管理 图4-13 分页式地址变换过程 100 存储 管理 二、 快表 因为页表是存放在内存中的CPU要存取一个数据，需访问主 存两次。 第一次：访内存中的页