分页分段前，先搞懂连续分配、覆盖、交换与碎片治理

我们来说连续分配存储管理。很多人看操作系统教材时，看到“连续分配”“交换”“覆盖”“存储碎片”这些词只觉得概念绕，考试背完就忘。但我自己调过内存通道、写过嵌入式启动级的分配器之后，发现这东西其实是理解后面分页、分段、虚拟内存的一把钥匙。所谓连续分配，本质上就是“每个进程或模块在物理内存里必须占一块连续的区域”，它带来两个绕不开的副产品：碎片和容量限制。而覆盖和交换，就是早期系统在“内存不够用，但又没有现代虚拟内存机制”的约束下，用很朴素的手段跟这两个问题硬碰硬。今天这篇就把这几个机制从头到尾拆开讲，包括怎么设计、怎么实现、怎么排查，给你一套可以拿去直接用的经验。

这篇文章适合刚学操作系统的学生，也适合要接触嵌入式裸机内存管理、或者做内核里 boot 阶段内存初始化的开发同学。你不用先背着一堆理论，跟着我的思路走，先理解为什么老设计这样做，再看代码和参数怎么落地，最后我会分享一些实际调试时踩过的坑。

1. 连续分配的基础思路与它为什么要存在

1.1 从最原始的物理内存说起

你得先回到一个前提：在没有 MMU 硬件辅助、或者 MMU 还没初始化的阶段，CPU 访问内存就是“地址总线给多少，物理内存就用多少”。这时候如果你把一个进程的代码、数据、栈拆得七零八落，CPU 就没法通过一套简单线性地址去访问它。所以最简单的办法就是，把整个作业放进一段连续的物理地址空间里。

这就是连续分配的全部初衷。它的好处其实是被低估的：

• 硬件开销为零，不需要页表、TLB 这些结构；
• 地址转换就是直接址访问，一次内存访问就能拿到数据；
• 内存保护可以通过一对边界寄存器（基址限长寄存器）完成，成本极低；
• 代码实现极其简单，几十行 C 代码就能写一个能用的分配器。

这也是为什么即使是在现代操作系统里，内核自身的启动阶段、嵌入式裸机程序、以及很多实时系统，依然大量使用连续分配。你不能因为分页漂亮就否定连续分配，在“可靠性优先、性能优先、而且内存紧张”的场景里，它反而是最合适的选择。

1.2 交换：把整个进程换进换出的代价与收益

连续分配的一个直接限制是：物理内存只能同时容纳尽量少的进程。假如只有 64MB 内存，而每个进程平均 30MB，那最多放两个完整的。第三个进程要运行怎么办？早期系统给的办法很简单——把它换进去，同时把另一个换出去。

交换的基本流程我可以用一个场景描述：系统里有进程 A、B、C，内存只够放两个。A 正在 I/O 等待，C 准备好了。这时候分配器发现找不到连续的空闲区域给 C，于是选择把 A 复制到磁盘交换区，回收 A 占用的整块内存，然后创建出足够大的空闲区，再把 C 从磁盘加载进去。整个过程叫“swap out / swap in”。

你可能会想，现在谁还用这种全进程换入换出呢？其实在内存极度受限的嵌入式环境、以及内核里某些死路检测场景，依然有 swap 的痕迹。但教科书上的交换主要告诉我们三个工程问题：

1. 换出谁？不能随便换，优先选择阻塞中、不会立刻运行的进程，否则刚换出去又要换回来，系统就抖动了。
2. 换出到哪里？需要预留交换区，通常是磁盘上的一个文件或独立分区。
3. 花了多久？整个进程传到磁盘再传回来，是毫秒级甚至上百毫秒级操作。频繁交换会明显拖慢响应。

交换本身不解决碎片，它只是“通过腾出一整块连续空间来解决放不下问题”的手段。真正和碎片硬碰硬的是覆盖技术和分配算法。

1.3 存储碎片：外部碎片和内部碎片的本质区别

连续分配绕不开碎片，我先帮你把两个碎片定义彻底掰清楚，这两概念混淆的人太多了。

• 外部碎片：发生在“动态分区”场景里，空闲块的总量足够，但没有一块连续的区域满足进程需求。就像停车场的空位加起来有 10 个，但都是分散的单个车位，停不了一辆能占 8 个连排车位的加长车。
• 内部碎片：发生在“固定分区”场景里，进程分到的分区比自己实际所需大，里面有一部分被白白浪费。比如分区固定 16KB，进程只要 10KB，那 6KB 就死在那里，别人也用不了。

这两个碎片的治理方向完全不同：外部碎片靠紧凑、合并、选择合适分配策略来缓解；内部碎片靠精确设定分区大小、混合分配、或者干脆放弃固定分区来消除。下面我会分章节讲。

2. 覆盖技术的手工虚拟内存

2.1 覆盖解决什么：程序太大，但内存确实不够

覆盖和交换是两种不同维度的手段。覆盖更早、也更是“程序员自己做内存管理”的思路。它的出发点是：一个程序虽然整体很大，但执行过程中不是每一个模块都会被同时用到。那么，我为什么不把这些模块错开放在同一块内存区域里呢？

给我一个场景：一个大型数据处理程序有主模块、输入模块、排序模块、报表模块。主模块全程驻留，输入模块只在开头用，排序模块在中间用，报表模块在结尾用。如果严格按连续分配，整个程序可能要 5MB；但如果你给输入模块、排序模块、报表模块规划出同一个共享区域，比如它们都能在 2MB 的覆盖区里跑，那整个程序驻留内存只需要主模块 1MB 加上覆盖区 2MB，一共 3MB。省了 40%。

这个技术在磁盘容量和内存容量都贵得要命的年代，几乎是唯一能让大型程序跑起来的办法。它是“手动版虚拟内存”的关键所在：因为虚拟内存的本质就是“只把我用到的部分放进来，不用的留在磁盘上”，覆盖就是还没有硬件支持时，由工程师手工完成换入换出。

2.2 覆盖区怎么规划才合理

规划覆盖区有一套可以计算的规则，别凭感觉来。我把一个两层的覆盖结构拆给大家看：

• 根模块：一直驻留内存的部分，包含主函数、公共数据、调度逻辑。根模块的大小记作 S_root。
• 覆盖区：一块固定大小的区域，同一时间只能放一个（或一组互斥的）覆盖模块。

关键公式是：覆盖区的大小 = 所有“在同一时刻可能被同时调用的模块大小之和”的最大值，而不是所有覆盖模块的大小之和。

比如排序模块分为三块：读数据块 600KB、归并块 500KB、写结果块 400KB，这三块在运行时有先后关系，不可能同时存在。流程可能是“读数据块 → 归并块 → 写结果块”，那它们的互斥组合中最大单一成员是 600KB。如果你又有另一个报表模块，大小 800KB，它和排序模块不可能同时运行，所以可以共享同一个覆盖区，覆盖区大小就取 max(600, 500, 400, 800) = 800KB，而不是 600+500+400+800 = 2300KB。

这里面有个最容易犯的错误：忘记考虑覆盖模块之间会不会互相调用。如果排序的归并块在执行时还要读取另一个公共处理模块，那这个公共处理模块就得和归并块同时驻留，它就不能放进那个互斥覆盖区里，得并入根模块或者给公共模块单独开辟区域。所以规划覆盖结构时，必须先画出模块调用互斥图，再算最大驻留集。

2.3 覆盖和虚拟内存的界限在哪

覆盖看起来很聪明，为什么后来被虚拟内存彻底替代？原因有三个：

• 对程序员极其不友好：划分模块、计算覆盖区、手动管理，都要开发者自己写。虚拟内存则由操作系统和 MMU 自动完成。
• 粒度太粗：覆盖以“模块”为单位换入换出，虚拟内存在分页机制下是以“页”为单位，更细更省空间。
• 无法处理运行期才确定的依赖：现代程序的动态链接、运行时加载插件，覆盖模型很难优雅处理。

但覆盖思想没有死。嵌入式 Bootloader、早期图形驱动的 HAL 层、以及一些内存受限的 SoC 固件里，覆盖思想以“分阶段加载”的形式继续存在。控制好覆盖区，等于你在没有 MMU 的环境里又给自己挣出了一大块可用内存。

3. 连续分配的几种实现方式与分配算法

3.1 固定分区：简单但有先天缺陷

固定分区是把内存提前切成若干大小固定的区域，每个能装入一个进程。实现上只要一张分区表记录起始地址和占用标志。

它的优点是极简：分配时扫表找空闲分区，释放时把标志位改回空闲即可。但问题也很明显：

1. 分区大小固定，进程如果超过分区大小就放不进去；
2. 分区内残留的未使用空间形成内部碎片；
3. 对进程大小分布不灵活，一个要 9MB 的进程无法放进 8MB 的分区，但内存里可能有一大堆 16MB 的分区用不上。

工程中唯一还在流行“固定分区”的地方，是嵌入式设备划分 MMU 保护域、或者实时系统为关键任务预留内存池。因为固定分区能严格保证资源上限，避免某个任务把内存吃光。它牺牲了灵活性，换来了可控性。

3.2 动态分区：主流分配策略对比

动态分区不再提前切块，而是每次按进程实际需要的空间，从空闲区里找足够大的一块，再切出需求大小给进程，剩余部分成为新的空闲块。这就形成了外部碎片。

四种经典算法大家都背过，但你知道吗，它们在不同的应用场景表现完全不一样：

我个人的实际经验是：没有特殊理由做从未经充分测试的复杂选择，先上首次适应。原因很简单：

• 它的平均扫描深度远小于最佳适应和最坏适应；
• 分配后会留下一个“后半段”的空闲区，后续小型请求继续利用；
• 空闲块链表只要稍做优化，加一个“起始地址排序”和一个“分裂后插入”逻辑，速度完全可以接受。

最佳适应看起来省空间，实际很容易产生一堆几十字节的死角碎片，碎片数量上升以后，分配器会反复扫描可能找不到可用的位置，即使在剩余总量足够的情况下也会分配失败。这种场景就是教科书里定义的“高外部碎片”，非常难调。

3.3 伙伴系统：折中方案

伙伴系统算是对连续分配的一种增强。它把内存按 2 的幂次大小分块管理，比如请求 3KB 就分配大小为 4KB 的块；释放时，如果相邻的两个同大小块可以合并成更大的块，就立刻合并，尽量减少外部碎片。

它的好处是：

• 分配和释放都是 O(log N) 级别，非常快；
• 天然支持块的合并，碎片控制效果好；
• 在 Linux 内核物理页面分配、以及一些嵌入式 RTOS 里都有成熟实现。

坏处是内部碎片不可避免：你申请 3KB，系统给你 4KB，浪费 25%。而且如果频繁申请各种奇怪大小的内存，块之间的合并机会减少，最终仍然容易形成“大块被小块卡死”的状态。实际使用中，伙伴系统往往会搭配 slab 分配器使用：物理内存交给伙伴系统管大块，内核对象用 slab 机制收集同大小对象复用。

4. 碎片处理与回收策略的工程实现

4.1 紧凑：把内存“推一推”合并出大块

针对外部碎片，最直观的手段是紧凑（compaction）：把已分配的区域全部向内存的低地址方向移动，让所有空闲块汇合成一块大连续区。

听起来简单，做起来极其麻烦。你移动一个进程的过程，相当于复制了它的整个地址空间，然后还要修正它内部所有指针。如果这个进程正在和外设做 DMA 传输，指向缓冲区地址的 DMA 描述符是硬件层面的，你移动完内存，外设并不知道，数据就会写到旧地址去，直接造成数据损坏。所以在做紧凑之前，必须暂停整个进程、收回所有 I/O 操作，这在实时系统里几乎是不可接受的。

工程上怎么做？通常不是一次性把全部内存“整理得漂漂亮亮”，而是利用进程换进换出的时机“顺手”做一次轻量迁移。例如，进程 A 被换出后，正好它的后面有碎片，系统可以在换出期间把前一个进程向后挪一挪，形成一个大空闲区。这就是“择机整理”，代价被隐藏在磁盘 I/O 的等待时间里，用户无感。如果你要自己实现一个嵌入式分配器，紧凑功能一定要做成可选，并且要求访问该内存的任务暂停，否则不要碰。

4.2 空闲块合并与边界标记法

动态分区释放内存时，最关键的是判断“这块内存是不是和旁边的空闲块相邻”，如果相邻就要合并。但如果每次释放都扫描整个空闲链表，性能会很难看。解决这个问题的方式叫边界标记法：

在每一块已分配区域和空闲区域的头部和尾部，都保存一个“分配状态”标志位，并记录块大小。释放时，分配器可以直接查看当前块前一个结构的尾部标记和后一个结构的头部标记，知道相邻块是否空闲。如果空闲，就合并并在 O(1) 时间内完成更新。

我在自己写嵌入式分配器时，结构设计大概是这样：

typedef struct mem_block { uint32_t size; // 整个块大小，包括 overhead uint32_t magic; // 保护字，调试用 uint8_t allocated; // 1=占用, 0=空闲 struct mem_block *next; // 空闲链表的 next，只在空闲块中有效 // ... 用户数据从这之后开始 } mem_block_t;

注意：空闲块和已分配块对同一块内存“结构复用”时要非常小心。空闲块里需要有 next 指针，但已分配块里不需要。用一个 union 能省 4 字节，但一旦调试起来就很难受。我建议保留下一个指针字段，别在这点开销上抠，省出来的空间不够弥补一次踩内存 debug 的崩溃。

合并代码的关键路径是尾部节点读取：

if (!after->allocated) { // 合并当前块和后面的块 block->size += after->size; remove_from_free_list(after); }

如果不做尾部标记，你需要找到 after 前的空闲块，就得遍历。边界标记的精髓就是用尾部标记换时间。大部分教学示例不重视这个点，但实际内存碎片频繁时，这个 O(1) 合并直接影响分配器的稳定性。

4.3 分配失败时的应急措施

真实环境里“明明剩余内存很多，却分配失败”的情况非常常见。我梳理一套排查顺序：

1. 查看空闲块数量和最大空闲块大小：如果空闲块数量巨大、最大块很小，就是严重外部碎片。
2. 检查是否有紧凑接口：有的话先触发轻量紧凑，把低地址碎块推走。
3. 若无紧凑接口或紧凑失败，启用交换策略：换出一个常驻的长任务，腾出整块连续区。
4. 若连交换区都不够：考虑 panic，或者等待其他进程退出。

这里要插一个重要经验：分配失败不一定是内存总量真的不足。我曾经在一个小型物联网平台上遇到“分配 100 字节失败，但系统统计空闲内存还有 20KB”的怪现象，最后发现空闲块被切成几十个 200~500 字节的碎片，最大连续区不到 100 字节。这种情况下用什么策略都很难救，除非一开始就减少小对象的频繁分配。后来我们在项目中加了一个内存池，把固定大小的消息对象统一从池里分配，连续分配器里的碎片压力才彻底缓解。这是一个从源头控制外部碎片的有效手段。

5. 实操：手写一个可用的连续分配管理器

5.1 数据结构设计

我给出一个最小实现，它包含全部关键操作。设计目标：

• 支持初始化、分配、释放、合并；
• 使用首次适应；
• 输出碎片状况统计能力，方便调试；
• 代码结构清晰，能移植到裸机环境。

核心数据结构是一个按地址排序的空闲链表。初始化的时候，将整块内存作为一个超大 free block：

typedef struct allocator { uint8_t *base; // 内存区起始基址 size_t total_size; // 总大小 block_t *free_head; // 空闲链表头 uint32_t alloc_count; // 当前已分配块数量 size_t alloc_bytes; // 当前已分配总字节数 size_t frag_max; // 当前最大空闲块 } allocator_t;

5.2 分配函数：切分空闲块

分配逻辑如下：

block_t *alloc_contig(allocator_t *al, size_t need) { need = align_up(need, 8); // 对齐到 8 字节 block_t *cur = al->free_head; while (cur) { if (!cur->allocated && cur->size >= need + sizeof(block_t)) { // 找到足够大的空闲块，切分 block_t *new_block = (block_t *)((uint8_t *)cur + need); new_block->size = cur->size - need; new_block->allocated = 0; new_block->next = cur->next; cur->size = need; cur->allocated = 1; cur->next = NULL; // 空闲链表重接 if (al->free_head == cur) al->free_head = new_block; else replace_pre_next(...); // 前驱节点重链 al->alloc_count++; al->alloc_bytes += need; return cur; } cur = cur->next; } return NULL; // 分配失败，可能碎片过多 }

这段代码里的几个细节非常值得注意：

1. 对齐。没有对齐的分配器是危险的。ARM 处理器上访问非对齐地址会触发异常，即使 x86 能容忍，性能也会下降。最少按 8 字节对齐，很多分配器按 16 字节做，为了配合 SIMD 指令。
2. 块最小大小。切分后剩余部分不能太小。如果一个空闲块剩余部分连一个 block_t 头部都放不下，这个剩余块就是纯垃圾。我一般在创建新块时判断remain >= sizeof(block_t) + 8，否则不切分，整块给进程。
3. 空闲链表顺序。刚写分配器的人最常犯的错是链表不按地址排序，释放合并时扫不到相邻块。空闲链表必须始终按内存地址递增排列，这样合并时才能很快确认前后邻居。

5.3 释放与合并

释放时要把块标记为空闲，然后找前后邻居合并。因为我用了相邻地址，可以这样：

void free_contig(allocator_t *al, block_t *blk) { blk->allocated = 0; // 尝试向低地址合并 block_t *prev = al->free_head; while (prev && (uint8_t *)prev + prev->size < (uint8_t *)blk) { if (prev->next == blk) break; prev = prev->next; } if (prev && (uint8_t *)prev + prev->size == (uint8_t *)blk && !prev->allocated) { prev->size += blk->size; // 合并 blk = prev; // 从合并后的块继续 } // 尝试向高地址合并 block_t *next = (block_t *)((uint8_t *)blk + blk->size); if ((uint8_t *)next < al->base + al->total_size && !next->allocated) { blk->size += next->size; remove_from_free_list(next); } // 按地址插入空闲链表 insert_sorted(al, blk); al->alloc_count--; al->alloc_bytes -= blk->size; // 注意这里是释放前块大小需要提前记录 }

合并操作 O(n) 是因为遍历链表找前驱，但只要链表有序，这已经比“先全部扫描再判断”好很多。更进一步的优化是上一节说的边界标记法，在块尾存一个 size 和状态，这样释放时 O(1) 判断前一块。这里为了可读性仍然保留顺序扫描。

5.4 覆盖模块加载管理器

用一个非常简化的 overlay 管理器来说明覆盖思想如何落地：

typedef struct overlay_module { uint32_t id; uint32_t size; void (*entry)(void); // 加载来源（磁盘偏移） uint32_t file_offset; } overlay_module_t; #define OVERLAY_REGION_SIZE 8192 static uint8_t overlay_region[OVERLAY_REGION_SIZE]; static uint32_t cur_overlay_id = 0; int load_overlay(uint32_t id) { if (id == cur_overlay_id) return 0; // 从外部存储读取模块数据到覆盖区 if (read_external(id, overlay_region, overlay_size[id]) < 0) { return -1; } cur_overlay_id = id; return 0; }

实际工程中，覆盖管理器要注意两点：一是写入覆盖区前确保没有任何指针还指向旧模块里面；二是模块的重定位问题——如果模块里含绝对地址引用，加载时得重定位。这两点恰恰是最容易出 bug 的地方。所以覆盖模块通常会被设计成“位置无关代码”，所有地址都用相对寻址，加载后无需修复。这也是为什么早期很多系统模块都是汇编写的，因为位置无关手工处理太痛苦。

5.5 测试与验证

分配器写完之后，别急着上线。我常用的测试套路：

• 用固定种子随机执行 allocate/free 数千次，检查 alloc_bytes 和 free 块的尺寸总和是否等于 total_size；
• 在释放前对块内填充0xAA，释放时检查增量区域的内存是否被外部改写；
• 故意循环分配小对象再释放，观察最大空闲块是否能恢复原状，判断合并是否有效；
• 模拟分配失败路径，确认返回值处理和日志。

这套测试救过我很多次，碎片相关 bug 大多出现在“连续分配、连续释放”之后，峰值内存没超过上限，但分配器把空闲链表搞坏了。

6. 常见问题与排查技巧实录

6.1 症状与原因速查表

我把连续分配相关系统常见的故障整理成一张表，你可以直接把它贴在手边：

6.2 排查流程：别一上来就改算法

遇到碎片问题，我踩过不少坑，也总结出一套固定流程，先判断再动手：

1. 先量化，再猜测。写一个统计函数，输出 free 块数量、平均空闲大小、最大空闲块。如果 max_free_block_size 明显小于 total_free，就是碎片问题。
2. 区分碎片和泄漏。泄漏的表现是 free 块数量减少、总空闲急剧下降；碎片的表现是总空闲不变、最大空闲变小且块数巨多。
3. 快速验证方式：禁用某个高频分配的小对象，改成从静态缓冲分配，观察碎片是否减轻。
4. 再调整分配策略：从首次适应改最佳适应，看最大空闲块分布是否变好。如果变好，再考虑是否付出扫描开销。
5. 最后考虑换出或紧凑：这两个操作影响大，尽量放到系统空窗期执行。

6.3 一些实战经验

我在这里说一些常规文档不会写的东西，都是我真金白银调出来的：

• 宁可多对齐，不要省碎片。很多嵌入式分配器为了省内存把对齐降到 4，结果 64 位访问时踩异常。一次异常排查半小时起步，省那两个字节根本不值。
• 不要给不同类型的对象混用同一个连续分配器。如果你既要分配 8 字节的节点，又要分配 4KB 的缓冲区，缓冲区块会逐渐被节点块分割。解决办法是按大小分桶，比如小号统一用池分配，大号走分配器。
• 覆盖区不要塞递归调用。覆盖的前提是模块互斥，递归调用会让一个模块在运行时重新进入自己，逻辑上就会踩到另一个被覆盖的模块。真要递归，就把递归部分放进根模块。
• 交换和覆盖不要同时用。一边整进程换入换出，一边模块级覆盖，内存布局会变得完全不可预测，调试时你会疯掉。单一方案，清晰得多。

个人体会是这样：连续分配在现代大内存机器上显得“过时”，但它的思维模式——按块管理内存、关注碎片、计算峰值驻留集——是每个做底层系统的人绕不开的基本功。尤其当你面对一块很小的、没有 MMU 的 SRAM 时，覆盖和交换就是你的武器。很多在应用层写代码的同事理解不了为什么内存会“越用越碎”，但在连续分配的世界里，这就是日常。你能做的不是消灭碎片，而是通过合理的算法和回收策略，把碎片对系统的影响控制在一个可接受的范围里。

最后再分享一个小技巧：给你的分配器加一个“调试模式”，它在每个分配块头部填充一个魔数，释放时检查魔数是否被改写。这一招能抓到八成内存越界 bug，而且开销只在调试时时存在，发布版本直接关掉。如果你现在正在被内存碎片问题折磨，先别急着换算法，按我上面的流程先量化再动手，多半能在半小时里定位到真正的问题根源。