我最早真实感受到“连续分配存储管理”这几个字的重量是在写一个模拟内存分配的小项目时明明内存总量够大程序却不断报“分配失败”我盯着控制台上那块越碎越小的空闲区列表第一次体会到什么叫存储碎片比容量不足更折腾人。这篇文章想把这段经历背后的东西讲透包括覆盖、交换这两个经典的内存扩充手段以及它们和碎片之间那些容易被忽略的连带关系。如果你正在学操作系统、做嵌入式相关开发或者准备面试这篇文章会帮你把这些概念串成一条线而不是让它们各自躺在教科书的不同章节里。1. 连续分配到底在解决什么问题1.1 内存管理首先得回答“程序放哪”任何程序要运行第一步都是把指令和数据放进内存。连续分配存储管理指的是操作系统为每个进程分配一段地址连续的内存区域进程在这块区域内按顺序存放自己的代码和数据。为什么非要“连续”因为在早期的硬件和操作系统设计里连续分配让地址转换极其简单。CPU发出的逻辑地址加上一个基址寄存器里的起始地址就能得到物理地址这个过程只要一个加法操作不需要额外的查表、硬件遍历、多级索引。对当年那些内存以KB为单位的系统来说能用最少的硬件代价完成内存访问比节省一点点空间重要得多。你可以把内存想象成一条很宽的马路连续分配就是给每辆车划分一段连续的行驶区段车只能在属于自己的那一段里往前走。好处是管理简单、隔离清晰坏处是如果车很小却分到很长的路段或者车辆来来去去把整条路切得七零八落道路实际利用率就会直线下降。这两个坏处对应的就是内部碎片和外部碎片后面会展开聊。1.2 从固定分区到动态分区两种思路的取舍连续分配具体落地时主要分两个流派固定分区和动态分区。固定分区的思路是在系统启动时把内存划分为若干个大小固定、互不重叠的分区。每个分区可以装入一个进程。按分区大小是否相同还分等长分区和不等长分区。贴合实际的是不等长分区比如系统内存在启动时就规划好一个4KB分区、两个8KB分区、一个16KB分区进程来了就找能装下自己的那个分区进入。固定分区最大的优势是管理逻辑极简一个分区表就能记录所有分区的使用情况。但它有一个天生的浪费如果一个进程只需要6KB内存而系统最小的空闲分区是8KB那这6KB进程会被放入8KB分区剩下的2KB就彻底用不上了。这部分无法给任何其他进程使用的空间就是内部碎片。动态分区则不再预设大小进程需要多少内存就从当前空闲内存中切一块刚好够用的给出去。这个问题立刻变成了“怎么找一块合适的空闲块”于是诞生了首次适应、最佳适应、最坏适应三种经典分配算法。动态分区没有内部碎片但会引入新的问题进程不断分配、释放内存中会留下许多大小不一、散布各处的空闲区这些空闲区总和可能很大但单独一块都装不下新进程这就是外部碎片。为了防止外部碎片影响分配系统可能需要做“紧凑”把进程都往一端靠拢把碎片聚合成大块代价是搬运所有进程的内存内容非常耗时。固定分区和动态分区的核心差异可以看这张表对比项固定分区动态分区分区大小启动时固定按需动态划分内部碎片明显基本没有外部碎片不存在严重时可用率骤降分配算法查表即可需要搜索空闲块复杂度低较高从固定分区到动态分区本质上是拿“管理复杂度”换“空间利用率”。但动态分区做到极致也无法根治外部碎片因为只要要求进程占用的物理地址连续空闲块被切割成零碎小块就只是一个时间问题。2. 覆盖和交换内存不够时的两种“变通术”连续分配解决“程序放哪”的问题但程序需要的空间可能比实际可用内存还大。覆盖和交换就是在这一背景下出现的两种内存扩充技术思路完全不同非常容易被混为一谈。2.1 覆盖技术把程序拆开让模块共享同一块内存覆盖Overlay解决的是“单个程序太大装不进内存”的问题。它的核心思想是程序虽然大但并非所有模块都需要同时驻留内存。某些相互独立的模块完全可以先后使用同一块内存区域。最典型的结构是程序由一个常驻部分和若干覆盖段组成。常驻部分始终留在内存里负责调度和公共功能覆盖区是一块固定大小的内存在程序运行的不同阶段从外存把不同的覆盖段读进来覆盖掉之前的内容。我第一次理解覆盖是在看一个早期编译器的设计说明。编译器工作时词法分析、语法分析、代码生成这些阶段并不是同时运行的它们之间有先后依赖但彼此并不会同时活跃。于是编译器的设计者把它们设计成互相覆盖的模块内存里只保留当前阶段需要的代码和数据一个原本需要很大内存的编译器就能装进很小的内存空间里运行。覆盖技术看起来很美但它有一个不小的代价程序模块之间的覆盖关系往往需要程序员手动分析并声明。程序员要清楚地知道哪些模块不可能同时执行才能安全地让它们共享同一块内存。一旦分析错程序可能在运行到某个分支时覆盖掉正在使用的模块导致难以排查的崩溃。为了降低手工负担系统也提供自动覆盖的机制程序员只需说明模块间的调用关系构建工具会据此自动生成覆盖结构。但无论自动还是手动覆盖技术本身都有一个无法回避的弱点——它增加的是程序的设计复杂度并不减少程序实际运行时的总工作量反而因为模块需要反复从外存装载运行效率会下降。覆盖的适用场景本质上是“单个进程的逻辑占用空间超过物理内存但执行阶段彼此独立”。在个人电脑时代这种东西已经很少见了因为虚拟内存和分页机制已经接管了这个任务但在早期系统、嵌入式环境以及部分特殊设备上覆盖依然是可行的内存节约手段。2.2 交换技术把整个进程切换到外存去交换Swapping则站在完全不同的层面处理内存不足。它不关心进程内部模块之间的关系而是把整个进程当作一个单位当内存紧张时把一个或多个进程从内存搬到外存通常是专用的交换区或者系统磁盘上的交换文件腾出内存给需要的进程等时机合适再把这些进程从外存换回内存。交换的最大价值在于它突破了“内存只能装下当前正在运行的程序”的限制允许多个进程轮流使用物理内存。你可以把交换理解成宿舍里的“轮流值班”床位不够就让不值班的人先去隔壁休息室待着等轮到自己了再回来。交换的代价非常直观那就是磁盘I/O。把一个进程整体换出再换入要搬运的是这个进程的全部内存映像哪怕它大部分代码在等待期间并没有被执行。这个过程非常慢——磁盘速度比内存慢几个数量级——所以交换必须谨慎触发不能太频繁。实际操作中交换的触发条件一般包括操作系统内存分配失败、有高优先级进程等待内存、批处理系统需要调整进程集合等。换出的对象通常是阻塞的、低优先级的进程因为它们在不久的将来不需要运行换入的对象则相反是已经就绪且能够运行的进程。关于交换目标区域我有一个很实际的建议无论是交换区还是交换文件都应该放在尽可能快的磁盘上。机械硬盘时代很多人会把交换区放在磁盘最内侧的区域因为那里寻道距离更短、传输速度也相对稳定放到SSD时代这个问题淡化了很多但你依然不应该把交换区放在网络盘上。2.3 覆盖和交换到底哪里不一样很多初学者分不清覆盖和交换因为它们都是为了解决“内存不够用”的问题。区别在于覆盖是程序内部做的事情它以模块为单位一个进程内部的内存区域可以重复使用交换是操作系统做的事情它以进程为单位整个进程被搬进搬出。覆盖需要程序员的参与和静态分析交换是操作系统的自动决策对应用程序透明。用一个不太严谨但好记的类比覆盖是“同一个锅轮流炒不同的菜”交换是“把不用的锅收进柜子把要用的锅拿出来”。实际系统里交换和覆盖完全可以同时使用覆盖用来压缩单个进程的驻留需求交换用来协调多个进程对内存的竞争。后来虚拟内存技术出现后覆盖基本退场交换还以“换页/换段”的形式留在系统中只是粒度更细了。3. 存储碎片连续分配的“天然硬伤”3.1 内部碎片和外部碎片到底哪里“碎”固定分区造成的是内部碎片字面意思是碎片出在“分配出去的内存块内部”。你申请了10KB系统给你个12KB的分区那2KB就永远浪费在分区里谁也看不见、谁也拿不走。动态分区造成的是外部碎片碎片出在“已经分配的内存块之间”。一堆已分配进程之间散布着大小不等的空闲区这些空闲区单独看都不大但总和可能很可观。搞笑的是这种碎片恰恰是动态分配“灵活”带来的副作用——因为它根据进程实际需求切大小切来切去把内存切成了“豆腐渣”。内部碎片和外部碎片的防范方向完全不同。内部碎片可以通过把固定分区换成动态分区来消除或者把分区粒度做得更细外部碎片则几乎无法靠“分配合适大小”来消除只能靠紧凑、合并、或者从根本上换用分页机制来规避。3.2 碎片是怎么一步步累积的一个小型推演我用一个具体数字来展示外部碎片的恶化过程。假设内存总量100KB进程A申请30KB操作系统分配[0,30)。进程B申请20KB操作系统分配[30,50)。进程C申请40KB操作系统分配[50,90)。目前空闲区是[90,100)共10KB。进程B退出释放[30,50)现在空闲区有[30,50)和[90,100)共30KB。进程D申请25KB假设用首次适应算法在[30,50)里切出25KB剩下[55,50)这不可能应该是[55,50)? 实际上是[30,55)分配剩下[55,50)? 不对[30,50)大小20KB不够25KB所以会跳过这块进入[90,100)也不够分配失败。但此时一个25KB的进程实际上无法分配因为两个空闲区都不够大尽管总空闲空间30KB。这个例子暴露了连续分配最尴尬的地方空闲空间总量足够但“连续”的空闲空间不够。50KB的空闲空间分布在两个孤岛上新进程必须属于某一个岛才能上岛。注意如果用最佳适应算法事情可能更糟最佳适应会在所有空闲块中找“最小能满足”的那块长期运行后内存中会留下大量非常小的、几乎无用的碎片这些碎片加起来可能不少但每一个都小到没有任何进程能用。这就是为什么虽然最佳适应从局部看最“节省”但在高强度动态场景下反而常常表现不佳。3.3 碎片整理的常见手段合并、紧凑、分配策略优化清理碎片有三个层面可以下手。第一个层面是“合并”。动态分区分配器在释放内存时如果发现相邻区域也是空闲的就把它们合并成更大的空闲块。这是最基础的操作必须做但只能处理“相邻”的空闲区对不相邻的碎片无能为力。第二个层面是“紧凑”。紧凑的核心操作是把所有已分配的内存块向内存一端移动让分散的空闲区汇合成一个大块。这个操作看起来简单但要移动所有进程的代码和数据搬运量极大。只有在支持动态重定位也就是有重定位寄存器辅助的系统中紧凑才是可实现的否则移动进程后程序就跑不起来了。紧凑通常是“好钢用在刀刃上”在分配失败但总空闲空间足够时才会触发。第三个层面是“分配策略优化”。首次适应倾向于在内存低地址端留下少量碎片但整体分配速度快最佳适应倾向于产生大量微小碎片大块内存保留得较好最坏适应每次都选最大的空闲块来切试图让剩余部分仍然可用但它会让大块迅速被切碎。我在实际做模拟时发现首次适应往往是最稳定的日常选择不是因为性能最好而是因为它在速度、内存利用率和实现复杂度之间取得了最舒服的平衡。这三个层面都只是“缓解”碎片并没有真正“解决”碎片。只要系统要求进程物理地址连续碎片就是一种必然的熵增。解决碎片问题的终极方案是放弃“连续分配”这个前提采用分页或分段机制让一个进程的地址空间可以映射到不连续的物理页框上——这就进入了另一个世界。顺着这个逻辑你就能理解为什么后来分页会成为主流。4. 实操记录用Python写一个内存分配模拟器直观看到碎片光讲理论没有感觉我建议你也自己写一个最简单的内存分配模拟器。我当初用Python花了大概一个晚上写完跑完一圈后对碎片的感受完全不一样了。4.1 模拟固定分区与内部碎片固定分区很简单维护一个分区大小列表和一个占用标记列表就行。下面这段代码演示了不等长固定分区下的分配逻辑partitions [64, 64, 128, 256, 512] # 每个分区的KB大小 occupied [False] * len(partitions) def fixed_allocate(size_kb): for i, p in enumerate(partitions): if not occupied[i] and p size_kb: occupied[i] True internal_fragment p - size_kb return i, internal_fragment return None, None跑一个例子进程请求100KB系统遍历后找到128KB分区返回分区编号2内部碎片是28KB。这个28KB就永远浪费了这是固定分区的“结构性浪费”。4.2 模拟动态分区与三种分配算法动态分区的核心数据结构是空闲区链表。每个空闲区记录起始地址和长度分配时按算法选择一块进行切割。free_list [[0, 1024]] # 每个元素是 [start, size] def first_fit(size): for block in free_list: start, bsize block if bsize size: block[1] - size if block[1] 0: free_list.remove(block) return start bsize return None def best_fit(size): best None best_idx -1 for idx, block in enumerate(free_list): start, bsize block if bsize size and (best is None or bsize best[1]): best (start, bsize) best_idx idx if best is None: return None start, bsize best free_list[best_idx][1] - size if free_list[best_idx][1] 0: free_list.pop(best_idx) return start bsize释放时不能只是把空闲区加回去必须做相邻合并否则连续几次分配释放之后空闲区链表就会充满碎片def free_block(start, size): free_list.append([start, size]) free_list.sort() # 合并相邻空闲区 merged [] for block in free_list: if merged and merged[-1][0] merged[-1][1] block[0]: merged[-1][1] block[1] else: merged.append(block) free_list[:] merged这个合并步骤非常关键。我在最初写的版本里偷懒没有做合并跑了几十次随机分配释放之后发现明明释放了大量内存空闲空间却越来越碎新进程经常分配失败。加上合并之后情况立刻改善很多——这正对应了真实分配器里“合并是基本功”的说法。4.3 用模拟器观察三种算法的差异我写了一个随机负载生成器随机创建进程、随机让进程退出记录分配失败率。跑完1000次操作以后首次适应整体最稳分配失败率最低空闲区分布比较均匀。最佳适应经常留下大量又小又碎的空闲块失败率最高而且每次分配都要遍历整条链表速度也最慢。最坏适应大块空闲区被迅速消耗中后期分配失败率明显上升。这个结果和教科书上写的一致但你亲手跑出来之后才会真的相信“最佳适应不是最优选择”这个听起来反直觉的结论。4.4 模拟交换的代价交换的模拟更偏向策略而不是数据结构。核心是换出进程要记录它的完整地址空间还要标记它占用的内存已释放换入时要把地址空间重新拷贝回内存并更新进程的内存映射。class Process: def __init__(self, pid, size): self.pid pid self.size size self.in_memory True self.addr_space bytearray(size) def swap_out(proc): proc.in_memory False release_memory(proc.addr_space) write_to_swap(proc.pid, proc.addr_space) def swap_in(proc): addr_space read_from_swap(proc.pid) addr allocate_memory(len(addr_space)) proc.addr_space addr_space proc.in_memory True当你跑一遍交换模拟你会立刻看到交换的代价每次换入换出都要做一次全量读写。如果进程只是偶尔等待某个阻塞事件换出再换入的成本很可能比让它占着内存等更贵。所以在真实系统里交换算法会尽量选择“短时间内不会运行”的进程换出而不是随便挑一个倒霉的进程。5. 扩展思考覆盖、交换与分页之间的关系5.1 为什么覆盖被淘汰交换却演化成了分页覆盖和交换本质上都是“时间换空间”用更多的磁盘I/O和软件开销换取有限内存的更大吞吐。覆盖需要程序员深入参与在三五十年前的软件规模下可行到了现代应用动辄千万行代码的体量靠人工静态分析模块覆盖关系根本不现实。交换把整个进程搬进搬出代价太大于是操作系统自然想到能不能不搬整个进程只搬进程的一部分这个思路一路演化最终变成了请求分页以页为单位按需加载、按需淘汰内存和外存之间的数据流动粒度从整个进程缩小到页通常4KB。分页不仅解决了内存不足还顺带攻克了外部碎片——页面大小固定物理内存被分成了等长的页框不再需要连续分配碎片的概念被彻底改写。5.2 连续分配在今天还有没有用很多人可能觉得连分配都够老了分页才是王道。事实上连续分配在今天依然有不可替代的场景。嵌入式系统中很多实时性要求高的环境依然采用静态分区甚至固定分区因为实时系统需要可预测的分配延迟动态分区和分页的复杂度会引入不可控抖动。内核本身的启动阶段也普遍使用简单的连续分配内核代码和数据在早期自举阶段往往被加载到连续的物理内存中直到内存管理初始化完成、页表建立起来之后才开始复杂的分配。还有一类典型的应用是DMA。DMA传输通常要求目标内存物理连续因为I/O设备根本不理解页表它就要一段连续的物理地址。所以在驱动程序之间你会看到很多“分配连续物理内存”的专属接口这本质上就是连续分配在分页系统里的残留需求。5.3 从碎片角度看整个内存管理的发展脉络如果你沿着“碎片”这条线索看整个内存管理会发现所有方案都是一环扣一环的固定分区被吐槽内部碎片于是有了动态分区。动态分区被吐槽外部碎片于是有了紧凑算法和复杂分配策略。紧凑太贵、碎片治标不治本于是分页方案彻底放弃连续性用固定大小的页框抹平碎片。分页解决了碎片但地址转换开销变大于是有了TLB加速。虚拟内存需要按需加载于是结合交换思想有了缺页中断和页置换算法。这条线把教科书上那些看似独立的概念全部串起来了。这也是为什么我一直建议学操作系统不要背结论最好亲手写一遍模拟器当你自己为外部碎片头疼的时候你就会发自内心地说出“分页真是个天才的发明”。6. 常见问题快查与避坑心得在实际操作、学习、面试中围绕连续分配、覆盖、交换和碎片有几个问题出现的频率极高我把它们整理成一张速查表问题核心原因解决思路进程明明没释放内存却不够内部碎片或已分配记录错误检查固定分区剩余空间检查分配器是否有重复分配空闲空间总和够进程却分配失败外部碎片导致没有单一连续块触发紧凑或改用分页释放进程后内存还是一直分配失败没有做相邻空闲区合并在释放例程里增加向前/向后合并覆盖程序偶尔崩溃覆盖模块之间存在隐式依赖重新分析调用关系公共数据放常驻区交换后系统卡顿严重交换太频繁或换出对象选择不当提高交换阈值优先换出阻塞且低优先级进程固定分区系统利用率很低分区大小和进程负载不匹配重新规划分区大小增加不等长分区种类我再分享几条实操心得。第一写动态分区分配器时一定要先把“空闲区链表的数据结构”想清楚而不是先写算法。链表里的每项除了起始地址和长度最好还记录前驱、后继指针这样合并相邻空闲区时能直接通过指针访问邻居而不需要遍历整个链表。第二观察碎片时要可视化不要只盯数字。我当初在模拟器里加了一个最简单的命令行直方图每次分配释放后把空闲块画成一行星号肉眼看到内存被切得东一块西一块那种直观冲击比任何描述都强烈。如果现实场景下有条件也用图形化工具观察内存水位比盯着监控曲线迟钝得多。第三面试里如果被问到“覆盖和交换的区别”不要只背定义最好用一个具体例子说明。比如“覆盖是编译器自身把词法分析、语法分析复用同一块内存交换是操作系统把一个等待中的进程整体搬到磁盘上”。带例子的回答会让考官觉得你真的理解而不是临时背概念。第四真项目里遇到内存不足第一反应不应该是优化碎片而是先看是否有内存泄漏。我见过不止一个人花大量时间研究碎片和紧凑最后发现是某处循环里不断申请内存却从不释放。碎片优化是性能工程的一部分但泄漏才是合格工程师最先排查的问题。关于连续分配、覆盖交换和存储碎片的内容到这里基本就聊完了。最后再补充一个我自己的体会如果你在做一个内存分配相关的模拟或实验建议把“首次适应 释放时合并 紧凑触发条件”作为基线配置再去对比其他策略。这个组合在大多数场景下表现稳健它能让你在踩坑之前先建立一个正确的直觉后续调整策略时也有了参照系。