c - Malloc 分配方案

Question

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

马洛克讲座。 我在网上找到了这个链接，你可以看一下幻灯片 7，看看我在说什么。

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

谢谢你。

Answer 1

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

释放块时。只有四种可能的情况：

• 空闲块在空闲块之后是相邻的。
• 空闲块在空闲块之前是相邻的。
• 空闲块位于它之前和之后的两个空闲块之间并与之相邻。
• 空闲块不与任何空闲块相邻。

合并相邻空闲块的目的是：

• 减少链表的长度
• 准确反映空闲块的大小，而不会给分配器带来负担来查看两个块是否相邻

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