分区存储管理实战：从分配算法到碎片合并的完整模拟

1. 分区存储管理到底在解决什么问题

1.1 从一次内存告急说起

很多同学第一次接触操作系统里的存储管理，都是在做课程设计或者准备面试的时候。我当时也一样，看到“分区存储管理”这六个字，第一反应就是：不就是把内存切成几块吗，有什么好讲的。结果真到动手写模拟程序的时候，才发现坑远比想象中多——碎片怎么算、分配算法怎么选、回收之后怎么合并，每一个细节都能让人卡上大半天。

分区存储管理，说白了就是操作系统早期用来管理内存的一套办法。它的核心思路非常朴素：把物理内存划分成若干个区域，每个区域装一个进程，进程用完就释放，释放出来的区域再留给下一个进程。它要解决的问题也很直接——多个程序同时驻留内存时，怎么让它们互不打架，怎么让有限的内存尽量装下更多的程序。

这套东西今天看起来有点“原始”，因为现代操作系统早就用上了分页、分段、虚拟内存这些更高级的机制。但你别小看它，分区存储管理是理解后续所有内存管理技术的基石。分页里的“页框分配”、分段里的“段表”、甚至虚拟内存的“换入换出”，底层思想都能在分区管理里找到影子。所以不管你是为了应付考试、准备面试，还是想真正搞懂操作系统怎么管内存，这一块都绕不过去。

这篇文章适合谁看？如果你是计算机相关专业的学生，正在学操作系统课程，那这篇能帮你把课本上干巴巴的概念变成能跑起来的代码；如果你是准备面试的求职者，分区管理的几种算法和碎片问题是高频考点，我会把容易问到的细节都拆开讲；如果你只是对底层原理好奇的开发者，那更好，我会尽量用生活化的类比把原理讲透，不堆砌术语。

接下来我会从整体设计思路讲起，然后逐个拆解核心算法和数据结构，再给出一套可以直接复现的实操方案，最后把我踩过的坑和常见问题整理成速查表。全程按从业者分享经验的节奏来，不搞教科书那套。

2. 整体设计思路与方案选型

2.1 为什么会有“固定”和“动态”两条路线

分区存储管理最核心的分歧点，就在于分区是“提前切好”还是“用时再切”。这两条路线分别对应固定分区和动态分区，它们的设计取舍直接决定了整个系统的行为特征。

固定分区，顾名思义，就是在系统启动的时候，把内存一次性切成若干块，每块大小固定，之后不再改变。每个分区只能装一个进程，进程来了就找一个够大的空分区塞进去。这种做法的好处是管理极其简单，操作系统只需要维护一张分区表，记录每个分区的大小、起始地址和占用状态就行。但它的毛病也很明显：分区大小是拍脑袋定的，定大了浪费，定小了装不下。比如你把内存切成10MB、20MB、50MB三块，结果来了个25MB的进程，50MB那块装它，剩下25MB就白白空着，这就是所谓的“内部碎片”——分区内部用不上的空间。

动态分区则灵活得多。它不提前切分，而是等进程来了，根据进程实际需要的大小，从一块大的空闲区域里“切”出刚好够用的一块分配出去。进程走了，这块区域再还回来。这样理论上不会有内部碎片，因为分配的大小就是进程要的大小。但代价是管理复杂了，而且会产生“外部碎片”——空闲区域被已分配区域隔开，变得零零散散，单个空闲块可能都不够大，但加起来其实够用。

我个人的经验是，理解这两条路线的关键，不在于记住定义，而在于想清楚它们各自在“空间利用率”和“管理开销”之间做了什么权衡。固定分区是用空间换简单，动态分区是用复杂换灵活。实际教学和模拟中，动态分区是绝对的主角，因为它引出了分配算法、碎片整理、回收合并这一整套有意思的问题。所以后面的重点会放在动态分区上，固定分区作为对照简单带过。

2.2 动态分区管理的三个核心动作

动态分区管理看起来复杂，但拆开来看，其实就三个动作在循环：分配、回收、合并。把这三个动作想清楚了，整个系统就通了。

分配，就是进程请求内存时，从空闲区域里找一块合适的给它。这里“合适”怎么定义，就引出了首次适应、最佳适应、最坏适应等不同的分配算法。回收，就是进程结束时，把它占用的区域标记为空闲。合并，是回收之后的关键一步——如果回收的区域旁边正好也是空闲的，就要把它们拼成一块更大的空闲区域，否则空闲区会越切越碎。

这三个动作里，合并最容易被忽略，但它恰恰是决定碎片严重程度的关键。我见过不少同学写的模拟程序，分配和回收都实现了，就是忘了合并，结果跑不了几轮，空闲区就碎成一地，明明总空闲量够，却再也分配不出大块内存。所以你在设计的时候，一定要把合并逻辑当成一等公民来对待，而不是事后补丁。

2.3 数据结构怎么选：空闲表还是空闲链表

实现动态分区，绕不开一个问题：空闲区域用什么数据结构来记录。常见的有两种，空闲分区表和空闲分区链。

空闲分区表就是一个数组或者列表，每一项记录一个空闲区的起始地址和大小。它的优点是直观，遍历、查找、修改都方便，适合教学演示。缺点是插入和删除元素时可能要移动大量数据，效率一般。

空闲分区链则是把空闲区用指针串起来，每个节点记录起始地址、大小和指向下一个空闲区的指针。它的优点是插入删除快，而且可以按地址顺序串联，方便回收时判断相邻关系。缺点是查找需要遍历链表，而且指针操作容易出错。

我在做模拟的时候，两种都用过。如果是纯粹为了讲清楚算法逻辑，空闲分区表更省心，代码可读性高。但如果想更贴近真实操作系统的做法，空闲分区链更合适，尤其是按地址排序的双向链表，回收合并的时候特别顺手。我的建议是，初学阶段先用表把逻辑跑通，等逻辑没问题了，再改成链去体会工程上的取舍。这样循序渐进，不容易一上来就被指针绕晕。

3. 核心算法拆解与实操要点

3.1 首次适应、最佳适应、最坏适应到底怎么选

分配算法是分区管理的灵魂，不同的算法直接决定了碎片的分布形态。下面把三种最经典的算法掰开讲。

首次适应，就是从空闲区列表的头部开始找，找到第一个大小足够的就分配。它的逻辑最简单，速度也快，因为不用遍历整个列表。但它有个特点：低地址部分会被反复切割，变得很碎，而高地址部分的大块空闲区反而被保护得很好。这其实不完全是坏事，因为大块空闲区留着，后面来了大进程还能装得下。

最佳适应，是遍历整个空闲列表，找到能满足要求且最小的那块来分配。听起来很“精打细算”，但它有个致命问题：每次分配都留下最小的剩余碎片，这些碎片小到几乎再也用不上，于是外部碎片会迅速累积。所以最佳适应在实际表现中往往是最差的，这点很多人第一次学的时候会感到意外。

最坏适应，反过来，每次都挑最大的那块来分配。它的逻辑是：反正都要切，那就切最大的，剩下的部分还足够大，还能继续用。这个思路有一定道理，但它会把大块空闲区很快消耗掉，导致后面来了大进程反而没地方放。

为了让你直观对比，我整理了一张表：

算法	查找方式	优点	缺点	碎片倾向
首次适应	从头找第一个够大的	速度快，保留大块	低地址碎片多	中等
最佳适应	找最小的够用块	单次浪费最小	产生大量微小碎片	严重
最坏适应	找最大的块	剩余块较大	大块被快速耗尽	中等偏重

实测下来，首次适应的综合表现往往最好，这也是为什么很多真实系统在类似场景下会倾向于它或者它的变种。最佳适应虽然名字好听，但实际效果经常垫底，这个反差值得你亲手跑一遍数据去体会。

3.2 回收与合并：最容易被写错的地方

回收一个区域，表面上看就是把它标记为空闲，但真正的难点在于合并。合并要处理四种情况，我把它总结成一句话：看前看后，四种组合。

具体来说，回收区域为R，检查它前面紧邻的区域是否空闲，再检查它后面紧邻的区域是否空闲。四种情况分别是：前后都忙，那就直接把R标记为空闲，独立成块；前忙后闲，把R和后面的空闲块合并；前闲后忙，把R和前面的空闲块合并；前后都闲，三块合并成一块。

这里的关键是“紧邻”的判断，必须基于地址连续性。也就是说，前一个空闲区的起始地址加上它的大小，正好等于R的起始地址，才算紧邻。很多同学写合并的时候只判断了“有没有空闲区”，忘了判断地址是否连续，结果把不相邻的空闲区也合并了，程序直接出错。

还有一个细节：合并之后，空闲区列表的排序可能会被打乱。如果你用的是按地址排序的链表，合并后需要重新调整位置。我的做法是，回收时先按地址找到插入点，插入后再统一做前后合并，这样逻辑最清晰，不容易漏。

提示：合并逻辑一定要单独写成一个函数，并且用单元测试覆盖四种情况。我当初就是图省事把合并揉在回收里，结果调试的时候根本分不清是回收错了还是合并错了，白白多花了两小时。

3.3 碎片问题的量化与应对

碎片是分区管理的宿敌，但很多人只是模糊地知道“有碎片”，却不知道怎么量化它。其实有两个指标很实用：外部碎片总量和最大可用空闲块。

外部碎片总量，就是所有空闲区大小之和减去最大空闲区大小，它反映了“被浪费在零散小块里的内存”。最大可用空闲块，则决定了当前还能不能装下一个大进程。这两个指标结合起来看，就能判断系统的健康程度。比如总空闲有100MB，但最大块只有5MB，那说明碎片已经很严重了，虽然总量够，但大进程根本进不来。

应对碎片，主要有两条路：紧凑和置换。紧凑就是把所有已分配区域往一端挪，把空闲区挤到另一端拼成大块。这个操作能彻底消除外部碎片，但代价是要移动大量数据，而且移动期间系统基本得暂停，开销很大。置换则是把某些进程暂时挪到外存，腾出内存空间，这已经属于虚拟内存的范畴了。

在模拟程序里，我建议至少实现一个碎片统计功能，每轮分配回收后打印一下碎片指标。这样你能直观看到不同算法下碎片增长的速度差异，比看课本上的静态描述有说服力得多。

4. 完整实操流程与关键环节实现

4.1 环境准备与整体框架搭建

这套模拟程序用什么写都行，Python、Java、C++都可以。我选Python，因为它写起来快，列表操作方便，适合把精力集中在算法逻辑上而不是内存管理本身。如果你用C++，那更贴近底层，但要自己管指针，调试成本高一些。

整体框架我分成三个模块：内存模型、分配器、调度器。内存模型负责维护空闲区和已分配区的状态；分配器实现三种分配算法和回收合并；调度器模拟进程的到达和离开，驱动整个流程。这样分层的好处是，换算法只需要改分配器，内存模型和调度器不用动。

内存模型我用一个列表来表示，每个元素是一个字典，记录起始地址、大小、状态（空闲或占用）、占用它的进程ID。初始时整个内存是一块大的空闲区。这里有个小技巧：地址和大小都用整数，单位统一，避免浮点数带来的精度问题。

class MemoryBlock: def __init__(self, start, size, is_free=True, pid=None): self.start = start self.size = size self.is_free = is_free self.pid = pid class MemoryManager: def __init__(self, total_size): self.blocks = [MemoryBlock(0, total_size, True)] self.total_size = total_size

这段代码是整个系统的地基，看起来简单，但字段设计要想清楚。比如pid字段，回收的时候要靠它找到对应的块，所以分配时必须记上。

4.2 三种分配算法的代码实现

先看首次适应。它的逻辑是从头遍历，找到第一个大小足够的空闲块就分配。

def first_fit(self, size, pid): for block in self.blocks: if block.is_free and block.size >= size: return self._allocate(block, size, pid) return None

_allocate是公共的分配动作：如果空闲块比请求的大，就把它切成两块，前面一块给进程，后面一块留作空闲；如果刚好相等，直接标记为占用。

最佳适应需要遍历所有空闲块，记录下满足条件且最小的那个。

def best_fit(self, size, pid): best = None for block in self.blocks: if block.is_free and block.size >= size: if best is None or block.size < best.size: best = block if best: return self._allocate(best, size, pid) return None

最坏适应则是找最大的那个，逻辑类似，只是比较方向反过来。

这里有个实现细节要注意：_allocate在切割块的时候，要保证新块的起始地址正确。前面给进程的块起始地址不变，大小变成请求大小；后面空闲块的起始地址是原起始地址加请求大小，大小是原大小减请求大小。这个加法减法千万别搞反，我见过有人把起始地址算错的，结果内存块直接重叠。

4.3 回收与合并的完整实现

回收的入口是进程ID，先找到对应的已分配块，标记为空闲，然后触发合并。

def free(self, pid): for block in self.blocks: if not block.is_free and block.pid == pid: block.is_free = True block.pid = None self._merge() return True return False

合并函数是重点。先把所有块按起始地址排序，然后从头扫一遍，如果当前块空闲且下一块也空闲，就合并它们，合并后大小相加，然后继续检查。

def _merge(self): self.blocks.sort(key=lambda b: b.start) i = 0 while i < len(self.blocks) - 1: cur = self.blocks[i] nxt = self.blocks[i + 1] if cur.is_free and nxt.is_free: cur.size += nxt.size self.blocks.pop(i + 1) else: i += 1

这段代码看着短，但它是整个程序正确性的关键。排序保证了相邻判断的准确性，while循环里的pop要小心索引，合并后不要急着i加一，因为新的下一块可能还能合并。

4.4 模拟调度与碎片统计

调度器负责生成一系列进程请求，每个请求包含进程ID、所需大小、到达时间和运行时长。为了简单，我用一个事件列表来驱动，按时间顺序处理到达和离开。

def simulate(manager, requests, algorithm): time = 0 events = [] for req in requests: events.append((req['arrive'], 'arrive', req)) events.append((req['arrive'] + req['duration'], 'leave', req)) events.sort() for t, etype, req in events: if etype == 'arrive': result = algorithm(req['size'], req['pid']) if result is None: print(f"时间{t}: 进程{req['pid']}分配失败，内存不足") else: manager.free(req['pid']) print_stats(manager, t)

print_stats打印当前空闲块数量、外部碎片总量和最大空闲块。跑一遍下来，你就能看到不同算法下这些指标的变化曲线。我实测过一组随机请求，首次适应的最大空闲块下降得比较慢，最佳适应则很快就把大块切没了，碎片总量飙升。

注意：模拟的请求序列最好固定下来，用同一组数据对比三种算法，否则变量太多，结论没有说服力。我一般会生成一组随机请求后存成文件，三种算法都读同一份。

5. 常见问题与排查技巧实录

5.1 分配失败但明明有足够空闲

这是最典型的问题。现象是总空闲内存明明大于请求大小，但分配就是失败。原因几乎可以肯定是外部碎片——空闲区被切得太碎，单个块都不够大。

排查方法很简单，打印出所有空闲块的起始地址和大小，看看最大的那块是多少。如果最大块小于请求大小，那就是碎片问题。解决办法有两个：一是换分配算法，比如从最佳适应换成首次适应，看看是否改善；二是实现紧凑功能，把空闲区合并到一端。

我当初遇到这个问题的时候，第一反应是代码有bug，查了半天分配逻辑，最后才发现是碎片。所以建议你在分配失败时，第一件事就是打印空闲块详情，而不是盯着分配代码看。

5.2 合并之后内存块重叠或丢失

合并写错，轻则碎片统计不准，重则内存块地址重叠，整个模拟结果全乱。常见错误有三种：忘了排序就判断相邻、合并后起始地址没更新、pop之后索引没处理好。

排查的时候，可以在每次合并前后打印所有块的起始和结束地址，检查是否有重叠（前一块的结束地址大于后一块的起始地址就是重叠）。另外，合并后所有块的总大小应该始终等于内存总量，这个不变量可以用来验证正确性。我习惯在每轮操作后加一句断言，检查总大小是否守恒，一旦不守恒立刻报错，能快速定位问题。

5.3 不同算法结果差异不明显

有同学跑完发现三种算法结果差不多，就以为算法没用。这通常是因为请求序列设计得不好——如果所有请求大小都差不多，或者内存远大于总需求，那算法差异自然体现不出来。

要让差异明显，请求序列要满足两个条件：一是大小分布要广，既有小块也有大块；二是总需求要接近甚至超过内存容量，制造一定的分配压力。我一般会设计成小块占多数、偶尔来一个大块的模式，这样首次适应保留大块的优势和最佳适应切碎大块的劣势都会暴露出来。

5.4 常见问题速查表

问题现象	可能原因	排查方法	解决思路
分配失败但空闲够	外部碎片	打印最大空闲块	换算法或紧凑
内存块重叠	合并逻辑错误	检查地址连续性	排序后合并，校验总大小
算法差异不明显	请求序列不合理	看大小分布	设计大小混合、高压力序列
回收后找不到块	pid记录错误	检查分配时pid	分配时务必写入pid
碎片增长过快	算法选择不当	对比碎片指标	优先首次适应

5.5 几个课本不会讲的实操心得

第一，别一上来就追求功能全。我见过有同学一开始就想把紧凑、置换全实现，结果基础分配都没跑通。正确的顺序是先让首次适应加回收合并跑起来，再加其他算法，最后才考虑紧凑。

第二，日志比调试器好用。内存管理这种状态变化频繁的程序，打断点很容易迷失。我习惯在每个关键操作后打印一行状态摘要，跑完一遍看日志，问题一目了然。

第三，用不变量做自检。总内存守恒、空闲块不重叠、已分配块不重叠，这几条不变量在每轮操作后都检查一遍，能挡掉绝大多数低级错误。这个习惯我从做这个模拟开始养成，后来做其他项目也一直受益。

第四，对比实验要控制变量。同一组请求、同样的初始内存，只换算法，这样得出的结论才可信。我一般会把结果导出成表格，横向对比，比凭感觉判断靠谱得多。

这套分区存储管理的模拟，看起来是个小项目，但真做下来，对内存管理的理解会上一个台阶。等你把碎片、合并、算法差异都亲手跑过一遍，再去看分页和虚拟内存，会发现很多概念都是相通的。我个人在实际操作中的体会是，底层原理这东西，光看是看不明白的，非得自己写一遍、错一遍、改一遍，才能真正变成自己的东西。