内存分配与碎片
复习
- 页面置换：内存装满后应该换出哪一页
- 工作集与内存抖动：程序频繁缺页时为什么会忙着换页却不再做事
- 写时复制：先共享页面，真正修改时再复制
TL;DR
- 内存要不停地被分配和回收，得有专门的分配器打理
- 内部碎片：分出去的一块里没用到的那部分
- 外部碎片：零散的空闲块，单个都太小、拼不起来
- 分配策略（首次匹配、最佳匹配等）各有取舍
正文
前面的分页、置换，都在讲“页”这一层。可程序要内存时，并不是按页来要的——它要的是“一块能放 100 个整数的地方”。从“页”到“一块大小不定的内存”，中间还需要一个内存分配器。
两种分配场合
内存分配大致分两个层面：
- 内核的分配：操作系统自己需要内存，比如创建进程、记录结构
- 运行时的分配：程序运行中申请内存，比如动态创建一个对象、一个变长数组
不管哪一层，分配器都要面对同一件事：从一片空闲区域里，切出一块给申请者，用完再收回来。
两种碎片
切来切去、收来收去，就会产生碎片。碎片有两类：
- 内部碎片：分出去的这一块，比实际需要的稍大，多出来的部分被浪费。分页的“最后一页填不满”就是典型。
- 外部碎片：空闲的内存被切得七零八落，单个空块都太小，凑不出一块连续的大空位。分段留下的空隙就是典型。
外部碎片示意：
[占用][空][占用][空][空][占用][空]
↑太小 ↑太小（合起来也许够，但不连续）
内部碎片是“给多了浪费”，外部碎片是“零散得用不上”。
分配策略
从一个空闲块里切一块出来，切哪儿？常见几种挑法：
- 首次匹配：从头上找，第一个够大的就用
- 最佳匹配：找最接近所需大小的那一块，最省但查找慢、还容易留下更小的碎块
- 最差匹配：找最大的那块来切，切完剩下的还够用
它们各有优劣，没有一种总能赢。实际系统往往还会做内存整理（把散块挪到一起）来对抗外部碎片——但整理本身也有代价。
到这里，内存这条线就基本讲完了。接下来换个方向：程序总要和设备、和磁盘打交道，那又是怎么组织的？下一章，看操作系统怎样面对形形色色的设备。
思考题
“内部碎片”和“外部碎片”，哪一种更麻烦？为什么分页选择接受内部碎片，而分段却会留下外部碎片？
小结
知识点
- 内存分配器负责切分和回收空闲内存
- 内部碎片：分配块内没用上的部分
- 外部碎片：零散、拼不起来的小空块
- 首次/最佳/最差匹配等分配策略各有取舍
参考资料
- Wikipedia(zh)：内存分配：memory allocation
- Wikipedia(zh)：碎片化：fragmentation
思考题答案（仅供参考）
一般来说，外部碎片更麻烦：内部碎片顶多是“一块里浪费一点”，浪费有上限；而外部碎片可能让一大片内存因为“凑不齐连续空间”而根本用不上，且越用越碎。分页之所以接受内部碎片，是因为固定大小的块彻底消灭了外部碎片——最后一点浪费换来“任何空块都能用”，很划算。分段则因为段长不定，天然会产生外部碎片。这也说明：在内部碎片和外部碎片之间，工程师往往宁愿选前者。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪