第三章 内存管理 - Part1

存储器的管理

  • 存储层次：寄存器-cache-主存-外存
  • 存储管理的基本目标：地址独立（程序地址与物理地址无关）、地址保护（程序之间不能访问）
  • 存储管理的核心问题：分配和回收
  • 地址变换：可执行文件生成中的链接技术、程序加载时的重定位技术，进程运行时硬件和软件的地址变换技术和机构。
  • 存储共享与保护：代码数据共享对地址空间的访问权限
  • 存储器扩充：存储器的逻辑组织和物理组织
  • 地址空间与存储空间
    • 地址空间（虚拟地址）：程序编译后限定于地址空间内，是逻辑地址的集合
    • 存储空间（物理地址）：主存存储单元相关，是物理地址的集合

单程序的内存管理

此情况下内存中只有操作系统和一个用户程序

  • 操作系统只占用固定空间
  • 用户程序永远从同一个地方开始运行，地址在运行前可以进行计算
  • 方法：
    • 静态地址翻译：在程序运行前计算出所用的物理地址（可以由程序加载器实现），且无需地址翻译，运行速度快
  • 缺点：
    • 比物理内存大的程序无法加载、运行
    • 不区分常用数据导致资源浪费

多程序的内存管理 - 分区式内存管理

  • 把内存分为相等或不等的分区，操作系统占用一个分区，每个程序占用一个/多个分区
  • 支持多程序并发执行，但难以进行内存分区的共享

静态式分区分配：程序适应分区

  • 存储空间被分为任意大小的区域，区域大小不能更改，每次获取一部分分区进行作业
  • 分区数据统计：分区表
  • 分区分配：以待分配程序构成的队列
    • 单队列：所有程序在一条队列中等待任意一个空白分区
    • 多队列：每个分区都有若干大小相近的程序等待
  • 优点：开销小，实现简单
  • 缺点：内碎片浪费、分区数目受限

静态式分区也被叫做固定式分区，其允许不同分区大小不同

动态式分区分配：分区适应程序

  • 分区的边界可以进行移动，即动态地改变分区大小，以适应程序需要
  • 优点：无内碎片
  • 缺点：有外碎片

可变分区分配（不常用）

  • 内存分配使用两张表：已分配分区表和未分配分区表；
    • 每张表单项为存储控制块MCB，分配了的即AMCB(allocated)，未分配即FMCB(free)
image-20230218150958760
  • 空闲分区中的一小部分作为存储控制块按次序形成FMCB链表结构；当分区被分配后，前后指针无意义
image-20230218151214857

系统中的碎片

内存中无法被利用的存储空间被称为碎片

  • 内部碎片：
    • 分区分配后，区块内没被使用的内存
    • 分区大小固定的存储管理方式均会出现内部碎片
    • 内部碎片无法整理，只能等待程序结束后释放整个分区，从而释放这些碎片
  • 外部碎片：
    • 系统无法利用的空闲分区、分区间存在的内存，空间小且不连续
    • 动态分区管理会产生外部碎片
    • 外部碎片是造成内存系统性能下降的主要原因，对分区进行紧凑处理可消除外部碎片

闲置空间的管理

操作系统跟踪内存的两种方法：位图表示法（分区表）、链表表示法（分区链表）

  • 位图表示法：给每个分区赋予一个字位，记录该单元是否闲置（例如取0代表闲置，取1代表占用）
    • 空间成本固定：仅依赖于内存分区数量，与程序数量无关
    • 时间成本低：直接对位图修改即可
    • 无容错能力：若位图因错误访问被更改，其本身不具有检错的能力
image-20230218145920225
  • 链表表示法：将给程序分配的单元按照位图的形式连接起来，再在不同程序间采用链表进行连接
    • 空间成本不定：取决于程序数量
    • 时间成本：链表遍历、修改、插入删除较慢
    • 有一定容错能力：链表有被占用的标志位，可以一定程度上互相验证
image-20230218150205665

分区分配操作

分配内存

  • 实现内存分配的流程：
    • 规定size为不再切割的剩余分区的大小、请求的分区大小为u.size，空闲分区的大小为m.size
    • 若m.size - u.size <= size，则将整个分区都分配给请求者（按最小单位也分不开了，就全给了吧）
    • 否则从该分区内划分一部分并进行分配，余下部分保留在空闲分区表/链表中
  • 流程图如下：
image-20230218151956700

回收内存

  • 回收分区上下紧邻空闲分区时，直接进行合并，合并后修改空闲分区表/链表中的首地址和大小
  • 回收分区不邻接空闲分区时，在空闲分区表/链表中新建表项，记录分区的首地址和大小

内存分配算法

  • 首次适应算法：按地址递增顺序从头查询，选择第一个空间符合要求的分区分配
    • 优先利用低地址的空闲分区，开始时查找简单，但易在低地址产生大量不能利用的碎片，增加了后续查找的开销
  • 下次适应算法：按地址递增顺序从上次分配的地址开始查询（到达最大值后循环），选择第一个符合要求的分区
    • 均匀利用所有分区，不会产生密集的碎片，但使得内存中不存在大空间的分区
  • 最佳适应算法：总寻找大小最接近作业所需区域的分区进行分配
    • 由于选取大小最接近的分区，划分后的碎片几乎没有办法应用，所以极易产生大量碎片
  • 最坏适应算法：只寻找最大的空白分区并进行分配
    • 内存中大空间的分区较难保留，大任务难处理，但碎片相对少

为了提高搜索空闲分区的速度，大中型系统使用基于索引搜索的动态分区分配算法

  • 快速适应算法：把空闲分区按照容量大小进行分类，根据程序所需找到能容纳它的最小的空闲区链表，取下第一块进行分配
    • 可以保留大的分区，也不会产生碎片；但归还内存时系统开销大

伙伴系统

伙伴系统是介于固定分区和可变分区间的动态分区方法

在分配存储块时将一个大块分裂成两个相同大小的小块（伙伴）

  • 伙伴系统内所有分区的大小都是$2^k$，其中$n\le k\le m$，$2^n$表示最小的分区大小，$2^m$表示整个可分配内存的大小
  • 在不断划分分区的过程中，可能形成若干个不连续的空闲分区
  • 内存管理模块包含多个空闲块链表，单个链表内部都指向相同大小的空分区
  • 内存分配时：程序提出一个$2^k$字节（应大于所需内存字节数，同时保证$k$最小）大小的申请，从链表中查找一个$2^{k+1}$字节大小的空分区，一半供给程序，另一半放入空闲块链表中
  • 内存回收时：考虑能否和伙伴块合并为一个更大的块，再递归此操作（注意不能和非伙伴块合并）
  • 特点：
    • 回收内存时只需要搜索一部分块（同大小的）进行查询
    • 会产生内部碎片
image-20230218212431919 image-20230218212528666

可重定位分区分配

定时地、或在内存紧张时，移动已分配区域的数据，把外部碎片和空白的分区合并为一个大的连续区域

  • 以时间换空间
  • 对系统的性能开销要求大

程序的链接和装入

一个用户源程序在内存中通常需要如下处理：

  • 编译：使用编译程序将源程序编译成若干个模块
  • 链接：将目标模块和使用的库函数链接成可装载模块（可执行文件）
  • 装入：将可装载模块装入内存空间

程序的链接

系统编译C程序时，是以.c文件作为编译单元的，每个文件都会生成一个.o文件，但这些文件无法知晓地址

链接则是将这些.o文件组合到一起，形成最终的可执行文件，并将未填写的地址补充（重定位），组合的本质是将相同的程序段段合并到一起

image-20230219202217260
  • 重定位：在符号解析基础上将有关联的模块合并，确定符号在虚拟地址空间中的地址，在符号的引用处重定位引用的地址；总的来说就是把和地址跳转相关的数值/地址值全部修改成能保证运行时地址正确的值
typedef struct {
	Elf32_Addr r_offset;
    						/* 给出了使用重定位的地址地点*/
    Elf32_Word r_info;(symbol:24; type:8)
    						/* 给出了与修改地点相关的符号表索引和重定位类型*/
} Elf32_Rel;

对于使用重定位动作的地点：

  • 重定位文件：从节起始处到收重定位影响的存储单元的字节偏移量

  • 可执行文件、共享目标文件：受重定位影响的存储单元的虚拟地址

  • 一个源程序可以采用静态链接或动态链接的方式完成链接这一操作

  • 静态链接：把共享库代码直接链接入程序代码时使用静态链接

  • 动态链接：仅当需要某些目标模块时才进行链接工作，节省内存但速度较慢

程序的装入

程序一般采用动态运行时装入方式

  • 程序在内存中的物理位置（绝对地址）会根据系统需求发生改变，为了保证能够便捷更改位置，装入程序在程序运行时才把相对地址转换为绝对地址（需要一个重定位寄存器支持这个功能）
  • 名空间、地址空间与存储空间：
    • 名空间：包括符号指令、数据说明、I/O说明
    • 地址空间：从0开始，到程序结束的一段空间
    • 存储空间：从装入地址开始到程序结束的一段空间
  • 多重分区分配：一个作业常由多段相对独立的程序、数据段组成，把这些片段分别装入存储空间的不同区域的过程被称为多重分区分配

程序段

一个程序本质上是由.bss段、.data段、.text段三部分组成的

一个装入内存的程序还需要一个stack和一个heap

  • bss段：程序中未初始化的全局变量的存放空间，采用静态内存分配
  • data段：已初始化的全局变量（和static修饰的变量）的存放空间，采用静态内存分配
  • text段：存放程序代码的一段空间，大小确定，大多为只读（可能包含只读常量）

这三部分中，.data和.text从可执行文件中加载到内存中，.bss段由系统进行初始化

  • 程序段内存示意图：
image-20230218230855885
  • stack段：存放、交换临时数据的区域；用于临时存放函数中的局部变量、保存或恢复函数现场
  • heap段：存放进程中动态分配的内存段；大小并不固定，使用malloc或free等函数时内存变动都在heap上进行

gcc编译+链接时使用的工具：

  • 预处理器+编译器：cc1
  • 汇编器：as
  • 链接器：collect2

程序的装载与运行

程序的装载

  • 装载前调用fork()，创建子进程
  • 该子进程调用execve()加载需要执行的程序
  • 加载器查询ELF文件中与segment相关的信息，其中Type为Load的segment是需要被加载到内存中的
  • segment在文件中的大小小于在内存中的大小，如果出现此种情况在载入内存时需要补零使其达到内存所占用的大小

程序的装载流程

  • 读取ELF文件的开头魔数进行比对
  • 根据ELF文件中的段表信息（起始位置在文件中偏移、段表大小、包含了多少项）找到段表项
  • 解析各段应当被加载的虚地址、文件中的偏移、内存中/文件中的大小
  • 根据段在内存中的大小分配物理页并映射到虚地址上，并拷贝文件至内存中
  • 设置进程块中PC为ELF记录的入口地址，进程开始执行

可执行文件的内存映像（x86）

image-20230219212547198

程序、进程和作业

  • 程序是静态的可执行文件，存放在磁盘上
  • 进程是动态的，是程序的执行过程、用户分配资源的基本单位；进程可以创建其他的进程
    • 系统进程：完成操作系统功能的进程
    • 用户进程：完成用户功能的进程
  • 作业是用户要求计算机完成工作的集合；一个作业由至少一个进程构成
    • 作业常用于批处理系统，进程常用于分时系统、多道程序系统
作业 - 若干进程 - 程序 + 数据集合 + 进程控制块