动态内存分配方案

Question

5

是的，我正在修计算机系统课程。我有几个关于实现malloc的不同分配方案的问题。对于显式链表，如果我使用类似LIFO堆栈的方式来实现malloc，那么为什么需要指向之前已释放内存的指针？为什么需要双向链表？单向链表不也可以吗？

这是一个Malloc讲座。您可以查看第7页以了解我在说什么。

当查看分离列表分配方案时，这些列表是单向的，对吗？那么，粘合机制到底是什么？例如，如果释放了4个字，则在将其插入到相应的分离链接列表中之前，您是否首先尝试加入周围的空闲空间？或者您是否只是将4个字块插入到相应的分离链接列表的“4字”部分中？

谢谢。

- de1337ed

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wallyk · Accepted Answer

由于释放的块始终有两个指针的空间，为什么不将列表双向链接呢？这简化了合并代码，因为它不需要在遍历列表时保持尾随指针。它还允许以任何方向遍历列表，以便在搜索开始时有哪一端更接近的提示。我曾经看过一个晦涩的系统，在其中保留了“中间”的指针，即上次活动发生的位置。

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

1. 释放块在一个空闲块之后。 2. 释放块在一个空闲块之前。 3. 释放块在两个相邻的空闲块之间。 4. 释放块不与任何空闲块相邻。

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

1. 减少链表长度。 2. 准确反映空闲块的大小，而不会使分配器负担过重以查看两个块是否相邻。

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