Malloc分配方案

Question

是的，我正在选修计算机系统课程。关于实现malloc的各种分配方案，我有几个问题。对于显式列表，如果我使用类似于LIFO的堆栈实现malloc，那么让指针指向以前释放的内存的目的到底是什么？比如，为什么你需要双向链表？单链表不是也能正常工作吗？

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

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

谢谢。

Answer 1

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

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

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

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

• 可减少链表的长度
• 可准确反映空闲块的大小而不会增加分配器的负担可向前看以查看两个块是否相邻

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