1
$\begingroup$

The buddy algorithm is:

The buddy for any block of size $2^k$ is another block of the same size, and with the same page frame number except that the kth bit is reversed.

Example:

If the block size if $2^3$ and the start page frame number(aka pfn) of this block is 0xC, the page frame number of the buddy of this block is pfn=0x4.

This algorithm is very ingenious but I have two questions.

  1. Why the buddy of 0xC is 0x4 instead of 0x14?
  2. Why reversing the kth bit does the trick?

References: http://research.cs.vt.edu/AVresearch/MMtutorial/buddy.php

$\endgroup$
  • $\begingroup$ I think that your example is incorrect - starting point of block with size 2^n should be aligned to 2^n. Then, reversing the n'th bit of that address, you will find its buddy, and together they form block of size 2^(n+1) $\endgroup$ – Bulat Aug 28 '18 at 21:45
  • $\begingroup$ en.wikipedia.org/wiki/Buddy_memory_allocation $\endgroup$ – Bulat Aug 28 '18 at 21:46
1
$\begingroup$

The buddy algorithm is just treating your memory of size $2^K$ as a binary tree where the root is the entire memory, and each node of size $2^k$ has two children which are the two equal size subblocks of size $2^{k-1}$.

The buddy system restricts you to only splitting a node into its two children (which are then the two buddies), or taking two buddies and coalescing them into their parent. This restriction is put in place entirely to enable the cute/ingenious trick of identifying your buddy by flipping the $k$th bit.

Other than being cute, there is very little to recommend buddy systems as memory allocators. More general systems that allow you to coalesce with any neighbor, even if it's not your buddy, are slightly more expensive to compute per deallocation, but result in much less internal and external fragmentation in practice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.