《Operating Systems: Three Easy Pieces》学习笔记(十三) 空闲空间管理
要满足变长的分配请求，应该如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时间和空间开销如何？
假设
通过 malloc()和 free()分配释放内存
只有外部碎片
分配后不能移动，大小固定
底层机制
- 空闲链表
分割：
合并：
追踪已分配空间的大小
为每块分配的空间添加头块，实际占用空间是头块大小加上分配大小。
头块包括分配大小和幻数，幻数用于验证，是个固定常数，如 1234567
释放时，头块也要释放
- 嵌入空闲列表
head 指向空闲列表头，组成一个空闲列表。
合并空闲空间需要遍历。
- 让堆增长
类似 sbrk 可以扩展堆大小
基本策略
最优匹配
遍历整个空闲列表，选择最接近用户请求大小的块，从而尽量避免空间浪费，但遍历要付出较高的性能代价。最差匹配
最差匹配（worst fit）方法与最优匹配相反，它尝试
遍历找最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表。大多数研究表明它的表现非常差，导致过量的碎片，同时还有很高的开销首次匹配
首次匹配（first fit）策略就是找到
第一个足够大的块，将请求的空间返回给用户。无需全遍历下次匹配
不同于首次匹配每次都从列表的开始查找，下次匹配（next fit）算法多维护一个指针， 指向上一次查找结束的位置。其想法是将对空闲空间的查找操作扩散到整个列表中去，避免对列表开头频繁的分割。这种策略的性能与首次匹配很接它，同样
避免了遍历查找。无需全遍历
其他方式
- 分离空闲列表(segregated list)
如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象。其他大小的请求都一给更通用的内存分配程序。比如 16KB 大小的块列表，好处是不会产生碎片。
- 伙伴系统
空闲空间首先从概念上被看成大小为 2^N 的大空间。当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再一分为二就无法 满足）。形成一棵二叉树
递归合并伙伴，如果将这个 8KB 的块归还给空闲列表，分配程 序会检查“伙伴”8KB 是否空闲。如果是，就合二为一，变成 16KB 的块。然后会检查这 个 16KB 块的伙伴是否空闲，如果是，就合并这两块。
每对互为伙伴的块的内存地址只有一位不同，找到对应伙伴很容易
小结
讨论了最基本的内存分配程序形式。