Buddy System

2의 거듭제곱 블록으로 빠르게 쪼개고 합친다

요청 크기를 가장 가까운 2n 블록으로 올린 뒤, 빈 블록을 반씩 나누거나 같은 크기의 버디와 다시 합칩니다.

요청 33KB 할당
64KB 필요 33KB를 담는 최소 2n
31KB 낭비 내부 단편화
분할 큰 블록을 반씩 나눔
256KB 빈 블록
128KB + 128KB 첫 번째 split
64KB + 64KB 할당 가능한 크기
해제 버디가 비면 coalescing
64KB 반환 짝 버디 확인
128KB 복원 둘 다 비면 병합
큰 연속 공간 다음 대형 요청 대비
장점

탐색과 병합이 빠름

크기 계층이 정해져 있어 빈 리스트 관리가 단순하고, 연속 블록 복구가 쉽습니다.

비용

내부 단편화는 남음

요청 크기보다 큰 2n 블록을 주므로 남는 공간이 생길 수 있습니다.

효과

외부 단편화를 줄임

해제된 버디를 합쳐 큰 블록을 되살리므로 물리 메모리 관리에 적합합니다.

Linux 관점

물리 페이지 프레임을 order별 목록으로 나누어 관리하는 방식이 이 아이디어를 따른 것입니다.