这几天晚上总是遇到各式各样的事,导致看了部分内容,但没同时把总结写出来的结果。今天不知道过一会有没有事,趁这点时间,先把看过的内容理解写一点。

放置策略

分配器收到应用请求字节块的请求时,需要搜索空闲链表,查找到一个空闲块的方式称为放置策略。

常见的放置策略有首次适配、下一次适配、最佳适配。

首次适配从头搜索空闲链表,找到第一个满足要求的空闲块。它趋向于把大的空闲块保留在链表后侧,同时把小空闲块的碎片留在链表前侧。增大了对较大块的搜索时间。

下一次适配的搜索起始点时上一次搜索结束的地点。链表前端碎片较多时,速度更快。不过该方式的内存利用率低于首次适配。

最佳适配检查每个空闲块,之后选择适合所需请求大小的最小空闲块。内存利用率高于前两种方式。缺点是每次请求要对堆进行彻底搜索。

分割块

一旦找到匹配的空闲块后,如果空闲块大小大于请求大小,一般会选择对空闲块进行分割。

获取额外内存

获取额外内存一般使用sbrk函数。之后分配器将额外内存转化为一个大的空闲块,将这个块插入空闲链表。之后将之前请求不成功的块放置在新的空闲块中。

合并空闲块

释放一个已分配块后,为了避免假碎片的产生(许多可用的内存块被分割为许多小、无法使用的空闲块),要进行空闲块的合并。

合并有两个策略:立即合并,即每当一个块被释放时,合并所有的相邻块。推迟合并,一个例子是直到某个分配请求失败时,分配器才开始对整个堆进行合并操作。

边界标记——前后向指针更具创意的双向链表

解决的问题:合并时,如果想把一个块和它之前的一个块合并,那么每次这样的合并都是线性时间复杂度。

解决方式:在每个块的结尾增加一个脚部。脚部的内容就是一个块头部的副本。分配器可以通过检查一个块头部前固定距离下,前一个块脚部的内容,得知前一个块的大小,进而从该块的开头,加减得到的前一个块大小,从而迭代到前一个块的头部。

释放后的合并分为四种情况:

  • 当前块前一个块已分配,后一个块空闲。用当前块和后面块大小的和以更新当前块头部和后一个块脚部。
  • 当前块前一个块空闲,后一个块已分配。用两个块的大小之和更新前一个块头部和当前块脚部。
  • 当前块、前一个块、后一个块空闲:三个块大小的和更新前一个块头部、后一个块脚部。
  • 只有当前块空闲:改变当前块的分配状态,无其他操作。

边界标记要求每个块保持一个头部、一个脚部,在大量小块的分配场景下,开销显著。

一种优化策略:注意到只有当前一个块空闲时,才需要用到它的脚部。那么可以把前一个块的分配情况存放在当前块中的空闲位。如果前一个块已被分配,那么不需要保存它的脚部。