운영체제 메모리 할당과 버디 시스템·슬랩 할당의 구조

메모리 요청의 크기와 수명에 맞춰 고르는 할당 방식

운영체제는 프로세스에 물리 메모리를 내주고 다시 회수하는 일을 반복한다. 이때 할당 방식은 단편화, 처리 속도, 메모리 활용률을 좌우한다. 큰 틀에서는 연속 할당과 불연속 할당으로 나뉘며, 버디 시스템과 슬랩 할당은 각각 페이지 프레임과 커널 객체 관리 문제를 다루기 위해 쓰인다.

메모리 관리에서 함께 고려할 대상은 빠른 할당·해제, 낮은 오버헤드, 구현의 단순성만이 아니다. 내부·외부 단편화를 줄이고, 다양한 크기의 요청과 동적 크기 조정, 멀티프로세스 환경도 감당해야 한다.

단편화는 메모리가 작은 조각으로 나뉘어 필요한 요청에 쓸 수 없는 상태다. 내부 단편화는 할당된 블록 안에서 남는 공간을 뜻한다. 예를 들어 17KB 요청에 20KB를 할당하면 3KB가 낭비된다. 외부 단편화는 블록 사이의 작은 빈 공간들 때문에 전체 여유 공간은 충분해도 연속된 영역을 확보하지 못하는 경우다.

⤢✕

연속된 공간을 직접 배정하는 방식

연속 할당은 프로세스마다 이어진 메모리 영역을 부여한다. 구조는 단순하지만, 빈 공간의 모양과 요청 크기가 맞지 않으면 단편화가 문제가 된다.

고정 분할은 메모리를 미리 정한 파티션으로 나누는 방식이다. 모든 파티션을 같은 크기로 만들 수도 있고, 파티션마다 다른 크기를 둘 수도 있다. 할당과 해제는 빠르고 구현도 단순하지만, 동시에 실행할 수 있는 프로세스 수는 파티션 수에 묶인다. 내부 단편화가 커지기 쉽고, 파티션보다 큰 프로세스는 실행할 수 없다.

가변 분할은 프로세스 크기에 맞춰 영역을 동적으로 잡는다. 빈 블록을 찾는 정책에 따라 특성이 달라진다.

First Fit은 충분한 첫 번째 빈 공간을 사용한다. 검색은 빠르지만 앞부분에 단편화가 몰릴 수 있다.
Best Fit은 들어갈 수 있는 블록 가운데 가장 작은 것을 고른다. 남는 공간은 작아지지만 작은 조각이 많이 생길 수 있다.
Worst Fit은 가장 큰 빈 블록에서 할당해 큰 조각을 보존한다.
Next Fit은 이전 할당 지점부터 탐색한다. 메모리를 비교적 고르게 쓰지만 First Fit보다 느리다.

⤢✕

외부 단편화를 해소하려면 압축을 사용할 수 있다. 프로세스를 한쪽으로 옮겨 빈 영역을 하나의 큰 블록으로 합치고, 프로세스 주소를 다시 설정하는 방식이다. 다만 재배치 비용이 크고 프로세스 중단과 동적 재배치 지원이 필요하다.

프로세스를 조각내어 배치하는 방법

불연속 할당은 프로세스를 여러 부분으로 나누어 물리 메모리 곳곳에 둔다. 연속된 큰 빈 공간을 찾는 제약을 줄이는 대신, 주소 변환과 관리 구조가 필요해진다.

페이징이 만드는 고정 단위

페이징은 논리 메모리와 물리 메모리를 고정 크기 블록으로 나눈다. 페이지는 논리 메모리 단위이며 보통 4KB이고, 프레임은 페이지와 같은 크기의 물리 메모리 단위다. 페이지 테이블은 페이지와 프레임의 대응 관계를 유지한다.

논리 주소는 페이지 번호와 오프셋으로, 물리 주소는 프레임 번호와 오프셋으로 구성된다. 이 변환에는 MMU 하드웨어 지원이 필요하다. 외부 단편화가 없고 메모리 보호와 공유 메모리를 지원하기 쉽지만, 최대 페이지 크기-1의 내부 단편화, 페이지 테이블 오버헤드, 주소 변환 시간이 남는다.

세그먼트가 보존하는 논리 구조

세그멘테이션은 코드, 데이터, 스택, 힙처럼 논리적인 단위로 메모리를 나눈다. 세그먼트 테이블에는 시작 주소를 나타내는 Base, 세그먼트 크기인 Limit, 접근 권한을 위한 Protection bits가 담긴다.

프로그램의 논리 구조를 반영하고 공유·보호 및 동적 크기 조정에 유리하다. 반면 가변 크기 세그먼트는 외부 단편화를 만들며, 할당과 해제 관리가 복잡해진다.

페이지드 세그멘테이션은 세그먼트를 다시 페이지로 나누는 결합 방식이다. 세그먼트 테이블과 페이지 테이블을 함께 사용해 두 단계 주소 변환을 수행한다. 외부 단편화를 줄이면서 세그먼트의 논리적 구조와 메모리 보호를 유지한다.

분할과 병합으로 페이지를 관리하는 버디 시스템

버디 시스템은 메모리를 2의 거듭제곱 크기 블록으로 다루는 동적 할당 기법이다. 전체 메모리를 2^n 크기 블록으로 시작하며, 예를 들면 256KB 메모리에서 요청에 맞는 블록을 찾는다.

요청 크기 이상인 최소 2^k 블록이 없으면 더 큰 블록을 절반으로 나눈다. 이렇게 생긴 두 블록은 서로 버디 관계가 되고, 적합한 크기에 이를 때까지 분할이 이어진다. 해제할 때는 버디도 비어 있는지 확인해 병합하고, 더 이상 합칠 수 없을 때까지 이를 반복한다.

⤢✕

버디 주소는 비트 연산으로 계산할 수 있다.

Buddy_Address = Block_Address XOR Block_Size
주소 64KB, 크기 64KB인 블록의 Buddy = 64 XOR 64 = 0KB이며 병합할 수 있다.

할당과 해제는 O(log n)으로 빠르고, 자동 병합은 외부 단편화를 완화한다. 구현이 간단하고 캐시 친화적이라는 점도 장점이다. 다만 2의 거듭제곱 크기만 지원하므로 내부 단편화가 최대 50%까지 생길 수 있다. 17KB 요청에는 32KB가 할당된다.

Linux 커널에서는 버디 시스템이 페이지 프레임 할당에 사용된다. 2^0 ~ 2^10 페이지를 다루는 11개 free list와 MAX_ORDER = 11을 사용하며, 최대 연속 할당은 4MB (2^10 × 4KB)다. Per-CPU 페이지 캐시, DMA·Normal·HighMem Zone 기반 관리, Anti-fragmentation 기법도 적용한다.

고정 크기 커널 객체를 캐시하는 슬랩 할당

슬랩 할당은 커널 객체를 위한 캐시 기반 할당 기법이다. 커널 객체는 크기가 고정적인 경우가 많고 생성과 소멸이 빈번하다. 페이지 단위인 버디 시스템만으로 이를 처리하면 단위가 너무 크며, 객체 초기화 비용도 반복된다.

슬랩 구조는 특정 객체 타입을 관리하는 캐시, 하나 이상의 연속된 페이지로 구성된 슬랩, 실제 할당 단위인 객체의 계층으로 이루어진다.

⤢✕

슬랩은 객체 사용 상태에 따라 관리된다. Full Slab은 모든 객체가 사용 중이라 할당할 수 없으며 Full list에 연결된다. Partial Slab은 일부 객체가 사용 중이고 추가 할당이 가능해 Partial list에 연결된다. Empty Slab은 모든 객체가 비어 재사용을 기다리며, 일정 시간 후 해제된다.

할당 시에는 캐시의 partial slab을 먼저 찾고 그 안의 free object를 반환한다. partial slab이 없으면 empty slab에서 할당하며, empty slab도 없으면 버디 시스템을 통해 새 슬랩을 만든다.

객체 색칠은 캐시 성능을 위한 최적화다. 각 슬랩의 객체 배치를 조금씩 옮기고 오프셋을 다르게 두어, 서로 다른 슬랩의 같은 인덱스 객체가 다른 캐시 라인을 사용하게 한다. 캐시 라인 충돌을 줄이고 하드웨어 캐시 활용률을 높이려는 목적이다.

슬랩 할당은 O(1)으로 빠른 할당·해제를 제공하고, 객체 재사용으로 초기화 비용을 줄인다. 객체 크기에 맞춰 내부 단편화를 최소화하며, 타입별 통계, 메모리 누수 탐지, 디버깅도 지원한다.

Linux의 SLUB은 SLAB을 개선한 버전이다. 구조와 Partial list를 단순화하고 큐와 일부 메타데이터를 제거했다. Per-CPU 캐시를 통합하며 NUMA 지원도 개선했다.

할당 기법별로 달라지는 제약

기법	단편화	할당 속도	메모리 효율	적용 대상
연속 할당	외부 단편화	빠름	낮음	초기 운영체제
페이징	내부 단편화	중간	높음	일반 메모리 관리
버디 시스템	내부 단편화	빠름	중간	페이지 프레임 할당
슬랩 할당	최소	매우 빠름	높음	커널 객체 관리

Linux와 사용자 공간에서의 계층적 조합

Linux의 메모리 관리는 버디 시스템으로 페이지 프레임을 할당하고, 슬랩 할당자(SLUB)로 작은 객체를 다룬다. vmalloc은 가상 메모리 영역을 할당하며, kmalloc은 일반 커널 메모리 할당에 쓰인다.

작은 객체(<8KB)는 SLUB 캐시가 처리한다. 8KB-128KB 중간 객체는 kmalloc을 거쳐 버디 시스템으로, 큰 객체(>128KB)는 vmalloc을 거쳐 불연속 할당으로 이어진다.

사용자 공간의 malloc 구현도 크기에 따라 경로를 나눈다. 작은 할당은 미리 확보한 풀에서 반환하고, 큰 할당은 mmap 시스템 콜을 사용하며, 중간 크기는 brk 시스템 콜로 힙을 확장한다. 애플리케이션 수준 메모리 풀은 할당·해제 오버헤드를 낮추고 단편화를 제어하는 데 쓰인다.

임베디드 시스템은 제한된 메모리와 실시간 요구사항, 단편화 민감성 때문에 다른 선택을 요구한다. 고정 크기 풀과 정적 할당을 선호하고 컴팩션은 최소화한다.