操作系统内存连续分配管理：四大算法原理、碎片分析与实战解析

最近在复习操作系统内存管理时，发现很多同学对“连续分配管理”这块内容感到头疼，概念多、算法杂，做题时容易混淆。本文将以一张核心图为主线，系统梳理内存连续分配管理的四大算法（单一连续、固定分区、动态分区、动态可重定位分区），并结合408考研真题风格，深入剖析其原理、优缺点、适用场景及内部碎片/外部碎片的产生机制。无论你是正在备考的学子，还是希望巩固操作系统基础的在职开发者，这份笔记都能帮你构建清晰的知识框架。

1. 内存连续分配管理：核心概念与问题背景

在操作系统中，内存管理是核心功能之一，其首要任务就是将有限的主存空间有效地分配给多个并发进程使用。连续分配管理是一种经典的内存分配策略，它要求每个进程必须被装入一片连续的内存区域中。

为什么需要连续分配？这主要源于早期计算机的硬件设计（如基址寄存器）和程序加载的简便性。程序指令和数据在逻辑地址空间中是连续的，将其映射到物理内存时，保持连续性可以简化地址转换过程。

然而，连续分配面临一个核心矛盾：如何高效地满足多个进程对连续内存空间的需求，同时尽量减少内存空间的浪费？这种浪费主要表现为两种“碎片”：

• 内部碎片：分配给进程的内存分区中，有一部分未被进程使用，但其他进程也无法利用。这发生在分区内部。
• 外部碎片：内存中存在一些小的、不连续的空闲分区，它们总和可能很大，但因为不连续，无法满足稍大进程的连续内存需求。这发生在分区之间。

不同的连续分配算法，正是在用不同的策略与这两种碎片做斗争。下面这张“一图流”概括了四种主要算法的核心对比，我们将以此图为纲，逐一深入。

(示意图：纵轴为内存空间，横轴为时间或进程序列，展示四种算法下内存的划分与进程的装入情况)

2. 环境与知识准备

在深入算法细节前，我们需要明确讨论的“环境”和前提知识。本文的讨论基于经典的操作系统内存管理模型，不涉及具体编程语言或框架版本。

核心模型假设：

1. 内存模型：将物理内存抽象为一个从0开始、地址连续增长的线性空间。
2. 进程模型：每个进程有一个已知的、固定大小的内存需求。
3. 管理要素：操作系统需要维护一个空闲分区表或空闲分区链，来记录当前内存中哪些区域是空闲的。
4. 分配目标：当新进程到达时，为其寻找一个足够大的空闲分区；进程终止时，回收其占用的分区，并可能与相邻空闲分区合并。

理解以下关键数据结构有助于后续算法的学习：

• 分区描述符：通常包含起始地址、分区大小、状态（已分配/空闲）。
• 空闲分区表：一个数组，每个表项是一个空闲分区的描述符。
• 空闲分区链：将空闲分区用链表连接起来，每个节点包含分区信息和前后指针。

3. 算法一：单一连续分配

这是最简单、最古老的内存分配方式，主要用于单道批处理系统和早期的个人计算机。

3.1 原理与实现

内存被划分为两个固定区域：

1. 系统区：仅供操作系统使用，通常位于内存低地址部分。
2. 用户区：整个剩余部分作为一个连续分区，一次只装入一个用户进程。

当有进程需要运行时，它被装入用户区的起始位置。进程运行结束后，用户区被清空，等待下一个进程。

// 概念性数据结构示意 typedef struct { int base; // 用户区起始地址，固定为系统区大小 int size; // 用户区总大小 int allocated_base; // 当前进程装入的起始地址（通常等于base） int allocated_size; // 当前进程大小 } SingleContiguousMemory; void allocate(SingleContiguousMemory *mem, Process *p) { if (p->memory_needed <= mem->size) { mem->allocated_base = mem->base; mem->allocated_size = p->memory_needed; // 装入进程p到地址 mem->allocated_base printf("进程已装入，起始地址：%d\n", mem->allocated_base); } else { printf("错误：进程所需内存(%d)超过用户区总大小(%d)\n", p->memory_needed, mem->size); } }

3.2 优缺点与碎片分析

• 优点：管理简单，开销极小，无外部碎片。
• 缺点：
  1. 仅适用于单用户、单任务环境，资源利用率极低。
  2. 会产生内部碎片。因为即使用户进程很小，它也会独占整个用户区，用户区内未使用的部分就成了内部碎片。
  3. 进程地址空间受物理内存大小限制。

碎片总结：仅存在内部碎片。外部碎片不存在，因为整个用户区是一个整体。

4. 算法二：固定分区分配

为了支持多道程序，引入了分区概念。固定分区分配在系统初始化时，将用户内存空间静态地划分为若干个大小固定（可以相等也可以不等）的分区。每个分区只能装入一个进程。

4.1 原理与实现

操作系统维护一张分区说明表，记录每个分区的起始地址、大小和状态（是否已分配）。

当新进程到达时，由内存分配程序检索分区说明表，找出一个大小足够且空闲的分区分配给该进程。如果找不到，则分配失败。

// 固定分区分配数据结构示意 #define FIXED_PARTITION_NUM 4 typedef struct { int base; int size; int is_free; // 0-已分配，1-空闲 int process_id; // 装入的进程ID，-1表示空闲 } FixedPartition; FixedPartition partition_table[FIXED_PARTITION_NUM] = { {100, 20, 1, -1}, // 分区0：起始100KB，大小20KB，空闲 {120, 40, 1, -1}, // 分区1：起始120KB，大小40KB，空闲 {160, 30, 1, -1}, // 分区2：起始160KB，大小30KB，空闲 {190, 50, 1, -1} // 分区3：起始190KB，大小50KB，空闲 }; // 分配函数（首次适应策略） int allocate_fixed(Process *p) { for (int i = 0; i < FIXED_PARTITION_NUM; i++) { if (partition_table[i].is_free && partition_table[i].size >= p->memory_needed) { partition_table[i].is_free = 0; partition_table[i].process_id = p->id; // 计算内部碎片 int internal_frag = partition_table[i].size - p->memory_needed; printf("进程P%d装入分区%d，起始地址%dKB，产生内部碎片%dKB\n", p->id, i, partition_table[i].base, internal_frag); return partition_table[i].base; // 返回起始地址 } } printf("错误：无合适分区容纳进程P%d（需%dKB）\n", p->id, p->memory_needed); return -1; // 分配失败 }

4.2 优缺点与碎片分析

• 优点：实现简单，适用于作业大小、数量事先已知的批处理系统。
• 缺点：
  1. 分区大小和数量固定，缺乏灵活性。大作业可能无法装入任何分区，小作业则浪费大分区空间。
  2. 存在严重的内部碎片。进程大小几乎不可能恰好等于分区大小。
  3. 分区数量限制了系统并发度。

碎片总结：主要存在内部碎片。由于分区固定且不回收合并，不存在外部碎片。

5. 算法三：动态分区分配（可变分区分配）

这是连续分配中最重要的算法，也是408考研的重点。它根据进程的实际需要，动态地划分内存分区。分区的大小和数量是可变的。

5.1 原理与核心数据结构

初始时，整个用户内存是一个大空闲分区。当进程到达时，从空闲分区中划出一块恰好满足需求的空间分配给它。进程终止时，释放其占用的分区，系统会立即尝试与相邻的空闲分区合并，形成一个更大的空闲分区。

系统需要动态维护空闲分区表或空闲分区链。常见的组织方式有：

• 按地址排序：便于合并相邻空闲分区。
• 按大小排序：便于实现特定分配算法（如最佳适应）。

5.2 三种经典分配算法

当有多个空闲分区能满足进程需求时，需要选择哪一个？这就是动态分区分配算法的核心。

5.2.1 首次适应算法

• 策略：从空闲分区链的起始地址开始顺序查找，选择第一个能满足要求的空闲分区。
• 实现：空闲分区链按地址从低到高排列。
• 优点：简单、快速，倾向于利用低地址部分的内存，高地址部分可能保留大空闲块。
• 缺点：低地址部分容易产生很多难以利用的小碎片（外部碎片）。

5.2.2 最佳适应算法

• 策略：从所有空闲分区中，选择大小与进程需求最接近的空闲分区进行分配。
• 实现：空闲分区链按分区大小从小到大排列。每次分配都需要从头查找。
• 优点：看似最节约，每次分配留下的剩余空闲分区最小。
• 缺点：会产生大量难以利用的极小外部碎片。查找效率较低（需遍历或特殊数据结构）。

5.2.3 最坏适应算法

• 策略：与最佳适应相反，选择最大的空闲分区进行分配。
• 实现：空闲分区链按分区大小从大到小排列。
• 优点：分配后剩下的空闲分区仍然较大，不易产生非常小的碎片。
• 缺点：不利于大进程的分配，因为大空闲分区被快速切割。

// 动态分区-空闲分区链节点定义 typedef struct FreeBlock { int base; int size; struct FreeBlock *next; } FreeBlock; FreeBlock *free_list_head = NULL; // 空闲分区链头指针 // 首次适应算法分配示例 FreeBlock* allocate_FF(int need_size) { FreeBlock *prev = NULL; FreeBlock *curr = free_list_head; while (curr != NULL) { if (curr->size >= need_size) { // 找到可用的分区 if (curr->size == need_size) { // 大小正好，分配整个分区 if (prev == NULL) free_list_head = curr->next; else prev->next = curr->next; printf("分配整个分区：地址[%d-%d]，大小%d\n", curr->base, curr->base+curr->size, curr->size); return curr; } else { // 从该分区中划出need_size，剩余部分作为新空闲块 FreeBlock *allocated_block = (FreeBlock*)malloc(sizeof(FreeBlock)); allocated_block->base = curr->base; allocated_block->size = need_size; // 修改原空闲块信息 curr->base += need_size; curr->size -= need_size; printf("从大分区中划出：分配地址[%d-%d]，大小%d；剩余空闲地址[%d-%d]，大小%d\n", allocated_block->base, allocated_block->base+need_size, need_size, curr->base, curr->base+curr->size, curr->size); return allocated_block; } } prev = curr; curr = curr->next; } printf("分配失败：无足够大空闲分区（需%d）\n", need_size); return NULL; }

5.3 回收与合并

回收内存时，不仅要将被释放的分区标记为空闲，更重要的是将其与相邻的空闲分区合并，这是对抗外部碎片的关键。

// 回收内存并合并相邻空闲分区 void free_and_merge(FreeBlock *block_to_free) { // 1. 将释放块插入空闲链，保持按地址有序 FreeBlock *curr = free_list_head; FreeBlock *prev = NULL; while (curr != NULL && curr->base < block_to_free->base) { prev = curr; curr = curr->next; } // 插入到prev和curr之间 block_to_free->next = curr; if (prev == NULL) free_list_head = block_to_free; else prev->next = block_to_free; // 2. 向前合并（与prev） if (prev != NULL && (prev->base + prev->size) == block_to_free->base) { prev->size += block_to_free->size; prev->next = block_to_free->next; free(block_to_free); block_to_free = prev; // 让block_to_free指向合并后的块，便于后续向后合并 printf("向前合并完成\n"); } // 3. 向后合并（与curr，此时curr可能是原curr或block_to_free->next） FreeBlock *new_curr = (prev == NULL) ? free_list_head->next : prev->next; if (new_curr != NULL && (block_to_free->base + block_to_free->size) == new_curr->base) { block_to_free->size += new_curr->size; block_to_free->next = new_curr->next; free(new_curr); printf("向后合并完成\n"); } }

5.4 优缺点与碎片分析

• 优点：灵活性高，按需分配，提高了内存利用率。
• 缺点：
  1. 会产生外部碎片。这是动态分区分配最显著的问题。经过多次分配和回收后，内存中会散布大量小的空闲分区，尽管其总容量可能足够，但无法满足稍大的进程需求。
  2. 分配和回收算法相对复杂，尤其是合并操作。

碎片总结：主要存在外部碎片。内部碎片几乎不存在（分配大小刚好满足需求），但外部碎片问题严重。

6. 算法四：动态可重定位分区分配

为了解决外部碎片问题，在动态分区分配的基础上引入了“紧凑”技术。

6.1 原理与“紧凑”技术

当内存中外部碎片太多，无法满足新进程需求，但所有碎片总和足够时，操作系统会进行“紧凑”（或称“碎片整理”）。

• 操作：将内存中所有已分配进程向内存一端移动，使所有空闲分区聚集在另一端，形成一个大的连续空闲区。
• 关键问题：进程在内存中移动了，其指令和数据中的地址如何修正？
• 解决方案：引入动态重定位硬件支持。每个进程的物理地址 = 逻辑地址 +重定位寄存器（基址寄存器）的值。当进程被移动时，操作系统只需更新该进程对应的重定位寄存器的值（即新的起始物理地址），进程本身无需修改。

6.2 实现流程

1. 检查空闲分区是否满足新进程需求。如不满足，检查所有空闲分区总和。
2. 若总和满足，则触发“紧凑”操作。
3. 更新所有被移动进程的重定位寄存器。
4. 将合并后的大空闲分区分配给新进程。

// 概念性紧凑过程描述 void compaction(Process processes[], int num_processes, FreeBlock free_blocks[], int *num_free_blocks) { int new_base = 0; // 假设系统区在0-99，用户区从100开始 int current_addr = 100; printf("开始紧凑操作...\n"); // 1. 将所有进程向低地址端移动 for (int i = 0; i < num_processes; i++) { if (processes[i].state == RUNNING) { int old_base = processes[i].physical_base; int size = processes[i].memory_needed; // 模拟移动内存内容（实际由OS完成） // memmove(new_addr, old_addr, size); processes[i].physical_base = current_addr; // 更新该进程的重定位寄存器（基址寄存器） processes[i].relocation_register = current_addr; printf("移动进程P%d: 从[%d-%d] 到 [%d-%d]\n", processes[i].id, old_base, old_base+size, current_addr, current_addr+size); current_addr += size; } } // 2. 所有进程移动后，剩余空间形成一个大的空闲分区 int free_size = TOTAL_MEMORY - current_addr; free_blocks[0].base = current_addr; free_blocks[0].size = free_size; *num_free_blocks = 1; printf("紧凑完成。形成一个大空闲分区：[%d-%d]，大小%d\n", current_addr, TOTAL_MEMORY, free_size); }

6.3 优缺点与碎片分析

• 优点：基本消除了外部碎片，内存利用率得到极大提升。
• 缺点：
  1. “紧凑”操作开销巨大。需要移动大量内存数据，消耗CPU时间，系统性能会短暂下降。
  2. 需要硬件（重定位寄存器）支持，增加了成本。
  3. 移动进程时，该进程必须处于暂停状态，影响了并发性。

碎片总结：可以消除外部碎片，但以巨大的系统开销为代价。内部碎片情况与动态分区相同。

7. 四种算法对比与真题演练

现在，让我们回到开篇的“一图流”，并结合408真题风格进行总结和演练。

7.1 核心对比表格

7.2 408真题风格问题解析

问题1：某系统采用动态分区分配，空闲分区链按地址递增排列。现有以下空闲分区（单位KB）：空闲分区链：起始地址->[100, 30] -> [200, 50] -> [300, 80] -> [450, 60]现有进程请求序列：P1(20KB), P2(70KB), P3(35KB)。使用首次适应算法分配，请描述分配过程，并指出最终的外部碎片情况。

解析：

1. P1请求20KB：从链首开始找。第一个分区[100,30]满足要求（30>=20）。分配后，该分区剩余[100,10]（假设从低地址开始分配）。空闲链变为：[100,10] -> [200,50] -> [300,80] -> [450,60]。
2. P2请求70KB：从链首[100,10]开始，不满足；下一个[200,50]不满足；下一个[300,80]满足（80>=70）。分配后，该分区剩余[300,10]。空闲链：[100,10] -> [200,50] -> [300,10] -> [450,60]。
3. P3请求35KB：查找。[100,10]不满足；[200,50]满足（50>=35）。分配后，该分区剩余[200,15]。空闲链：[100,10] -> [200,15] -> [300,10] -> [450,60]。
4. 最终外部碎片：存在四个小空闲分区：10KB, 15KB, 10KB, 60KB。总空闲95KB，但最大连续空闲块只有60KB。外部碎片显著。

问题2：为什么说最佳适应算法容易产生很多小碎片？

解析：最佳适应算法总是挑选与进程需求最接近的空闲分区。分配后，剩余的空闲分区大小 = 原分区大小 - 进程大小。因为这个差值是最小的，所以产生的剩余分区也是尽可能小的。经过多次分配后，内存中会积累大量这种极小的空闲分区，它们可能小到无法满足任何后续进程的需求，从而成为无法利用的外部碎片。

8. 最佳实践与工程启示

虽然现代操作系统主要使用非连续分配（如分页、分段）来从根本上避免外部碎片问题，但连续分配管理的设计思想依然具有重要的学习价值和工程启示：

1. 空间与时间的权衡：动态可重定位分区通过“紧凑”牺牲时间（性能）来换取空间（消除碎片）。在软件设计中，这种权衡无处不在，例如用空间换时间的缓存，或用时间换空间的压缩算法。
2. 数据结构的核心作用：动态分区分配的性能和碎片情况，很大程度上取决于空闲分区链的组织方式（按地址或按大小排序）和查找算法。这启示我们，在解决资源调度、存储管理问题时，选择合适的数据结构至关重要。
3. “碎片”的普遍性：碎片问题不局限于内存。磁盘存储、数据库存储、甚至网络资源分配中都有类似的“碎片化”问题。理解内存碎片的成因和解决方案，有助于触类旁通。
4. 硬件与软件协同：动态重定位需要硬件（基址寄存器）的支持。这体现了计算机系统中一个核心思想：通过硬件辅助来解决软件层面的性能瓶颈或复杂性问题。现代CPU的TLB、MMU都是这一思想的延伸。

对于备考408的同学，建议：

• 理解本质：不要死记硬背四种算法的名字，要理解它们是如何在“连续性”约束下，与“内部碎片”、“外部碎片”做斗争的演进过程。
• 动手模拟：在纸上或写简单代码模拟不同算法下的分配、回收、合并过程，这是应对计算题和判断题的最佳方法。
• 关联对比：将连续分配与非连续分配（尤其是分页管理）进行对比，理解后者是如何解决外部碎片这一核心痛点的。

希望这份结合“一图流”的深度笔记，能帮你彻底厘清内存连续分配管理的脉络。在复习时，多问几个“为什么”，理解算法背后的设计动机，远比单纯记忆结论有效。