内存分配策略：首次适应、最佳适应、最差适应
大家好，我是老李。今天咱们聊聊动态内存分配里的三种经典策略。说白了，就是操作系统或者内存管理器，在收到你 malloc(1024) 这样的请求时，到底怎么从一堆空闲块里挑一块给你。
这三种策略——首次适应、最佳适应、最差适应——我当年在学校里背得滚瓜烂熟，但真正理解它们的差异，还是在一次嵌入式项目里踩了坑之后。嗯，咱们一个一个来看。
1. 首次适应（First Fit）
这个策略最直观。空闲块链表从头开始扫，找到第一个大小够用的块，直接切一块给你，剩下的继续留在链表里。
优点：速度快，因为找到第一个能用的就停了。而且它倾向于在内存低地址区域留下很多小碎片，高地址区域相对完整。
缺点：低地址区域容易变成“碎渣堆”。你想想看，每次分配都从低地址开始，小块的释放后，低地址区域会越来越碎。我有个项目里，就是因为这个，导致一个需要连续大块内存的缓冲区分配失败，明明总空闲内存还有不少，但就是凑不出一块连续的。
2. 最佳适应（Best Fit）
这个策略听起来很聪明——遍历整个空闲链表，找到一块大小刚好大于等于请求大小的空闲块。说白了，就是“最小够用”原则。
优点：能最大程度减少大块内存的浪费。每次切出来的剩余部分都很小，理论上能保留大块内存给后续的大请求。
缺点：性能开销大，每次都要遍历整个链表。而且，它会产生大量极其微小的碎片——这些碎片小到几乎没法再用，但还占着链表节点。我曾经在一个实时系统里用过最佳适应，结果发现分配时间抖动很大，因为每次都要扫一遍链表，最坏情况下的延迟完全不可控。
3. 最差适应（Worst Fit）
这个策略正好反过来——找一块最大的空闲块，切一部分给你，剩下的部分依然很大。它的想法是：既然要切，就从最大的块上切，这样剩下的部分还能满足后续的大请求。
优点：能避免产生大量小碎片。因为每次都是从最大的块上切，剩下的块依然比较大，不容易变成碎渣。
缺点：同样需要遍历整个链表找最大块，性能开销大。而且，它会很快把最大的那块内存切小，导致后续大请求失败。我记得有一次做图像处理，需要分配几个大缓冲区，用了最差适应，结果第一个分配就把最大的块切掉一半，第二个分配直接失败——明明总内存够，但最大的块已经被切碎了。
4. 三种策略对比
| 策略 | 查找方式 | 碎片倾向 | 分配速度 | 典型场景 |
|---|---|---|---|---|
| 首次适应 | 从头扫描，找到第一个够用的 | 低地址碎片多 | 快（平均） | 通用系统、嵌入式 |
| 最佳适应 | 全扫描，找最小够用的 | 碎片数量最多 | 慢（全扫描） | 内存极小、分配模式固定 |
| 最差适应 | 全扫描，找最大的 | 碎片数量少但大块易碎 | 慢（全扫描） | 大块分配为主、分配次数少 |
5. 核心逻辑流程图
下面这张图展示了三种策略在同一个空闲链表上的决策路径。你可以看到，同样的空闲块，三种策略会选中不同的块。
6. 实际项目中的选择
我个人习惯是：默认用首次适应。原因很简单——它够快，而且大多数场景下碎片问题没那么严重。如果你发现碎片导致分配失败，再考虑其他策略或者加一个内存整理机制。
我曾经在一个网络协议栈里，因为频繁分配和释放小包，导致首次适应产生了大量碎片。后来我换成了伙伴系统（Buddy System），它本质上是一种特殊的最差适应变体，但通过固定块大小（2的幂次）来避免碎片。嗯，那是另一个故事了。
最后说一句：没有银弹。这三种策略各有优劣，关键是你得理解你的内存分配模式。如果分配和释放是随机的，首次适应最稳；如果分配大小很固定，最佳适应可能更好；如果大块分配居多，最差适应也许能减少碎片。但无论如何，先跑起来，再优化——别一开始就纠结选哪个，先让程序能跑，然后用性能分析工具看内存碎片率，再决定要不要换策略。