The buddy memory allocation technique is a memory allocation algorithm that divides memory into partitions to try to satisfy a memory request as suitably as possible. This system makes use of splitting memory into halves to try to give a best fit.  According to Donald Knuth, the buddy system was invented in 1963 by Harry Markowitz, and was first described by Kenneth C. Knowlton (published 1965). The Buddy memory allocation is relatively easy to implement. It supports limited but efficient splitting and coalescing of memory blocks.

Algorithm 
There are various forms of the buddy system; those in which each block is subdivided into two smaller blocks are the simplest and most common variety. Every memory block in this system has an order, where the order is an integer ranging from 0 to a specified upper limit. The size of a block of order n is proportional to 2n, so that the blocks are exactly twice the size of blocks that are one order lower. Power-of-two block sizes make address computation simple, because all buddies are aligned on memory address boundaries that are powers of two. When a larger block is split, it is divided into two smaller blocks, and each smaller block becomes a unique buddy to the other. A split block can only be merged with its unique buddy block, which then reforms the larger block they were split from.

Starting off, the size of the smallest possible block is determined, i.e. the smallest memory block that can be allocated. If no lower limit existed at all (e.g., bit-sized allocations were possible), there would be a lot of memory and computational overhead for the system to keep track of which parts of the memory are allocated and unallocated. However, a rather low limit may be desirable, so that the average memory waste per allocation (concerning allocations that are, in size, not multiples of the smallest block) is minimized. Typically the lower limit would be small enough to minimize the average wasted space per allocation, but large enough to avoid excessive overhead. The smallest block size is then taken as the size of an order-0 block, so that all higher orders are expressed as power-of-two multiples of this size.

The programmer then has to decide on, or to write code to obtain, the highest possible order that can fit in the remaining available memory space. Since the total available memory in a given computer system may not be a power-of-two multiple of the minimum block size, the largest block size may not span the entire memory of the system. For instance, if the system had 2000 K of physical memory and the order-0 block size was 4 K, the upper limit on the order would be 8, since an order-8 block (256 order-0 blocks, 1024 K) is the biggest block that will fit in memory. Consequently, it is impossible to allocate the entire physical memory in a single chunk; the remaining 976 K of memory would have to be allocated in smaller blocks.

Example 

The following is an example of what happens when a program makes requests for memory. Assume that in this system, the smallest possible block is 64 kilobytes in size, and the upper limit for the order is 4, which results in a largest possible allocatable block, 24 times 64 K = 1024 K in size. The following shows a possible state of the system after various memory requests.

This allocation could have occurred in the following manner
 The initial situation.
 Program A requests memory 34 K, order 0.
 No order 0 blocks are available, so an order 4 block is split, creating two order 3 blocks.
 Still no order 0 blocks available, so the first order 3 block is split, creating two order 2 blocks.
 Still no order 0 blocks available, so the first order 2 block is split, creating two order 1 blocks.
 Still no order 0 blocks available, so the first order 1 block is split, creating two order 0 blocks.
 Now an order 0 block is available, so it is allocated to A.
 Program B requests memory 66 K, order 1. An order 1 block is available, so it is allocated to B.
 Program C requests memory 35 K, order 0. An order 0 block is available, so it is allocated to C.
 Program D requests memory 67 K, order 1.
 No order 1 blocks are available, so an order 2 block is split, creating two order 1 blocks.
 Now an order 1 block is available, so it is allocated to D.
 Program B releases its memory, freeing one order 1 block.
 Program D releases its memory.
 One order 1 block is freed.
 Since the buddy block of the newly freed block is also free, the two are merged into one order 2 block.
 Program A releases its memory, freeing one order 0 block.
 Program C releases its memory.
 One order 0 block is freed.
 Since the buddy block of the newly freed block is also free, the two are merged into one order 1 block.
 Since the buddy block of the newly formed order 1 block is also free, the two are merged into one order 2 block.
 Since the buddy block of the newly formed order 2 block is also free, the two are merged into one order 3 block.
 Since the buddy block of the newly formed order 3 block is also free, the two are merged into one order 4 block.

As you can see, what happens when a memory request is made is as follows:
 If memory is to be allocated
 Look for a memory slot of a suitable size (the minimal 2k block that is larger or equal to that of the requested memory)
 If it is found, it is allocated to the program
 If not, it tries to make a suitable memory slot. The system does so by trying the following:
 Split a free memory slot larger than the requested memory size into half
 If the lower limit is reached, then allocate that amount of memory
 Go back to step 1 (look for a memory slot of a suitable size)
 Repeat this process until a suitable memory slot is found

 If memory is to be freed
 Free the block of memory
 Look at the neighboring block – is it free too?
 If it is, combine the two, and go back to step 2 and repeat this process until either the upper limit is reached (all memory is freed), or until a non-free neighbour block is encountered

Implementation and efficiency 

In comparison to other simpler techniques such as dynamic allocation, the buddy memory system has little external fragmentation, and allows for 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(log2(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 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. 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.

jemalloc is a modern memory allocator that employs, among others, the buddy technique.

See also
 Memory pool
 Stack-based memory allocation
Fibonacci number

References 

Memory management algorithms
버디 메모리 할당() 기술은 가능한 적당하게 메모리 요청을 만족하도록 메모리를 여러 부분으로 나누는 메모리 할당 알고리즘이다. 이 시스템은 메모리의 크기를 절반씩 분할을 하면서 가장 잘 맞는 크기의 메모리를 찾는다. 도널드 커누스(Donald Knuth)에 의하면, 버디 시스템은 1963년에 해리 마코위츠(Harry Markowitz, 1990년 노벨 경제학상 수상)가 고안한 것으로, 켄 놀튼(Kenneth C. Knowlton, 1965년 출판)에서 처음으로 선보였다.

기능 추가 및 결과 
버디 메모리 할당은 최신 운영 체제에 쓰이는 메모리 할당 기술들에 비해 상대적으로 구현하기가 쉬운 편이다.

동적 할당과 같은 다른 간단한 기술들에 견주어 볼 때, 버디 메모리 시스템은 약간의 외부 단편화와 메모리 간결화를 하는 오버헤드를 가지고 있다.

버디 메모리 할당 기술이 작동 방식 때문에 적당한 양의 내부 단편화가 있을 수 있다. 다시 말해, 요청된 메모리가 작은 블록보다 조금 더 크면 메모리가 낭비된다.(66K 메모리를 요청한 프로그램은 128K가 할당되는데, 결과적으로 62K의 메모리가 낭비된다.)

작동 원리 
버디 메모리 할당 기술은 2의 거듭제곱 값(예를 들면, 2x. 여기서 x는 숫자)으로 메모리를 할당한다. 따라서, 프로그래머는 x값의 상한선을 결정하거나 구할 수 있는 코드를 작성해야 한다. 예를 들면, 시스템이 2000K의 물리적인 메모리를 가지고 있다면, 210(1024K)이 할당할 수 있는 가장 큰 블록이기 때문에 x값의 상한선은 10이 될 것이다. 이는 단일 청크에 물리적 메모리 전부를 할당하는 것이 불가능하기 때문이다. 남은 976K 메모리는 좀더 작은 블록들로 할당이 되어야 한다.

상한선(앞으로는 상한선을 u 로 표기하겠음)을 결정한 뒤에는, 프로그래머는 할당될 수 있는 가장 작은 메모리 블록인 하한선을 결정해야 한다. 이 하한선은 저장하는데 발생되는 오버헤드를 최소화하고 비어있는 메모리 공간을 최소화 하기 위해서 필요하다. 이 하한선이 없다면, 많은 프로그래머들은 1K나 2K 같은 작은 블록의 메모리를 요구할 것이고, 시스템은 할당되고 할당되지 않은 블록들을 기억하기 위해서 많은 공간을 낭비하게 될 것이다. 전형적으로 이 숫자(12 같은, 212 = 4K 블록에 할당된 메모리)는 공간의 낭비를 최소화할 수 있을만큼 충분히 작은 적당한 숫자이고, 과도한 오버헤드를 피할 수 있을만큼 충분히 큰 숫자이기도 하다. 앞으로는 이 하한선을 l 로 부르도록 하겠다.

이제 우리는 한계선을 갖게 되었으니, 프로그램이 메모리 요청을 하게 되면 무슨 일이 일어나는지 보도록 하겠다. 26 = 64K, l = 6 을, 할당할 수 있는 가장 큰 블록인 210 = 1024K, u = 10 을 이 시스템에 요청한다. 다음의 표는 다양한 메모리 요청에 대한 시스템의 가능한 상태를 보여준다.

이 할당은 아래의 방식으로 발생할 수 있다.
 프로그램 A가 34K ~ 64K 크기의 메모리를 요청한다.
 프로그램 B가 66K ~ 128K 크기의 메모리를 요청한다.
 프로그램 C가 35K ~ 64K 크기의 메모리를 요청한다.
 프로그램 D가 67K ~ 128K 크기의 메모리를 요청한다.
 프로그램 C가 메모리를 해제한다.
 프로그램 A가 메모리를 해제한다.
 프로그램 B가 메모리를 해제한다.
 프로그램 D가 메모리를 해제한다.

보다시피, 메모리 요청이 발생되었을 때 다음과 같은 일들이 벌어졌다.
 메모리가 할당되면
 적당한 크기의 메모리 슬롯을 찾는다.(최소한 요청된 메모리와 동일하거나 큰 2k 블록)
 적당한 크기의 메모리 슬롯이 발견되면, 프로그램에 할당한다.
 적당한 크기의 메모리 슬롯이 발견되지 않으면, 적당한 메모리 슬롯을 만들기를 시도한다. 시스템은 아래의 일들을 시도한다.
 요청된 메모리 크기보다 크게 절반씩 빈 메모리 슬롯을 자른다.
 하한선에 도착하게 되면, 해당 메모리(하한선 크기의 메모리)를 할당한다.
 다시 첫 번째 단계로 돌아간다.(적당한 크기의 메모리를 찾기 위해서)
 적당한 메모리 슬롯이 발견될 때까지, 이 과정을 반복한다.
 메모리가 해제되면
 메모리 블록을 해제한다.
 주변의 블록들을 살펴 본다 - 주변 블록들도 해제된 상태인가?
 만약 그렇다면, 두 메모리 블록을 조합하고 다시 두 번째 단계로 돌아간다. 그리고 해제된 모든 메모리들이 상한선에 도달할 때까지 이 과정을 반복하거나, 해제되지 않은 주변 블록들을 마주칠 때까지 반복한다.

메모리를 해제 하는 이 방법은 log2(u/l)과 같은 가장 효과적인 간결화 숫자를 이용하면 간결화가 상대적으로 빠르게 이루어져서 꽤 능률적이다.(log2(u)- log2(l))

전형적으로 버디 메모리 할당 시스템은 사용되거나 사용되지 않은 두 가지 상태로 메모리 블록들을 나누는 것을 뜻하는 이진 트리를 이용해서 구현 된다.

하지만, 여전히 내부 단편화의 문제점은 남아 있다. 여러 경우에 있어서, 내부 단편화의 양을 최소화하는 것은 필수적이다. 이 문제점은 slab allocation에 의해서 해결될 수 있다.

버디 할당 알고리즘 중 한 버전은 도널드 커누스(Donald Knuth)의 컴퓨터 프로그래밍의 예술의 volume 1에 자세히 묘사되어 있다.

참고 자료

외부 링크 
  Buddy System for Storage Management

메모리 관리
메모리 관리 알고리즘