跳转至

08 空闲空间管理与分页 — 碎片的解法,和它带来的两个新麻烦

1. 这一章讲什么

第 07 章结尾留下一句预言:变长块的碎片没有好解,真正的出路是 永远不按变长块分配。本章先兑现前一半:假如不得不用变长块 (malloc 就必须),空闲空间该怎么管——分割、合并、四种策略、 分离列表。然后兑现预言本身:分页——把地址空间切成固定大小的页, 外部碎片从根上消失;代价是新的一对麻烦:页表太大、翻译太慢; 本章最后用 TLB 把第二个麻烦压下去,只留下「表太大」给下一章。

2. 顶层全景

  malloc 的世界(变长块,碎片是宿命):
    空闲列表 ──分割(split)──▶ 小块给出去
           ◀──合并(coalesce)── 邻居空闲块并回来
    找块策略:best / worst / first / next fit —— 都各有反例,没有最优
        │
  分页的世界(固定块,碎片灭绝,新麻烦诞生):
    虚拟地址 = [VPN | 偏移] ──▶ 页表查 VPN→PFN ──▶ 物理地址 = [PFN | 偏移]
    毛病一:页表太大(32 位/4KB 页 = 每进程 4MB)
    毛病二:每次访存多一次查表(慢一倍以上)
        │
    TLB(翻译缓存):热翻译放在片上的小缓存 ──▶ 命中时翻译零成本
    新毛病:上下文切换时,上个进程的翻译还在 TLB 里(冲刷 or ASID)

图说:上半是「躲不开的碎片管理学」,下半是「用固定块换干净, 再逐个填补新窟窿」的工程接力。

3. 核心原理

3.1 malloc 的三件底层机制(主线例子:30 字节的堆)

书里用 30 字节的玩具堆讲全部机制,数值照抄1:

空闲列表与分割。堆里 [0–9] 空闲 | [10–19] 已用 | [20–29] 空闲, 空闲列表两个节点:(addr 0, len 10)、(addr 20, len 10)。 请求 1 字节时,分配器「分割」:从 addr 20 那块切下 1 字节给出去, 列表变成 (0,10)、(21,9)2。

合并(coalescing)。free(10) 归还中间那块,若只是简单插回列表, 全堆其实空了、列表却显示三个 10 字节碎块——再要 20 字节就会 「不够」而失败(明明够!)。所以归还时必须看邻居:新空闲块挨着 已空闲块就合并——三个 10 合并回一个 303。不分配合并的 分配器,内存会「碎成看起来不够用」的形状。

头部(header)记账。free(ptr) 不收大小,库怎么知道还多少? 答案:每次 malloc 多分一个小头部,藏在返回指针紧前面 (ptr - 1 处),里面记 size 和 magic 校验数。要 N 字节时, 库里实际找的是 N + 头部大小 的空闲块4。

把列表嵌进空闲内存里。分配库不能给自己 malloc——它的列表节点 直接存放在空闲块自己内部(节点只占 size + next 两个整数); 书里 4096 字节堆的初始化:第一个节点 size = 4088、next = NULL5。

3.2 四种找块策略:一个例子看清全部

空闲列表里有 10、30、20 三块,请求 156:

策略 选哪块 剩余 特点
Best fit 20(能装下的最小) 5 省空间,但要扫全表;常留下难用的小渣
Worst fit 30(最大) 15 想留住大块;实测「既碎又慢」
First fit 30(第一个够大的) 15 快;列表开头被小渣污染(可按地址排序缓解)
Next fit 从上次停处继续找 视情况 均匀化搜索位置,行为近似 first fit

图说:四行表格说明本章的判词——没有任何策略在最坏输入下体面, 「理想分配器要快又要不碎,但请求序列可以任意恶毒」7。 工程上的两个进阶:按对象大小编队的分离空闲列表(Solaris 内核的 slab 分配器,连「初始化状态」都缓存了,省掉反复构造的开销8); 只按 2 的幂分块、合并时找「伙伴」的伙伴分配——合并高效但 内部碎片大(块比请求大,多给的部分白占着9)。

3.3 主线例子:64 字节地址空间里的一次访存(全轨迹)

分页怎么工作,书里用最小的完整例子讲透了10:

设定。虚拟地址空间 64 字节,页大小 16 字节 → 每个地址 6 位, 高 2 位是虚拟页号 VPN,低 4 位是页内偏移。页表(每个进程一张)记着: VP0→帧3,VP1→帧7,VP2→帧5,VP3→帧2。

翻译一条指令。程序执行 movl 21, %eax:

  1. 21 的二进制 = 010101。劈开:VPN=01(第 1 页),偏移=0101(第 5 字节)。
  2. 查页表:VPN 1 → PFN 7(111)。
  3. 拼接物理地址:PFN 111 + 偏移 0101 = 1110101₂ = 117。
  4. 偏移原样不动——翻译只换页号,不换页内位置11。

这条指令的真实代价。页表存在内存里,所以每条访存实际是两次访存: 先查页表(物理地址 = 页表基址寄存器 + VPN × 表项大小, 书里 64 字节例子的掩码是 0x30、移位是 412),再访问真实数据。 「进程慢一倍甚至更多」——这就是毛病二的量化。

一个循环的完整轨迹(array.c)。64KB 地址空间、1KB 页、 int array[1000] 清零循环。数组占 4000 字节,虚拟地址 40000–44000,落在 VPN 39–42;假设映射 39→7、40→8、41→9、42→10, 代码在 VPN 1→4。于是循环的每一次迭代产生三类访存: 取指(先查页表找代码页、再取指)、显式写数组(先查页表、再写)、 页表自身被反复读——书里图 18.7 把前五次迭代的虚/实地址轨迹画全了13。

3.4 页表项里有什么

x86 的页表项(图 18.5)是全景图14:PFN 之外有——

位 作用
P(存在位) 页在内存还是在盘上(换出);P=0 时访问会陷入,由 OS 分辨「合法但不在」还是「非法」
R/W、U/S 保护:可写吗?用户态可访问吗?
A(访问位) 这页最近被碰过吗——页替换策略(09 章)的原料
D(脏位) 改过吗——决定换出时要不要写回磁盘

图说:一张 4 字节的表项里,翻译只占一部分,其余全是给策略留的传感器。 有效位(valid bit)支撑稀疏地址空间:地址空间中间的空洞页 在表里标「无效」,不占用物理帧——虚拟内存的「省」就省在这15。

3.5 TLB:让翻译免费的硬件小抄

TLB(translation lookaside buffer)是 MMU 里的地址翻译缓存, 典型的 32/64/128 项、全相联:给定 VPN 可能在任何一项里, 硬件并行搜索16。控制流程是缓存的标配17:查 TLB—— 命中则零额外访存直接拼物理地址;未命中(硬件管理的 TLB) 硬件自己去走页表、填 TLB、重试指令。

TLB 命中率的第一个例子:10 个整数的数组、16 字节页。 10 次访问的命中模式是 miss, hit, hit, miss, hit, hit, hit, miss, hit, hit = 70% 命中率——靠空间局部性(同页元素挤在一起,一页只 miss 一次); 页大一倍 miss 更少(4KB 页时密集数组访问基本每页一次 miss); 若循环后再访问一遍,时间局部性把命中率推近 100%18。 书里给了缓存哲学:「快缓存必须小——物理定律,光速管着」19。

谁处理未命中?硬件管理(x86,CISC 老派:硬件认识页表格式, CR3 寄存器指表)或软件管理(MIPS/SPARC,RISC:硬件只抛异常, OS 的 miss 处理程序查自己的表、填 TLB、返回重试)。 软件管理的好处是灵活——OS 想用任何数据结构当页表都行,不用等硬件改20。 细节一:miss 处理后的返回必须重试出错的那条指令(不是下一条); 细节二:处理程序的代码本身不能被 miss 绊住——用「常驻 TLB 项」 (wired translation)兜底21。

上下文切换的 TLB 麻烦。TLB 里的翻译属于上一个进程的页表! 书里 P1 的 VPN 10→帧 100、P2 的 VPN 10→帧 170 的例子: 不换脑子,新进程会用旧翻译访问错内存22。两个解法: 切换时冲刷 TLB(简单,代价是新进程从头 miss); 或给每项加地址空间标识 ASID——翻译带上进程标签, 不同进程的翻译共存,切换零成本23。

4. 作者的判断与证据

书里给了证据的判断:

  • 四种分配策略各配反例;分配器的「理想」被请求序列的任意性判了死刑7。
  • TLB 的 70% 例子、页大小的影响、时间/空间局部性的作用,全部有 手算轨迹支撑18。
  • 软件 vs 硬件 TLB 管理的取舍给了真实架构(x86 vs MIPS/SPARC)佐证20。

作者的判断(立场):

  • 「缓存尽可能用」被点名为系统性能第一技法,TLB 只是它的一个实例19。
  • 对 best fit 等策略的判词很朴素:别信直觉,看工作负载实测—— worst fit「多数研究显示表现糟糕」就是例子6。

5. 边界与局限

  • 空闲空间管理一章的 malloc 是教学模型;真实的 glibc malloc (ptmalloc)还分小/大/巨块多种路径,本章策略只覆盖核心思想。
  • TLB 未命中的「多一次访存」是线性页表下的账;多级页表(下一章) 最坏要多走好几层——miss 更贵,这反过来抬高了 TLB 的价值。
  • ASID 解决了切换,没解决换页:页被换出后 TLB 里那条还热着吗? 这一层交给下一章的「TLB 击落」话题。

6. 可带走的

  1. 合并与分割是空闲空间管理的呼吸:只分不合,内存必碎成 「看起来不够用」。
  2. free 不传大小是因为头部记账;要给头部预留空间,这是「malloc 要的 比给的多」的原因之一。
  3. 分页的翻译一句话:高几位换页号,低几位原样走。
  4. 分页消灭外部碎片,换来内部碎片(页内用不满)——书里的账: 变大页省表但内碎变大,这是下一章的第一个权衡。
  5. TLB 是「程序局部性」的兑换所:写循环的访问模式,直接决定 系统跑多快——性能问题常常不是算法,是访存模式。
  6. 每个看似免费的缓存(快表、缓存、分支预测)都在切换时刻暴露代价: 上下文切换 = 一切局部性清零。系统设计者永远在为「切换」付账。

7. 原文地图

主题 原书章 原文位置
内部碎片定义 17. Free-Space Management text/19-ch17-17-free-space-management.txt:52(搜「internal fragmentation」)
30 字节堆与分割 17. Free-Space Management text/19-ch17-17-free-space-management.txt:90(搜「30-byte heap」)
合并的必要 17. Free-Space Management text/19-ch17-17-free-space-management.txt:145(搜「coalesce」)
头部与 free 的记账 17. Free-Space Management text/19-ch17-17-free-space-management.txt:183(搜「header」)
列表嵌在空闲空间里 17. Free-Space Management text/19-ch17-17-free-space-management.txt:222(搜「4096-byte」)
四种策略与 15 字节例子 17. Free-Space Management text/19-ch17-17-free-space-management.txt:439(搜「Best Fit」)与:482(搜「15」)
没有最优策略 17. Free-Space Management text/19-ch17-17-free-space-management.txt:436(搜「best」)
slab 分配器 17. Free-Space Management text/19-ch17-17-free-space-management.txt:517(搜「segregated」)
伙伴分配与内碎 17. Free-Space Management text/19-ch17-17-free-space-management.txt:567(搜「Buddy」)
分页总览:灵活与简单 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:46(搜「advantages」)
页表定义与例子 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:73(搜「page table」)
64 字节例子与 VA 21→117 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:115(搜「movl 21」)
32 位页表 4MB 的账 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:181(搜「4MB」)
有效位与稀疏地址空间 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:224(搜「valid bit」)
x86 页表项 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:248(搜「Page Table Entry」)
每次访存多一次引用 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:328(搜「extra memory reference」)
翻译伪代码(VPN_MASK) 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:303(搜「VPN_MASK」)
array.c 轨迹 18. Paging: Introduction text/20-ch18-18-paging-introduction.txt:366(搜「array」)
TLB 控制流程 19. Paging: Faster Translations (TLBs) text/21-ch19-19-paging-faster-translations-tlbs.txt:30(搜「TLB Hit」)
数组例子的 70% 命中 19. Paging: Faster Translations (TLBs) text/21-ch19-19-paging-faster-translations-tlbs.txt:156(搜「70%」)
缓存哲学(快=小) 19. Paging: Faster Translations (TLBs) text/21-ch19-19-paging-faster-translations-tlbs.txt:164(搜「CACHING」)
硬件 vs 软件管理的 TLB 19. Paging: Faster Translations (TLBs) text/21-ch19-19-paging-faster-translations-tlbs.txt:217(搜「Who Handles」)
切换冲刷与 ASID 19. Paging: Faster Translations (TLBs) text/21-ch19-19-paging-faster-translations-tlbs.txt:372(搜「flush」)与:388(搜「address space identifier」)

  1. 出处:「17. Free-Space Management」第 88–130 段(text/19-ch17-17-free-space-management.txt:90,搜「30-byte heap」)。 ↩

  2. 出处:「17. Free-Space Management」第 106–130 段(text/19-ch17-17-free-space-management.txt:107,搜「splitting」)。 ↩

  3. 出处:「17. Free-Space Management」第 131–155 段(text/19-ch17-17-free-space-management.txt:145,搜「coalesce」)。 ↩

  4. 出处:「17. Free-Space Management」第 178–211 段(text/19-ch17-17-free-space-management.txt:204,搜「header_t」)。 ↩

  5. 出处:「17. Free-Space Management」第 222–249 段(text/19-ch17-17-free-space-management.txt:222,搜「4096-byte」)。 ↩

  6. 出处:「17. Free-Space Management」第 439–509 段(text/19-ch17-17-free-space-management.txt:439,搜「Best Fit」)。 ↩↩

  7. 出处:「17. Free-Space Management」第 426–437 段(text/19-ch17-17-free-space-management.txt:435,搜「quite badly」)。 ↩↩

  8. 出处:「17. Free-Space Management」第 517–565 段(text/19-ch17-17-free-space-management.txt:531,搜「slab」)。 ↩

  9. 出处:「17. Free-Space Management」第 567–590 段(text/19-ch17-17-free-space-management.txt:580,搜「internal fragmentation」)。 ↩

  10. 出处:「18. Paging: Introduction」第 84–170 段(text/20-ch18-18-paging-introduction.txt:115,搜「movl 21」)。 ↩

  11. 出处:「18. Paging: Introduction」第 161–164 段(text/20-ch18-18-paging-introduction.txt:161,搜「offset stays the same」)。 ↩

  12. 出处:「18. Paging: Introduction」第 298–312 段(text/20-ch18-18-paging-introduction.txt:303,搜「VPN_MASK」)。 ↩

  13. 出处:「18. Paging: Introduction」第 363–459 段(text/20-ch18-18-paging-introduction.txt:402,搜「64KB」)。 ↩

  14. 出处:「18. Paging: Introduction」第 237–266 段(text/20-ch18-18-paging-introduction.txt:248,搜「Page Table Entry」)。 ↩

  15. 出处:「18. Paging: Introduction」第 224–233 段(text/20-ch18-18-paging-introduction.txt:224,搜「valid bit」)。 ↩

  16. 出处:「19. Paging: Faster Translations (TLBs)」第 316–333 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:318,搜「32, 64, or 128」)。 ↩

  17. 出处:「19. Paging: Faster Translations (TLBs)」第 30–84 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:30,搜「TLB Hit」)。 ↩

  18. 出处:「19. Paging: Faster Translations (TLBs)」第 86–200 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:156,搜「70%」)。 ↩↩

  19. 出处:「19. Paging: Faster Translations (TLBs)」第 164–188 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:164,搜「CACHING」)。 ↩↩

  20. 出处:「19. Paging: Faster Translations (TLBs)」第 217–315 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:217,搜「Who Handles」)。 ↩↩

  21. 出处:「19. Paging: Faster Translations (TLBs)」第 242–287 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:285,搜「infinite chain」)。 ↩

  22. 出处:「19. Paging: Faster Translations (TLBs)」第 337–360 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:346,搜「P1」)。 ↩

  23. 出处:「19. Paging: Faster Translations (TLBs)」第 372–390 段(text/21-ch19-19-paging-faster-translations-tlbs.txt:372,搜「flush」)与:388(搜「address space identifier」)。 ↩