内存还剩 8GB 空闲，malloc 为什么还会失败？——连续分配、碎片与三种“适应“算法

内存还剩 8GB 空闲，malloc 为什么还会失败？——连续分配、碎片与三种"适应"算法

有一次线上事故，查到最后谁都没想到：机器 free 显示还有 8GB 空闲内存，可一个进程 malloc 一块 4GB 的连续内存，直接返回 NULL。运维看着监控懵了——“内存明明剩这么多啊？”

问题不在"总量够不够"，而在"够不够连续"。那 8GB 是散落在内存各处的一堆小空洞，加起来够，但没有一块连续的 4GB。这就是外部碎片（external fragmentation）——操作系统内存管理里最经典、也最容易让人栽跟头的问题。

这也是 408 操作系统（35 分）"内存管理"一章的核心考点：三种连续分配算法（首次/最佳/最坏适应）、内部碎片与外部碎片、紧凑、伙伴系统。选择题年年在这上面做文章。今天把它一次算清楚。

一、先定义两类碎片，别混

内存分配后，碎片分两种，名字像、本质完全不同：

• 内部碎片（internal fragmentation）：已经分给进程的那块内存里，没用完的部分。比如进程要 3KB，系统按 4KB 的固定单位给，多出来的 1KB 被"包"在分配块内部，别人用不了——这叫内部碎片。
• 外部碎片（external fragmentation）：空闲内存之间的那些小空洞。它们彼此不相邻，每一块单独看都不够大，但加在一起可能绰绰有余——就像开头那 8GB。

一句话记：内部碎片在"块里面"，外部碎片在"块之间"。

二、三种"适应"算法：各有什么脾气

连续分配的大前提：给进程分配一块物理上连续的内存。空闲内存用一张"空闲分区表/链表"维护（记录每块空闲区的起始地址和大小）。来了一个大小为 n 的请求，算法负责"从哪块空闲区切"。区别只在挑选策略，所以才有三种"适应"：

2.1 首次适应（First Fit）

从头开始找，碰到第一个"够大"的空闲区就切。

• 复杂度：最坏 O(m)（m 是空闲区个数），但平均很快——因为够大的块往往在前面就找到了。
• 特点：低地址区被频繁切割，留下很多小碎片；高地址区相对完整，留给大请求。
• 一句话：先到先得，图快。

2.2 最佳适应（Best Fit）

找"最贴合请求大小"的那个空闲区——即所有够大的块里，剩余最小的那个。

• 复杂度：要遍历全表 O(m)（或按大小排序的空闲链表）。
• 特点（最反直觉的一点）：它追求"切得刚刚好"，结果每次剩下的都是最小的碎屑，这些碎屑小到几乎再也装不下任何请求 → 反而产生最多的小碎片（外部碎片）。最佳适应，名字好听，碎片最惨。
• 一句话：精打细算，却把内存切成一地碎渣。

2.3 最坏适应（Worst Fit）

找最大的空闲区切，让剩下的块尽可能还大、还能用。

• 复杂度：也要遍历全表 O(m)。
• 特点：剩余块大，暂时不碎；但最大的块很快被越切越小，大请求很快找不到家。
• 一句话：拆东墙补西墙，大块先被消耗光。

三种算法没有绝对最优，只有取舍——这跟进程调度"没有最好、只有最合适"是同一个道理（见进程调度为什么没有「最好」只有「最合适」？）。

三、用一个具体例子，把外部碎片"算"出来

设内存总共 100MB，按顺序发生：

① 分配 A = 20MB （剩 80MB 连续）
② 分配 B = 30MB （剩 50MB 连续）
③ 分配 C = 40MB （剩 10MB 连续）
④ 释放 B（30MB） （空闲区变成两块：30MB 和 10MB，不连续）
⑤ 请求 D = 35MB

此刻空闲内存总量 = 30 + 10 = 40MB，远大于 35MB，但没有任何一块连续空闲区 ≥ 35MB → D 分配失败。这就是外部碎片：总量够，连续不够。

想救它，唯一的办法是紧凑（Compaction）：把 A、C 这些"活的"进程整体往一端挪，把散落的 30MB 和 10MB 挤成一整块 40MB。但紧凑有两个代价：

所以紧凑不是免费午餐，这也是它只能偶尔做、不能天天做的原因。

四、伙伴系统：用"2 的幂"把分裂和合并管起来

连续分配还有一条更工程化的路线——伙伴系统（Buddy System）。它不维护一张"任意大小"的空闲链表，而是把内存按 2 的幂次切成若干块：

2

0

,

2

1

,

2

2

,

…

,

2

k

2^0, 2^1, 2^2, \\dots, 2^k

20,21,22,…,2k，每个大小各维护一条空闲链表。

分配（请求 n，先对齐到 2 的幂）：找"最小的、够大的"那个 2 的幂块；如果它比需要的大，就不断一分为二，直到恰好装下（或再分就不够），把另一半放回对应链表。

释放：检查它的伙伴——即"地址相邻、大小相同、且起始地址按块大小对齐"的那块——如果伙伴也空闲，就合并成更大的块，再继续往上合并。

为什么这样设计？ 因为"伙伴"关系是严格成对的：一块 8KB 只能由两块相邻的 4KB 拼成，这两块 4KB 也互为唯一伙伴。于是合并操作是 O(1) 判定的（算一下地址就知道伙伴是谁），整个分配/释放复杂度 O(log n)。

代价：因为只能按 2 的幂分配，请求 3KB 会拿到 4KB 块，那 1KB 就成了内部碎片。所以伙伴系统是"用内部碎片换外部碎片的可控"——碎片还可能有，但不会再出现"总量够、连续不够"的失控局面。

给个数字：请求 100KB，

2

6

=

64

<

100

≤

2

7

=

128

2^6=64 < 100 \\le 2^7=128

26=64<100≤27=128，于是从 128KB 块里切，浪费 28KB 内部碎片。

五、为什么现代系统最终抛弃了"连续分配"

连续分配绕不开外部碎片这个死结，紧凑又太贵。于是人们换了个思路：干脆不要求物理连续——把物理内存切成固定大小的页框（page frame），进程的每一页放进任意一个页框，靠一张页表记录"第 i 页在哪"。物理上散落没关系，逻辑上依然连续。这就是分页（非连续分配），它彻底消灭了外部碎片（每页都等大，任何空闲页都能塞进任何页）。

所以你看，从连续分配到分页，本质上是一次"用页表（额外开销）换碎片（内存浪费）"的取舍。理解了连续分配的碎片之痛，你就懂了分页为什么长成那样。

六、408 怎么考，几个高频坑

这部分属于 408 操作系统"内存管理"的选择题高频区，常结合"给定请求序列，用三种算法分别画出分配结果"出小题。复杂度分析如果心里没底，可以回顾（为什么你写得出代码，却说不出它"有多快"？——时间复杂度，一次讲透）。

七、收个尾

回到开头那个"8GB 空闲却 malloc 失败"的现场。它不是 bug，是外部碎片在教我们：内存管理的本质从来不是"有多少给多少"，而是"怎么给，才不会越给越碎"。连续分配用三种"适应"算法去挑、用紧凑去救、用伙伴系统去控，最后还是败给了碎片，才有了分页。每一次方案迭代，都是在跟"碎片"这个甩不掉的对手周旋。

留一道练手题：内存 64KB，依次分配 A=8KB、B=16KB、C=32KB，释放 B，再请求 20KB。用首次适应和最佳适应分别模拟，画出空闲区变化，并判断这次产生了哪种碎片、20KB 能否成功分配。想不通的空闲区划分，可以用 CoLearn（yantucs.com） 的 AI 答疑就着你画错的那一步问。

操作系统内存管理这块和数据结构、组成原理的存储系统紧密联动，是 408 的拿分重头，推荐 B 站【408实验室】的《数据结构》把复杂度分析的地基打牢，再回头啃内存管理会顺很多。