c – 伙伴分配算法 – 开始堆地址

发布时间：2020-12-16 05:06:57 所属栏目：百科来源：网络整理

导读：我目前正在尝试实现计算机程序设计Vol：1中描述的 Buddy Allocator,它利用了给定数据块及其相应伙伴的地址中的重要不变量.计算如下…… BUDDY(X):X + 2^i if x mod 2^i+1 = 0X - 2^i if x mod 2^i-1 = 0Where X is the address of the block; i is the curre

我目前正在尝试实现计算机程序设计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进行xor'ing).如果给出左块地址,则返回右块.如果给出正确的块,则返回左侧块. 但是,此方法假定堆以地址0开头.如果堆以具有i顺序范围内的位的地址开始,则执行上述计算将不会为您提供其伙伴的正确地址. 因此,简单地说,有没有办法推广这个计算,以便它可以在任何起始堆地址执行？假设有一个最大订单的约束. IE *如果最大订单是18,我们不会尝试执行大于或等于18的任何计算,因此您不需要找到它的伙伴. 对此非常感谢的任何帮助或建议！

解决方法

哇,铁杆.感谢阅读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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!