最近在复习操作系统内存管理时发现很多同学对“连续分配管理”这块内容感到头疼概念多、算法杂做题时容易混淆。本文将以一张核心图为主线系统梳理内存连续分配管理的四大算法单一连续、固定分区、动态分区、动态可重定位分区并结合408考研真题风格深入剖析其原理、优缺点、适用场景及内部碎片/外部碎片的产生机制。无论你是正在备考的学子还是希望巩固操作系统基础的在职开发者这份笔记都能帮你构建清晰的知识框架。1. 内存连续分配管理核心概念与问题背景在操作系统中内存管理是核心功能之一其首要任务就是将有限的主存空间有效地分配给多个并发进程使用。连续分配管理是一种经典的内存分配策略它要求每个进程必须被装入一片连续的内存区域中。为什么需要连续分配这主要源于早期计算机的硬件设计如基址寄存器和程序加载的简便性。程序指令和数据在逻辑地址空间中是连续的将其映射到物理内存时保持连续性可以简化地址转换过程。然而连续分配面临一个核心矛盾如何高效地满足多个进程对连续内存空间的需求同时尽量减少内存空间的浪费这种浪费主要表现为两种“碎片”内部碎片分配给进程的内存分区中有一部分未被进程使用但其他进程也无法利用。这发生在分区内部。外部碎片内存中存在一些小的、不连续的空闲分区它们总和可能很大但因为不连续无法满足稍大进程的连续内存需求。这发生在分区之间。不同的连续分配算法正是在用不同的策略与这两种碎片做斗争。下面这张“一图流”概括了四种主要算法的核心对比我们将以此图为纲逐一深入。(示意图纵轴为内存空间横轴为时间或进程序列展示四种算法下内存的划分与进程的装入情况)2. 环境与知识准备在深入算法细节前我们需要明确讨论的“环境”和前提知识。本文的讨论基于经典的操作系统内存管理模型不涉及具体编程语言或框架版本。核心模型假设内存模型将物理内存抽象为一个从0开始、地址连续增长的线性空间。进程模型每个进程有一个已知的、固定大小的内存需求。管理要素操作系统需要维护一个空闲分区表或空闲分区链来记录当前内存中哪些区域是空闲的。分配目标当新进程到达时为其寻找一个足够大的空闲分区进程终止时回收其占用的分区并可能与相邻空闲分区合并。理解以下关键数据结构有助于后续算法的学习分区描述符通常包含起始地址、分区大小、状态已分配/空闲。空闲分区表一个数组每个表项是一个空闲分区的描述符。空闲分区链将空闲分区用链表连接起来每个节点包含分区信息和前后指针。3. 算法一单一连续分配这是最简单、最古老的内存分配方式主要用于单道批处理系统和早期的个人计算机。3.1 原理与实现内存被划分为两个固定区域系统区仅供操作系统使用通常位于内存低地址部分。用户区整个剩余部分作为一个连续分区一次只装入一个用户进程。当有进程需要运行时它被装入用户区的起始位置。进程运行结束后用户区被清空等待下一个进程。// 概念性数据结构示意 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 优缺点与碎片分析优点管理简单开销极小无外部碎片。缺点仅适用于单用户、单任务环境资源利用率极低。会产生内部碎片。因为即使用户进程很小它也会独占整个用户区用户区内未使用的部分就成了内部碎片。进程地址空间受物理内存大小限制。碎片总结仅存在内部碎片。外部碎片不存在因为整个用户区是一个整体。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 优缺点与碎片分析优点实现简单适用于作业大小、数量事先已知的批处理系统。缺点分区大小和数量固定缺乏灵活性。大作业可能无法装入任何分区小作业则浪费大分区空间。存在严重的内部碎片。进程大小几乎不可能恰好等于分区大小。分区数量限制了系统并发度。碎片总结主要存在内部碎片。由于分区固定且不回收合并不存在外部碎片。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-basecurr-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-baseneed_size, need_size, curr-base, curr-basecurr-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 优缺点与碎片分析优点灵活性高按需分配提高了内存利用率。缺点会产生外部碎片。这是动态分区分配最显著的问题。经过多次分配和回收后内存中会散布大量小的空闲分区尽管其总容量可能足够但无法满足稍大的进程需求。分配和回收算法相对复杂尤其是合并操作。碎片总结主要存在外部碎片。内部碎片几乎不存在分配大小刚好满足需求但外部碎片问题严重。6. 算法四动态可重定位分区分配为了解决外部碎片问题在动态分区分配的基础上引入了“紧凑”技术。6.1 原理与“紧凑”技术当内存中外部碎片太多无法满足新进程需求但所有碎片总和足够时操作系统会进行“紧凑”或称“碎片整理”。操作将内存中所有已分配进程向内存一端移动使所有空闲分区聚集在另一端形成一个大的连续空闲区。关键问题进程在内存中移动了其指令和数据中的地址如何修正解决方案引入动态重定位硬件支持。每个进程的物理地址 逻辑地址 重定位寄存器基址寄存器的值。当进程被移动时操作系统只需更新该进程对应的重定位寄存器的值即新的起始物理地址进程本身无需修改。6.2 实现流程检查空闲分区是否满足新进程需求。如不满足检查所有空闲分区总和。若总和满足则触发“紧凑”操作。更新所有被移动进程的重定位寄存器。将合并后的大空闲分区分配给新进程。// 概念性紧凑过程描述 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_basesize, current_addr, current_addrsize); 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 优缺点与碎片分析优点基本消除了外部碎片内存利用率得到极大提升。缺点“紧凑”操作开销巨大。需要移动大量内存数据消耗CPU时间系统性能会短暂下降。需要硬件重定位寄存器支持增加了成本。移动进程时该进程必须处于暂停状态影响了并发性。碎片总结可以消除外部碎片但以巨大的系统开销为代价。内部碎片情况与动态分区相同。7. 四种算法对比与真题演练现在让我们回到开篇的“一图流”并结合408真题风格进行总结和演练。7.1 核心对比表格特性单一连续分配固定分区分配动态分区分配动态可重定位分区分区特点整个用户区为一个分区分区数量、大小固定分区数量、大小动态变化分区动态变化可移动内部碎片有严重有严重基本无基本无外部碎片无无有严重无通过紧凑消除适用系统单道批处理、早期PC多道批处理已知作业多道批处理、分时对性能要求不苛刻的多道系统管理开销极小小中等维护空闲链/表大紧凑开销硬件需求无无无需要重定位寄存器7.2 408真题风格问题解析问题1某系统采用动态分区分配空闲分区链按地址递增排列。现有以下空闲分区单位KB空闲分区链起始地址-[100, 30] - [200, 50] - [300, 80] - [450, 60]现有进程请求序列P1(20KB), P2(70KB), P3(35KB)。使用首次适应算法分配请描述分配过程并指出最终的外部碎片情况。解析P1请求20KB从链首开始找。第一个分区[100,30]满足要求3020。分配后该分区剩余[100,10]假设从低地址开始分配。空闲链变为[100,10] - [200,50] - [300,80] - [450,60]。P2请求70KB从链首[100,10]开始不满足下一个[200,50]不满足下一个[300,80]满足8070。分配后该分区剩余[300,10]。空闲链[100,10] - [200,50] - [300,10] - [450,60]。P3请求35KB查找。[100,10]不满足[200,50]满足5035。分配后该分区剩余[200,15]。空闲链[100,10] - [200,15] - [300,10] - [450,60]。最终外部碎片存在四个小空闲分区10KB, 15KB, 10KB, 60KB。总空闲95KB但最大连续空闲块只有60KB。外部碎片显著。问题2为什么说最佳适应算法容易产生很多小碎片解析最佳适应算法总是挑选与进程需求最接近的空闲分区。分配后剩余的空闲分区大小 原分区大小 - 进程大小。因为这个差值是最小的所以产生的剩余分区也是尽可能小的。经过多次分配后内存中会积累大量这种极小的空闲分区它们可能小到无法满足任何后续进程的需求从而成为无法利用的外部碎片。8. 最佳实践与工程启示虽然现代操作系统主要使用非连续分配如分页、分段来从根本上避免外部碎片问题但连续分配管理的设计思想依然具有重要的学习价值和工程启示空间与时间的权衡动态可重定位分区通过“紧凑”牺牲时间性能来换取空间消除碎片。在软件设计中这种权衡无处不在例如用空间换时间的缓存或用时间换空间的压缩算法。数据结构的核心作用动态分区分配的性能和碎片情况很大程度上取决于空闲分区链的组织方式按地址或按大小排序和查找算法。这启示我们在解决资源调度、存储管理问题时选择合适的数据结构至关重要。“碎片”的普遍性碎片问题不局限于内存。磁盘存储、数据库存储、甚至网络资源分配中都有类似的“碎片化”问题。理解内存碎片的成因和解决方案有助于触类旁通。硬件与软件协同动态重定位需要硬件基址寄存器的支持。这体现了计算机系统中一个核心思想通过硬件辅助来解决软件层面的性能瓶颈或复杂性问题。现代CPU的TLB、MMU都是这一思想的延伸。对于备考408的同学建议理解本质不要死记硬背四种算法的名字要理解它们是如何在“连续性”约束下与“内部碎片”、“外部碎片”做斗争的演进过程。动手模拟在纸上或写简单代码模拟不同算法下的分配、回收、合并过程这是应对计算题和判断题的最佳方法。关联对比将连续分配与非连续分配尤其是分页管理进行对比理解后者是如何解决外部碎片这一核心痛点的。希望这份结合“一图流”的深度笔记能帮你彻底厘清内存连续分配管理的脉络。在复习时多问几个“为什么”理解算法背后的设计动机远比单纯记忆结论有效。
