c - Malloc 分配方案

Question

是的，我正在学习计算机系统类(class)。我对实现 malloc 的各种分配方案有一些疑问。对于显式列表，如果我使用类似 LIFO 的堆栈实现 malloc，那么拥有指向先前已释放内存的指针的确切目的是什么？比如为什么需要双向链表？单向链表不是同样有效吗？

Malloc lecture.我在网上找到了这个链接，您可以查看幻灯片 7 以了解我在说什么。

在查看隔离列表分配方案时，这些列表是单向的，对吗？而且，合并机制到底是什么？例如，如果释放了 4 个单词，您会先尝试在您周围的空闲空间加入它，然后再将其插入各自的隔离链表吗？或者您会简单地将 4 字 block 插入相应隔离链表的“4 字”部分吗？

谢谢。

Answer 1

既然一个释放的 block 总是有两个指针的空间，为什么不对列表进行双向链接呢？它简化了合并代码，因此在遍历列表时不必维护尾随指针。它还允许在任一方向遍历列表，以防出现列表的哪一端可能更接近开始搜索的提示。我曾经看过的一个不起眼的系统在“中间”保留了一个指针，最后一个事件发生的地方。

释放 block 时。只有四种可能的情况:

• 空闲 block 与空闲 block 相邻。
• 空闲 block 在空闲 block 之前相邻。
• 空闲 block 位于其前后两个空闲 block 之间并与之相邻。
• 空闲 block 不与任何空闲 block 相邻。

合并相邻空闲 block 的目的是:

• 减少链表的长度
• 准确反射(reflect)空闲 block 的大小，而不会给分配器带来负担，让他们提前查看两个 block 是否相邻

将空闲 block 排序到特定长度的空闲列表中通常有好处，但在大多数实际实现中，合并是优先事项，因此对不同大小块的 alloc() 请求不会不合适当有许多不同大小的空闲 block 时被拒绝。