버디 메모리 할당 문서 원본 보기

{{위키데이터 속성 추적}}
'''버디 메모리 할당'''({{lang|en|buddy memory allocation}}) 기술은 가능한 적당하게 메모리 요청을 만족하도록 메모리를 여러 부분으로 나누는 [[메모리 할당]] 알고리즘이다. 이 시스템은 메모리의 크기를 절반씩 분할을 하면서 가장 잘 맞는 크기의 메모리를 찾는다. [[도널드 커누스]](Donald Knuth)에 의하면, 버디 시스템은 1963년에 [[해리 마코위츠]](Harry Markowitz, 1990년 [[노벨 경제학상]] 수상)가 고안한 것으로, [[켄 놀튼]](Kenneth C. Knowlton, 1965년 출판)<ref>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 [http://books.google.com/books?id=0uHME7EfjQEC&printsec=frontcover#PPA84,M1] page 85]</ref>에서 처음으로 선보였다.

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

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

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

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

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

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

{| class="wikitable" width="100%"
|-
!
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
!64K
|-
|<math>t=0</math>
| colspan="16" | 1024K
|-
|<math>t=1</math>
| style="background-color:#cff" | A-64K
|64K
| colspan="2" | 128K
| colspan="4" | 256K
| colspan="8" | 512K
|-
|<math>t=2</math>
| style="background-color:#cff" | A-64K
|64K
| colspan="2" style="background-color:#9f3" | B-128K
| colspan="4" | 256K
| colspan="8" | 512K
|-
|<math>t=3</math>
| style="background-color:#cff" | A-64K
| style="background-color:#f03" | C-64K
| colspan="2" style="background-color:#9f3" | B-128K
| colspan="4" | 256K
| colspan="8" | 512K
|-
|<math>t=4</math>
| style="background-color:#cff" | A-64K
| style="background-color:#f03" | C-64K
| colspan="2" style="background-color:#9f3" | B-128K
| colspan="2" style="background-color:#903" | D-128K
| colspan="2" | 128K
| colspan="8" | 512K
|-
|<math>t=5</math>
| style="background-color:#cff" | A-64K
|64K
| colspan="2" style="background-color:#9f3" | B-128K
| colspan="2" style="background-color:#903" | D-128K
| colspan="2" | 128K
| colspan="8" | 512K
|-
|<math>t=6</math>
| colspan="2" | 128K
| colspan="2" style="background-color:#9f3" | B-128K
| colspan="2" style="background-color:#903" | D-128K
| colspan="2" | 128K
| colspan="8" | 512K
|-
|<math>t=7</math>
| colspan="4" | 256K
| colspan="2" style="background-color:#903" | D-128K
| colspan="2" | 128K
| colspan="8" | 512K
|-
|<math>t=8</math>
| colspan="16" | 1024K
|}

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

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

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

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

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

버디 할당 알고리즘 중 한 버전은 [[도널드 커누스]](Donald Knuth)의 ''[[컴퓨터 프로그래밍의 예술]]''<ref>{{서적 인용| authorlink= 도널드 커누스 | 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>의 volume 1에 자세히 묘사되어 있다.

== 같이 보기 ==
* [[메모리 풀]]
* [[피보나치 수]]
== 각주 ==
<references/>

== 외부 링크 ==
* {{언어링크|en}} [http://www.brpreiss.com/books/opus4/html/page431.html#SECTION0014400000000000000000 Buddy System for Storage Management]

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