★ FEATURED ARTICLE 1. 分区存储管理到底在解决什么问题1.1 从一次内存告急说起很多刚接触操作系统这门课的朋友第一次听到“分区存储管理”这个词脑子里大概率是一团浆糊。教材上画了一堆方块标着“已分配”“空闲”“操作系统区”“用户区”然后就开始讲首次适应、最佳适应、最坏适应讲完就考试考完就忘。我自己当年学的时候也是这样直到后来真正去啃内存分配器的源码回头再看这一章才发现它讲的其实是一个非常朴素的问题一台机器只有一块物理内存多个程序要同时跑怎么把这块内存切好、分好、管好既不打架又不浪费。你可以把物理内存想象成一栋写字楼操作系统是物业各个进程是来租办公室的公司。分区存储管理就是最早期、最直接的一种“租房方案”——物业先把楼按楼层切成若干块每块租给一家公司公司搬走之后这块地空出来再租给下一家。听起来简单但真做起来问题一大堆切多大合适切死了还是动态切空出来的洞怎么找找哪个洞最划算洞太碎了怎么办这一章的核心就是围绕这几个问题展开的。1.2 分区管理的两种基本形态分区存储管理按“切分时机”分成两大类这个分类是理解整章的骨架必须先拎清楚。固定分区也叫静态分区。物业在开业之前就把楼层切好了比如一楼给操作系统自己用二楼到五楼切成四个固定大小的办公室每个办公室大小写死。程序来了就分配一个走了就回收。它的优点是实现极其简单分配回收就是查表改标志位几乎不花时间。缺点也很致命办公室大小是拍脑袋定的来个大公司装不下来个皮包公司又浪费一大半空间。这种“内部碎片”是固定分区天生的毛病切得越死浪费越狠。动态分区也叫可变分区。物业不预先切而是等公司来了按它实际需要的大小从空闲区域里现切一块出来。公司走了这块地还回去和相邻的空闲区域合并。这种方式灵活多了不会出现“办公室比公司大太多”的内部碎片但会催生另一种毛病——外部碎片。因为每家公司大小不一样进进出出之后整栋楼被切得七零八落空出来的洞加起来可能够大但没有一个连续的洞能装下新来的大公司。这就是外部碎片也是动态分区最头疼的问题。提示内部碎片是“分给你的比你要的多多出来的你用不上”外部碎片是“空闲的总量够但都是零碎的拼不成一整块”。这两个概念考试爱考实际调优也绕不开。1.3 为什么今天还要学它有人会问现在都用虚拟内存、分页分段了分区管理这种老古董还有必要学吗我的看法是非常有必要而且它是理解后续所有内存管理机制的基石。分页解决的就是外部碎片分段解决的是逻辑划分段页结合是两者的折中而它们要解决的问题全都是分区管理时代遗留下来的。你不理解外部碎片是怎么产生的就理解不了分页为什么要引入页表、为什么要做地址映射。你不理解动态分区的分配算法就看不懂现代内存分配器里那些 free list、buddy system 的设计思路。更实际一点说嵌入式系统、实时操作系统里分区管理至今还在用。因为它的分配时间是可预测的不会像通用分配器那样出现最坏情况下的长延迟。对实时性要求高的场景可预测性比空间利用率更重要。所以这一章不是纯理论它有真实的工程落点。2. 动态分区的四种分配算法拆解2.1 首次适应从低地址开始找第一个够用的洞首次适应First Fit的思路最直白空闲分区按地址从低到高排成一条链来一个请求就从链头开始扫找到第一个大小满足要求的空闲块切一块给它剩下的还留在链上。我拿一组具体数字走一遍你就能看明白。假设内存空闲区初始只有一块起始地址 0大小 640K。现在依次来了几个请求请求顺序请求大小分配后空闲链状态1100K[100K已用] [540K空闲]2200K[100K已用] [200K已用] [340K空闲]350K[100K已用] [200K已用] [50K已用] [290K空闲]现在释放第二个 200K 的块空闲链变成[100K已用] [200K空闲] [50K已用] [290K空闲]。这时候再来一个 150K 的请求首次适应会从低地址扫先碰到 200K 那个洞够用切 150K 出去剩 50K。它不会去管后面那个 290K 的大洞。首次适应的优点是倾向于保留高地址的大空闲区因为低地址的小洞会先被消耗掉。这样后面来大请求时高地址还有大块可用。缺点是低地址区域会被反复切割产生大量小碎片每次分配都要从低地址扫一遍扫描开销随碎片增多而上升。2.2 循环首次适应别老盯着低地址循环首次适应Next Fit是对首次适应的改进。它不再每次都从链头开始而是记住上次分配到的位置下次从那个位置往后接着找找到链尾再绕回链头。这个改动的意图很明确避免低地址区域被过度切割。首次适应老是从头扫低地址的洞被切得稀碎循环首次适应让分配指针轮转起来碎片分布更均匀。实测下来循环首次适应的分配速度比首次适应快一些因为不用每次都从头扫。但代价是它不再保留高地址的大空闲区大请求来了可能找不到足够大的连续块空间利用率反而可能下降。注意循环首次适应在考试里经常和首次适应放一起对比核心区别就一句话——首次适应每次从头扫循环首次适应从上次位置接着扫。别记混。2.3 最佳适应找最合适的那个洞最佳适应Best Fit要求空闲链按容量从小到大排序。来一个请求从头扫找到第一个够用的也就是最小的够用块切给它。还是刚才那组数据空闲链是 [200K空闲] [290K空闲]按大小排序。来一个 150K 请求最佳适应会选 200K 那个因为它是能满足要求的最小块切完剩 50K。它不会选 290K因为那会浪费 140K。最佳适应的逻辑是“尽量不浪费大块”听起来很美但实际效果往往最差。为什么因为它每次都挑最小的够用块切完之后剩下的边角料极小这些小碎片几乎再也无法被利用外部碎片反而最严重。而且空闲链要维持有序分配回收时都要排序开销也大。所以最佳适应是“理论好看、实践拉胯”的典型。2.4 最坏适应专挑最大的洞切最坏适应Worst Fit反过来空闲链按容量从大到小排序每次都选最大的空闲块来切。它的逻辑是切最大的块剩下的部分还足够大还能继续用不至于产生无法利用的小碎片。听起来也有道理但问题是它会把大块迅速消耗掉等到真正的大请求来了反而没有大块可用了。而且和最佳适应一样要维持有序链开销不小。2.5 四种算法的横向对比算法空闲链排序选择策略优点缺点首次适应按地址递增第一个够用的保留高地址大块简单低地址碎片多扫描慢循环首次适应按地址递增从上次位置起第一个够用的碎片分布均匀分配快不保留大块大请求易失败最佳适应按容量递增最小的够用块看似不浪费大块外部碎片最严重开销大最坏适应按容量递减最大的空闲块剩余块较大可用大块消耗快大请求易失败实测和理论都表明首次适应和循环首次适应综合表现最好最佳适应和最坏适应往往不如它们。这个结论和很多人的直觉相反但数据摆在那里。原因就在于分配算法的好坏不只看单次分配浪不浪费更要看长期运行后碎片的分布形态。首次适应那种“从低地址啃”的策略反而让高地址保留了大块连续空间整体上更健康。3. 碎片问题与紧凑技术3.1 外部碎片是怎么一步步积累的外部碎片的产生是一个渐进过程我用一个简化场景演示。假设内存 1000K初始一整块空闲。依次分配 A(200K)、B(300K)、C(150K)内存变成 [A 200][B 300][C 150][空闲 350]。现在释放 B空闲区变成两块[空闲 300][C 150][空闲 350]。注意这两块空闲区不连续中间隔着 C。这时候来一个 400K 的请求。空闲总量是 300350650K完全够但没有一个连续的 400K 块分配失败。这就是外部碎片的典型表现总量够连续性不够。如果 C 也被释放三块空闲区合并成 800K问题就解决了。但现实中进程的释放顺序不可控碎片就这样一点点攒起来。3.2 紧凑把碎片挤到一起解决外部碎片最直接的办法叫紧凑Compaction也叫拼接。思路是把所有已分配的分区往一端挪让空闲区合并成一大块。就像停车场里车停得七零八落管理员把所有车往一头挪腾出一整片空地。紧凑听起来简单做起来代价很大。第一移动分区意味着要修改进程的所有地址引用因为进程的物理起始地址变了。第二移动过程中进程必须暂停不能一边跑一边挪。第三紧凑本身要消耗大量 CPU 时间内存越大、碎片越多挪起来越慢。所以紧凑不能频繁做通常只在分配失败且碎片率超过阈值时才触发。提示紧凑需要重定位寄存器的支持进程里的地址都是相对地址运行时加上重定位寄存器的值才是物理地址。挪动进程时只要改重定位寄存器的值进程内部的相对地址不用动。这是紧凑能实现的前提。3.3 紧凑的触发时机与代价权衡紧凑什么时候做是个策略问题。做早了浪费 CPU做晚了分配失败影响体验。常见的触发条件有这么几种分配失败时触发最保守只在真的分不出来时才紧凑。缺点是可能已经失败了一次用户体验有损。碎片率超阈值触发比如空闲总量够但最大连续块小于请求量且碎片率超过某个百分比就提前紧凑。这个阈值需要根据负载调。周期性触发定时做一次适合负载稳定的场景。缺点是可能在不必要的时候做浪费资源。我个人的经验是分配失败时触发 碎片率阈值组合使用比较稳。单纯靠失败触发太被动单纯靠周期触发太浪费。阈值设多少要看具体场景一般碎片率超过 30% 到 40% 就可以考虑紧凑了但这个数字不是死的要结合实际请求大小分布来调。4. 分区管理的实操实现要点4.1 空闲分区链的数据结构设计动态分区的核心数据结构是空闲分区链free list。每个空闲块用一个结构体描述至少包含这几个字段typedef struct FreeBlock { int start_addr; // 起始地址 int size; // 大小 int is_free; // 空闲标志1空闲0已用 struct FreeBlock *next; // 下一个空闲块 struct FreeBlock *prev; // 上一个空闲块双向链方便合并 } FreeBlock;用双向链表而不是单向是为了回收时能方便地找到前一个块做合并。如果只用单向链回收一个块时要从头扫到它的前驱效率低。双向链多花一个指针的空间换来 O(1) 的前驱访问很划算。已分配分区也需要记录通常用另一张表或者同一个结构体加标志位。我倾向于用统一的结构体用is_free区分这样回收时不用在两套结构之间搬数据。4.2 分配操作的完整流程分配一个大小为req_size的请求流程如下遍历空闲链按选定算法首次适应/最佳适应等找到合适的空闲块。如果找不到返回失败触发紧凑或报错。如果找到的块大小刚好等于req_size直接从空闲链摘除标记为已用。如果找到的块大于req_size从块的低地址端切出req_size剩余部分留在空闲链上起始地址后移大小减小。更新相关标志位和链表指针。这里有个细节要注意切块时从低地址端切还是高地址端切。从低地址端切剩余块的高地址部分保持连续有利于后续大请求从高地址端切剩余块的低地址部分连续。一般习惯从低地址端切因为地址空间从低到高增长低地址先被消耗符合直觉。但这个不是强制的具体看实现。4.3 回收与合并的边界处理回收一个块时要检查它和前后相邻块是否空闲能合并就合并。这里有四种情况情况前邻空闲后邻空闲处理1否否直接标记为空闲插入空闲链2是否与前邻合并大小相加3否是与后邻合并起始地址不变大小相加4是是三块合并成一块合并的关键是正确找到前邻和后邻。后邻好找当前块结束地址就是后邻起始地址遍历空闲链匹配即可。前邻稍麻烦需要知道当前块的前一个物理相邻块是谁。如果空闲链按地址排序前邻就是链中地址小于当前块且结束地址等于当前块起始地址的那个。所以空闲链按地址排序是个好习惯合并时方便很多。注意合并操作一定要在回收时立即做不能拖。拖一次两次没事拖多了碎片就攒起来了后面再合并代价更大。即时合并是控制外部碎片的第一道防线。4.4 一个可运行的最小实现下面给一个简化版动态分区管理器的核心逻辑用 Python 写方便理解。实际工程用 C 写但逻辑一样。class Block: def __init__(self, start, size, is_freeTrue): self.start start self.size size self.is_free is_free self.next None self.prev None class MemoryManager: def __init__(self, total_size): self.head Block(0, total_size, True) self.tail self.head def allocate(self, req_size): cur self.head while cur: if cur.is_free and cur.size req_size: if cur.size req_size: cur.is_free False return cur.start else: # 从低地址端切 new_block Block(cur.start req_size, cur.size - req_size, True) new_block.next cur.next new_block.prev cur if cur.next: cur.next.prev new_block else: self.tail new_block cur.next new_block cur.size req_size cur.is_free False return cur.start cur cur.next return -1 # 分配失败 def free(self, start): cur self.head while cur: if cur.start start and not cur.is_free: cur.is_free True self._merge(cur) return True cur cur.next return False def _merge(self, block): # 与后邻合并 if block.next and block.next.is_free: block.size block.next.size block.next block.next.next if block.next: block.next.prev block else: self.tail block # 与前邻合并 if block.prev and block.prev.is_free: block.prev.size block.size block.prev.next block.next if block.next: block.next.prev block.prev else: self.tail block.prev这段代码实现了首次适应分配和即时合并回收。你可以拿它跑几个分配释放序列打印空闲链状态直观感受碎片是怎么产生和合并的。实际工程里还要考虑线程安全、对齐、边界检查等但核心逻辑就是这个。5. 常见问题与排查技巧实录5.1 分配失败但空闲总量明明够这是最典型的“外部碎片”症状。排查思路打印当前空闲链看最大连续空闲块是多少。对比请求大小如果最大连续块小于请求就是碎片问题。统计碎片率 1 - (最大连续空闲块 / 空闲总量)。碎片率超过阈值就触发紧凑或者调整分配算法。我踩过的一个坑是空闲链没有按地址排序导致合并时找不到前邻碎片越攒越多。后来强制每次插入都按地址排序问题就缓解了。排序有开销但相比碎片带来的分配失败这个开销值得。5.2 紧凑之后还是分配失败紧凑理论上能把所有空闲区合并成一块如果紧凑后还失败说明空闲总量本身就不够不是碎片问题。这时候要检查是不是有内存泄漏已分配块没被回收。是不是请求大小超过了物理内存总量。紧凑逻辑是不是有 bug比如漏合并了某块。排查内存泄漏可以用引用计数或者定期 dump 已分配块列表看有没有长期不释放的块。5.3 分配算法选哪个这个问题我被问过很多次。我的建议是通用场景首次适应简单可靠综合表现好。碎片敏感场景循环首次适应碎片分布均匀。实时场景固定分区分配时间可预测。大块请求多首次适应保留高地址大块。最佳适应和最坏适应除非有特殊理由一般不用。它们的理论优势在实际负载下往往体现不出来反而带来额外开销。5.4 常见问题速查表问题现象可能原因排查方法解决方向分配失败但总量够外部碎片打印空闲链看最大连续块紧凑或换算法碎片增长快未即时合并检查回收逻辑回收时立即合并合并出错空闲链未按地址排序检查插入逻辑按地址排序分配慢扫描链太长统计链长度换循环首次适应大请求总失败大块被切碎看大块消耗情况换首次适应保留大块5.5 几个容易忽略的细节对齐问题。实际内存分配要按字或页对齐不对齐会导致访问效率下降甚至硬件异常。分区管理里如果按字节分配要额外处理对齐通常向上取整到对齐边界。这会引入少量内部碎片但换来访问效率值得。边界检查。分配和回收时一定要检查地址范围防止越界。我见过因为没检查边界回收了一个不属于自己的块把整个空闲链搞乱的案例。加一行断言省一堆调试时间。并发保护。多线程环境下空闲链是共享资源分配回收都要加锁。锁的粒度可以粗可以细粗锁简单但并发差细锁复杂但性能好。分区管理本身分配快粗锁通常够用。统计与监控。生产环境要记录分配失败次数、碎片率、紧凑次数等指标这些数据是调优的依据。没有监控就是盲调效率极低。6. 从分区管理到现代内存管理的演进逻辑分区管理是内存管理的起点理解了它的局限就能理解后续所有机制为什么长成那样。分页把内存切成固定大小的页彻底消灭外部碎片代价是引入页表和地址映射开销。分段按逻辑单位切方便共享和保护但外部碎片还在。段页结合取两者之长是现代主流方案的基础。但分区管理的思想并没有消失。现代内存分配器里的 free list、buddy system、slab 分配本质上都是分区管理的变体。buddy system 就是固定分区和动态分区的结合按 2 的幂次切分合并时只合并互为伙伴的块兼顾了分配速度和碎片控制。slab 分配针对小对象做了缓存避免频繁切分大块。这些设计里都能看到分区管理的影子。所以学这一章不是为了背几个算法应付考试而是为了建立“内存是有限资源、分配有代价、碎片要管理”的基本认知。这个认知在你后面调优任何系统时都用得上。我自己在排查一个服务的内存增长问题时就是靠对碎片和分配算法的理解定位到是某个分配器参数配置不当导致碎片率过高调整后内存占用降了三成。这种问题不懂分区管理的人根本无从下手。最后分享一个我常用的练习方法拿上面那段 Python 代码自己改一改实现最佳适应和最坏适应然后设计几组分配释放序列对比四种算法的碎片率和分配成功率。跑上几十组数据你对这四种算法的直觉就建立起来了比看十遍书都管用。
阅读完成 · 觉得有帮助？
