Buddy分配算法 - 开始堆地址 [英] Buddy Allocation Algorithm - Beginning Heap Address

问题描述

我目前正尝试实施 The Art of Computer Programming Vol：1 中描述的 Buddy Allocator ， / em>，其利用给定数据块及其对应伙伴的地址中的重要不变量。计算如下...

I am currently trying to implement the Buddy Allocator described in The Art of Computer Programming Vol: 1, which takes advantage of an important invariant in the address of a given block of data and its corresponding buddy. The calculation is as follows...

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）。如果给定左块地址，这将返回右块。

What makes the buddy system perform so well is that this calculation to find the buddy's address, can simply be performed with a flip of the ith order bit (via xor'ing it with 1 << i). If given the left blocks address, this will return the right block. If given the right block, this will return the left block.

但是，这个方法假定堆以地址0开头。如果堆以地址开头位在i顺序的范围内有一个，执行上面的计算将不会给它的伙伴的正确地址。

However, this method assumes that the heap begins with at address 0. If the heap begins with addresses that have bits within the range of i order that have one, performing the above calculation will not give you the correct address of the its buddy.

因此，简单地说，是有一个方法来推广这个计算，以便它可以在任何起始堆地址执行？假设有一个绑定到最大顺序。 IE *如果max order是18，我们不会尝试执行任何大于或等于18的计算，所以你不需要找到它的伙伴。

Therefore, put simply, is there a way to generalize this computation so that it can be performed at any starting heap address? Assume that there is a bound to the max order. IE* if max order is 18, we are not going to try to perform any computation greater than or equal to an order of 18, so you don't need to find its buddy.

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

Any help or suggestions toward this a very much appreciated!

推荐答案

Woah， Kudos阅读Knuth！

Woah, hardcore. Kudos for reading Knuth!

无论如何，我可能会缺少点，但在某些时候，你要求（我假设）一个连续的内存块从操作系统到应用好友系统。所以你不能保留起始地址（你还需要它 free（）），并使用该偏移量，使您使用的地址似乎为零基于？即：像这样：

Anyway, I might be missing the point, but at some point you're requesting (I presume) a contiguous chunk of memory from the OS to apply the buddy system to. So couldn't you just keep the starting address around (you need it to free() later anyway), and use that offset to make the addresses you use appear to be zero-based? i.e. something like this:

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;
}

这篇关于Buddy分配算法 - 开始堆地址的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！