3주차 - 리눅스 커널이 쓰는 버디 시스템, 2의 거듭제곱으로만 메모리를 관리하는 이유

전체 메모리를 2의 거듭제곱 크기 블록으로만 관리하는 버디 시스템

Seglist에서 크기까지 강제하는 제약 버전. 전체 메모리를 2의 거듭제곱 크기 블록으로만 관리. 리눅스 커널의 물리 페이지 할당기가 실제로 이거 씀.

• 크기가 안맞으면 반으로 쪼갬
• 쪼갠 두 조각을 서로의 버디로 부름
• 둘다 비면 다시 합침

크기가 안 맞으면 반으로 쪼갬

초기: 1MB 한 덩어리
[--------------------- 1M ---------------------]

70KB 요청 → 128KB가 필요하니 128KB 될 때까지 반으로 쪼갬
[--- 512K ---][--- 512K ---]           (1M 분할)
[256K][256K][--- 512K ---]             (앞 512K 분할)
[128K][128K][256K][--- 512K ---]       (앞 256K 분할)
 ^^^^ 여기 할당

버디 시스템의 대표적 단점은 내부 단편화

이게 버디 시스템의 대표적 단점인 내부 단편화고, 최악의 경우 거의 50%까지 낭비(2^n + 1 바이트 요청 시). 70KB 요청에 128KB를 줬으니 58KB가 그냥 버려짐.

버디를 찾는 법: 주소에 XOR 연산 한번 하면 끝

주소에 XOR 연산 한번 하면 끝. O(1)에 짝을 찾아 상태만 확인하면 되니 연결(coalescing)이 극도로 빠름, 경계 태그를 뒤져야 하는 일반 할당기와 대비되는 지점.

buddy_addr = block_addr ^ block_size;

크기가 2의 거듭 제곱이고 블록이 자기 크기의 배수 주소에 정렬되어 있다면 짝의 주소는 해당 비트 하나만 뒤집은 값이 됨

블록 크기 128 (0b10000000), 시작 주소 0x300 (0b1100000000)
버디 = 0x300 ^ 0x80 = 0x380

0x300 과 0x380 이 서로 짝
0x380 ^ 0x80 = 0x300  ← 역방향도 성립

XOR 연산 자체가 특정 비트 하나를 뒤집는 연산

블록 크기와 시작 주소를 XOR 연산하면 딱 128을 나타내는 비트만 뒤집어서 바로 옆의 128짜리 블록으로 이동함

위의 설명에서 역방향도 성립하는 이유는 XOR 연산을 2번 반복하면 원래대로 돌아오기 때문

둘 다 비면 다시 합침

해제 후:
[128K 가용][128K 가용][256K 할당][--- 512K 가용 ---]
    A          B

A의 버디 B가 비어있고 크기도 같음 → 병합
[------ 256K 가용 ------][256K 할당][--- 512K 가용 ---]

이 256K의 버디는 옆 256K인데 할당 중 → 여기서 멈춤

리스트 구조는 세그리스트와 같음

세그리스트와 같음

free_list[0]  → 4KB   블록들
free_list[1]  → 8KB   블록들
free_list[2]  → 16KB  블록들
...
free_list[10] → 4MB   블록들

리눅스는 order 0부터 order 10까지 관리

리눅스에선 order 0(4KB 페이지 하나)부터 Order 10(4MB)까지 관리. /proc/buddyinfo를 열어보면 각 order에 가용 블록이 얼마나 남았는지 실제로 확인 가능

Node 0, zone   Normal   1902   1015    427    115     42 ...
                        order0 order1 order2 ...

seglist와 비교

클래스가 논리적 구분이냐 물리적 제약이냐가 결정적 차이입니다. seglist에서 class[3]은 "65~128바이트인 블록들을 엮은 리스트"라는 인덱스일 뿐이지만, 버디에서 order 3은 "실제로 정확히 8단위 크기이고 8의 배수 주소에 정렬된 블록"이라는 물리적 사실입니다.

시리즈에서 이어 읽기 · Malloc Lab →