Editing Buddy memory allocation (section)

== Implementation and efficiency ==

In comparison to other simpler techniques such as [[dynamic allocation]], the buddy memory system has little [[Fragmentation (computer)#External fragmentation|external fragmentation]], and allows for [[Data compaction|compaction]] of memory with little overhead. The buddy method of freeing memory is fast, with the maximal number of compactions required equal to O(highest order) = O(log<sub>2</sub>(total memory size)). Typically the buddy memory allocation system is implemented with the use of a [[binary tree]] to represent used or unused split memory blocks. The address of a block's "buddy" is equal to the bitwise [[exclusive OR]] (XOR) of the block's address and the block's size.

However, there still exists the problem of [[Fragmentation (computer)#Internal fragmentation|internal fragmentation]] – memory wasted because the memory requested is a little larger than a small block, but a lot smaller than a large block. Because of the way the buddy memory allocation technique works, a program that requests 66 K of memory would be allocated 128 K, which results in a waste of 62 K of memory. This problem can be solved by [[slab allocation]], which may be layered on top of the more coarse buddy allocator to provide more fine-grained allocation.

One version of the buddy allocation algorithm was described in detail by Donald Knuth in volume 1 of ''[[The Art of Computer Programming]]''.<ref>{{cite book | authorlink= Donald Knuth | first= Donald | last= Knuth | series= [[The Art of Computer Programming]] | volume= 1 | title= Fundamental Algorithms | edition= Second | location= Reading, Massachusetts | publisher= Addison-Wesley | year= 1997 |pages=  435–455 | isbn= 0-201-89683-4}}</ref> The [[Linux kernel]] also uses the buddy system, with further modifications to minimise external fragmentation, along with various other allocators to manage the memory within blocks.<ref>{{cite book |last= Mauerer |first= Wolfgang |title= Professional Linux Kernel Architecture |publisher= [[Wrox Press]] |date=October 2008 |isbn= 978-0-470-34343-2}}</ref>

<code>jemalloc</code> is a modern memory allocator that employs, among others, the buddy technique.<ref>
{{Citation |last=Evans |first=Jason |title=A Scalable Concurrent <code>malloc(3)</code> Implementation for FreeBSD |date=16 April 2006 |pages=4–5 |url=http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf}}
</ref>