버디 메모리 할당

**버디 메모리 할당**(buddy memory allocation) 기술은 가능한 적당하게 메모리 요청을 만족하도록 메모리를 여러 부분으로 나누는 메모리 할당 알고리즘이다. 이 시스템은 메모리의 크기를 절반씩 분할을 하면서 가장 잘 맞는 크기의 메모리를 찾는다. 도널드 커누스(Donald Knuth)에 의하면, 버디 시스템은 1963년에 해리 마코위츠(Harry Markowitz, 1990년 노벨 경제학상 수상)가 고안한 것으로, 켄 놀튼(Kenneth C. Knowlton, 1965년 출판)Kenneth C. Knowlton. A Fast storage allocator. Communications of the ACM 8(10):623-625, Oct 1965. *also* Kenneth C Knowlton. A programmer's description of L6. Communications of the ACM, 9(8):616-625, Aug. 1966 [see also : Google books page 85에서 처음으로 선보였다.
# 기능 추가 및 결과
버디 메모리 할당은 최신 운영 체제에 쓰이는 메모리 할당 기술들에 비해 상대적으로 구현하기가 쉬운 편이다. 동적 할당과 같은 다른 간단한 기술들에 견주어 볼 때, 버디 메모리 시스템은 약간의 외부 단편화와 메모리 간결화를 하는 오버헤드를 가지고 있다. 버디 메모리 할당 기술이 작동 방식 때문에 적당한 양의 내부 단편화가 있을 수 있다. 다시 말해, 요청된 메모리가 작은 블록보다 조금 더 크면 메모리가 낭비된다.(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 을 이 시스템에 요청한다. 다음의 표는 다양한 메모리 요청에 대한 시스템의 가능한 상태를 보여준다. {| class="wikitable" width="100%" |- ! !64K !64K !64K !64K !64K !64K !64K !64K !64K !64K !64K !64K !64K !64K !64K !64K |- |t=0 | colspan="16" | 1024K |- |t=1 | | A-64K |64K | colspan="2" | 128K | colspan="4" | 256K | colspan="8" | 512K |- |t=2 | | A-64K |64K | colspan="2" | B-128K | colspan="4" | 256K | colspan="8" | 512K |- |t=3 | | A-64K | | C-64K | colspan="2" | B-128K | colspan="4" | 256K | colspan="8" | 512K |- |t=4 | | A-64K | | C-64K | colspan="2" | B-128K | colspan="2" | D-128K | colspan="2" | 128K | colspan="8" | 512K |- |t=5 | | A-64K |64K | colspan="2" | B-128K | colspan="2" | D-128K | colspan="2" | 128K | colspan="8" | 512K |- |t=6 | colspan="2" | 128K | colspan="2" | B-128K | colspan="2" | D-128K | colspan="2" | 128K | colspan="8" | 512K |- |t=7 | colspan="4" | 256K | colspan="2" | D-128K | colspan="2" | 128K | colspan="8" | 512K |- |t=8 | colspan="16" | 1024K |} 이 할당은 아래의 방식으로 발생할 수 있다. # 프로그램 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)의 *컴퓨터 프로그래밍의 예술*isbn= 0-201-89683-4의 volume 1에 자세히 묘사되어 있다.