Malloc分配计划

Question

是的,我正在参加计算机系统课程.我有几个关于实现malloc的各种分配方案的问题.对于显式列表,如果我使用类似LIFO的堆栈实现malloc,那么指向前一个释放内存的目的究竟是什么？就像为什么你需要双链表？不会单独链接列表工作吗？

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

在查看隔离列表分配方案时,这些列表是单向的吗？而且,合并机制到底是什么？例如,如果释放了4个单词,您是否会首先尝试在您将自由空间插入相应的隔离链表之前加入它？或者您只是在相应的隔离链表的"4个字"部分中插入4个字块？

谢谢.

Answer 1

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

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

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

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

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

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