버디 메모리 할당

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

기능 추가 및 결과 편집

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

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

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

작동 원리 편집

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

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

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

	64K	64K	64K	64K	64K	64K
$t=0$	1024K
$t=1$	A-64K	64K	128K	256K		512K
$t=2$	A-64K	64K	B-128K	256K		512K
$t=3$	A-64K	C-64K	B-128K	256K		512K
$t=4$	A-64K	C-64K	B-128K	D-128K	128K	512K
$t=5$	A-64K	64K	B-128K	D-128K	128K	512K
$t=6$	128K		B-128K	D-128K	128K	512K
$t=7$	256K			D-128K	128K	512K
$t=8$	1024K

이 할당은 아래의 방식으로 발생할 수 있다.

프로그램 A가 34K ~ 64K 크기의 메모리를 요청한다.
프로그램 B가 66K ~ 128K 크기의 메모리를 요청한다.
프로그램 C가 35K ~ 64K 크기의 메모리를 요청한다.
프로그램 D가 67K ~ 128K 크기의 메모리를 요청한다.
프로그램 C가 메모리를 해제한다.
프로그램 A가 메모리를 해제한다.
프로그램 B가 메모리를 해제한다.
프로그램 D가 메모리를 해제한다.

보다시피, 메모리 요청이 발생되었을 때 다음과 같은 일들이 벌어졌다.

메모리가 할당되면

적당한 크기의 메모리 슬롯을 찾는다.(최소한 요청된 메모리와 동일하거나 큰 2^k 블록)
1. 적당한 크기의 메모리 슬롯이 발견되면, 프로그램에 할당한다.
2. 적당한 크기의 메모리 슬롯이 발견되지 않으면, 적당한 메모리 슬롯을 만들기를 시도한다. 시스템은 아래의 일들을 시도한다.
  1. 요청된 메모리 크기보다 크게 절반씩 빈 메모리 슬롯을 자른다.
  2. 하한선에 도착하게 되면, 해당 메모리(하한선 크기의 메모리)를 할당한다.
  3. 다시 첫 번째 단계로 돌아간다.(적당한 크기의 메모리를 찾기 위해서)
  4. 적당한 메모리 슬롯이 발견될 때까지, 이 과정을 반복한다.

메모리가 해제되면

메모리 블록을 해제한다.
주변의 블록들을 살펴 본다 - 주변 블록들도 해제된 상태인가?
만약 그렇다면, 두 메모리 블록을 조합하고 다시 두 번째 단계로 돌아간다. 그리고 해제된 모든 메모리들이 상한선에 도달할 때까지 이 과정을 반복하거나, 해제되지 않은 주변 블록들을 마주칠 때까지 반복한다.

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

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

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

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

참고 자료 편집

↑ 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 [1] page 85]
↑ Knuth, Donald (1997). 《Fundamental Algorithms》. The Art of Computer Programming 1 Seco판. Reading, Massachusetts: Addison-Wesley. 435–455쪽. ISBN 0-201-89683-4.

외부 링크 편집

(영어) Buddy System for Storage Management

[1] 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 [1] page 85]

[2] Knuth, Donald (1997). 《Fundamental Algorithms》. The Art of Computer Programming 1 Seco판. Reading, Massachusetts: Addison-Wesley. 435–455쪽. ISBN 0-201-89683-4.

[1]

[2]