空闲块合并




额外堆存储器

如果分配器不能为请求块找到合适的空闲块。一个选择就是通过合并哪些在存储器中物理上相邻的空闲块来创建一些更大的空闲块。如果这样还是不能生成一个足够大的块,且空闲块已经是最大程度的合并,此时分配器就会向内核请求额外的堆存储器,此时要么调用mmap函数,或sbrk函数,此时分配器会将额外的存储器转换成一个大的空闲块,将这个块插入到空闲链表中,然后再将请求的块放入这个新的空闲块中。



合并空闲块

当分配器释放一个已分配块时,可能有其它空闲块与这个新释放的块相邻,这些相邻的块可能会形成一个假碎片现象,对付这种假碎片现象,任何实际的分配器都必须合并相邻的空闲块,这个过程称为合并操作。
常见的合并方式有:立即合并 推迟合并两种策略。



边界标记合并

边界标记的方法就是在每个块的脚步定义个同头部一样的标记,可以记载块的状态,当后一个块释放时,直接检测前一个块的状态,可以快速的进行相邻的块合并。
边界标记策略是Knuth提出的一个聪明通用的技术,允许在常数时间内进行对前面块的合并,这种思想是在每个块的结尾处添加一个脚部,其中脚步就是头部的一个副本。如果每个块包括这样一个脚部,那么分配器就可以通过检查前面一个块的脚步,来判断前面一个块的起始位置和状态。



为了使空闲块可以进行快速合并,分配器采用了新的策略:边界标记合并来快速合并空闲块。

相关阅读:
mmap函数
free函数用法
碎片
隐式空闲链表