8

我目前正在尝试实现The Art of Computer Programming Vol: 1 中描述的Buddy Allocator，它利用了给定数据块及其相应伙伴的地址中的一个重要不变量。计算如下...

BUDDY(X):

X + 2^i if x mod 2^i+1 = 0
X - 2^i if x mod 2^i-1 = 0

Where X is the address of the block; i is the current order

使伙伴系统表现如此出色的原因在于，这种查找伙伴地址的计算可以简单地通过翻转第 i 个顺序位来执行（通过将其与 1 << i 进行异或）。如果给定左块地址，这将返回右块。如果给定右块，这将返回左块。

但是，此方法假定堆从地址 0 开始。如果堆从具有 i 顺序范围内的位的地址开始，则执行上述计算不会为您提供其伙伴的正确地址。

因此，简单地说，有没有一种方法可以泛化这种计算，以便它可以在任何起始堆地址处执行？假设有一个最大订单的界限。IE* 如果最大阶数为 18，我们不会尝试执行任何大于或等于 18 阶的计算，因此您不需要找到它的伙伴。

非常感谢您对此的任何帮助或建议！

4

1 回答 1

6

哇，铁杆。感谢阅读 Knuth！

无论如何，我可能错过了这一点，但在某些时候，您会从操作系统请求（我认为）一块连续的内存来应用伙伴系统。所以你不能只保留起始地址（无论如何你以后都需要它free()），并使用该偏移量来使你使用的地址看起来是从零开始的吗？即是这样的：

uint8_t* start_addr = malloc(SIZE_IN_BYTES);

uint8_t* buddy(uint8_t* real_x) {
    uint8_t *x = real_x - start_addr;
    // do buddy bit-flipping on "x"
    return x + start_addr;
}
于 2013-10-30T07:20:34.993 回答