内存分配算法

Question

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

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

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

为例

甲-一

B-1

C-4

D-2

0 1 2 3 4 5 6 7 8 9

X A x B C D D x

当我们释放内存时(如x所示)，如果我们在可用的最小地址上分配内存，那么就会出现碎片。因此，在上面的例子中，即使3个单元是空闲的，我们也不能分配3个连续单元的内存。

Answer 1

搜索“好友系统”或“好友内存分配”。这可能是你能找到的最好的解决方案。虽然它不是纯粹的O(1)，它有一些内部碎片，外部碎片也可能发生.

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