分离适配

• 分配器维护空闲链表数组，每个大小类一个空闲链表
• 当分配器需要一个大小为n的块时:
  • 搜索相应的空闲链表，其大小要满足m > n
  • 如果找到了合适的块:
    • 拆分块，并将剩余部分插入到适当的可选列表中
  • 如果找不到合适的块, 就搜索下一个更大的大小类的空闲链表
  • 直到找到为止
• 如果空闲链表中没有合适的块:
  • 向操作系统请求额外的堆内存 (使用sbrk())
  • 从这个新的堆内存中分配出 n 字节
  • 将剩余部分放置在适当的大小类中
• 释放块:
  • 合并，并将结果放置到相应的空闲链表中
• 分离适配的优势
  • 更高的吞吐量
    • log time for power-of-two size classes 按照2的幂得到各类使用 log 时间
  • 更高的内存使用率
    • 对分离空闲链表的简单的 首次适配搜索 搜索，其内存利用率近似于对整个堆的最佳适配搜索的内存利用率.
    • 极端示例：如果每个块都属于它本身尺寸的大小类，那么就相当于最佳适应算法