운영체제
Buddy System Memory Allocation버디 시스템
버디 시스템(Buddy System)은 메모리를 2의 거듭제곱 크기 블록으로 관리하는 메모리 할당 알고리즘이다. Linux 커널 페이지 할당자의 핵심 구현이며, 외부 단편화를 줄이면서 빠른 병합을 가능하게 한다.
핵심 원리
메모리 1024KB 요청 128KB:
[1024KB]
→ 분할: [512KB][512KB]
→ 분할: [256KB][256KB][512KB]
→ 분할: [128KB][128KB][256KB][512KB]
→ 할당: [128KB*][128KB][256KB][512KB]
반환 시: 버디(형제 블록)가 비었으면 병합
[128KB*] 반환 → 128KB 버디가 비어있으면 [256KB]로 병합구현
python
class BuddyAllocator:
def __init__(self, total_size):
self.total = total_size
self.free = {total_size: [0]} # size -> [시작주소 목록]
def alloc(self, size):
# 2의 거듭제곱으로 올림
block_size = 1
while block_size < size: block_size <<= 1
for s in sorted(self.free.keys()):
if s >= block_size and self.free[s]:
addr = self.free[s].pop(0)
# 필요한 크기까지 분할
while s > block_size:
s >>= 1
self.free.setdefault(s, []).append(addr + s)
return addr
return None # OOM
def free_block(self, addr, size):
block_size = 1
while block_size < size: block_size <<= 1
# 버디 주소 = addr XOR block_size
while block_size < self.total:
buddy = addr ^ block_size
if buddy in self.free.get(block_size, []):
self.free[block_size].remove(buddy)
addr = min(addr, buddy)
block_size <<= 1
else:
break
self.free.setdefault(block_size, []).append(addr)