메모리연속할당

title: 2025-09-10 author: 강병호 date: 2025-09-10 category: TIL/강병호/2025/09 layout: post — 연속할당 : 하나의 프로세스가 하나의 연속된 물리 메모리 공간을 받는 고전적 방식

빈 공간(hole)으로 이루어진 free list 중 어디에 새 요청을 넣을지 결정하는 규칙 → first-fit, best-fit, worst-fit

free list란? 운영체제나 메모리 할당기가 현재 사용되지 않고 비어 있는 메모리 블록(holes)들을 연결리스트 형태로 관리하는 자료구조 ex) malloc 이나 프로세스가 메모리를 요청하면 free list에서 적절한 블록을 찾아내어 할당 반대로 메모리 반환 시에는 그 블록은 free list로 들어가고, 인접한 빈 블록과 병합될 수 있음

free list에 들어있는 정보 시작 주소 (base address) 크기 (size)

다음 블록 포인터 (next)

+이전 블록 포인터 (prev), 경계 태그(boundary tag) 등

Free List 관리 방식 정리

1. 주소순 (Address-ordered Free List)

정렬 기준: 물리적 메모리 주소 오름차순으로 빈 블록을 관리

동작: 보통 First-fit과 함께 사용 → 낮은 주소부터 순차 탐색 후 할당

장점

• 인접 블록 병합(coalescing)이 매우 쉬움 → 외부 단편화 줄이는 데 유리
• 구현이 단순

단점

• 탐색 효율이 떨어짐 → 큰 요청 시에도 앞에서부터 하나하나 확인해야 함
• 파편화가 앞쪽에 몰리는 경향

1. 크기순 (Size-ordered Free List)

정렬 기준: 블록 크기 순으로 관리. (작은 것부터 or 큰 것부터)

동작: 보통 Best-fit / Worst-fit과 함께 사용 → 조건 맞는 블록 탐색이 쉬움

장점

• Best-fit → 작은 조각을 딱 맞게 사용 가능
• Worst-fit → 큰 블록에서 잘라 쓰는 전략에 적합

단점

• 블록이 주소순으로 정렬되지 않으므로, 병합(coalescing) 과정이 더 복잡해짐
• 전체 관리 오버헤드가 커짐

1. 세그리게이티드 리스트 (Segregated Free List)

정렬 기준: 크기 구간(bin)별로 별도 리스트 유지

• 예: 8바이트 bin, 16바이트 bin, 32바이트 bin, 64바이트 bin …

동작: 요청 시 해당 크기 bin에서 바로 탐색. 없으면 더 큰 bin에서 분할(split)

장점

• 탐색 속도가 매우 빠름 (O(1) 접근 가능)
• 비슷한 크기 요청들이 같은 bin을 재활용 → 단편화 완화
• 현대 동적 메모리 할당기(glibc malloc, jemalloc, tcmalloc 등)에서 사실상 표준

단점

• bin 관리 비용이 발생
• bin 크기 설계가 비효율적이면 낭비 가능