巴迪分配算法 - 开始堆地址 [英] Buddy Allocation Algorithm - Beginning Heap Address
问题描述
我目前正在实施href="http://en.wikipedia.org/wiki/Buddy_memory_allocation">好友分配器的中描述的
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＆LT是异或运算;＆LT;我）。如果给左块地址，这将返回右挡。如果给予适当的块，这将返回左块。
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。如果堆开始具有广泛的我命令有一个范围内的位地址，执行上述计算不会给你正确的地址了伙计。
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 *如果最大订单是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.
任何帮助或建议朝这是一个非常AP preciated！
Any help or suggestions toward this a very much appreciated!
推荐答案
哇，硬核。荣誉阅读克努特！
Woah, hardcore. Kudos for reading Knuth!
不管怎样，我可能会错过了点，但在某些时候你的要求（我presume）一个连续的内存块从操作系统到应用的好友系统。所以，你就不能只是一味的起始地址各地（你需要它免费（）以后反正），并使用该偏移，使您使用的地址显示为零为基础的？即是这样的：
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;
}
这篇关于巴迪分配算法 - 开始堆地址的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
