排查内存分配失败的问题时我翻过不少模拟器代码和源码发现无论你在用户态写一个小型内存池还是在操作系统课程里做内存管理实验有一组算法永远绕不开——动态分区分配算法里的First Fit、Next Fit、Best Fit、Worst Fit。我第一次真正把这四个算法摆在一起对比是在自己动手实现空闲分区链表管理的时候同样的一串内存请求四个算法走完一轮剩余空间的碎片情况天差地别有的还能继续分配有的已经彻底碎成渣。这篇分享不是把教材概念再抄一遍。我会从固定分区为什么不行讲起把四个算法的搜索逻辑逐一拆开用一个可以手算的模拟案例展示它们在同样请求下的不同结局再给出一份能直接运行的Python模拟器实现最后聊一些教材不会写但做题和面试常踩的坑。适合正在学操作系统、准备保研考研复试或者想写内存池和内存模拟器的朋友。1. 为什么固定分区不够用动态分区要解决的问题1.1 固定分区的三个死穴早期的存储管理方案里最简单粗暴的做法是固定分区把内存按预设大小切成若干块每个分区可以放一个进程分区大小可以不同但一旦切好就不再变化。看起来好像很省心但只要实际跑过几个进程就知道它有多别扭。第一个问题是内部碎片。给你举个例子内存里预留了一个100KB的分区一个进程实际只需要80KB它被放进去之后那20KB就永远空在那了谁也用不上。当年内存贵得要命这种浪费是可耻的。第二个问题是缺乏灵活性进程大小和分区大小不一定对得上。如果预切的分区都小于当前要运行的作业即使内存总空闲空间足够这个作业也进不来反过来分区都太大又浪费。第三个问题是并发能力受限分区数量是固定的不可能临时多开几个进程。这些痛点逼着操作系统设计者换思路既然进程大小千变万化那不如干脆按需分配——要多少给多少用完释放剩下的空间继续给别人用。1.2 动态分区的核心矛盾外部碎片动态分区的思想听起来简单在内存里找一块够大的连续空闲区分配给进程进程结束后把这块区域重新标记为空闲。但实际跑起来问题就来了。假设内存有100KBA进程申请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)请求序列如下P1申请10KBP2申请40KBP3申请20KB释放P1释放P2P4申请20KBP5申请45KBP6申请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(funknown 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(start0, size100) # 前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 关键指标和适用场景对照实际操作下来我用一张表总结四种算法在典型负载下的表现指标First FitNext FitBest FitWorst Fit平均查找开销中低高中外部碎片总量中中严重较轻大块连续空间保留好差好差分配成功率(综合)高中中高中低实现复杂度低中中中适用场景通用、多进程中小请求密集空间紧张、需保大块请求大小均匀这张表里的适用场景是长期跑模拟器后的体会。比如嵌入式设备内存有限、请求大小相对固定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就能用重点看空闲块的数量和位置变化。只要连续打十几行日志你就能直观地看到碎片是怎么一点点产生的也能很快定位到是分配逻辑问题还是合并逻辑问题。另外如果你打算在这个模拟器基础上继续深入可以试试这两件事一是把进程申请顺序做成随机序列多跑几组再统计你会发现单一序列得出的结论经常有误导性二是在链表节点里增加一个上次分配查找步数的计数器用来评估每个策略的实际查找消耗。这些指标比肉眼看碎片状态更能说明问题。动态分区分配的价值不止存在于考试卷上很多自研内存池、嵌入式系统的内存管理里都能看到这四个算法的影子。把模拟器亲手写一遍、跑一遍你对碎片化问题的理解会有一个质的提升。 
长河君 · 2026/9/18 2:43:19 · 阅读 1.2k 动态分区分配算法详解：First Fit、Best Fit等四种策略的模拟与对比
排查内存分配失败的问题时我翻过不少模拟器代码和源码发现无论你在用户态写一个小型内存池还是在操作系统课程里做内存管理实验有一组算法永远绕不开——动态分区分配算法里的First Fit、Next Fit、Best Fit、Worst Fit。我第一次真正把这四个算法摆在一起对比是在自己动手实现空闲分区链表管理的时候同样的一串内存请求四个算法走完一轮剩余空间的碎片情况天差地别有的还能继续分配有的已经彻底碎成渣。这篇分享不是把教材概念再抄一遍。我会从固定分区为什么不行讲起把四个算法的搜索逻辑逐一拆开用一个可以手算的模拟案例展示它们在同样请求下的不同结局再给出一份能直接运行的Python模拟器实现最后聊一些教材不会写但做题和面试常踩的坑。适合正在学操作系统、准备保研考研复试或者想写内存池和内存模拟器的朋友。1. 为什么固定分区不够用动态分区要解决的问题1.1 固定分区的三个死穴早期的存储管理方案里最简单粗暴的做法是固定分区把内存按预设大小切成若干块每个分区可以放一个进程分区大小可以不同但一旦切好就不再变化。看起来好像很省心但只要实际跑过几个进程就知道它有多别扭。第一个问题是内部碎片。给你举个例子内存里预留了一个100KB的分区一个进程实际只需要80KB它被放进去之后那20KB就永远空在那了谁也用不上。当年内存贵得要命这种浪费是可耻的。第二个问题是缺乏灵活性进程大小和分区大小不一定对得上。如果预切的分区都小于当前要运行的作业即使内存总空闲空间足够这个作业也进不来反过来分区都太大又浪费。第三个问题是并发能力受限分区数量是固定的不可能临时多开几个进程。这些痛点逼着操作系统设计者换思路既然进程大小千变万化那不如干脆按需分配——要多少给多少用完释放剩下的空间继续给别人用。1.2 动态分区的核心矛盾外部碎片动态分区的思想听起来简单在内存里找一块够大的连续空闲区分配给进程进程结束后把这块区域重新标记为空闲。但实际跑起来问题就来了。假设内存有100KBA进程申请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)请求序列如下P1申请10KBP2申请40KBP3申请20KB释放P1释放P2P4申请20KBP5申请45KBP6申请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(funknown 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(start0, size100) # 前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 关键指标和适用场景对照实际操作下来我用一张表总结四种算法在典型负载下的表现指标First FitNext FitBest FitWorst Fit平均查找开销中低高中外部碎片总量中中严重较轻大块连续空间保留好差好差分配成功率(综合)高中中高中低实现复杂度低中中中适用场景通用、多进程中小请求密集空间紧张、需保大块请求大小均匀这张表里的适用场景是长期跑模拟器后的体会。比如嵌入式设备内存有限、请求大小相对固定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就能用重点看空闲块的数量和位置变化。只要连续打十几行日志你就能直观地看到碎片是怎么一点点产生的也能很快定位到是分配逻辑问题还是合并逻辑问题。另外如果你打算在这个模拟器基础上继续深入可以试试这两件事一是把进程申请顺序做成随机序列多跑几组再统计你会发现单一序列得出的结论经常有误导性二是在链表节点里增加一个上次分配查找步数的计数器用来评估每个策略的实际查找消耗。这些指标比肉眼看碎片状态更能说明问题。动态分区分配的价值不止存在于考试卷上很多自研内存池、嵌入式系统的内存管理里都能看到这四个算法的影子。把模拟器亲手写一遍、跑一遍你对碎片化问题的理解会有一个质的提升。