地址空间与内存分配：碎片与适配算法

一句话定义

操作系统为每个进程提供从 0 开始、看起来独占整机的虚拟地址空间；把虚拟地址落到物理内存需要分配策略，连续分配的三大适配算法（首次/最佳/最坏适配）与碎片问题是其经典模型。

为什么重要

"每个程序都以为自己独占整台机器"是内存虚拟化的第一直觉冲击，理解它之后，分页（kp-017）、虚拟内存（kp-018）、COW（kp-007）才有了叙事起点。碎片问题则解释了为什么现代系统全部转向分页，以及 malloc 慢、内存涨不回等日常现象的根源。

前置知识

kp-002（内存与总线的基本模型）。

核心概念

• 虚拟地址 vs 物理地址：程序看到与使用的是虚拟地址，真实访问前由硬件翻译。
• 地址空间布局：代码段、数据段、堆（向上涨）、栈（向下长）、内核区（高地址），空洞与随机化见 kp-020。
• 内碎片：分给你的块里用不到的部分（固定块大小造成）。
• 外碎片：总空闲量够但被切成不连续小块，无法满足大请求（动态分配造成）。
• 适配算法：首次适配（first fit）、最佳适配（best fit）、最坏适配（worst fit）、以及分离空闲链表等工程改进。
• 紧凑（compaction）：搬移进程合并空洞——纯软件开销大，分页是它的替代答案。

原理与机制

连续分配下空闲区是一条空洞链表，分配时按策略挑选：

物理内存空洞(单位KB): [100 | 30 | 60 | 200 | 40]   请求: 50KB

首次适配: 选第一个放得下的 -> 100 的洞 -> 剩余 50+碎片, 速度快
最佳适配: 遍历选最小可容纳 -> 60 的洞 -> 剩 10KB 极小碎片, 恰是最坏的小碎片制造者
最坏适配: 选最大 -> 200 的洞 -> 剩 150, 但很快把大洞用光

关键洞察：三种朴素策略都无法长期抗住"分配-释放"混合负载，外碎片会稳步累积。工程界的两条出路：其一，紧凑——停机搬移数据合并空洞，代价高（正是调度与地址重定位的难题）；其二，分页——把地址空间与物理内存都切成固定大小，任何空闲帧都能服务任何页，外碎片从结构上消失，只剩内碎片（最后一页平均半页，<0.1%）。分页正是 kp-017 的主角。

公式或模型

内碎片率 ≈ 每请求平均浪费 / 请求大小；页大小 P 下期望浪费 P/2，4KB 页对 100KB 进程的内碎片率约 2%。

直观类比

连续分配像用一排不同长度的空车位停各种车：总有几个"缝隙位"谁也停不进去（外碎片）。分页像把所有车都拆成标准尺寸的集装箱块、地面划成标准格：任何空格都能用，只是最后一块常装不满（内碎片）。

实例或案例

cat /proc/self/maps     # 观察一个进程真实的虚拟地址空间布局：代码/堆/栈/共享库分段
pmap -x <pid>           # 详细的地址区间与占用（macOS 用 vmmap）

注意 maps 里堆不是从地址 0 开始、各段间有大空洞与随机偏移——前者是内核区占据低位的反向呈现，后者是 kp-020 的 ASLR。

常见误区

• 认为程序里的地址就是内存条上的地址：中间永远隔着一次地址翻译，这是隔离与虚拟内存的基础。
• 认为"最佳适配"总体最优：它追求当下浪费最小，却制造最多微型碎片，长期性能往往最差。
• 把 malloc 的失败与物理内存不足画等号：分配失败发生在虚拟地址空间或上限约束上（见 kp-019 的惰性分配）。

与其他知识点的关系

地址翻译机制在 kp-017 展开；分配的工程实现（伙伴系统、slab）在 kp-019；地址布局随机化在 kp-020。

延伸阅读

《操作系统导论》"Mechanism: Address Translation"与空闲空间管理章节；《深入理解计算机系统》第 9 章前半。

自测题

1. 外碎片与内碎片的区别？分页消除的是哪种？

答：外碎片是空闲内存总量够但不连续，源于变长分配；内碎片是分配块内部用不到的部分，源于固定块。分页从结构上消除外碎片，只留下少量内碎片。

1. 为什么最佳适配不"最佳"？

答：它每次挑最小可容纳空洞，留下大量几乎无法复用的微小空洞，长期产生的外碎片最严重。

1. 每个进程的虚拟地址从 0 开始，物理内存会不会真的被写成全 0 起步？

答：不会；地址 0 只是虚拟空间的起点，经由页表翻译到任意物理帧，且页面通常按需才真正分配物理内存。