버디 메모리 할당

버디 메모리 할당() 기술은 가능한 적당하게 메모리 요청을 만족하도록 메모리를 여러 부분으로 나누는 메모리 할당 알고리즘이다. 이 시스템은 메모리의 크기를 절반씩 분할을 하면서 가장 잘 맞는 크기의 메모리를 찾는다. 도널드 커누스(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 을 이 시스템에 요청한다. 다음의 표는 다양한 메모리 요청에 대한 시스템의 가능한 상태를 보여준다.

64K64K64K64K64K64K64K64K64K64K64K64K64K64K64K64K 1024K A-64K64K 128K 256K 512K A-64K64K B-128K 256K 512K A-64K C-64K B-128K 256K 512K A-64K C-64K B-128K D-128K 128K 512K A-64K64K B-128K D-128K 128K 512K 128K B-128K D-128K 128K 512K 256K D-128K 128K 512K 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)의 컴퓨터 프로그래밍의 예술의 volume 1에 자세히 묘사되어 있다.

 같이 보기 
 메모리 풀
 피보나치 수
 각주 

 외부 링크 
  Buddy System for Storage Management

분류:메모리 관리
분류:메모리 관리 알고리즘