버디 할당 알고리즘 - 시작 힙 주소

Question

현재 컴퓨터 프로그래밍 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 

수행 ... 다음 xor'ing 통해 (이 계산은 간단히, i 번째 오더 비트의 플립 수행 될 수 있고, 친구의 주소를 찾을 수 있다는 것이다대로 그것과 함께 1 < <). 왼쪽 블록 주소를 받으면 오른쪽 블록을 반환합니다. 주어진 오른쪽 블록을 받으면 왼쪽 블록을 반환합니다.

그러나이 방법은 힙이 주소 0에서 시작한다고 가정합니다. 힙이 하나의 순서 범위 내에있는 비트로 시작하는 주소를 가진 경우 위의 계산을 수행해도 올바른 주소가 제공되지 않습니다. 그 친구. 간단히 말하자면 따라서

, 그것이 어떤 힙 개시 어드레스에서 수행 될 수 있도록이 계산을 일반화하는 방법은 무엇입니까? 최대 차수에 대한 경계가 있다고 가정합니다. IE * 최대 주문이 18 인 경우, 18의 순서보다 크거나 같은 계산을 수행하지 않으므로 해당 친구를 찾을 필요가 없습니다.

어떤 도움이나이 대한 제안은 대단히 감사합니다!

Answer 1

와우, 하드 코어. 크 누스 독서를위한 명성!

어쨌든, 나는 지점을 누락 될 수 있지만, 어떤 시점에서 당신은에 버디 시스템을 적용 OS에서 (나는 가정) 메모리의 연속 된 덩어리를 요청하고 있습니다. 그래서 당신은 단지 주변의 시작 주소를 내지 못했습니다 (당신은 나중에 어쨌든 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; 
}