我们来说连续分配存储管理。很多人看操作系统教材时看到“连续分配”“交换”“覆盖”“存储碎片”这些词只觉得概念绕考试背完就忘。但我自己调过内存通道、写过嵌入式启动级的分配器之后发现这东西其实是理解后面分页、分段、虚拟内存的一把钥匙。所谓连续分配本质上就是“每个进程或模块在物理内存里必须占一块连续的区域”它带来两个绕不开的副产品碎片和容量限制。而覆盖和交换就是早期系统在“内存不够用但又没有现代虚拟内存机制”的约束下用很朴素的手段跟这两个问题硬碰硬。今天这篇就把这几个机制从头到尾拆开讲包括怎么设计、怎么实现、怎么排查给你一套可以拿去直接用的经验。这篇文章适合刚学操作系统的学生也适合要接触嵌入式裸机内存管理、或者做内核里 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.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而不是 600500400800 2300KB。这里面有个最容易犯的错误忘记考虑覆盖模块之间会不会互相调用。如果排序的归并块在执行时还要读取另一个公共处理模块那这个公共处理模块就得和归并块同时驻留它就不能放进那个互斥覆盖区里得并入根模块或者给公共模块单独开辟区域。所以规划覆盖结构时必须先画出模块调用互斥图再算最大驻留集。2.3 覆盖和虚拟内存的界限在哪覆盖看起来很聪明为什么后来被虚拟内存彻底替代原因有三个对程序员极其不友好划分模块、计算覆盖区、手动管理都要开发者自己写。虚拟内存则由操作系统和 MMU 自动完成。粒度太粗覆盖以“模块”为单位换入换出虚拟内存在分页机制下是以“页”为单位更细更省空间。无法处理运行期才确定的依赖现代程序的动态链接、运行时加载插件覆盖模型很难优雅处理。但覆盖思想没有死。嵌入式 Bootloader、早期图形驱动的 HAL 层、以及一些内存受限的 SoC 固件里覆盖思想以“分阶段加载”的形式继续存在。控制好覆盖区等于你在没有 MMU 的环境里又给自己挣出了一大块可用内存。3. 连续分配的几种实现方式与分配算法3.1 固定分区简单但有先天缺陷固定分区是把内存提前切成若干大小固定的区域每个能装入一个进程。实现上只要一张分区表记录起始地址和占用标志。它的优点是极简分配时扫表找空闲分区释放时把标志位改回空闲即可。但问题也很明显分区大小固定进程如果超过分区大小就放不进去分区内残留的未使用空间形成内部碎片对进程大小分布不灵活一个要 9MB 的进程无法放进 8MB 的分区但内存里可能有一大堆 16MB 的分区用不上。工程中唯一还在流行“固定分区”的地方是嵌入式设备划分 MMU 保护域、或者实时系统为关键任务预留内存池。因为固定分区能严格保证资源上限避免某个任务把内存吃光。它牺牲了灵活性换来了可控性。3.2 动态分区主流分配策略对比动态分区不再提前切块而是每次按进程实际需要的空间从空闲区里找足够大的一块再切出需求大小给进程剩余部分成为新的空闲块。这就形成了外部碎片。四种经典算法大家都背过但你知道吗它们在不同的应用场景表现完全不一样算法分配策略速度外部碎片影响适用场景首次适应First Fit从头扫描找第一个足够大的空闲块快平均扫描次数少较大块集中在后半段低地址碎片多通用系统推荐首选循环首次适应Next Fit从上次位置继续找更快空闲块分布更均匀但大块少需要降低扫描开销时最佳适应Best Fit找最接近需求大小的空闲块慢全表扫描产生大量极小的碎片难合并空闲回收频繁、追求外碎最小化最坏适应Worst Fit找最大的空闲块切完还剩大的慢大块被切碎导致后续分配难很少用仅特殊场景我个人的实际经验是没有特殊理由做从未经充分测试的复杂选择先上首次适应。原因很简单它的平均扫描深度远小于最佳适应和最坏适应分配后会留下一个“后半段”的空闲区后续小型请求继续利用空闲块链表只要稍做优化加一个“起始地址排序”和一个“分裂后插入”逻辑速度完全可以接受。最佳适应看起来省空间实际很容易产生一堆几十字节的死角碎片碎片数量上升以后分配器会反复扫描可能找不到可用的位置即使在剩余总量足够的情况下也会分配失败。这种场景就是教科书里定义的“高外部碎片”非常难调。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 分配失败时的应急措施真实环境里“明明剩余内存很多却分配失败”的情况非常常见。我梳理一套排查顺序查看空闲块数量和最大空闲块大小如果空闲块数量巨大、最大块很小就是严重外部碎片。检查是否有紧凑接口有的话先触发轻量紧凑把低地址碎块推走。若无紧凑接口或紧凑失败启用交换策略换出一个常驻的长任务腾出整块连续区。若连交换区都不够考虑 panic或者等待其他进程退出。这里要插一个重要经验分配失败不一定是内存总量真的不足。我曾经在一个小型物联网平台上遇到“分配 100 字节失败但系统统计空闲内存还有 20KB”的怪现象最后发现空闲块被切成几十个 200~500 字节的碎片最大连续区不到 100 字节。这种情况下用什么策略都很难救除非一开始就减少小对象的频繁分配。后来我们在项目中加了一个内存池把固定大小的消息对象统一从池里分配连续分配器里的碎片压力才彻底缓解。这是一个从源头控制外部碎片的有效手段。5. 实操手写一个可用的连续分配管理器5.1 数据结构设计我给出一个最小实现它包含全部关键操作。设计目标支持初始化、分配、释放、合并使用首次适应输出碎片状况统计能力方便调试代码结构清晰能移植到裸机环境。核心数据结构是一个按地址排序的空闲链表。初始化的时候将整块内存作为一个超大 free blocktypedef 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; // 分配失败可能碎片过多 }这段代码里的几个细节非常值得注意对齐。没有对齐的分配器是危险的。ARM 处理器上访问非对齐地址会触发异常即使 x86 能容忍性能也会下降。最少按 8 字节对齐很多分配器按 16 字节做为了配合 SIMD 指令。块最小大小。切分后剩余部分不能太小。如果一个空闲块剩余部分连一个 block_t 头部都放不下这个剩余块就是纯垃圾。我一般在创建新块时判断remain sizeof(block_t) 8否则不切分整块给进程。空闲链表顺序。刚写分配器的人最常犯的错是链表不按地址排序释放合并时扫不到相邻块。空闲链表必须始终按内存地址递增排列这样合并时才能很快确认前后邻居。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 症状与原因速查表我把连续分配相关系统常见的故障整理成一张表你可以直接把它贴在手边现象直接原因深层原因对策内存总量够分配失败没有足够大的连续空闲块外部碎片严重合并、紧凑、换出大进程系统内存不足但“freelist”很长碎片块数量多算法选择不当或对象大小杂乱改用内存池/slab多次交换后系统性能骤降频繁换入换出换出策略选了正在活跃的进程按“阻塞时长优先级”选择牺牲者程序运行一段时间后地址错乱覆盖区被别的模块覆盖模块互斥关系没画全重新分析调用互斥图释放后再分配数据被破坏空闲块合并错误前后邻居状态标志失效启用边界标记和 magic 校验固定分区内利用率低内部碎片分区大小与作业需求不匹配改用动态分区或混合方式6.2 排查流程别一上来就改算法遇到碎片问题我踩过不少坑也总结出一套固定流程先判断再动手先量化再猜测。写一个统计函数输出 free 块数量、平均空闲大小、最大空闲块。如果 max_free_block_size 明显小于 total_free就是碎片问题。区分碎片和泄漏。泄漏的表现是 free 块数量减少、总空闲急剧下降碎片的表现是总空闲不变、最大空闲变小且块数巨多。快速验证方式禁用某个高频分配的小对象改成从静态缓冲分配观察碎片是否减轻。再调整分配策略从首次适应改最佳适应看最大空闲块分布是否变好。如果变好再考虑是否付出扫描开销。最后考虑换出或紧凑这两个操作影响大尽量放到系统空窗期执行。6.3 一些实战经验我在这里说一些常规文档不会写的东西都是我真金白银调出来的宁可多对齐不要省碎片。很多嵌入式分配器为了省内存把对齐降到 4结果 64 位访问时踩异常。一次异常排查半小时起步省那两个字节根本不值。不要给不同类型的对象混用同一个连续分配器。如果你既要分配 8 字节的节点又要分配 4KB 的缓冲区缓冲区块会逐渐被节点块分割。解决办法是按大小分桶比如小号统一用池分配大号走分配器。覆盖区不要塞递归调用。覆盖的前提是模块互斥递归调用会让一个模块在运行时重新进入自己逻辑上就会踩到另一个被覆盖的模块。真要递归就把递归部分放进根模块。交换和覆盖不要同时用。一边整进程换入换出一边模块级覆盖内存布局会变得完全不可预测调试时你会疯掉。单一方案清晰得多。个人体会是这样连续分配在现代大内存机器上显得“过时”但它的思维模式——按块管理内存、关注碎片、计算峰值驻留集——是每个做底层系统的人绕不开的基本功。尤其当你面对一块很小的、没有 MMU 的 SRAM 时覆盖和交换就是你的武器。很多在应用层写代码的同事理解不了为什么内存会“越用越碎”但在连续分配的世界里这就是日常。你能做的不是消灭碎片而是通过合理的算法和回收策略把碎片对系统的影响控制在一个可接受的范围里。最后再分享一个小技巧给你的分配器加一个“调试模式”它在每个分配块头部填充一个魔数释放时检查魔数是否被改写。这一招能抓到八成内存越界 bug而且开销只在调试时时存在发布版本直接关掉。如果你现在正在被内存碎片问题折磨先别急着换算法按我上面的流程先量化再动手多半能在半小时里定位到真正的问题根源。