algorithm - malloc 的最佳启发式

Question

考虑使用 malloc() 在碎片堆中分配 x 字节的内存。假设堆有多个大小大于 x 字节的连续位置。

哪个是最好的（导致最少的堆浪费）启发式选择以下位置？

1. 选择大于 x 字节的最小位置。
2. 选择大于 x 字节的最大位置。

我的直觉是大于 x 字节的最小位置。我不确定哪个是实践中最好的。

不，这不是任何作业问题。我在读这个malloc() 和 free() 如何工作？这看起来是一个很好的后续问题。

Answer 1

在一个混合了不同大小的分配的通用堆中，我会在这两个中将分配放在可以容纳它的最小块中（以避免在需要之前减少我们可以分配的最大块的大小） .

还有其他实现堆的方法，但是这会降低这个问题的相关性（例如 Doug Lea 的流行dlmalloc - 它汇集了相似大小的块以提高速度并减少整体碎片）。

哪种解决方案最好总是归结为应用程序执行其内存分配的方式。如果您事先了解应用程序模式，您应该能够在大小和速度上击败通用堆。

Answer 2

最好选择最小的位置。考虑未来的 malloc 请求。您不知道它们会是什么，并且您希望尽可能多地满足请求。所以最好找一个完全符合你需求的位置，这样以后更大的请求也能得到满足。换句话说，选择最小的位置可以减少碎片。

Answer 3

您列出的启发式方法分别用于最佳拟合和最差拟合算法。还有 First Fit 算法，它简单地采用它发现的第一个足够大的空间。它大约与 Best Fit 一样好，而且速度更快。