五：操作系统内存管理之连续内存分配
操作系统内存管理：连续内存分配及其挑战
内存管理是操作系统核心功能之一，它负责有效地分配和管理主存储器，以满足多个并发运行进程的需求。最简单、也是历史上较早的一种内存分配策略是 连续内存分配 (Contiguous Memory Allocation)。在这种策略下，每个进程在内存中占用一个单一的、连续的内存块。本文将深入探讨连续内存分配的原理、不同实现方式、面临的挑战以及解决方案。
1. 什么是连续内存分配？
顾名思义，连续内存分配要求一个进程的所有部分（代码、数据、栈、堆等）必须加载到内存中一个连续的地址空间里。操作系统需要找到一块足够大的空闲内存区域来容纳整个进程。
这种方法的优点是概念简单，易于实现。进程的各个部分之间通过相对地址就可以直接访问，不需要复杂的地址翻译机制（至少在加载时或运行时，只需要一个基地址即可）。
然而，连续内存分配的最大挑战在于如何有效地管理和分配可用的连续内存块，尤其是在多个进程动态创建和终止的环境中。
2. 分区分配 (Partition Allocation)
为了实现连续内存分配，操作系统需要将物理内存划分成若干区域，用于存放进程。这引出了分区分配的概念，主要有两种类型：固定分区和动态分区。
2.1 固定分区分配 (Fixed-Partition Allocation)
-
概念: 在系统启动时，操作系统将物理内存划分为若干个大小固定的内存分区。每个分区可以容纳一个进程。分区的大小可以相同，也可以不同。
-
工作方式:
- 操作系统维护一个表格，记录每个分区是否被占用以及被哪个进程占用。
- 当一个新进程到达时，操作系统查找一个足够大的空闲分区。
- 如果找到一个合适的分区，进程被加载到该分区中，分区状态标记为“已占用”。
- 如果没有找到足够大的空闲分区，进程可能需要等待。
-
示例:
假设物理内存大小为 1MB，被划分为四个固定分区：- 分区 1: 200 KB
- 分区 2: 300 KB
- 分区 3: 500 KB
- 分区 4: 100 KB
进程 A (150KB) 到达，可以放入分区 1 (200KB)。
进程 B (250KB) 到达，可以放入分区 2 (300KB)。
进程 C (450KB) 到达，可以放入分区 3 (500KB)。
进程 D (80KB) 到达，可以放入分区 4 (100KB)。此时内存状态：[OS][A(150K in 200K)][B(250K in 300K)][C(450K in 500K)][D(80K in 100K)]
-
优点:
- 实现简单。
- 开销小。
-
缺点:
- 内部碎片 (Internal Fragmentation): 这是固定分区分配的主要问题。如果一个进程的大小小于它所在分区的大小，那么分区内剩余的空间无法被其他进程使用，形成浪费。在上面的示例中，进程 A 浪费了 50KB，B 浪费了 50KB，C 浪费了 50KB，D 浪费了 20KB。这些浪费的空间都属于内部碎片。
- 限制进程数量: 最多只能运行与分区数量相等的进程。
- 限制进程大小: 大于任何分区的进程无法运行。
2.2 动态分区分配 (Dynamic-Partition Allocation)
-
概念: 内存不预先划分固定大小的分区。当一个新进程到达时，操作系统根据进程的大小，动态地从当前可用的空闲内存空间中分配一个刚好能容纳它的连续块。
-
工作方式:
- 操作系统维护一个空闲内存块列表（Free List）。最初，整个可用内存可能只有一个大的空闲块。
- 当一个新进程到达并需要 n KB 内存时，操作系统在空闲列表中寻找一个大小大于或等于 n KB 的空闲块。
- 如果找到这样的块，就从中分配 n KB 给进程。如果空闲块大于 n KB，剩余的部分会作为一个新的更小的空闲块加入到空闲列表中。
- 当进程终止时，其占用的内存块被释放，并可能与相邻的空闲块合并，形成更大的空闲块。
-
示例:
初始状态：总共有 1000 KB 可用空闲内存 [Free 1000K]- 进程 A (200KB) 到达：[A(200K)][Free 800K]
- 进程 B (300KB) 到达：[A(200K)][B(300K)][Free 500K]
- 进程 C (100KB) 到达：[A(200K)][B(300K)][C(100K)][Free 400K]
- 进程 B 终止，释放内存：[A(200K)][Free 300K][C(100K)][Free 400K]
- 进程 D (150KB) 到达：可以在 300K 或 400K 的空闲块中选择一个分配。假设分配在 300K 块中：[A(200K)][D(150K)][Free 150K][C(100K)][Free 400K]
-
优点:
- 没有内部碎片（分配的大小几乎等于进程需要的大小）。
- 更有效地利用了内存空间。
-
缺点:
- 外部碎片 (External Fragmentation): 这是动态分区分配的主要问题。随着进程不断地进入和离开内存，会产生许多小的、分散的空闲内存块。虽然这些小块的总和可能很大，但它们不是连续的，因此无法满足需要较大连续空间的进程的需求。在上面的示例中，虽然总共有 150K + 400K = 550K 的空闲内存，但如果此时有一个需要 500K 连续空间的进程到来，它将无法被满足。
- 实现和管理空闲列表比固定分区复杂。
- 分配和释放内存块需要更多的计算开销。
3. 碎片问题 (Fragmentation)
碎片是内存分配中导致空间浪费的问题，主要分为两类：
3.1 内部碎片 (Internal Fragmentation)
-
定义: 已分配给进程的内存块中，未被进程使用但不能被系统分配给其他进程的那些部分。
-
原因: 通常发生在分配单元大小固定，但进程需要的空间小于分配单元时。最典型的例子是固定分区分配，以及后续会学到的分页（如果最后一页没有完全填满）。
-
特点: 发生在分配的块内部。这部分空间在逻辑上属于某个进程，但在物理上是闲置的。
-
示例:
固定分区大小为 200KB。进程需要 150KB。系统分配一个 200KB 的分区。进程使用 150KB，剩下 50KB。这 50KB 就是内部碎片，它在 200KB 分区内部，且无法分配给其他进程。
3.2 外部碎片 (External Fragmentation)
-
定义: 内存中未分配的空闲空间被分割成许多小的、不连续的区域。这些区域总和起来可能很大，但由于不是连续的，无法满足需要较大连续内存空间的进程。
-
原因: 通常发生在动态分区分配中，随着进程的不断加载和卸载，在已分配块之间留下零散的空闲块。
-
特点: 发生在已分配块之间。这部分空间是逻辑上和物理上都闲置的，但由于其分散性而难以利用。
-
示例:
内存中有三个空闲块：10KB, 20KB, 30KB。总空闲空间为 60KB。如果一个进程需要 50KB 的连续内存，它无法被满足，即使总空闲空间足够。这些分散的 10KB, 20KB, 30KB 空闲块就是外部碎片。
动态分区分配避免了内部碎片，但引入了更严重的外部碎片问题。
4. 动态分区分配算法 (Dynamic Partition Allocation Algorithms)
在动态分区分配中，当一个进程请求 n KB 内存时，操作系统需要在空闲内存块列表中选择一个块进行分配。有几种常见的算法来决定选择哪个空闲块：
4.1 首次适应算法 (First Fit)
- 策略: 扫描空闲内存块列表，找到第一个大小大于或等于请求大小的空闲块，然后将进程分配到这个块中。
- 工作方式:
- 从空闲列表的开头开始查找。
- 找到第一个满足
free_block_size >= requested_size的块。 - 如果
free_block_size == requested_size，将整个块分配给进程，并从空闲列表中移除该块。 - 如果
free_block_size > requested_size，从该块的起始位置分配requested_size的空间给进程，剩余的部分形成一个新的空闲块，并更新空闲列表。
- 示例:
空闲列表（按地址顺序）：[100KB at addr 1000], [500KB at addr 3000], [200KB at addr 9000], [300KB at addr 12000], [600KB at addr 16000]
请求内存：250KB- 扫描列表：
- 100KB (太小)
- 500KB (满足) -> 选择 500KB 块。
- 分配 250KB。新的空闲列表：[100KB at 1000], [250KB at 3250 (剩余)], [200KB at 9000], [300KB at 12000], [600KB at 16000]
- 扫描列表：
- 优缺点:
- 优点: 速度快，因为只需要找到第一个合适的块即可。
- 缺点: 倾向于在空闲列表的开头产生小的碎片，使得后续的查找过程可能需要跳过这些小块，效率下降。同时，较大的空闲块可能会被留在列表的末尾，较少被利用。
4.2 最佳适应算法 (Best Fit)
- 策略: 扫描整个空闲内存块列表，找到大小最小的、但仍然大于或等于请求大小的空闲块，然后将进程分配到这个块中。
- 工作方式:
- 遍历整个空闲列表，找出所有满足
free_block_size >= requested_size的块。 - 从这些满足条件的块中，选择大小最小的那一个。
- 进行分配（分割或整体分配）。
- 遍历整个空闲列表，找出所有满足
- 示例:
空闲列表：[100KB at 1000], [500KB at 3000], [200KB at 9000], [300KB at 12000], [600KB at 16000]
请求内存：250KB- 满足条件的块：500KB, 300KB, 600KB。
- 最小的满足条件的块是 300KB。
- 分配 250KB 从 300KB 块。新的空闲列表：[100KB at 1000], [500KB at 3000], [200KB at 9000], [50KB at 12250 (剩余)], [600KB at 16000]
- 优缺点:
- 优点: 分配后剩下的空闲块是最小的，理论上可以最大限度地减少本次分配造成的内部碎片（虽然动态分配本身没有内部碎片，这里的剩余部分是外部碎片），并且倾向于保留大的空闲块。
- 缺点: 需要遍历整个空闲列表来找到最佳块，速度较慢。容易产生大量非常小的、难以利用的外部碎片。
4.3 最坏适应算法 (Worst Fit)
- 策略: 扫描整个空闲内存块列表，找到大小最大的空闲块，然后将进程分配到这个块中。
- 工作方式:
- 遍历整个空闲列表，找到大小最大的空闲块。
- 如果最大块满足
free_block_size >= requested_size，则从中分配。 - 进行分配（分割）。
- 示例:
空闲列表：[100KB at 1000], [500KB at 3000], [200KB at 9000], [300KB at 12000], [600KB at 16000]
请求内存：250KB- 最大的空闲块是 600KB。
- 分配 250KB 从 600KB 块。新的空闲列表：[100KB at 1000], [500KB at 3000], [200KB at 9000], [300KB at 12000], [350KB at 16250 (剩余)]
- 优缺点:
- 优点: 分配后剩下的空闲块是相对较大的，理论上希望可以通过保留较大的剩余块来更好地满足后续的大型请求（但实际效果存疑）。
- 缺点: 需要遍历整个空闲列表，速度慢。它专门破坏最大的空闲块，可能迅速消除满足大型进程所需的空间。实践中证明，最坏适应算法通常效果最差，会导致外部碎片问题更严重。
算法选择考量:
- First Fit 通常是实现中最常用的算法，因为它速度最快，并且在许多情况下，其内存利用率并不显著劣于 Best Fit。
- Best Fit 和 Worst Fit 都需要遍历整个空闲列表，开销更大。
5. 紧凑 (Compaction)
紧凑是解决外部碎片问题的一种技术手段。
-
概念: 通过移动内存中的进程，将分散的空闲内存块聚集到一起，形成一个或几个较大的连续空闲块。
-
工作方式: 操作系统遍历内存，将所有已分配的进程块移动到内存的一端（例如，低地址端），从而在另一端（高地址端）形成一个大的连续空闲区域。
-
示例:
内存状态（有外部碎片）：[Process A][Free 10KB][Process B][Free 20KB][Process C][Free 30KB]
进行紧凑后：[Process A][Process B][Process C][Large Free Block 60KB] -
优缺点:
- 优点: 有效地解决了外部碎片问题，将分散的空闲空间整合成可用的大块。
- 缺点: 成本高昂。
- 需要暂停正在运行的进程。
- 需要移动大量的内存数据，这会消耗大量的 CPU 时间和内存带宽。
- 如果地址绑定是在加载时进行的，移动进程会导致进程内部的地址引用失效，需要修改（重定位）进程内部的地址。如果使用执行时绑定（逻辑地址 vs 物理地址），则只需要更新进程的基址寄存器或页表等映射机制，无需修改进程本身的代码。因此，紧凑通常要求硬件支持执行时地址绑定。
- 何时进行紧凑是难以决定的：太频繁开销大，太不频繁则外部碎片问题无法解决。
由于紧凑的高成本，现代操作系统通常更倾向于使用非连续内存分配技术（如分页、分段）来从根本上避免外部碎片问题，而不是依赖于频繁的紧凑操作。
结论
连续内存分配是一种简单直观的内存管理策略，尤其适用于早期或简单的系统。固定分区分配引入了内部碎片，限制了系统灵活性。动态分区分配消除了内部碎片，但带来了严重的外部碎片问题。动态分区分配算法（如 First Fit, Best Fit, Worst Fit）是解决如何选择空闲块的策略，但它们都无法根除外部碎片。紧凑技术可以解决外部碎片，但由于其高昂的成本和复杂性，在现代多任务操作系统中，非连续内存分配技术（如分页）成为了主流，因为它能更有效地利用内存并从根本上避免了外部碎片问题。理解连续内存分配及其挑战，是进一步学习更高级内存管理技术的基础。