버디 메모리 할당

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 작동 원리
3. 장단점
- 3.1. 장점
- 3.2. 단점
4. 개선 및 응용
참조

1. 개요

버디 메모리 할당은 2의 거듭제곱 크기로 메모리를 할당하는 방식이다. 메모리 요청 시에는 요청 크기 이상의 최소 블록을 찾아 할당하고, 메모리 해제 시에는 인접 블록과 병합하는 과정을 거친다. 이 방식은 외부 단편화를 줄이고 메모리 압축에 용이하지만, 내부 단편화 문제가 발생할 수 있다. 이러한 단점을 보완하기 위해 슬랩 할당과 같은 기술이 사용되며, 리눅스 커널, jemalloc 등에서 활용된다.

더 읽어볼만한 페이지

메모리 관리 알고리즘 - 키오시아
키오시아는 도시바의 반도체 메모리 사업을 계승하여, 2017년 분사 후 베인캐피털 컨소시엄에 인수되어 2019년 현재 사명으로 변경되었으며, NAND 플래시 메모리 기술 기반의 제품을 생산하고 요카이치, 키타카미 공장을 주요 생산 시설로 두고 있다.
메모리 관리 알고리즘 - Least Recently Used
Least Recently Used(LRU)는 가장 최근에 사용되지 않은 항목을 교체하는 캐시 알고리즘이며, 연결 리스트와 연관 배열을 통해 O(1) 시간 복잡도로 계산하고, CPU 캐시 메모리 및 정리법 등에도 활용된다.
메모리 관리 - 동적 메모리 할당
동적 메모리 할당은 프로그램 실행 중 힙 영역에서 메모리 공간을 확보 및 해제하여 효율적인 메모리 관리와 유연성을 제공하는 기술로, 메모리 누수 방지 및 가비지 컬렉션 등의 고려 사항이 중요하며 C, C++, C++/CLI, C# 등에서 사용된다.
메모리 관리 - 정적 변수
정적 변수는 프로그램 실행 시간 동안 값을 유지하며, C 언어에서 `static` 키워드로 정의되어 함수 호출 간에 값을 유지하고, 객체 지향 프로그래밍에서 클래스의 모든 인스턴스에서 공유되는 클래스 변수로 사용된다.

버디 메모리 할당
일반 정보
이름	버디 메모리 할당
종류	메모리 할당 알고리즘
고안 시기	1963년
고안자	케네스 놀턴
특징
장점	구현이 비교적 간단함 할당 및 해제가 빠름 외부 단편화 감소
단점	내부 단편화 발생 가능성 존재 특정 크기의 블록을 찾기 어려울 수 있음
작동 원리
기본 개념	사용 가능한 메모리 블록을 2의 제곱 크기로 분할하고 관리
할당 과정	요청된 크기에 맞는 블록이 없으면 더 큰 블록을 반으로 나누어 요청을 만족시킴
해제 과정	해제된 블록과 인접한 블록이 사용 가능하고 같은 크기이면 병합하여 더 큰 블록을 만듦
활용
운영체제	리눅스 커널 등에서 사용
기타	메모리 풀, 게임 개발 등

2. 작동 원리

버디 메모리 할당은 메모리를 2의 거듭제곱(예: 2^x) 단위로 할당하는 기술이다. 프로그래머는 할당 가능한 메모리 블록의 상한선(u)과 하한선(l)을 결정해야 한다.
메모리 할당 과정:1. 프로그램이 특정 크기의 메모리를 요청한다.

2. 시스템은 요청된 크기 이상인 가장 작은 2^k 크기의 블록을 찾는다.

3. 해당 블록이 있으면 프로그램에 할당한다.

4. 없으면, 더 큰 빈 블록을 절반씩 나누어 요청된 크기의 블록을 만든다.

하한선에 도달하면 해당 크기의 블록을 할당한다.

5. 적절한 크기의 블록을 찾을 때까지 반복한다.
메모리 해제 과정:1. 프로그램이 메모리 해제를 요청하면, 시스템은 해당 블록을 해제한다.

2. 인접한 블록(버디 블록)이 비어 있는지 확인한다.

3. 비어 있다면 두 블록을 병합하고, 상한선에 도달하거나 사용 중인 블록을 만날 때까지 반복한다.

아래는 상한선 u=10 (1,024,000), 하한선 l=6 (64,000)인 시스템에서 메모리 요청(A: 34,000~64,000, B: 66,000~128,000, C: 35,000~64,000, D: 67,000~128,000) 및 해제 과정을 나타낸 표이다.

	64,000	64,000	64,000	64,000	64,000	64,000
t=0	1,024,000
t=1	A-64,000	64,000	128,000	256,000		512,000
t=2	A-64,000	64,000	B-128,000	256,000		512,000
t=3	A-64,000	C-64,000	B-128,000	256,000		512,000
t=4	A-64,000	C-64,000	B-128,000	D-128,000	128,000	512,000
t=5	A-64,000	64,000	B-128,000	D-128,000	128,000	512,000
t=6	128,000		B-128,000	D-128,000	128,000	512,000
t=7	256,000			D-128,000	128,000	512,000
t=8	1,024,000

t=0: 초기 상태 (1,024,000 블록).
t=1: A (64,000) 요청, 1,024,000 블록 분할 후 할당.
t=2: B (128,000) 요청, 128,000 블록 할당.
t=3: C (64,000) 요청, 64,000 블록 할당.
t=4: D (128,000) 요청, 256,000 블록 분할 후 할당.
t=5: C 해제.
t=6: A 해제.
t=7: B 해제.
t=8: D 해제, 주변 빈 블록과 병합하여 1,024,000 블록 복구.

메모리 해제는 log₂(u/l)과 같은 효율적인 병합을 통해 빠르게 이루어진다. 버디 메모리 할당은 보통 이진 트리로 구현되며, 각 블록은 사용 중이거나 비어 있는 상태를 가진다.

버디 시스템에서 모든 블록은 차수(0부터 상한까지의 정수)를 가지며, 차수 n 블록 크기는 2ⁿ에 비례하여 주소 계산을 단순하게 한다. 모든 버디가 2의 거듭제곱인 메모리 주소 경계에 정렬되기 때문이다. 더 큰 블록은 두 개의 작은 블록(서로 고유한 버디)으로 나뉘며, 분할된 블록은 고유한 버디 블록과만 병합될 수 있다.

처음에는 가장 작은 블록 크기(차수-0 블록)가 결정된다. 하한이 너무 낮으면 메모리 및 계산 오버헤드가 발생할 수 있지만, 평균 할당 당 메모리 낭비를 최소화하기 위해 적절한 하한 설정이 필요하다.

2. 1. 기본 개념

버디 메모리 할당은 메모리를 2의 거듭제곱 단위로 할당하는 기술이다. 프로그래머는 할당 가능한 메모리 블록 크기의 상한선과 하한선을 결정해야 한다.

상한선 (u): 시스템이 할당할 수 있는 가장 큰 메모리 블록 크기이다. 예를 들어, 시스템에 2000K의 물리적 메모리가 있다면, 2¹⁰ (1024K)가 할당 가능한 가장 큰 블록이므로 상한선은 10이 된다. 이는 단일 청크로 전체 물리적 메모리를 할당하는 것이 불가능하기 때문이다. 나머지 976K 메모리는 더 작은 블록으로 할당해야 한다.
하한선 (l): 할당될 수 있는 가장 작은 메모리 블록 크기이다. 이는 저장 오버헤드를 최소화하고 메모리 낭비를 줄이기 위해 필요하다. 하한선이 없으면 작은 블록 요청으로 인해 시스템이 많은 공간을 낭비할 수 있다. 일반적으로 하한선은 공간 낭비를 최소화할 만큼 작으면서도 과도한 오버헤드를 피할 만큼 충분히 큰 값으로 설정된다. (예: 2¹² = 4K)

메모리 요청 및 할당 과정:시스템에 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

메모리 할당 과정:1. 프로그램이 메모리를 요청한다. (예: A: 34K\~64K, B: 66K\~128K, C: 35K\~64K, D: 67K\~128K)

2. 시스템은 요청된 크기 이상의 가장 작은 2^k 블록을 찾는다.

3. 찾으면 해당 블록을 할당한다.

4. 못 찾으면, 더 큰 빈 블록을 절반씩 나누어 요청된 크기의 블록을 만든다.

하한선에 도달하면 해당 메모리를 할당한다.

5. 적절한 크기의 블록을 찾을 때까지 이 과정을 반복한다.
메모리 해제 과정:1. 프로그램이 메모리 해제를 요청한다.

2. 시스템은 해당 블록을 해제한다.

3. 인접한 블록이 해제된 상태인지 확인한다.

4. 해제된 상태라면 두 블록을 병합하고, 상한선에 도달하거나 해제되지 않은 블록을 만날 때까지 반복한다.

이러한 메모리 해제 방식은 log₂(u/l) ( = log₂(u) - log₂(l) )과 같이 효율적인 병합을 통해 빠르게 메모리를 정리할 수 있다.

버디 메모리 할당은 일반적으로 이진 트리를 사용하여 구현되며, 각 블록은 사용 중이거나 사용되지 않는 상태를 가진다.

하지만, 버디 메모리 할당은 내부 단편화 문제가 발생할 수 있다. 내부 단편화는 할당된 메모리 블록 내부에 사용되지 않는 공간이 생기는 현상이다. 이 문제는 slab allocation을 통해 해결할 수 있다.

버디 할당 알고리즘의 한 버전은 도널드 커누스의 ''컴퓨터 프로그래밍의 예술''^[6] 1권에 자세히 설명되어 있다.

버디 시스템의 가장 단순하고 일반적인 형태는 각 블록이 두 개의 작은 블록으로 세분화되는 방식이다. 모든 메모리 블록은 차수(0부터 지정된 상한까지의 정수)를 가지며, 차수 n의 블록 크기는 2ⁿ에 비례한다. 2의 거듭제곱 블록 크기는 주소 계산을 단순하게 만드는데, 모든 버디가 2의 거듭제곱인 메모리 주소 경계에 정렬되기 때문이다. 더 큰 블록이 분할되면 두 개의 작은 블록으로 나누어지고, 각 작은 블록은 서로 고유한 버디가 된다. 분할된 블록은 고유한 버디 블록과만 병합될 수 있으며, 이를 통해 원래의 더 큰 블록으로 다시 형성된다.

처음 시작할 때, 가능한 가장 작은 블록의 크기(차수-0 블록)가 결정된다. 하한이 너무 낮으면 메모리 및 계산 오버헤드가 발생할 수 있지만, 평균 할당당 메모리 낭비를 최소화하기 위해 적절한 하한 설정이 필요하다. 일반적으로 하한은 할당당 평균 낭비 공간을 최소화할 만큼 작지만 과도한 오버헤드를 피할 만큼 충분히 크게 설정된다.

프로그래머는 사용 가능한 나머지 메모리 공간에 맞출 수 있는 가장 높은 가능한 차수를 결정하거나 코드를 작성해야 한다. 시스템의 총 사용 가능한 메모리가 최소 블록 크기의 2의 거듭제곱 배수가 아닐 수 있으므로, 가장 큰 블록 크기가 시스템의 전체 메모리를 포괄하지 못할 수 있다. 예를 들어, 시스템에 2000K의 물리적 메모리가 있고 차수-0 블록 크기가 4K인 경우, 차수의 상한은 8이 된다. 차수-8 블록(256개 차수-0 블록, 1024K)이 메모리에 맞는 가장 큰 블록이기 때문이다. 나머지 976K의 메모리는 더 작은 블록으로 할당해야 한다.

2. 2. 할당 과정

버디 메모리 할당에서 메모리 요청이 오면 시스템은 2의 거듭제곱 크기로 메모리 블록을 할당한다. 이 과정을 자세히 살펴보자.
1. 초기 설정:

상한선 (u): 할당 가능한 가장 큰 메모리 블록 크기를 결정한다. 예를 들어, 시스템에 2000K의 물리 메모리가 있다면, 1,024,000 (2¹⁰)가 가장 큰 블록이므로 상한선은 10이 된다.
하한선 (l): 할당 가능한 가장 작은 메모리 블록 크기를 결정한다. 이는 메모리 할당 및 해제 정보를 저장하는 데 필요한 오버헤드를 줄이고, 작은 메모리 요청으로 인한 공간 낭비를 막기 위해 필요하다. 보통 4,000 (2¹²) 정도가 적절한 하한선으로 사용된다.

2. 메모리 할당 과정:프로그램이 특정 크기의 메모리를 요청하면, 시스템은 다음 단계를 따른다.

1. 적절한 크기 찾기: 요청된 메모리 크기보다 크거나 같은 2의 거듭제곱 크기의 블록을 찾는다.

2. 블록 할당:

찾은 블록이 있으면 해당 블록을 프로그램에 할당한다.
찾은 블록이 없으면, 더 큰 블록을 분할하여 적절한 크기의 블록을 만든다.
요청 크기보다 큰 블록을 절반으로 나눈다.
하한선에 도달하면 해당 크기의 블록을 할당한다.
적절한 크기의 블록을 찾을 때까지 이 과정을 반복한다.

3. 메모리 해제 과정:프로그램이 메모리 사용을 완료하면, 시스템은 다음 단계를 따른다.

1. 블록 해제: 해당 메모리 블록을 해제한다.

2. 주변 블록 확인: 주변(인접한) 블록이 비어 있는지 확인한다.

3. 블록 병합:

주변 블록이 비어 있으면, 두 블록을 합쳐 더 큰 블록을 만든다.
상한선에 도달하거나, 주변 블록이 사용 중일 때까지 이 과정을 반복한다.

예시:아래 표는 상한선이 10 (1,024,000), 하한선이 6 (64,000)인 시스템에서 다양한 메모리 요청에 따른 할당 과정을 보여준다.

시간	64,000	64,000	64,000	64,000	64,000	64,000
t=0	1,024,000
t=1	A-64,000	64,000	128,000	256,000		512,000
t=2	A-64,000	64,000	B-128,000	256,000		512,000
t=3	A-64,000	C-64,000	B-128,000	256,000		512,000
t=4	A-64,000	C-64,000	B-128,000	D-128,000	128,000	512,000
t=5	A-64,000	64,000	B-128,000	D-128,000	128,000	512,000
t=6	128,000		B-128,000	D-128,000	128,000	512,000
t=7	256,000			D-128,000	128,000	512,000
t=8	1,024,000

t=0: 초기 상태, 1,024,000 블록 하나가 존재한다.
t=1: 프로그램 A가 64,000 메모리를 요청하여, 1,024,000 블록이 분할되고 64,000 블록이 할당된다.
t=2: 프로그램 B가 128,000 메모리를 요청하여, 128,000 블록이 할당된다.
t=3: 프로그램 C가 64,000 메모리를 요청하여, 64,000 블록이 할당된다.
t=4: 프로그램 D가 128,000 메모리를 요청하여, 256,000 블록이 분할되고 128,000 블록이 할당된다.
t=5: 프로그램 C가 메모리를 해제한다.
t=6: 프로그램 A가 메모리를 해제한다.
t=7: 프로그램 B가 메모리를 해제한다.
t=8: 프로그램 D가 메모리를 해제하면서, 주변의 빈 블록들과 병합되어 1,024,000 블록으로 복구된다.

이처럼 버디 메모리 할당은 메모리 요청과 해제에 따라 블록을 분할하고 병합하는 과정을 반복하며 메모리를 효율적으로 관리한다.

2. 3. 해제 과정

메모리가 해제되면 다음과 같은 과정이 진행된다.

1. 메모리 블록을 해제한다.

2. 주변 블록을 살펴보고, 주변 블록도 해제된 상태인지 확인한다.

3. 만약 주변 블록도 해제되어 있다면, 두 메모리 블록을 합친다.

4. 2번 단계로 돌아가서, 상한선에 도달하거나 (모든 메모리가 해제됨) 해제되지 않은 주변 블록을 만날 때까지 이 과정을 반복한다.

이러한 메모리 해제 방식은 log₂(u/l) (여기서 u는 상한선, l은 하한선)과 같은 효율적인 간결화 숫자를 사용하여 비교적 빠르게 간결화를 수행하므로 매우 능률적이다.

메모리 해제 과정의 예시는 다음과 같다.

단계	64 K	64 K	64 K	64 K	64 K	64 K
5.2	A: 2⁰	C: 2⁰	B: 2¹	D: 2¹	2¹	2³
6	A: 2⁰	C: 2⁰	2¹	D: 2¹	2¹	2³
7.1	A: 2⁰	C: 2⁰	2¹	2¹	2¹	2³
7.2	A: 2⁰	C: 2⁰	2¹	2²		2³
8	2⁰	C: 2⁰	2¹	2²		2³
9.1	2⁰	2⁰	2¹	2²		2³
9.2	2¹		2¹	2²		2³
9.3	2²			2²		2³
9.4	2³					2³
9.5	2⁴

6단계: 프로그램 B가 메모리를 해제한다.
7단계: 프로그램 D가 메모리를 해제한다.
순서 1 블록 하나가 해제된다.
새로 해제된 블록의 버디 블록도 비어 있으므로, 두 블록을 병합하여 순서 2 블록을 만든다.
8단계: 프로그램 A가 메모리를 해제한다.
9단계: 프로그램 C가 메모리를 해제한다.
순서 0 블록 하나가 해제된다.
새로 해제된 블록의 버디 블록도 비어 있으므로, 두 블록을 병합하여 순서 1 블록을 만든다.
새로 형성된 순서 1 블록의 버디 블록도 비어 있으므로, 두 블록을 병합하여 순서 2 블록을 만든다.
새로 형성된 순서 2 블록의 버디 블록도 비어 있으므로, 두 블록을 병합하여 순서 3 블록을 만든다.
새로 형성된 순서 3 블록의 버디 블록도 비어 있으므로, 두 블록을 병합하여 순서 4 블록을 만든다.

이와 같이 버디 메모리 할당에서는 메모리 해제 시 주변 블록과의 병합을 통해 단편화를 줄이고, 효율적인 메모리 관리를 가능하게 한다.

2. 4. 주소 계산

버디 메모리 할당에서 모든 메모리 블록은 특정 ''차수''를 가지며, 이 차수는 0부터 지정된 상한값까지의 정수이다. 차수 n인 블록의 크기는 2ⁿ에 비례하므로, 블록은 바로 아래 차수 블록 크기의 정확히 두 배가 된다. 이러한 2의 거듭제곱 블록 크기는 주소 계산을 단순하게 만드는데, 그 이유는 모든 버디가 2의 거듭제곱인 메모리 주소 경계에 정렬되기 때문이다.^[6]

더 큰 블록이 분할될 때는 두 개의 작은 블록으로 나뉘며, 각각의 작은 블록은 서로에게 고유한 '버디'가 된다. 분할된 블록은 오직 자신의 고유한 버디 블록과만 병합될 수 있으며, 이를 통해 원래 분할되었던 더 큰 블록으로 다시 형성된다.^[6]

처음에는 할당 가능한 가장 작은 메모리 블록의 크기, 즉 차수-0 블록의 크기가 결정된다. 하한이 없는 경우, 시스템은 메모리의 어느 부분이 할당되었고 어느 부분이 할당되지 않았는지 추적하는 데 많은 메모리와 계산 오버헤드를 소모하게 된다. 그러나 평균 할당 당 메모리 낭비를 최소화하기 위해서는 (가장 작은 블록 크기의 배수가 아닌 할당과 관련하여) 상당히 낮은 하한이 바람직할 수 있다. 일반적으로 하한은 할당 당 평균 낭비 공간을 최소화할 만큼 작지만, 과도한 오버헤드를 피할 만큼 충분히 크게 설정된다.

이후 프로그래머는 사용 가능한 나머지 메모리 공간에 맞출 수 있는 가장 높은 가능한 차수를 결정하거나, 이를 결정하는 코드를 작성해야 한다. 주어진 컴퓨터 시스템의 총 사용 가능한 메모리가 최소 블록 크기의 2의 거듭제곱 배수가 아닐 수 있으므로, 가장 큰 블록 크기가 시스템의 전체 메모리를 포괄하지 못할 수도 있다. 예를 들어, 시스템에 2,000,000의 물리적 메모리가 있고 차수-0 블록 크기가 4,000인 경우, 차수의 상한은 8이 된다. 이는 차수-8 블록(256개의 차수-0 블록, 즉 1,024,000)이 메모리에 맞는 가장 큰 블록이기 때문이다. 결과적으로 전체 물리적 메모리를 단일 청크로 할당하는 것은 불가능하며, 나머지 976,000의 메모리는 더 작은 블록으로 할당되어야 한다.

3. 장단점

버디 메모리 할당은 구현이 비교적 쉽지만, 작동 방식 때문에 일정 수준의 내부 단편화가 발생할 수 있다. 요청된 메모리가 작은 블록보다 조금 더 크면 메모리가 낭비된다. 예를 들어 66K 메모리를 요청하면 128K가 할당되어 62K 메모리가 낭비된다.

동적 할당과 같은 다른 간단한 기술들과 비교했을 때, 버디 메모리 시스템은 약간의 외부 단편화와 메모리 간결화를 위한 오버헤드가 발생한다.

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

상한선(u)을 결정한 뒤에는, 할당될 수 있는 가장 작은 메모리 블록인 하한선(l)을 결정해야 한다. 이 하한선은 저장에 발생되는 오버헤드를 최소화하고 비어있는 메모리 공간을 최소화하기 위해 필요하다. 일반적으로 하한선은 공간 낭비를 최소화할 수 있을 만큼 충분히 작고, 과도한 오버헤드를 피할 수 있을 만큼 충분히 큰 적당한 숫자이다.

메모리 할당 및 해제 과정은 다음과 같이 요약될 수 있다.

'''메모리 할당:'''

# 요청된 크기에 맞는 가장 작은 2^k 블록을 찾는다.

## 적당한 크기의 블록이 발견되면 할당한다.

## 발견되지 않으면, 더 큰 블록을 절반씩 나누어 적당한 크기의 블록을 만든다.

### 하한선에 도달하면 해당 메모리를 할당하고, 아니면 다시 적당한 크기의 블록을 찾는다.

'''메모리 해제:'''

# 메모리 블록을 해제한다.

# 주변 블록(버디)이 해제된 상태인지 확인한다.

# 주변 블록도 해제되었다면 두 블록을 병합하고, 상한선에 도달하거나 해제되지 않은 블록을 만날 때까지 반복한다.

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

3. 1. 장점

버디 메모리 할당은 외부 단편화가 적고 오버헤드 없이 메모리 압축을 허용한다는 장점이 있다. 메모리 해제 속도가 빠르며, 필요한 최대 압축 횟수는 O(최고 차수) = O(log₂(총 메모리 크기))이다. Donald Knuth^영어의 ''컴퓨터 프로그래밍의 예술''^[6]에 버디 할당 알고리즘 버전이 상세히 설명되어 있다.

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

일반적으로 버디 메모리 할당 시스템은 사용되거나 사용되지 않은 분할된 메모리 블록을 나타내기 위해 이진 트리를 사용하여 구현된다. 블록의 "버디" 주소는 블록의 주소와 블록 크기의 비트 단위 배타적 OR (XOR)과 같다.

리눅스 커널은 외부 단편화를 최소화하기 위한 추가 수정과 함께 블록 내의 메모리를 관리하기 위해 다양한 다른 할당자와 함께 버디 시스템을 사용한다.^[3]

jemalloc^[4]은 특히 버디 기법을 사용하는 현대적인 메모리 할당자이다.

3. 2. 단점

버디 메모리 할당은 구현이 비교적 쉽지만, 몇 가지 단점을 가지고 있다.

내부 단편화: 요청된 메모리 크기가 2의 거듭제곱이 아닐 경우, 할당된 블록 내부에 사용되지 않는 공간이 발생한다. 예를 들어, 66K 메모리를 요청하면 128K 블록이 할당되어 62K가 낭비된다. 이러한 내부 단편화는 메모리 낭비로 이어진다.^[2]
외부 단편화: 동적 할당과 같은 다른 메모리 할당 기술과 비교했을 때, 버디 메모리 시스템은 약간의 외부 단편화와 메모리 압축을 위한 오버헤드가 발생한다.
상한선 및 하한선 결정: 프로그래머는 할당 가능한 가장 큰 메모리 블록 크기(상한선)와 가장 작은 블록 크기(하한선)를 결정해야 한다. 상한선은 시스템의 물리적 메모리 크기에 의해 제한되며, 하한선은 오버헤드를 최소화하고 메모리 낭비를 줄이기 위해 적절한 값으로 설정되어야 한다.
2의 거듭제곱 제한: 메모리 할당 및 해제는 항상 2의 거듭제곱 크기 블록으로 이루어진다. 이로 인해 2의 거듭제곱이 아닌 크기의 메모리 요청은 비효율적일 수 있다.

이러한 내부 단편화 문제는 슬랩 할당을 통해 해결할 수 있다.^[2] 슬랩 할당은 더 조악한 버디 할당자 위에 계층화되어 더 세분화된 할당을 제공한다.

리눅스 커널은 외부 단편화를 최소화하기 위한 추가 수정과 함께 블록 내 메모리 관리를 위해 다양한 할당자와 함께 버디 시스템을 사용한다.^[3]

`jemalloc`은 버디 기법을 사용하는 현대적인 메모리 할당자이다.^[4]

4. 개선 및 응용

동적 할당과 같은 다른 간단한 기법에 비해 버디 메모리 시스템은 외부 단편화가 적고 오버헤드 없이 메모리 압축을 허용한다. 메모리를 해제하는 버디 방식은 빠르며 필요한 최대 압축 횟수는 O(최고 차수) = O(log₂(총 메모리 크기))와 같다. 일반적으로 버디 메모리 할당 시스템은 사용되거나 사용되지 않은 분할된 메모리 블록을 나타내기 위해 이진 트리를 사용하여 구현된다. 블록의 "버디" 주소는 블록의 주소와 블록 크기의 비트 단위 XOR과 같다.

그러나 내부 단편화] 문제는 여전히 존재한다. 버디 할당 알고리즘의 한 버전은 도널드 커누스에 의해 ''컴퓨터 프로그래밍의 예술'' 제1권에 자세히 설명되었다.^[2]

4. 1. 슬랩 할당 (Slab Allocation)

슬랩 할당은 내부 단편화 문제를 해결하기 위해 사용될 수 있는 방법이다. 버디 메모리 할당 기법에서는 요청된 메모리가 작은 블록보다는 약간 크지만, 큰 블록보다는 훨씬 작을 경우 메모리가 낭비될 수 있다. 예를 들어, 66K의 메모리를 요청하는 프로그램은 128K를 할당받게 되어 62K의 메모리가 낭비되는 문제가 발생한다. 이러한 문제는 더 세분화된 할당을 제공하기 위해 버디 할당자 위에 계층화될 수 있는 슬랩 할당을 통해 해결할 수 있다.

리눅스 커널은 외부 단편화를 최소화하기 위한 추가 수정과 함께 블록 내의 메모리를 관리하기 위해 다양한 다른 할당자와 함께 버디 시스템을 사용한다.^[3]

`jemalloc`^[4]은 특히 버디 기법을 사용하는 현대적인 메모리 할당자이다.

4. 2. 리눅스 커널

리눅스 커널은 외부 단편화를 최소화하기 위한 추가 수정과 함께, 블록 내의 메모리를 관리하기 위해 다양한 다른 할당자와 함께 버디 시스템을 사용한다.^[3]

4. 3. jemalloc

jemalloc^영어은 버디 기법을 사용하는 현대적인 메모리 할당자이다.^[4]

참조

_[1] 논문 A Fast storage allocator 1965-10
_[2] 서적 Fundamental Algorithms Addison-Wesley
_[3] 서적 Professional Linux Kernel Architecture Wrox Press 2008-10
_[4] 간행물 A Scalable Concurrent malloc(3) Implementation for FreeBSD http://people.freebs[...] 2006-04-16
_[5] 논문 A Fast storage allocator 1965-10
_[6] 서적 Fundamental Algorithms Addison-Wesley

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com