连续分配策略：首次适应、最佳适应与碎片问题
上一篇我们看到，基址/界限模型给每个进程一套独立坐标系，但它隐含了一个要求：进程必须占用一整段连续的物理内存。现在问题来了——内存就这么一大块，进程不停地来、不停地走，操作系统该怎么决定"新来的进程放哪一段、放哪里"？
这听起来像个简单的"找空位"问题，可一旦你真的拿起笔推演几轮分配和释放，就会发现一个反直觉的现象：
内存明明还剩很多，加起来足够，却怎么也凑不出一段连续的空间，新进程就是装不进去。
这就是连续分配绕不开的碎片难题。这一篇我们先把"系统到底怎么找空位、怎么记账"这套机制讲透——空闲区表长什么样、首次适应和最佳适应每一步怎么走、分配和回收时数据结构怎么变——看清机制之后，再回过头解释碎片为什么是结构性的、为什么它最终把内存管理逼向了分页。
一、先把账本看清楚：空闲分区表
要分配连续内存，系统首先得知道"现在哪些地方是空的、各有多大"。这本账，就是空闲分区表（或空闲分区链）。
它的结构很朴素，每一条记录描述一个连续的空闲块：
- 起始地址：这块空闲区从物理内存的哪里开始；
- 长度：这块空闲区有多大；
- （在链表实现里，还有指向下一个空闲块的指针）。
举个例子，假设一台机器有 100 个单位的内存，经过一段时间运行后，空闲分区表可能长这样：
| 起始地址 | 长度 |
|---|---|
| 10 | 20 |
| 45 | 15 |
| 70 | 30 |
这意味着 [10,30)、[45,60)、[70,100) 三段是空的，中间夹着的都是已分配给某些进程的区域。系统的所有分配决策，都是围绕这本账展开的。每来一个请求，就在表里找一块够大的空闲区；每分配或回收一次，就更新这本账。
把这本账记牢，下面所有算法的差别，本质上就是**“在这张表里，按什么顺序、挑哪一块”**的差别。
二、首次适应：从头扫，遇到第一个够大的就停
最直接的策略叫首次适应（First Fit）。它的规则一句话就能说清：
从空闲分区表头开始顺序扫描，遇到第一个长度足够的空闲块，就从它里面切出所需大小分配出去。
我们走一遍完整流程。沿用上面的表，现在来了一个请求，需要 12 个单位：
- 看第一条
[10, 长度20]，20 ≥ 12，够大——停，就用它； - 从这块的头部切出 12 个单位分配给进程，占用
[10,22)； - 更新账本：这块空闲区缩小为起始地址 22、长度 8。
更新后的空闲分区表：
| 起始地址 | 长度 |
|---|---|
| 22 | 8 |
| 45 | 15 |
| 70 | 30 |
首次适应的关键特征是它根本不看后面的块——只要前面有一块够用就立刻决定。这带来一个很实际的好处：分配速度快，平均只需扫描表的前半部分。代价是，靠前的空闲块会被反复切割，越切越小，渐渐在内存低地址区域堆积出一堆细碎的小空闲块，而靠后的大块则相对完整。
有一个常见变体叫循环首次适应（Next Fit）：不每次都从表头扫，而是从上次分配结束的位置接着往下找。这样能让分配更均匀地散布在整个内存上，避免低地址区被过度切碎，但也因此更容易把大块也切散。
三、最佳适应：扫全表，挑最接近需求的那块
**最佳适应（Best Fit）**的出发点是想"少浪费一点"。它的规则是：
扫描整张空闲分区表，在所有够大的空闲块里，挑出长度最接近请求大小（即剩余最少）的那一块来分配。
同样的初始表，同样请求 12 个单位，最佳适应的走法不同：
- 扫描全表，找出所有 ≥ 12 的块：
[10,长度20]、[45,长度15]、[70,长度30]——三块都够； - 比较切完后的剩余：用 20 的剩 8，用 15 的剩 3，用 30 的剩 18；
- 剩余最少的是用
[45,长度15]这块，剩 3——选它； - 从中切出 12，占用
[45,57)，账本里这块更新为起始地址 57、长度 3。
更新后的空闲分区表：
| 起始地址 | 长度 |
|---|---|
| 10 | 20 |
| 57 | 3 |
| 70 | 30 |
注意最佳适应和首次适应的核心差别：最佳适应必须扫描整张表才能确定"最接近"的那块，所以它慢；而且它留下的那个长度为 3 的剩余块，很可能小到谁也用不上——这恰恰埋下了碎片的种子。这里就出现了一个非常重要的反直觉结论：
"最佳适应"这个名字极具误导性。它在单次分配上看起来最省，长期运行下来却往往制造出最多无法再利用的细小碎片。
与之相对还有个最坏适应（Worst Fit）：每次都挑最大的块来切。思路是"切完后剩下的还够大，仍然可用"，避免产生太小的碎片。但它的副作用是大块被优先消耗，等到真正需要大块时反而没有了。
四、回收：碎片不只在分配时产生，回收时更要小心合并
光看分配只是故事的一半。进程结束、释放内存时，系统怎么处理这块还回来的空间，对碎片的影响同样巨大。
回收一块内存时，关键动作是检查它前后相邻的区域是不是也空闲，如果是，就合并成一个更大的空闲块。这一步叫合并（coalescing），它是对抗碎片的重要手段。回收时有四种情况：
- 回收区前后都不空闲：直接作为一个新的空闲块插入空闲表；
- 回收区前面紧邻一个空闲块：与前块合并，扩大前块的长度；
- 回收区后面紧邻一个空闲块：与后块合并，更新起始地址和长度；
- 回收区前后都空闲：三块合并成一大块，把后面那块从表里删除。
如果系统偷懒、回收时不做合并，那么相邻的空闲小块就会一直各自为政，明明挨着却不能合起来用，碎片会急剧恶化。所以你看，碎片的产生和缓解，都藏在分配与回收这两套数据结构操作的细节里——这就是机制层面的真相。
五、看清机制后，再正面回答：碎片到底是什么
现在我们手里有了完整的机制视角，可以精确地定义碎片了。碎片分两种，初学者极易混淆：
- 外部碎片（external fragmentation）：空闲内存被切割成许多不相邻的小块，总量足够但无法满足一个连续的大请求。前面表里那些零散的长度 3、长度 8 的小块，就是外部碎片。它发生在已分配区域之间。
- 内部碎片（internal fragmentation）：分配给进程的内存块比它实际需要的略大，多出来的那部分用不上也还不回去。它发生在已分配区域内部。连续分配如果按固定大小的"分区"来分（固定分区法），就会产生内部碎片。
连续分配最致命的是外部碎片。我们用一张图直观感受它的产生过程——这正是上一篇结尾说的"碎片如何逼出分页"的具体画面：
这张图的关键在最后一步：空闲总量明明够，却因为不连续而分配失败。这不是某个算法没写好，而是"要求连续"这个前提本身导致的结构性后果——无论你用首次适应还是最佳适应，只要坚持连续分配，碎片就消除不掉，区别只是产生得快一点还是慢一点。
外部碎片不是实现 bug，而是"连续分配"这一模型与生俱来的结构性缺陷。换算法只能缓解，无法根治。
六、紧凑：能根治吗？为什么代价太大
既然碎片是因为空闲块零散不连续，那一个很自然的想法是：把所有已分配的进程都往一端挪一挪，挤到一起，让空闲块也聚到另一端连成一片。这个操作叫紧凑（compaction），也叫内存拼接。
紧凑确实能消除外部碎片——它把分散的空闲区合并成一整块连续空间。但它的代价高得惊人：
- 需要把大量进程的数据在物理内存里整体搬移，这是极其耗时的内存拷贝操作；
- 搬移过程中，被移动进程的物理位置变了，必须同步更新它们的基址寄存器（还好动态重定位让这一步成为可能，否则连搬都不能搬）；
- 紧凑期间系统往往得暂停相关进程，对延迟敏感的服务是不可接受的停顿。
所以紧凑虽然理论上能根治外部碎片，但实践中代价太大，只能偶尔为之，不能作为常态手段。这就把连续分配逼到了死角：算法换来换去治不了本，紧凑能治本却用不起。
七、为什么这道墙最终被分页推倒
走到这里，连续分配的困境已经很清楚了。它的所有麻烦，根子都在那两个字——连续。
- 因为要连续，才需要费心选首次适应还是最佳适应；
- 因为要连续，才会产生怎么也消除不掉的外部碎片；
- 因为要连续，才不得不用代价高昂的紧凑去勉强补救。
那么，能不能干脆放弃"连续"这个前提？这正是下一篇分页机制的核心思想：把进程的地址空间和物理内存都切成大小相同的小块（页与页框），允许一个进程的各个页散落在物理内存的任意位置，再用一张页表记录映射关系。
一旦不要求连续，外部碎片就被彻底消灭了——因为任何一个空闲页框都能装下任何一个页，再也不存在"凑不出连续空间"的问题。连续分配里那本费力维护的空闲分区表、那些纠结的适应算法、那个用不起的紧凑，统统不再需要。
所以连续分配的价值，恰恰在于它清清楚楚地暴露了问题，让我们明白分页到底在替我们解决什么。理解了这一篇的碎片之痛，你才会真正体会到分页的精妙。
八、和工程实践 / 后端开发的联系
连续分配的思想和它的碎片难题，在今天的工程里到处都有回声。
- 内存分配器（malloc/free）：用户态的内存分配器（如 glibc 的 ptmalloc、Google 的 tcmalloc）面对的正是同一类问题。它们维护的空闲链表、按大小分类的 bin、对相邻空闲块的合并，本质就是这一篇讲的空闲分区表与合并机制的精细化版本。
- 伙伴系统（Buddy System）：Linux 内核管理物理页框用的伙伴算法，按 2 的幂大小组织空闲块，分配时拆半、回收时尝试与"伙伴"合并——这是对碎片和合并效率的工程化权衡。
- 内存池 / 对象池：很多高性能服务预先按固定大小切好内存池，正是为了避免运行时频繁分配释放导致的外部碎片，用一点内部碎片换来分配的确定性和速度。
- 长跑服务的内存"虚高"：一个服务跑了很久后，RSS 居高不下、内存利用率反而下降，很可能不是真的有泄漏，而是分配器层面产生了大量碎片，空闲内存还不回操作系统。理解碎片，才能正确判断这类现象。
九、动手做一个小实验：手工推演一次碎片产生
理解碎片最扎实的办法，是拿纸笔亲手切几刀。这个实验不需要任何环境。
设定一块长度为 100 的连续内存，初始全空。按顺序执行以下操作，每一步都把空闲分区表写出来：
- 进程 A 申请 30，进程 B 申请 20，进程 C 申请 30（依次从低地址紧密分配）；
- 进程 B 结束，释放它的 20——观察中间出现一个空洞；
- 进程 D 申请 10——用首次适应，它会落在 B 留下的空洞里，空洞还剩 10；
- 进程 E 申请 25——你会发现：剩余空闲总量是
10(B空洞剩余) + 10(末尾) = 20？再算上 C 之后到 100 的空间……仔细记账，判断 E 到底能不能装进去。
做完一轮，再用最佳适应把同样的序列重走一遍，对比两者留下的碎片形态。你会非常直观地体会到：为什么"空闲够、却装不下"，以及为什么最佳适应反而更容易留下没人能用的小碎块。这一遍推演胜过背十遍定义。
学习这一部分最容易踩的坑
1. 把内部碎片和外部碎片搞混
外部碎片是已分配块之间那些零散的、拼不起来的空闲小块；内部碎片是分配块内部多给却用不上的部分。连续分配（可变分区）的主要敌人是外部碎片，分页则反过来——消灭外部碎片但引入内部碎片。方向搞反，后面就全乱了。
2. 以为"最佳适应"就是最好的
最佳适应每次都挑剩余最少的块，听起来最省，实际上它要扫全表（慢），还会留下大量小到没法再用的碎块（碎片更多）。名字最具迷惑性，工程上首次适应往往综合表现更稳。
3. 忽略回收时的合并
碎片的缓解一半靠回收时把相邻空闲块合并。只盯着分配算法、忘了合并机制，就无法完整理解碎片是怎么累积或被抑制的。
4. 以为换个聪明算法就能消除碎片
外部碎片是"连续分配"这个模型的结构性缺陷，任何分配算法都只能缓解、不能根治。真正的根治是放弃"连续"这个前提——也就是分页。把这条因果记牢，你才懂分页为什么必然出现。
总结
连续分配给了我们一个绝佳的起点：它足够直观，也足够清楚地暴露出内存管理为什么必须继续进化。把机制和结论一起带走：
- 连续分配的核心数据结构是空闲分区表，所有分配决策都是"在表里按什么顺序挑哪块"的差别；
- 首次适应从头扫、遇到第一个够大的就用，快但低地址易碎化；最佳适应扫全表挑剩余最少的，慢且易留无用小碎块；
- 回收时的合并相邻空闲块，是抑制碎片的关键一环，不可忽视；
- 外部碎片是连续分配与生俱来的结构性缺陷，换算法只能缓解，无法根治；
- 紧凑理论上能根治外部碎片，但搬移代价太高，用不起；
- 真正的出路是放弃"连续"这一前提——这正是下一篇分页机制的起点。
当你能亲手推演出"空闲够却装不下"的那一刻，你就真正理解了分页存在的意义。下一篇，我们就去看分页是如何把地址转换从"加一个偏移"升级成"查一张映射表"，从而一举消灭外部碎片的。
参考资源：
- 《现代操作系统》（Andrew S. Tanenbaum）内存管理章节
- 《操作系统导论》（Operating Systems: Three Easy Pieces）Free Space Management
- OSTEP - Free Space Management
- 《深入理解计算机系统》动态内存分配章节