企业官网建设流程全解析

排查内存分配失败的问题时，我翻过不少模拟器代码和源码，发现无论你在用户态写一个小型内存池，还是在操作系统课程里做内存管理实验，有一组算法永远绕不开——动态分区分配算法里的First Fit、Next Fit、Best Fit、Worst Fit。我第一次真正把这四个算法摆在一起对比，是在自己动手实现空闲分区链表管理的时候：同样的一串内存请求，四个算法走完一轮，剩余空间的碎片情况天差地别，有的还能继续分配，有的已经彻底碎成渣。

这篇分享不是把教材概念再抄一遍。我会从固定分区为什么不行讲起，把四个算法的搜索逻辑逐一拆开，用一个可以手算的模拟案例展示它们在同样请求下的不同结局，再给出一份能直接运行的Python模拟器实现，最后聊一些教材不会写但做题和面试常踩的坑。适合正在学操作系统、准备保研考研复试，或者想写内存池和内存模拟器的朋友。

1. 为什么固定分区不够用：动态分区要解决的问题

1.1 固定分区的三个死穴

早期的存储管理方案里，最简单粗暴的做法是固定分区：把内存按预设大小切成若干块，每个分区可以放一个进程，分区大小可以不同，但一旦切好就不再变化。看起来好像很省心，但只要实际跑过几个进程就知道它有多别扭。

第一个问题是内部碎片。给你举个例子，内存里预留了一个100KB的分区，一个进程实际只需要80KB，它被放进去之后那20KB就永远空在那了，谁也用不上。当年内存贵得要命，这种浪费是可耻的。第二个问题是缺乏灵活性，进程大小和分区大小不一定对得上。如果预切的分区都小于当前要运行的作业，即使内存总空闲空间足够，这个作业也进不来；反过来，分区都太大又浪费。第三个问题是并发能力受限，分区数量是固定的，不可能临时多开几个进程。

这些痛点逼着操作系统设计者换思路：既然进程大小千变万化，那不如干脆按需分配——要多少给多少，用完释放，剩下的空间继续给别人用。

1.2 动态分区的核心矛盾：外部碎片

动态分区的思想听起来简单：在内存里找一块够大的连续空闲区，分配给进程；进程结束后把这块区域重新标记为空闲。但实际跑起来，问题就来了。

假设内存有100KB，A进程申请30KB放在前头，B进程申请20KB紧随其后，C进程申请25KB放在第三段。用完后A先退出，空闲了一块30KB；接着C退出，又空闲了一块25KB。此时内存总空闲是55KB，但它们是两块不连续的区域。如果这时候来了一个D进程需要40KB，明明空闲总量够，却因为找不到连续的40KB空间而分配失败。这种分散在各处的零碎空闲区，就叫外部碎片。

到这里，动态分区分配算法要解决的核心问题就清晰了：当有多个空闲分区都能满足请求时，到底选哪一个？这个选择直接决定了碎片如何分布、后续大块请求能不能满足、以及查找开销有多高。First Fit、Next Fit、Best Fit、Worst Fit，就是四种不同的选择策略。它们共同的底层数据结构是空闲分区表或空闲分区链表，通常按起始地址排序，每个节点描述一块空闲空间的起点和大小。

2. 四种分配算法的搜索策略拆解

2.1 First Fit：从低地址开始找第一个够用的

First Fit的核心逻辑一句话：每次分配都从空闲链表的头部开始，顺序往后找，碰到第一个大小满足需求的空闲分区，就从中切出一块来。

用生活中的场景类比，就像你在一条停满车的路边找车位，从路口一路开过去，看到第一个能塞进你车子的空位就停进去，不管后面还有没有更大的位置。这样做的优点是实现最简单，链表只需要按地址排序，维护起来也很方便；由于每次优先利用低地址的空闲区，高地址区域的大块空闲空间往往能比较完整地被保留下来，这对后续可能到来的大作业是利好。

First Fit的缺点同样明显。低地址区域的空闲块会被反复切割，渐渐变成一堆细细碎碎的小块。等运行时间长了，每次分配都要从链表头开始，结果前面全是装不下的小块，白白扫描一大圈，查找开销越来越高。教材里经常说First Fit综合表现不错，但那是统计意义上的结论，具体到某个畸形请求序列，它也可能摔得很惨。

2.2 Next Fit：接着上次的位置继续转

Next Fit是对First Fit的一种改进尝试，思路是：反正每次都从头扫描太浪费，那我记下上次查到哪里，下次就从那里接着往后找。如果找到链表末尾还没找到，就绕回链表头继续，类似循环扫描。

这个改动带来的直接好处是，空闲分区被使用得更加均匀，不会再出现低地址被"啃"得千疮百孔、高地址却一直闲置的局面；同时，查找过程跨过的无用碎片区域少了很多，平均查找步数通常比First Fit低。在日常请求都是中小规模、且不太需要超大连续空间的场景下，Next Fit的分配速度和碎片分布都还不错。

但Next Fit有一个隐蔽的软肋：它会让大块空闲空间也被逐渐蚕食。因为扫描指针不会每次都回到低地址保留大块，它走到哪就切到哪，可能把一整块大空间分段切掉。结果是运行一段时间后，空闲链表里全是中等大小的块，真正的大块反而不见了。一旦来了一个大作业，其他算法可能还留着大块可以兜底，Next Fit往往直接失败。

2.3 Best Fit：最小满足原则，尽量"切得刚好"

Best Fit的理念听起来最优雅：在空闲链表中找出所有能满足请求的空闲分区，选那个大小最接近请求的分区来分配，避免"大炮打蚊子"式的浪费。如果空闲链表本身按容量升序排列，那么第一个满足条件的节点就是要找的目标；如果链表仍然按地址排序，那就得遍历整张表，记录下最小满足的那个。

举个例子，空闲分区大小分别是10KB、30KB、20KB，此时来了一个15KB的请求。First Fit会选择10KB? 显然不够，于是选30KB，造成15KB的空间浪费；Best Fit会选择20KB，只浪费5KB。从单次分配的角度看，Best Fit确实把空间利用做到了最精细。

但是，精打细算是有代价的。它会留下大量像5KB、3KB这样的微小碎片，这些碎片单独谁都装不下，却占据着链表节点，增加了后续扫描负担，也压缩了有效的连续空间。很多刚学这块内容的同学会以为Best Fit一定最优，实际上它的查找开销是四个算法里最高的，而且碎片化程度往往最严重。它唯一的优势在于，如果内存里本来就没有太多大块空间，Best Fit能延缓大块空间被切碎的速度，尽力把大块留给后面的进程。

2.4 Worst Fit：专挑最大的空闲区下手

Worst Fit的思路和Best Fit正好相反：既然申请的空间总是要切走一块，那我干脆找当前最大的空闲分区下手，切出去之后剩下的那块依然足够大，说不定还能满足后面的请求。

还是用刚才那组数：空闲分区是10KB、30KB、20KB，请求15KB。Worst Fit会选30KB来切，切完后剩下15KB。这个15KB还能服务后续一个15KB的请求，而Best Fit切20KB剩下的那5KB基本就废了。从减少微小碎片的角度看，Worst Fit确实有一定道理。

但它的致命伤在于，每次都拿最大的块开刀，等于一直在消耗系统的"战略储备"。运行一段时间之后，最大空闲块会被一轮一轮地切成中块、小块，最终导致一个大请求到达时，系统已经拿不出可以容纳它的连续区域了。所以Worst Fit的名字虽然听着像"最差"，但它在请求大小比较均匀、没有突发大请求的场景下，表现反而不差；最怕的就是大请求和大块被提前消耗两者叠加。

3. 100KB模拟案例：一次调度如何让四种算法走向不同结局

3.1 案例设计：什么样的请求序列能区分算法

只看文字解释还不够直观，我设计了一个100KB内存的模拟场景，手工推演四种算法的真实差异。这个过程我自己在实现模拟器时跑了好几遍，每次都有新发现。

内存大小100KB，初始空闲区为[0,100)，请求序列如下：

1. P1申请10KB
2. P2申请40KB
3. P3申请20KB
4. 释放P1
5. 释放P2
6. P4申请20KB
7. P5申请45KB
8. P6申请30KB

前几步对四个算法来说完全一样，真正的分叉从第6步开始。这个序列是我刻意构造的，目的是让"选哪个空闲分区"这件事直接决定后续大请求的生死。

3.2 逐步推演：第4个请求开始出现分叉

前3个请求分配完之后，内存布局是：P1占[0,10)，P2占[10,50)，P3占[50,70)，空闲区只剩下[70,100)，大小为30KB。P1和P2释放时发生了相邻合并，所以第5步结束后空闲区变成两块：[0,50)大小50KB，[70,100)大小30KB。这块状态对四种算法来说是一样的，接下来就看它们如何选择。

第6步P4申请20KB，四种算法开始分道扬镳：

• First Fit：从低地址开始扫，[0,50)满足要求，于是分配[0,20)，剩余[20,50)和[70,100)，都是30KB。
• Next Fit：假设上一次分配P3时查找指针停在50附近，这次从50往后找，绕过了前面的[0,50)，看到[70,100)大小为30KB满足要求，于是分配[70,90)，剩余[0,50)和[90,100)。
• Best Fit：遍历两个空闲块，[0,50)和[70,100)都能满足20KB需求，按"最小满足"原则选30KB的[70,100)，结果和Next Fit一样，剩余[0,50)和[90,100)。
• Worst Fit：选最大的空闲块[0,50)，分配[0,20)，结果和First Fit一样，剩余[20,50)和[70,100)。

第7步P5申请45KB，命运的分水岭出现了。First Fit和Worst Fit手里只有两个30KB的空闲块，无法满足45KB请求，分配失败；而Next Fit和Best Fit手里还握着那个50KB的[0,50)块，顺利切出[0,45)，然后再剩下一个5KB的空闲块。

到这里已经很清楚了：P4那一步选了"切哪块"，直接决定了P5能不能活下来。First Fit和Worst Fit因为贪图低地址的方便，把50KB大块切成了两个30KB，结果面对45KB需求只能干瞪眼。

第8步P6申请30KB，又有反转。Next Fit和Best Fit虽然赢下了P5，但把唯一的大块切成了5KB，现在剩下[45,50)和[90,100)，分别是5KB和10KB，连30KB需求都满足不了。换句话说，这两个算法在P5的成功是有代价的，代价就是提前透支了大块空间，后续中等请求照样失败。

3.3 更长序列的统计结果

手算案例能说明原理，但看不出整体趋势。我在模拟器里用500个随机请求跑了一组数据，内存大小512KB，请求大小在8KB到80KB之间随机，释放顺序按进程生命周期模拟。换一组随机种子，具体数字会有浮动，但下面这几个相对关系经常出现：

• First Fit的分配成功率和最大连续空闲块表现都比较稳，综合是最好的。
• Next Fit平均查找步数最低，但最大连续空闲块缩水严重，大请求容易失败。
• Best Fit的总空闲空间剩余最紧凑，但碎片块数量最多，最大连续空闲也小，典型地把空间切得支离破碎。
• Worst Fit的碎片块数量少，但大请求一旦来临，成功率下降明显。

这说明一个很反直觉的结论：名字里带"Best"的不一定最优，带"Worst"的也不一定最差。具体选哪个，完全取决于你面对的工作负载特征。

4. 从零写一个动态分区分配模拟器

4.1 数据结构选型：地址序链表与大小序链表

要把这四个算法落到代码里，第一件事是设计空闲分区的组织方式。最常用的结构是空闲分区链表，每个节点记录起始地址和大小。

链表的排序方式直接影响算法实现：First Fit和Next Fit适合用地址序链表，因为回收时要按起始地址找到正确位置，方便合并相邻空闲块；Best Fit和Worst Fit的教科书描述是"遍历所有分区找最小/最大"，这在地址序链表上就是O(n)全表扫描。如果追求效率，可以把链表按容量排列，Best Fit用升序、Worst Fit用降序，这样第一个满足条件的节点就是目标，查找可以提前终止，代价是每次回收后维护有序性的开销变大。

我写模拟器时用了单链表加dummy头节点的方式。用dummy节点可以省去很多"链表为空""删除头节点"之类的边界判断，代码写起来更干净。节点定义如下：

class FreeListNode: def __init__(self, start, size): self.start = start self.size = size self.next = None

空闲链表管理类里维护一个头指针和一个用于Next Fit的last指针。last指针指向最近一次找到的节点，这样Next Fit查找时可以直接从last.next开始。

4.2 分配模块：查找策略与内存切分的实现

分配的核心逻辑是两步：先用对应策略找到目标空闲块，然后从块中切出请求大小。如果切完后剩余大小为0，就把这个节点从链表中移除。

四种查找策略的实现如下：

def find_first_fit(self, req): pre = self.head cur = self.head.next while cur: if cur.size >= req: return pre, cur pre, cur = cur, cur.next return None, None def find_next_fit(self, req): if self.last is None: self.last = self.head cur = self.last.next or self.head.next first_scanned = cur while cur: if cur.size >= req: self.last = cur # 找到 last 的前驱，用于后续删除 pre = self.head while pre.next is not cur: pre = pre.next return pre, cur cur = cur.next if cur is None: cur = self.head.next if cur is first_scanned: break return None, None def find_best_fit(self, req): target_pre = None target = None pre = self.head cur = self.head.next while cur: if cur.size >= req and (target is None or cur.size < target.size): target_pre, target = pre, cur pre, cur = cur, cur.next return target_pre, target def find_worst_fit(self, req): target_pre = None target = None pre = self.head cur = self.head.next while cur: if cur.size >= req and (target is None or cur.size > target.size): target_pre, target = pre, cur pre, cur = cur, cur.next return target_pre, target

查找函数都返回目标节点的前驱和目标节点，这样后面删除节点时不用再扫一遍链表。分配接口汇总一下：

def alloc(self, req, strategy): if strategy == "first_fit": pre, node = self.find_first_fit(req) elif strategy == "next_fit": pre, node = self.find_next_fit(req) elif strategy == "best_fit": pre, node = self.find_best_fit(req) elif strategy == "worst_fit": pre, node = self.find_worst_fit(req) else: raise ValueError(f"unknown strategy: {strategy}") if node is None: return None start = node.start node.start += req node.size -= req if node.size == 0: pre.next = node.next if self.last is node: self.last = None return start

注意Next Fit里last指针的处理：如果last指向的节点被切空并删除，要把last重置为None，否则下次查找时last.next可能访问到不存在的节点。这个细节很容易被忽略，我第一次跑模拟器时就在这里踩了坑。

4.3 回收模块：四种相邻情况和合并处理

回收内存是动态分区管理里最讲究的部分。进程释放一块区域后，不能简单地把节点加回链表，必须先判断它和相邻空闲分区的关系，能合并就合并，否则碎片会越积越多。

具体有四种情况：新释放块和前面的空闲块相邻，和后面的空闲块相邻，和前后都相邻，以及两边都不相邻。我专门写了一个free方法处理：

def free(self, start, size): pre = self.head cur = self.head.next while cur and cur.start < start: pre = cur cur = cur.next # 情况1：和前面的空闲块相邻，向前合并 if pre is not self.head and pre.start + pre.size == start: pre.size += size # 看看能不能继续和后一块合并 if cur and pre.start + pre.size == cur.start: pre.size += cur.size pre.next = cur.next if self.last is cur: self.last = pre # 情况2：和后面的空闲块相邻，向后合并 elif cur and start + size == cur.start: node = FreeListNode(start, size + cur.size) node.next = cur.next pre.next = node if self.last is cur: self.last = node # 情况3：两边都不相邻，直接插入新节点 else: node = FreeListNode(start, size) node.next = cur pre.next = node

这段代码的好处是天然处理了"前后都相邻"的情况：先向前合并，合并后检查新块末尾是否衔接后块，如果是就继续合并，三块合成一块。这里dummy头节点的作用体现出来了，pre is not self.head的判断能安全区分"没有前驱空闲块"和"前驱就是第一个空闲块"。

4.4 把案例跑成测试

模拟器有了，我把第三章的案例放进去跑。为了方便观察，我给链表加一个__str__方法，把当前所有空闲块打出来：

def __str__(self): nodes = [] cur = self.head.next while cur: nodes.append(f"[{cur.start}, {cur.start + cur.size})") cur = cur.next return " -> ".join(nodes) if nodes else "empty"

然后构造序列：

fl = FreeList(start=0, size=100) # 前3个alloc不释放 fl.alloc(10, "best_fit") fl.alloc(40, "best_fit") fl.alloc(20, "best_fit") fl.free(0, 10) fl.free(10, 40) print("after releases:", fl) # [0,50) -> [70,100) fl.alloc(20, "best_fit") print("after P4:", fl) # 按best_fit，[0,50) -> [90,100) fl.alloc(45, "best_fit") print("after P5:", fl) # [45,50) -> [90,100)

把strategy换成first_fit再跑一遍，你就能清楚看到同一个序列在另一种策略下P5分配失败时的链表状态。这就是"数据结构和策略解耦"带来的好处：测试逻辑完全不用改，只换一个参数就能横向对比。

5. 四种算法的真实对比：教材结论之外的细节

5.1 关键指标和适用场景对照

实际操作下来，我用一张表总结四种算法在典型负载下的表现：

这张表里的"适用场景"是长期跑模拟器后的体会。比如嵌入式设备内存有限、请求大小相对固定，Worst Fit的精神其实是可取的，因为它能把大块空间留给系统级任务；而在通用操作系统里，你不知道下一个请求会不会是大块，所以保留高地址大块空间变得很重要，First Fit的"偏向低地址"策略天然合适。

5.2 为什么First Fit的综合表现通常最稳

很多教材在讲到动态分区分配时都会提到，实验统计里First Fit的综合性能往往是最好的，甚至优于看起来更聪明的Best Fit。原因有三点。

第一，First Fit把大块空间集中在高地址区域，而进程释放行为往往更倾向于先释放较晚分配的低地址区域，这使得低地址碎片不断产生也不断被合并，整体碎片反而能被控制。第二，First Fit的查找是顺序的，而且通常在链表前部就能命中，实际平均查找步数不高。第三，它的链表维护逻辑最简单，地址序单链表在回收合并时非常顺手。

相对应地，Best Fit虽然在单次分配上看起来最节省，但它会把每个空闲区都切得极碎，这些碎块都集中在原本中等大小的分区里，如果后续请求稍微变大一点，整个链表就找不到合适的块了。这个现象我一开始也不太信，直到自己跑了几百个请求的模拟数据，看到Best Fit的碎片节点数量比First Fit多出一倍，才彻底明白教材那句话背后的含义。

5.3 常见误区和面试易错点

这块内容在面试和考试里反复出现，很多人的理解是有偏差的。

第一个误区：Best Fit一定最省空间。不对，Best Fit在单次分配上最节省，但长期运行后外碎片最严重，因为它制造了大量微小的"边角料"。第二个误区：Worst Fit既然叫最差那就一定最差。实际上Worst Fit产生的碎片块数量较少，在请求大小均匀的场景下表现并不差，"最差"指的不是场景表现，而是说它每次都去切割最大块，容易把大块战略储备消耗光。

第三个误区：Next Fit比First Fit好，因为它不用每次都从头部扫描。如果只比查找速度，Next Fit确实快，但它会均匀地切碎所有大块，大作业分配成功率比First Fit低不少。第四个误区：外碎片可以用紧凑技术解决，所以无所谓。紧凑确实能把分散的空闲区合并成连续大块，但它需要移动进程的数据，修改地址映射，代价非常高，操作系统不可能频繁执行。

这些点如果只背结论很容易绕晕，但只要自己写过模拟器、看过碎片是怎么一步步累积起来的，面试时就能结合具体场景说清楚。

6. 我实现模拟器时的一些体会

整个模拟器写下来，我最大的收获倒不是把四种算法的区别背熟了，而是明白了工程实现和教材描述之间的差距。教材里一句话"Best Fit选择最小的满足需求的分区"，听起来很简单，但真正实现的时候你得考虑链表怎么排序、查找时怎么记录前驱、释放时怎么合并相邻块、Next Fit的指针在节点被删除后怎么处理。这些细节才是让算法真正跑起来的关键。

调试的时候我养成了一个习惯：在每次分配和释放后都把空闲链表的状态打出来。平台不挑，Python的print就能用，重点看空闲块的数量和位置变化。只要连续打十几行日志，你就能直观地看到碎片是怎么一点点产生的，也能很快定位到是分配逻辑问题还是合并逻辑问题。

另外，如果你打算在这个模拟器基础上继续深入，可以试试这两件事：一是把进程申请顺序做成随机序列，多跑几组再统计，你会发现单一序列得出的结论经常有误导性；二是在链表节点里增加一个"上次分配查找步数"的计数器，用来评估每个策略的实际查找消耗。这些指标比肉眼看碎片状态更能说明问题。动态分区分配的价值不止存在于考试卷上，很多自研内存池、嵌入式系统的内存管理里都能看到这四个算法的影子。把模拟器亲手写一遍、跑一遍，你对碎片化问题的理解会有一个质的提升。