内存管理概念

内存管理

内存管理（Memory Management） 是操作系统对 主存（内存） 进行统一管理的过程，其核心任务是：

为进程分配运行所需的内存空间，并负责回收、保护和管理这些空间。

例如，一个程序从磁盘启动时，操作系统需要：

1. 为程序分配一块内存空间；
2. 将程序代码、数据等装入内存；
3. 建立程序运行所需的地址映射关系；
4. 程序结束后回收所占用的内存空间。

随着多道程序设计的发展，内存管理不仅要解决 “有没有地方放” 的问题，还需要解决：

• 如何让多个进程同时共享有限的内存；
• 如何保证进程之间互不干扰（内存保护）；
• 如何提高内存利用率，减少碎片；
• 如何让程序认为自己拥有连续且足够大的内存空间（虚拟内存）。

因此，内存管理的核心就是：如何高效、安全地为进程组织和管理运行时所需的内存空间。

管理方式分类

操作系统中的各种内存管理方式并不是相互独立、一次性设计出来的，而是随着 多道程序设计、存储器容量和硬件地址转换能力的发展，逐步演进形成的。

其基本发展脉络可以概括为：

整个演进过程主要围绕两个目标展开：

1. 提高内存利用率

   • 允许更多程序同时驻留内存；
   • 减少内部碎片和外部碎片；
   • 允许进程离散地使用物理内存。

2. 增强内存管理能力

   • 实现进程隔离和内存保护；
   • 支持程序代码和数据的共享；
   • 保留程序本身的逻辑结构；
   • 支持虚拟内存。

从内存是否必须连续分配的角度看，内存管理方式大体可以分为两类：连续分配 和 离散分配。

所谓 连续分配，是指操作系统必须为一个进程分配一整段连续的内存区域。这类方式实现简单、地址转换开销较小，但灵活性不足。典型方式包括：

• 单一连续分配；
• 固定分区分配；
• 动态分区分配。

相比之下，离散分配 允许一个进程占用的物理内存空间彼此不连续，从而提高内存利用率和分配灵活性。典型方式包括：

• 页式管理；
• 段式管理；
• 段页式管理。

后文将沿着上述发展脉络，具体介绍各种内存管理方式的基本思想、解决的问题以及自身的局限性。

连续分配管理

连续分配（Contiguous Allocation） 是指：操作系统为每个进程分配一块连续的物理内存空间，进程在内存中的所有代码、数据、堆、栈等都必须存放在这一连续区域内。

由于整个进程必须连续存放，因此操作系统需要负责为进程寻找足够大的连续空闲区域，并维护这些空闲区域的分配和回收情况。

单一连续分配

在单一连续分配方式下，内存被划分为 系统区 和 用户区。

系统区供操作系统使用，用户区只装入一道用户程序，即整个用户内存空间都由该程序独占。系统区具体位于高地址还是低地址，取决于处理器和操作系统的设计。

单一连续分配是最早期、最简单的内存管理方式，适用于一次只运行一道用户程序的系统。

这种方式的优点包括：

• 实现简单；
• 管理开销小；
• 不会因为多个用户进程交替装入和退出而形成外部碎片。

其主要缺点包括：

• 一次只能运行一道用户程序；
• 当程序等待 I/O 时，CPU 可能长期空闲；
• 内存中未被当前程序使用的部分也无法供其他程序使用；
• CPU 利用率、内存利用率和系统吞吐量都很低。

单一连续分配的根本问题在于，它无法支持 多道程序并发驻留内存。

为了让一个程序等待 I/O 时，CPU 能够转而执行其他程序，操作系统开始在内存中同时保存多道程序，由此发展出了 固定分区分配。

固定分区分配

固定分区分配是最简单的一种 多道程序存储管理 方式。

它在系统启动或初始化时，将用户内存空间预先划分为若干个大小固定的分区，每个分区最多装入一道作业。

当存在空闲分区时，操作系统可以从外存的后备作业队列中选择一个能够放入该分区的作业，将其装入内存。这样，内存中便可以同时驻留多道程序。

固定分区可以采用两种划分方式：

• 分区大小相等：实现简单，但难以适应大小不同的程序；
• 分区大小不等：可以为不同大小的程序提供更多选择，但管理稍复杂。

为了方便管理，操作系统通常为固定分区建立一张 分区说明表。表中记录每个分区的：

• 起始地址；
• 分区大小；
• 当前状态；
• 已装入的作业或进程。

当有用户程序需要装入时，操作系统检索分区说明表，选择一个能够容纳该程序的空闲分区，并将其状态修改为“已分配”。

如果所有合适的分区都已被占用，即使内存中其他较小分区仍然空闲，该程序也无法装入。

固定分区分配首次实现了多道程序同时驻留内存，提高了 CPU 利用率和系统吞吐量，但它仍然存在明显问题：

1. 分区数量固定

   • 内存中能够同时驻留的进程数量受到分区数量限制。

2. 分区大小固定

   • 程序可能无法装入任何一个分区；
   • 较小的程序装入较大的分区时，会浪费分区内部的空间。

分区内部已经分配给某个进程、但没有被该进程实际使用的空间，称为 内部碎片。

固定分区的根本矛盾是：

分区大小是静态的，而程序所需内存大小是动态的。

为了解决固定分区尺寸僵化和内部碎片严重的问题，操作系统进一步提出了 动态分区分配。

动态分区分配

在 固定分区分配 中，用户内存被预先划分为若干大小固定的分区。

这种方式实现简单，但由于分区大小固定，而程序需要的内存大小各不相同，因此容易产生大量内部碎片。

为了解决固定分区“尺寸僵化、内存利用率低”的问题，操作系统引入了 动态分区分配。

动态分区分配的基本思想是：

不再预先划分固定大小的分区，而是在程序装入时，根据程序的实际需要，从空闲内存中动态划出一块大小合适的连续区域。

当进程请求内存时，操作系统从当前的空闲内存中划出一块连续区域分配给该进程。

当进程结束或主动释放内存时，该区域重新成为空闲内存，可供后续进程再次使用。

通过这种动态、按需分配的方式，内存可以从逻辑上划分为两类区域：

• 已分配区：正在被操作系统内核或进程占用的内存；
• 空闲区：当前尚未分配、可供后续进程使用的内存。

如下图所示，其中 内核内存（kernel memory） 和 进程内存（process memory） 属于已分配区域，其余部分为系统当前的空闲内存。

为了管理这些不断变化的空闲区域，操作系统通常维护一张 空闲分区表 或 空闲分区链表，用于记录每一块空闲内存的：

• 起始地址；
• 分区大小。

示意如下：

当进程申请内存时，操作系统会遍历空闲分区表，按照预定的 适应算法，例如首次适应、最佳适应等，从中选择一块满足需求的空闲区域，并完成内存分配。

不同适应算法选择空闲分区的方式不同，会影响查找效率、剩余空闲块的分布以及外部碎片的产生情况。

内存碎片

动态分区分配相比固定分区分配，可以根据进程的实际大小分配空间，因此大幅减少了固定分区中的内部碎片。

但是，它仍然无法避免 外部碎片。

下图以一个实例说明动态分区分配过程中内存碎片的产生过程：

由于各进程所需的内存大小不同，并且进程会不断装入和退出，因此内存中会逐渐形成许多彼此分散的小型空闲区域。

这些空闲区域虽然没有被任何进程占用，但由于它们彼此不连续，可能无法合并成一块足够大的连续空间。

所谓 外部碎片，是指位于已分配分区之间、不能满足当前连续内存申请的零散空闲空间。

例如，假设系统中存在三块空闲区域：

10 MB、20 MB、15 MB

此时空闲内存总量为 45 MB，但如果某个进程需要申请一块连续的 30 MB 内存，分配仍然会失败，因为不存在一块大小至少为 30 MB 的连续空闲区域。

因此，外部碎片的关键并不是空闲内存总量不足，而是：

空闲内存过于零散，不存在足够大的连续空间。

可以通过 紧凑（Compaction） 技术移动已分配分区，将零散的空闲空间合并为一块较大的连续区域。

但是，紧凑需要移动大量内存数据，并修改相关地址，执行开销很高，而且要求程序能够进行动态重定位，因此并不是一种理想的根本解决方案。

动态分区的根本局限是：每个进程仍然必须占据一块连续的物理内存。

为彻底摆脱连续物理分配的限制，操作系统后来引入了 离散分配管理，允许一个进程的数据分散存放在多个不连续的物理区域中。

适应算法

内存空间中的空闲区域可能大小不一，并且分布在不同位置，操作系统使用 空闲分区表 或 空闲分区链表 记录这些空闲区域。

当进程申请一块新的连续内存时，操作系统必须从现有空闲区域中选择一块进行分配。

动态分区常见的分配策略主要包含四种：

• 首次适应（First Fit）
• 临近适应（Next Fit）
• 最佳适应（Best Fit）
• 最坏适应（Worst Fit）

• First Fit （首次适应）：从空闲分区表或空闲链表的开头开始查找，找到 第一个大小足以满足请求的空闲分区，将其分配给进程。

• Next Fit （临近适应）：从 上一次查找结束位置的下一个位置 开始查找，找到第一个大小足以满足请求的空闲分区。如果到达表尾仍未找到，则从表头继续循环查找，直到找到合适分区或者完整遍历一轮。

• Best Fit （最佳适应）：遍历全部空闲分区，在所有能够满足请求的分区中，选择 大小最小的空闲分区。对于本次请求而言，该分区的利用率最高，分配后剩余空间最小。

• Worst Fit （最坏适应）：遍历全部空闲分区，在所有能够满足请求的分区中，选择 大小最大的空闲分区。对于本次请求而言，该分区的利用率最低，但分配后剩余的空闲块通常仍然较大。

假设进程申请的内存大小为 $P$ ，空闲分区大小为 $F$ ，且 $F\ge P$ ，则该分区对于本次分配的利用率可以表示为：

• $F$ 越接近 $P$ ，利用率越高；
• $F$ 越大，利用率越低。

因此：

• 最佳适应选择满足条件的最小空闲块，即利用率最高的空闲块；
• 最坏适应选择满足条件的最大空闲块，即利用率最低的空闲块。

举个例子，假设空闲块序列为：

[8, 22, 20, 14, 10, 24]

进程请求大小为：

P = 16

四种分配算法会得到不同结果：

四种适应算法在该例子中的对比如下：

各算法的典型特点如下：

当动态分区中的某块内存被释放时，操作系统需要检查释放分区的前后是否存在相邻的空闲分区，并尽可能完成合并。

根据相邻情况，可以分为四种情况：

1. 前后都不是空闲分区
   • 将释放分区作为新的独立空闲分区插入空闲分区表。
2. 前面是空闲分区
   • 将释放分区与前面的空闲分区合并；
   • 前面空闲分区的起始地址不变；
   • 增大其分区大小。
3. 后面是空闲分区
   • 将释放分区与后面的空闲分区合并；
   • 合并后起始地址修改为释放分区的起始地址；
   • 增大分区大小。
4. 前后都是空闲分区
   • 将前方空闲分区、释放分区和后方空闲分区合并为一块；
   • 删除其中多余的空闲分区表项。

合并相邻空闲分区可以减少外部碎片，但无法从根本上消除动态分区必须连续分配的问题。

堆内存分配

动态分区分配最初用于操作系统直接在物理内存中，为进程划分连续空间。

随着分页和虚拟内存的引入，进程不再需要占据一整块连续的物理内存，因此传统动态分区分配不再是现代操作系统为进程分配物理内存的主要方式。

但是，动态分区所体现的思想——在一段连续地址空间内动态划分、分割、回收和合并内存块——仍然被现代进程的 堆内存分配器 所继承。

其发展关系可以概括为：

1. 早期操作系统
   • 动态分区用于在物理内存中为整个进程分配连续空间。
2. 引入分页与虚拟内存
   • 操作系统可以将进程的虚拟页面离散地映射到不同物理页框；
   • 整个进程不再需要占据连续物理空间。
3. 动态分区思想应用于堆管理
   • 用户态运行库在进程堆或内存映射区域中维护大小不同的内存块；
   • 根据程序请求动态分割和回收这些内存块。

参考 进程内存空间。

当程序调用 malloc 时，它通常是在向用户态内存分配器申请一块连续可用的 虚拟地址空间。

当程序调用 free 时，分配器会将对应内存块标记为空闲，并可能与相邻空闲块合并。

堆内存分配器通常维护空闲块列表、大小分类链表或更复杂的数据结构。

当程序申请内存时，分配器会：

1. 寻找足够大的空闲块；
2. 必要时将较大的空闲块分割；
3. 将其中一部分返回给程序；
4. 保留剩余部分供后续分配。

当程序释放内存时，分配器会：

1. 将对应块标记为空闲；
2. 尝试与相邻空闲块合并；
3. 在适当条件下，将部分大块内存归还给操作系统。

需要注意的是，malloc 并不一定在每次调用时都直接向操作系统申请物理页。用户态分配器通常会先从已经获得的堆空间或内存映射区域中进行二次分配。

伙伴算法

伙伴算法（Buddy Algorithm）是一种按照 $2$ 的幂次管理内存块的分配方法。

它将可管理的内存划分为大小为：1 KB、2 KB、4 KB、8 KB、……

等 $2$ 的幂次大小的块。

当需要分配内存时，算法会寻找能够满足请求的最小块。如果没有合适大小的空闲块，就将更大的块不断一分为二，直到得到所需大小的块。

当内存被释放时，算法会检查对应的伙伴块是否也处于空闲状态。如果伙伴块空闲，则将两者合并为更大的块，并继续向上尝试合并。

内存分配过程

假设需要分配大小为 $S$ 的内存，算法首先找到满足下式的最小块大小：

其中 $n$ 应理解为使块大小满足要求的整数阶数，实际系统中的最小块大小不一定是 1 字节。

分配过程如下：

• 如果对应阶数的空闲链表中存在空闲块，则直接分配；
• 如果不存在，则向更高阶空闲链表查找更大的块；
• 找到更大的块后，将其平均分割为两个大小相同的伙伴块；
• 如果分割后的块仍然过大，则继续分割；
• 最终分配其中一个满足请求的块，其余块加入对应阶数的空闲链表。

下图展示了一个使用伙伴算法的内存分配实例：

伙伴算法分配的块大小必须为 $2$ 的幂，因此当请求大小不是 $2$ 的幂时，会向上取整到最近的块大小。

例如，请求 6 KB 时，可能需要分配一个 8 KB 的块，其中未使用的 2 KB 构成 内部碎片。

内存释放过程

释放一块内存时，算法会检查其伙伴块是否也处于空闲状态。

伙伴块需要同时满足以下条件：

• 与当前块大小相同；
• 地址满足伙伴关系；
• 两者由同一个更大的父块分割而来。

如果伙伴块空闲，则：

1. 将当前块与伙伴块合并为一个更大的块；
2. 将合并后的块加入更高一级的空闲链表；
3. 继续检查新块的伙伴是否也处于空闲状态；
4. 重复合并，直到伙伴不空闲或已经达到最大块大小。

伙伴关系

伙伴块的地址满足特定关系。

假设所管理内存区域的起始地址为 0，当前块大小为 $2^n$ ，则起始地址为 $A$ 的块，其伙伴地址为：

其中 $\oplus$ 表示按位异或。

例如，块大小为 8，即 $2^3$ ，则：

• 地址 0 的伙伴为 8
• 地址 8 的伙伴为 0
• 地址 16 的伙伴为 24
• 地址 24 的伙伴为 16

通过异或运算，系统可以快速定位某个内存块对应的伙伴块。

伙伴算法的主要特点是：

• 分割和合并速度快；
• 可以快速找到伙伴；
• 能够缓解外部碎片；
• 但会由于按 $2$ 的幂向上取整而产生一定的内部碎片。

现代操作系统内核常使用伙伴算法管理物理页框，而在更小对象的分配中，还会结合 Slab、SLUB 等分配器。

离散分配管理

连续分配方式要求整个进程或进程中的某个逻辑区域占据连续内存，因此容易受到外部碎片的限制。

离散分配的关键思想是：

将一个进程拆分成多个较小的单位，分别存放到不同的物理内存区域中，再通过地址映射结构将它们组织为完整的进程地址空间。

按照划分单位的不同，离散分配主要包括：

• 页式管理：按照固定大小的页划分；
• 段式管理：按照程序的逻辑结构划分；
• 段页式管理：先分段，再对每个段分页。

页式管理

页式管理的地址翻译、页表结构、TLB、缺页异常、页面置换和请求分页等细节，详见 组成原理中的对应章节。

本节重点介绍页式管理为什么出现，以及它与段式管理、段页式管理之间的区别。

动态分区虽然可以根据程序大小按需划分内存，但每个进程仍必须占据一整块连续的物理内存，因此容易受到外部碎片的限制。

页式管理的核心思想是：

将进程拆分为固定大小的页，使一个进程可以离散地存放在多个不连续的物理页框中。

页式管理通常进行如下划分：

• 将进程的虚拟地址空间划分为若干固定大小的 页（Page）；
• 将物理内存划分为与页大小相同的 页框 或 物理块（Frame）；
• 通过 页表 记录虚拟页号到物理页框号的映射关系。

由于页和页框大小相同，进程的任意虚拟页都可以装入任意空闲页框。

因此，进程在虚拟地址空间中看起来仍然是连续的，但其实际使用的物理页框可以分散在内存的不同位置。

页式管理带来的关键变化是：

连续分配：整个进程必须放入一块连续物理内存

页式管理：每个页单独分配页框，各页框可以彼此不连续

页式管理的主要优点包括：

• 不要求整个进程占据连续物理内存；
• 基本消除了动态分区中的外部碎片；
• 便于实现虚拟内存；
• 便于按照页面设置访问权限；
• 便于在进程之间共享某些页面。

页式管理的主要缺点包括：

• 页是由系统按照固定大小机械划分的，不反映程序的逻辑结构；
• 页表会占用额外内存；
• 地址翻译会带来额外开销；
• 进程最后一个页面通常无法被完全利用，因此仍可能存在少量内部碎片。

段式管理

段式管理并不是页式管理的简单升级，而是从另一个角度解决内存管理问题。

二者关注的核心问题不同：

页式管理：关注物理内存的分配效率，按照固定大小机械分页

段式管理：关注程序本身的逻辑结构，按照代码、数据、栈等逻辑单位分段

段式内存管理将程序按照逻辑功能划分为多个长度可变的 段（Segment），例如：

• 代码段；
• 数据段；
• 堆段；
• 栈段；
• 不同模块或过程对应的段。

每个段在逻辑上表示程序中的一个相对独立的组成部分。

段式管理的主要优点是能够反映程序的逻辑结构，因此更便于按照逻辑单位实现：

• 内存保护；
• 代码和数据共享；
• 模块化编程；
• 段的独立增长。

例如，可以将代码段设置为只读和可执行，将数据段设置为可读写，也可以让多个进程共享同一个只读代码段。

在早期 x86 体系结构中，分段机制是一种重要的地址管理和保护手段。8086 使用段寄存器与偏移量形成地址，但其分段机制与现代操作系统教材中抽象的段式存储管理并不完全等价，需要结合具体体系结构理解。

下文介绍段式内存管理中的三个关键概念：段、段表 和 地址翻译。

段概念

段是按照程序的逻辑结构划分的地址空间单位。

其主要特点包括：

• 每个段都有明确的逻辑含义，例如代码段、数据段或堆栈段；
• 不同段的长度可以不同；
• 同一个段内部的地址是连续的；
• 不同段可以放在彼此不连续的物理内存区域；
• 每个段可以设置独立的访问权限。

段式管理中的逻辑地址通常表示为：

段号用于确定访问哪个段，段内偏移表示访问该段中的哪个位置。

段表

每个进程拥有一张段表。

段表中的每个段表项通常记录：

• 段基址：该段在物理内存中的起始地址；
• 段长：该段的长度；
• 访问权限：例如可读、可写、可执行；
• 其他状态信息。

当程序使用段号和段内偏移访问内存时，处理器首先根据段号查找段表项，取得段基址和段长。

虽然一个进程的不同段可以离散地放置在物理内存中，但在纯段式管理中，每一个段内部通常仍然需要占据一块连续的物理内存。

因此，段式管理仍然可能产生 外部碎片。

地址翻译

假设逻辑地址由段号 $S$ 和段内偏移 $W$ 组成：

段式地址翻译过程如下：

1. 检查段号是否越界

   • 使用段号 $S$ 与段表长度进行比较；
   • 如果段号超出当前进程段表范围，则产生异常。

2. 查找段表项

   • 根据段表基址和段号找到对应段表项；
   • 读取该段的段基址和段长。

3. 检查段内偏移是否越界

   • 比较段内偏移 $W$ 与段长；
   • 如果 $W$ 不在合法范围内，则产生段越界异常。

4. 计算物理地址

   • 如果访问合法，则：

段式管理适合按照逻辑单位进行保护和共享，但存在两个主要问题：

• 每个段的长度可变，内存分配和回收较复杂；
• 每个段内部仍需连续存放，因此会产生外部碎片。

为了同时获得分段的逻辑组织能力和分页的离散分配能力，可以将两者结合，形成 段页式管理。

段页式管理

段页式管理（Paged Segmentation）是一种将 段式管理 与 页式管理 相结合的内存管理方式。

分页和分段各自解决的问题不同：

段页式管理的基本思想是：

先按照程序的逻辑结构分段，再将每一个段划分为固定大小的页。

其划分过程可以表示为：

程序
├── 代码段
│   ├── 第 0 页
│   ├── 第 1 页
│   └── ...
├── 数据段
│   ├── 第 0 页
│   ├── 第 1 页
│   └── ...
└── 栈段
    ├── 第 0 页
    ├── 第 1 页
    └── ...

操作系统首先通过 段表 管理各个逻辑段。

每个段表项不再直接给出整个段在物理内存中的起始地址，而是记录该段对应的：

• 页表起始地址；
• 段长或页表长度；
• 访问权限等信息。

在每个段内部，再通过独立的页表完成虚拟页到物理页框的映射。

在段页式管理中，虚拟地址通常被划分为三个部分：

• 段号（Segment Number）；
• 段内页号（Page Number）；
• 页内偏移（Offset）。

逻辑地址可以表示为：

地址翻译过程如下：

1. 根据虚拟地址中的 段号 查找段表；
2. 从段表项中取得该段页表的起始地址；
3. 根据 页号 查找该段对应的页表；
4. 从页表项中取得物理页框号；
5. 将物理页框号与 页内偏移 组合，得到最终物理地址。

段页式管理在逻辑上采用分段，在物理内存分配上采用分页：

逻辑组织：分段

物理分配：分页

它的主要优点包括：

• 保留程序的逻辑结构；
• 便于按照段进行共享和保护；
• 每个段内部可以离散地使用物理页框；
• 基本消除了纯段式管理中的外部碎片；
• 可以支持虚拟内存。

其主要缺点包括：

• 地址翻译过程更复杂；
• 需要同时维护段表和多个页表；
• 一次地址翻译可能涉及多次访存；
• 页表和段表都会占用额外内存。

虚拟存储器

虚拟存储器（Virtual Memory）并不是一种与分页、分段并列的地址空间划分方式，而是在这些基本内存管理方式之上进一步发展出来的 存储管理机制。

它的基本思想是：

程序运行时不必将全部内容一次性装入内存，只需装入当前需要使用的部分；其余内容暂时保存在外存中，并在访问时由操作系统按需调入。

虚拟存储器利用了程序执行过程中的 局部性原理：

• 在一段时间内，程序通常只会集中访问少量代码和数据；
• 暂时没有被访问的部分没有必要一直占用物理内存；
• 只要将当前需要的部分保存在内存中，程序就可以继续运行。

因此，一个程序的地址空间可以大于实际分配给它的物理内存，甚至可以大于整个物理内存的容量。

页式虚拟存储涉及的页表结构、TLB、缺页异常、请求调页和页面置换算法等硬件与操作系统协同细节，统一放在 组成原理章节 中展开。

最后总结一下内存管理的发展历史：