连续分配与碎片
基于通用操作系统概念 · 核于 2026-08
速查
- 固定分区（Fixed Partitioning）：内存预切成大小固定的分区，每分区一道进程；小进程进大分区 → 分区内剩余浪费 → 内部碎片（Internal Fragmentation）。分区大小一旦切定不变，分配/释放 O(1)，但空间利用率低。
- 动态分区（Dynamic Partitioning）：按进程需求恰好分配，无内部碎片；但分配/释放后产生大量小空洞 → 外部碎片（External Fragmentation）——总空闲够但无大块连续可用。
- 内部碎片 vs 外部碎片：内部=分配给进程的块内部有浪费（块大于需求，固定分区/伙伴系统）；外部=空闲块之间太碎凑不成大块（动态分区）。
- 首次适应（First-Fit）：从头扫描，第一个够大的空闲块即分配。低地址区被频繁切割 → 低地址碎片多；但扫描快，实际系统最常用。
- 最佳适应（Best-Fit）：扫描所有空闲块，选最小的够大块。省大块，但产生大量极小不可用碎片（恰好剩一点点），外部碎片最严重。
- 最坏适应（Worst-Fit）：选最大的空闲块分配（剩一大块给别人用）。减少小碎片，但大块很快耗尽，大进程一来就分配失败。
- 紧凑（Compaction）：搬移进程把零散空闲合并成大块。前提是执行时绑定（地址可动态重定位）；且要停机、开销大（搬整段内存 + 改映射），现实中很少频繁做。
- 碎片衡量：外部碎片用"总空闲 vs 最大连续空闲块"的差距衡量——总空闲 100MB 但最大块只有 5MB，则 95MB 是碎片。
- 放置策略复杂度：首次/最佳/最坏适应分配都要扫描空闲链表，最坏 O(n)；释放合并相邻空闲块 O(n)（找邻居）。这是伙伴系统 O(log n) 要改进的目标。
一、固定分区：内部碎片之源
固定分区（Fixed/Static Partitioning）在系统启动时就把用户区切成若干大小固定的分区（可等大，也可分成几档大小如小/中/大分区）。每个分区容纳一道进程：
内存
┌──────────┐
│ OS 区 │
├──────────┤
│ 分区1 8MB│ ← 进程A(2MB)，剩 6MB 内部碎片
├──────────┤
│ 分区2 8MB│ ← 进程B(7MB)，剩 1MB 内部碎片
├──────────┤
│ 分区3 8MB│ ← 空
├──────────┤
│ 分区4 8MB│ ← 进程C(3MB)，剩 5MB 内部碎片
└──────────┘- 内部碎片（Internal Fragmentation）：分区内未被进程用到的剩余空间。它被锁死在分区里，其他进程无法使用，纯浪费。分区越大、进程越小，浪费越严重。
- 优点：分配/释放极快（查分区表找个空分区即可），管理简单，硬件只需 base/limit 保护寄存器。
- 缺点：①小进程占大分区浪费（内部碎片）；②分区大小固定，进程大于最大分区就无法运行；③同时运行的进程数 ≤ 分区数。
- 改进——多档分区：切出几档不同大小（如若干小分区给小进程、几个大分区给大进程），按进程大小选合适分区，缓解内部碎片。IBM OS/360 的 MFT（固定任务数多道）用过。
二、动态分区：外部碎片之源
动态分区（Dynamic/Variable Partitioning）不预切，按进程实际需求恰好分配。维护一条空闲链表（free list），分配时从中找一块够大的切出来，释放时归还并尝试与相邻空闲块合并：
初始 分配A(2MB)B(7MB)C(3MB) 释放B后
┌────────┐ ┌────────┐ ┌────────┐
│ OS │ │ OS │ │ OS │
├────────┤ ├────────┤ ├────────┤
│ │ │ A 2MB │ │ A 2MB │
│ │ ├────────┤ ├────────┤
│ │ │ B 7MB │ │ 空7MB │ ← 与前后
│ 空闲 │ ───> │ │ ───> │ │ 空闲合并
│ │ ├────────┤ ├────────┤
│ │ │ C 3MB │ │ C 3MB │
│ │ ├────────┤ ├────────┤
└────────┘ │ 空闲 │ │ 空闲 │
└────────┘ └────────┘- 无内部碎片：分给进程的块恰好等于需求（切出来的就是进程要的大小），块内无浪费。
- 外部碎片（External Fragmentation）：随进程反复分配/释放，空闲空间被打碎成许多小块，散落在已分配块之间。空闲总量可能很大，但找不到一块连续的够大区域给新进程。这是动态分区的致命伤。
- 例子：总空闲 60MB，但分成 20+20+20 三块散布，则一个要 30MB 的进程分配失败——这就是外部碎片。
- 缓解手段：①用好的放置策略（首次/最佳/最坏适应）减少碎片产生；②紧凑 compaction（搬移合并）；③最终解法是非连续分配（分页，下一叶）彻底打散进程。
三、三种放置策略
动态分区分配一个进程时，空闲链表里可能有多个够大的块，选哪个？这就是放置策略（Placement Strategy）：
| 策略 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 首次适应（First-Fit） | 从头扫描，选第一个够大的块 | 快（找到即停）；最常用 | 低地址区被反复切割，碎片集中在低地址 |
| 最佳适应（Best-Fit） | 扫描所有块，选最小的够大块 | 省大块（保留大块给大进程） | 产生大量极小不可用碎片，外部碎片最严重 |
| 最坏适应（Worst-Fit） | 扫描所有块，选最大的块分配 | 剩一大块给别人，减少小碎片 | 大块迅速耗尽，大进程很快无块可分 |
- 首次适应：实验证明综合性能最好（扫描快、碎片可接受），是实际系统（早期 Unix、嵌入式分配器）的默认选择。
- 最佳适应：直觉上"最省"，但每次都恰好剩一点点 → 那一点点几乎没人能用 → 碎片灾难。慎选。
- 最坏适应：每次切大块，短期内小碎片少，但大块是稀缺资源，几次后就没了 → 大进程频繁失败。
- 复杂度：三者最坏都要 O(n) 扫描空闲链表。这是连续分配相对分页/伙伴系统的劣势之一。
四、内部碎片 vs 外部碎片
这两个概念极易混淆，必须分清——区别在碎片的位置：
| 内部碎片（Internal） | 外部碎片（External） | |
|---|---|---|
| 在哪 | 分配块内部（块 > 需求） | 空闲块之间（散碎凑不成大块） |
| 谁产生 | 固定分区、伙伴系统（向上取整） | 动态分区（频繁分配/释放） |
| 能否用 | 不能——已被分给某进程，锁死在块内 | 理论能——总空闲够，只是不连续 |
| 解法 | 让块大小接近需求（slab/可变块） | 紧凑 compaction / 分页打散 |
- 记忆口诀：内碎片"块里多了点用不掉"，外碎片"块间碎得拼不起来"。
- 伙伴系统两个都有：要 17KB 给 32KB（内碎片 15KB）；同时多次分配释放产生不连续小块（外碎片）。
- 分页是消除外碎片的利器——把进程打散到任意空闲页框，外碎片归零；但页内最后一格可能浪费（极小的内碎片）。
五、碎片整理：紧凑 compaction
对付外部碎片最直接的办法是紧凑（Compaction）——把已分配的进程搬移到内存一端，把零散空闲挤到另一端合并成大块：
紧凑前（碎片化） 紧凑后（连续空闲）
┌────────┐ ┌──┐┌─┐┌──┐ ┌────────┐┌──┐┌─┐┌──┐┌──────┐
│ A │ │空││B│ │空│ ──> │ A ││ B│ │C │ │大空闲│
│ │ │隙││ │ │隙│ │ ││ │ │ │ │ │
└────────┘ └──┘└─┘└──┘ └────────┘└──┘└──┘└──────┘- 前提：执行时绑定。搬移进程意味着进程的物理地址变了——只有在执行时绑定（MMU 动态翻译地址）下才能搬（改 base 寄存器或页表即可）。编译时/加载时绑定的进程搬了就地址全错。
- 代价高昂：①要搬移整段进程内存（拷贝几十 MB，慢）；②要更新所有地址映射；③停机进行（搬移中进程不能运行）。所以现实中很少频繁紧凑，多数系统用分页绕开它。
- 替代：移动与固定分区都救不了根本矛盾，分页（下一叶）让进程无需连续，从根本上消除外部碎片。
六、连续分配为何让位给分页
连续分配的矛盾——固定分区内碎片、动态分室外碎片、紧凑贵——催生了非连续分配：把进程打散到不连续的内存区域（页框），靠页表翻译逻辑地址到物理地址。这样：①进程无需大块连续内存，外部碎片归零；②页框大小固定，分配/释放 O(1)；③支持换页（虚拟内存）。这是下一叶的主题。但分页引入了页表存储与 TLB 的开销，伙伴系统/slab 仍是物理内存分配的底层。
下一步
连续分配的碎片问题讲清后，下一步看内存管理的两个高效分配机制——伙伴系统与 Slab 分配讲透 2 的幂次分配合并（O(log n)）与内核对象池复用，并引入非连续分配（分页/分段）作为下一叶的引子。