[컴퓨터 시스템] 동적 메모리 할당 - Buddy System의 개념

👯‍♀️ Buddy System이란?

Buddy System은 메모리 블록을 2의 제곱 단위로 관리하는 시스템을 의미한다.

💡 Buddy System 작동 방식

1. 메모리는 2의 제곱 단위의 fixed-size block으로 나누어져 있다.

2. 각각의 블록에는 사이즈 정보와 binary number와 같은 unique 식별자가 담겨 있다.

3. 초기에 모든 메모리 블록은 free 상태이고, 각각의 블록은 binary tree 구조 안에서 서로 연결되어 있다. 이때 리프 노드는 가장 작은 가용 블록을 나타낸다.

4. 프로세스가 메모리를 요청하면, 시스템은 요청 받은 사이즈를 충족할 수 있는 가장 작은 가용 블록을 찾는다. 만약에 찾은 블록이 요청한 사이즈보다 크면 시스템은 블록은 두 개의 "buddy" 블록으로 나눈다.

5. 시스템은 버디 중 한 개의 블록을 할당된 상태로 표시하고 프로세스의 memory allocation table에 넣는다. 나머지 버디 블록은 가용 리스트 pool로 반환해서 다시 binary tree 구조에 넣는다.

6. 프로세스가 메모리를 반환하면 시스템은 반환된 블록을 free 상태로 변경하고 그에 상응하는 버디 블록을 찾는다. 만약 버디 블록이 가용 상태라면 시스템은 두 블록을 병합한 뒤 binary tree로 반환한다.

😲 Buddy System의 장단점

우선 Buddy System은 외부 단편화를 줄일 수 있다는 장점이 있다.

외부 단편화는 메모리 전체로 봤을 때는 가용 메모리가 충분하지만, 메모리가 연속된 큰 블록으로 존재하지 않고 작은 크기의 블록들로 쪼개어져 있어서 할당하지 못하는 상황을 의미한다.

Buddy System은 메모리를 2의 거듭제곱 사이즈로 분할하고, 같은 사이즈 클래스에 속하는 버디 블록을 인접하게 배치하기 때문에 추후 메모리 블록이 반환되었을 때 연결하기가 쉽고, 외부 단편화 문제도 줄일 수 있다.

반면, 단점은 내부 단편화에 취약하다는 점이다. 예를 들어 257 바이트가 필요한 경우에는 2의 제곱 단위로 맞추기 위해 512(=2^9) 바이트를 할당해야 한다. 이처럼 2의 제곱 단위로 맞추기 위해 필요 이상으로 큰 메모리를 할당하여 메모리 낭비를 야기할 수 있다.

따라서 4kb 사이즈의 페이지 단위로 메모리를 관리하는 리눅스의 커널 같은 경우에는 Buddy System과 같은 방식이 적합할 것이고, 메모리 할당 사이즈가 천차만별인 경우에는 Buddy System과 같은 방식에는 적합하지 않을 수 있다.