algorithm - 内存分配算法

Question

我们如何实现具有以下约束的分配和跟踪内存的数据结构

1. 在 O(1) 中分配和释放内存
2. 最小碎片。

假设您有 1 KB 的内存单元。您需要在 2kB - 64 KB 内存之间分配

例如

A- 1

B-1

C-4

D-2

0 1 2 3 4 5 6 7 8 9 10

x A x BCCCCDD x

如果我们在释放内存时（如上面的 x 所示）可用的最小地址分配内存，我们将产生碎片。所以在上面的例子中，即使 3 个单元是空闲的，我们也不能分配 3 个连续单元的内存。

Answer 1

搜索“伙伴系统”或“伙伴内存分配”。这可能是您会找到的最佳解决方案。虽然，它不是纯粹的 O(1)，但它存在一些内部碎片，并且也可能发生外部碎片......

您可以通过使用增强树完全避免内部碎片，但是操作需要 O(log N) 时间。而且你仍然有外部碎片。