第五章 存储管理 2006年11月

存储管理 外存，内存，缓存 逻辑地址和物理地址 重定位 静态重定位和动态重定位 覆盖（overlay） 固定分区管理 可变分区管理 存储器的层次(3级存储器结构) 外存，内存，缓存 存储管理的基本概念 逻辑地址和物理地址 重定位 静态重定位和动态重定位 覆盖（overlay） 存储器的分区管理 固定分区管理 可变分区管理

存储管理 可变分区管理的三个策略 最先适应法FF 最佳适应法BF 最坏适应法WF 存储器的分页管理 存储器的分段管理 存储器的段页式管理

逻辑地址与物理地址 空闲区 100 进程 10100 进程 逻辑地址 (0 to max) 10000 操作系统 物理地址 (内存)

存储管理 系统占用区 由于操作系统自身需要占用主存的一部分空间用来存放操作系统的程序、数据、管理信息以及接口信息等，把这部分空间称为系统占用区。 用户区 其余的主存空间可用来存放用户的程序和数据，存储管理是针对主存储器中供用户使用的区域进行管理。

存储管理的基本概念

存储管理的基本概念 存储管理、存储管理的功能 逻辑地址和物理地址 重定位 静态重定位和动态重定位 覆盖（overlay）

存储管理 在单道程序系统中，内存一次只调入一个用户进程，且该进程占用剩余的存储空间，存储管理只是分配和回收内存区。 在多道程序系统中，多个作业同时装入内存，因而对存储管理提出了一系列要求： 如何有效的将内存分配给多个作业 如何共享和保护 要提高存储资源的利用率，同时又要方便用户使用 因此提出存储管理的四个功能

存储管理的功能（四个） 1. 主存空间的分配和回收 2. 重定位(地址转换、地址映射或映像) 记载每个内存单元的使用状况（占用或是空闲） 当有存储申请时，根据需要选定分配区进行分配 当程序不再使用已分配的区域，及时收回，置为空闲，供下次分配使用 内存分配分为静态分配和动态分配 2. 重定位(地址转换、地址映射或映像) 当内存分配确定后，需要把程序的逻辑地址转换成物理地址，这个变换过程称为重定向（重定位） 分为静态重定向和动态重定向

存储管理的功能（四个） 3. 主存空间的共享和保护 4. 主存空间的扩充 共享主存储器（多道作业共享） 共享主存储器的某些区域（如：调用编译程序） 为防止各存储区中的程序相互干扰，必须对它们采取保护措施，称为存储保护 4. 主存空间的扩充 内存容量是受实际单元所限制 扩充不是增加实际的存储单元 而是采用覆盖、交换、虚拟存储技术来实现在有限内存容量下，可执行比内存容量大的程序，或者在内存中调入尽可能多的程序

物理地址 物理地址（绝对地址） 主存储器的存储单元以字节为单位，每个存储单元都有一个地址与其对应，把主存空间的地址编号称为“物理地址” 由“物理地址”对应的主存空间称为“物理地址空间”

逻辑地址 逻辑地址（虚拟地址） 用户不能预先知道程序将被存入主存的实际位置，这样用户编制程序就不能使用绝对地址。 为方便用户，每个用户都认为自己作业的程序和数据存放在一组从“0”地址开始的连续空间中，把用户程序中使用的地址称为“逻辑地址” 对应的存储空间为“逻辑地址空间”

逻辑地址 n 从逻辑角度 看内存 5 4 3 2 1 字节 逻辑地址

重定位 静态重定位 在装入一个作业时，把作业的指令地址和数据地址全部转换成物理地址 地址转换工作是在作业执行前集中一次完成的 作业执行过程中就无需再进行地址转换工作

静态重定位 静态重定位的优点 静态重定位的缺点 无需增加地址转换机构 程序的存储空间是连续的一片区域，在执行期间不能移动，不能实现重新分配内存，不利于内存的利用 用户必须事先确定所需的存储量，若所需的存储量超过可用存储空间时，必须采用覆盖技术 每个用户进程难以共享内存的同一程序副本

动态重定位 动态重定位 动态重定位是由软件和硬件相互配合完成 硬件设置一个基址寄存器 存储管理为作业分配一个主存区域后，程序原封不动的把作业装入到所分配的区域中 把该主存区域的起始地址存入基址寄存器 作业执行过程中，由硬件的地址转换机构动态进行地址转换，执行指令时把逻辑地址与基址寄存器的起始地址相加即得到物理地址

动态重定位 进程 未分配的 基址 寄存器 10000 100 10100 70 10070 + 用户空间 物理 逻辑 地址 地址 10000 系统空间

动态重定位 动态重定位的优点 动态重定位的缺点 内存的使用更加灵活有效 几个作业共享一程序段的单个副本比较容易 可能向用户提供一个比内存空间更大的地址空间 无需用户干预，由系统负责全部的存储管理 动态重定位的缺点 需要附加硬件支持 实现存储管理的软件比较复杂

两个重定位方式的区别 静态重定位 动态重定位 装入主存储器的作业已经都是用物理地址指示 作业执行过程中不能移动位置 装入主存的作业仍保持原来的逻辑地址 必要时可以改变作业在主存中的存放区域(即改起始地址) 当作业被移到一个新区域后，只要改变基址寄存器中的内容为新区域的起始地址值 作业执行过程中，把逻辑地址与基址寄存器新的起始地址相加重新获得物理地址，作业仍可正确执行

覆盖技术 覆盖思想 任何时候只在内存中保留所需的指令和数据 当需要其他指令时，它们会装入到刚刚不需要的指令所占用的内存空间 覆盖是在程序运行过程中，把同一存储区在不同时刻分配给不同的程序段或数据段来共享的一种存储分配技术。 使用覆盖技术后，可以使一个进程大于它所分配到的内存空间 参看P142的例子

覆盖技术 缺点：是程序员必须小心地设计程序及其数据结构，使得要覆盖的段块具有相对独立性，不存在直接联系或相互交叉访问。 符号表 公共例程 覆盖区 公共例程 OS(32K) pass1 覆盖驱动程序 pass2

交换技术（ P142 ） 交换是指将一个进程从内存拷贝到磁盘（外存）上，以腾出空间给其他进程使用，需要时，再将该进程调入内存。 交换进程由换出和换进两个过程组成。 换出是把内存中的数据和程序换到外存的交换区，而换进则是把外存交换区中的数据和程序换到内存的分区中。 缺点：在交换系统中，交换所占用的时间相当多。

交换技术（ P142 ） 用户空间 换出 P1 P2 换入 系统空间 内存空间

两者区别 交换主要是在进程或作业之间进行的 覆盖主要是在同一个作业或进程中进行 只能覆盖与覆盖程序段无关的程序段

存储分配——连续内存分配 固定分区法 可变分区法

内存分配 最为简单的内存分配方法之一就是将内存分为多个固定大小相同或者不同的分区，一旦划分好，内存中分区的个数就固定了(固定分区)。 更为普通的方法是将内存根据进程大小划分，分区数目是可变化的是不可预知的(可变分区)。 采用连续内存分配方式，每个进程都占有一段连续的地址空间

连续分配图 logical view of memory

非连续分配图 logical view of memory

固定分区法(P138) 固定分区的基本思想 固定分区把内存划分为若干个大小不等的分区，分区大小、总数在系统初始建立，系统运行过程，它们是固定不变的。 固定分区管理通过“分区说明表”实现 固定分区管理的分配策略：依次查找分区说明表中的各个表目，将分区大小满足作业请求容量并且使用状态为空闲的第一个分区分配给该作业，作业运行完后，将释放的分区收回，状态设置为空闲

固定分区法 1000k 0k 1 8k 2 16k 1008k 3 32k 1024k 内碎片 分区(分配)说明表 1056 1024 区号 分区大小 起始地址 使用状态 1000k 0k 1 8k 2 16k 1008k 3 32k 1024k 作业B （28k） 剩余4k 3分区 1024 空闲 16k 2分区 1008 作业A （6K） 剩余2k 1分区 1000 OS 0分区 如果还有一个进程20K准备进入内存却无法进入，从而产生外碎片

固定分区算法 固定分区的特点 能使多个进程共享内存 具有数据结构简单 分配、回收容易实现 存在小作业占据大分区 造成内存浪费的碎片现象 OS process 固定分区的特点 能使多个进程共享内存 具有数据结构简单 分配、回收容易实现 存在小作业占据大分区 造成内存浪费的碎片现象 可调入内存的进程大小受到分区大小的限制 现在一般不再使用的技术

可变分区 可变分区的基本思想 可变分区又叫“动态分区” 可变分区存储管理不是预先把主存储器中的用户区域划成分区，而是在系统运行时，当作业要求装入主存储器时动态划分 根据作业需要的主存空间的大小和当时主存空间使用情况来决定是否为作业分配一个分区

可变分区 Vs 固定分区 分区建立时刻：可变分区的分区建立不是在系统初启时，而是在系统运行过程中，在作业装入时动态建立 可变分区与固定分区的不同 分区建立时刻：可变分区的分区建立不是在系统初启时，而是在系统运行过程中，在作业装入时动态建立 分区的大小：不是事先预定的，而是根据作业对内存的需求量而分配的 分配的个数：是变化不定的

可变分区的三个策略 最先适应法FF (first-fit) 找到第一个大于或等于作业需求量的空闲区并为其分配 最佳适应法BF (best-fit) 找到一个大于或等于作业需求量的“最小空闲区” 结果产生最小的剩余空间 需要扫描所有的空闲区 最坏适应法WF (worst-fit) 总是把最大的空闲区分配给作业 结果产生最大的剩余空间，以备分配给其他进程

可变分区 初始空闲区 假设进程0时刻到达 采用FCFS进程调度算法 作业队列 P1 600K 10 P2 1000K 5 未分配的 2160K 初始空闲区 (CPU time) 假设进程0时刻到达 采用FCFS进程调度算法 操作系统 400K

可变分区 作业队列 为进程P1,P2,P3分配空间 剩余260K空间未分配 P1 600K 10 P2 1000K 5 P3 300K 20 空闲区 260K P3 300K P2 1000K P1 600K 为进程P1,P2,P3分配空间 剩余260K空间未分配 OS 400K

可变分区 作业队列 P2 进程结束, 释放空间1000K P1 600K 10 P2 1000K 5 P3 300K 20 空闲区 260K P3 300K 1000K 空闲区 P1 600K P2 进程结束, 释放空间1000K OS 400K

可变分区 作业队列 P4 进程开始,需要空间700K 剩余300K + 260K 未分配， 但不足够大, P5不能开始执行 空闲区 260K P3 300K 300K 空闲区 P4 700K P1 600K P4 进程开始,需要空间700K 剩余300K + 260K 未分配， 但不足够大, P5不能开始执行 OS 400K

可变分区 作业队列 P1进程结束,释放空间600K P1 600K 10 P2 1000K 5 P3 300K 20 P4 700K 8 空闲区 260K P3 300K 300K 空闲区 P4 700K 600K P1进程结束,释放空间600K 空闲区 OS 400K

可变分区 作业队列 P5进程开始执行, 分配空间500K P1 600K 10 P2 1000K 5 P3 300K 20 空闲区 260K P3 300K 300K 空闲区 P4 700K 空闲区 P5进程开始执行, 分配空间500K 100K P5 500K OS 400K

可变分区 作业队列 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ P1 600K 10 空闲区 260K P3 300K 300K 空闲区 P4 700K 空闲区 100K P5 500K 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ OS 400K

FF算法 作业队列 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ P1 600K 10 空闲区 260K P3 300K 空闲区 45K P7 255K P4 700K 空闲区 P6 (1K) P6 99K P5 500K 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ OS 400K

FF算法 作业队列 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ P1 600K 10 空闲区 P7 P3 300K 300K 空闲区 P4 700K 空闲区 P6 P5 500K 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ OS 400K

WF算法 作业队列 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ P1 600K 10 空闲区 P7 P3 300K P6 空闲区 P4 700K 空闲区 100K P5 500K 思考：如果进程P6和P7准备进入内存，则分别按照上面所说的三种策略该如何分配？ OS 400K

可变分区 当前内存有两个空闲区域F1（100K）和F2（50K），分别按照WF，BF，FF分配策略，看看结果如何？ 作业队列 P1 30K 10 P2 70K 5 P3 50K 20 100K F1（100K） 50K F2（50K） 当前内存有两个空闲区域F1（100K）和F2（50K），分别按照WF，BF，FF分配策略，看看结果如何？ OS 400K

可变分区—FF策略 作业队列 按照FF分配策略，结果只有P1和P2进程可以装入内存。 P1 30K 10 P2 70K 5 F1（100K） P1（30K） F2（50K） 按照FF分配策略，结果只有P1和P2进程可以装入内存。 OS 400K

可变分区—WF策略 作业队列 按照WF分配策略，结果所有的作业都可以装入内存。 P1 30K 10 P2 70K 5 P3 50K 20 F1（100K） P3（50K） F2（50K） 按照WF分配策略，结果所有的作业都可以装入内存。 OS 400K

可变分区—BF策略 作业队列 按照BF分配策略，结果P3作业不能装入内存。 结论：不是WF就一定是最坏的，BF就一定是最佳的。 P1 30K 10 P2 70K 5 P3 50K 20 P2(70K) F1（100K） 30K 按照BF分配策略，结果P3作业不能装入内存。 P1(30K) F2（50K） 20K OS 400K 结论：不是WF就一定是最坏的，BF就一定是最佳的。

固定分区总结 每个分区只能装入一个作业 当装入一个小于分区的作业，则剩余的空间只能作为内碎片而不能使用 当有一块剩余的空闲区不足够大到可以装入一个正在等待进入内存的作业，则这块空闲区也只能作为外碎片而不能使用

固定分区总结 作业在执行的过程中不会改变存放区域，作业采用静态重定位的方式把作业装入到所分配的分区中。 从上分析可知，为了获得更好的内存利用率，产生了可变分区管理方案

可变分区总结 每个分区能装入多个作业 随着进程装入和移出内存，自由内存空间被分为小片段，当所有剩余的总的内存之和可以满足请求，但由于不连续不能分配时，就出现了外碎片的问题。 可以考虑采用移动（紧缩）技术来合并剩余的空间，但要付出相应系统开销的代价

紧凑合并、移动思想 260K 660K P3 300K 300K P3 300K P4 700K P4 700K 100K P5 500K OS 400K OS 400K

可变分区总结 从上述分析可以看出，可变分区通常采用动态重定位的方式把作业装入到所分配的分区中。 为了获得更好的内存利用率，产生了不连续的分区管理方案，如分页，分段，段页式等

存储管理——分页 （非连续的分配方式）

连续分配 Vs非连续分配 采用连续分配方式，一个进程必须占用一段连续的内存空间 采用非连续的分配方式时，当前内存只要有空闲区，一个进程可以分页或者分段的被分配进入内存 采用非连续的分配方式，可以解决外碎片问题

分页管理的基本思想 把作业的虚拟空间（逻辑空间）划分成若干个大小相同（相等）的块，称为页 与此相对应，把物理内存空间也划分成与页大小相同（相等）的若干块，称为帧 在进行内存分配时，总是以块为单位进行分配，但分配给作业的主存块可以不连续，即作业可以按页分散存放在主存的空闲帧中。即采用“见缝插针”方法，避免了为得到连续存储空间而进行的移动。 不存在外碎片问题，最多存在比帧更小的内碎片

逻辑内存与物理内存的分页模型 页表 页(或者帧)的大小一般在1K～4K page 0 page 2 page 1 page 3 1 2 3 帧号 page 0 page 2 page 1 page 3 1 2 3 4 5 6 7 8 9 page 0 page 1 page 2 page 3 1 4 3 7 1 2 3 页表 (页号与帧号的对应关系表) 逻辑内存 物理内存 页(或者帧)的大小一般在1K～4K

地址转换的一个例子 页表 page 0 page 2 page 1 page 3 1 2 3 4 5 6 7 8 9 1 4 3 7 1 2 1 2 3 4 5 6 7 8 9 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 4 5 6 7 a b c d 0 a b c d e f g h i j k l m n o p 12 13 14 15 i j k l 1 4 3 7 1 2 3 16 17 18 19 e f g h 28 29 30 31 m n o p 页表 每页大小为4B，总共16B，分成4页 逻辑内存16B 物理内存40B

地址转换的计算原理 如上例逻辑地址空间为2m(如16B，m=4)，且页的大小为2n(如4B，n=2)，那么逻辑地址的高“m-n” 位(4-2=2)表示页号，而低“n”(n=2)位表示页偏移。 逻辑地址分成两部分，一个页号和一个页偏移 页号 页偏移 2m= 2m-n * 2n p d 逻辑 空间 页数 页大小 m-n n

地址转换的计算原理 通过上述分析，地址转换只需要知道逻辑地址从而获得页号和页偏移，然后查找对应页表，就可以计算物理地址 在“页表”中，通过页号找到该页在物理内存对应的帧号，然后根据页偏移和每页大小就可以计算物理地址为 物理地址=帧号*块长+页偏移

分页 物理地址 进程 页号 偏移 帧号 偏移 逻辑内存 物理内存 页表

分页的一个例子 进程大小 16B,物理内存: 32B 页（帧）大小: 4B 则进程有4页，物理内存有8帧 逻辑地址5所对应的物理地址是多少？

分页的一个例子 逻辑地址 5 在第1页, 偏移地址是 1 5/4 = 1（页号） … 5 mod 4= 1（页偏移） 根据页表可知，第1页对应的帧号是4 第4帧的起始地址是 4 * 4 = 16 帧的起始地址=帧号*每帧大小 最后物理地址： 16 + 1 = 17

分页的例子 页表 5 17 frame process page 4 1 4 3 7 1 2 3 1 8 1 2 8 12 2 3 12 3 process page 4 1 4 3 7 1 2 3 1 5 8 1 2 8 12 2 3 12 3 页表 17 4 15 20 5 逻辑内存 6 (frames 1, 3, 4, 7 are free, frames 0, 2, 5, 6 are taken by another process) 7 31 物理内存

分页的总结 分页管理消除了外碎片 但是存在不可避免的内碎片问题 作业的大小不一定都是页大小的倍数，则总有进程需要n页再多一些，那么内存分配时就必须分配n+1页的空间，则导致内碎片 最坏的时候需要n页加一个字节，相当几乎产生了整个帧的内碎片 所以页大小的设置会影响内存使用率

分页 – 页表的特点 操作系统为每个进程设置一个页表 对一个很大的进程，该进程对应的页表也相应较大，需要较大的内存空间，影响查找页表时的速度 在计算物理地址时，首先要读取页表信息 为了使页表相对小些，也就考虑增大页块的大小，从而减少页的数目，而缩减页表。

分页 – 用户的观点 用户程序将内存作为一整块来处理，而且它只包括一个进程 事实上，一个用户程序与其它程序一起，分布在物理内存上。 分页的一个重要特点是用户观点的内存和实际的物理内存分离 用户程序将内存作为一整块来处理，而且它只包括一个进程 事实上，一个用户程序与其它程序一起，分布在物理内存上。 从逻辑地址到物理地址的映射转换是由操作系统控制的，对用户来说是隐藏的，看不到的

分页 – 帧表 操作系统也必须提供一个帧表并对其管理 帧表需要记录每个帧的使用情况（是空闲的还是已分配），如果分配了，是分配给哪个进程的哪一页？

共享页 假设当前系统支持让40个用户同时执行文本编辑器（如Unix操作系统） 系统只需要在物理内存中存放一个文本编辑器的副本，以供多个用户同时使用 做一个简单的例子，假设文本编辑器进程需要3页 (如code 1, code 2, code 3 in next slide) 每个用户进程都有自己处理的数据，占1页 每个用户编辑的数据不同

共享页的一个例子 页表 进程 1 1 2 data 1 3 4 data 3 5 6 code 1 7 8 code 2 9 进程 2 10 1 2 3 4 5 6 7 8 9 10 11 data 1 data 3 code 1 code 2 code 3 data 2 3 4 6 1 进程 2 code 1 code 2 code 3 data 2 3 4 6 7 进程 3 code 1 code 2 code 3 data 3 3 4 6 2 页表 物理地址 逻辑地址

存储管理——分段式存储管理

分段存储管理的基本思想 用户希望把一个作业分成若干段 如主程序段、若干子程序段、数据段 每一段都有独立的逻辑意义，可独立编程，且每段的长度不一定相等。 段式存储管理支持用户的分段观点 以段为单位进行存储空间的管理 每段的逻辑地址都从“0”开始 段内地址连续，而段与段之间的地址是不连续的

分段式存储管理——地址转换 100 450 1000 2000 200 500 5500 段2 Y 段0 段3 段1

分段存储管理——地址转换 地址转换——动态重定位方式 段的分配同可变分区方式，根据段长找到可以容纳该段的空闲区 段表记录段的分配信息，段长和段的起始地址 段的逻辑地址由两个元素组成 <段号，段偏移>

分段存储管理——地址转换 段的逻辑地址到物理地址转换方法 查段表，根据逻辑段号得到该段在主存的起始地址 起始地址加上段内偏移地址就是物理地址 物理地址=段的起始地址+段的偏移地址

段页式存储管理的基本思想 段式存储管理的致命弱点，即每段必须占据主存储器的连续区域 为了克服这个缺点，可采用分段和分页的方法，构成段页式存储管理 用户对作业仍采用分段组织，每段独立编程

段页式存储管理的基本思想 操作系统分配主存空间时，不是把每一段按单一的连续整体存放到主存储器中 而是把每段分成若干页，每一段不必占据连续的主存空间 可把它按页存放在不连续的主存块中

段页式存储管理的模型

段页式存储管理的地址转换 1 2 4 3 14 7 30

总结 存储管理的背景 地址绑定，动态加载，动态链接，覆盖 交换 连续分配 固定大小分配，可变大小分配，碎片 非连续分配 分页，分段，段页式