17.2 底层机制
- 分割与合并
在申请时分割,在归还时合并。
- 追踪已分配空间的大小
free(void *ptr)没有块大小的参数,因为它假定对于给定的指针吗内存分配哭可以很快确定要释放空间的大小,从而将它放回空闲列表。
大多数分配程序会在头块中保存一点额外信息,它在内存中,通常在返回的内存块之前。
- 嵌入空闲列表:需要在空闲空间本身中建立空闲空间列表。
17.3 基本策略
- 最优匹配
首先遍历整个空闲列表,找到和请求大小一样或更大的空闲快,然后返回这组候选这种最小的一块。
选择最接近用户请求大小的块从而避免空间浪费。然而代价是遍历查找的时候要付出较高的性能代价。
- 首次匹配
找到第一个足够大的块将请求空间返回给用户。
有速度优势,但有时会让空闲列表开头部分有很多小块。
- 下次匹配
该算法多维护一个指针,指向上一次查找结束的位置,避免了对列表开头频繁的分割。