가변 분할로 이해하는 동적 메모리 할당과 외부 단편화

프로세스 크기에 맞춰 나누는 메모리

가변 분할(Variable Partitioning), 또는 동적 분할(Dynamic Partitioning)은 프로그램이 실행되는 시점에 필요한 크기만큼 메모리를 나누어 할당하는 방식이다. 각 프로세스는 서로 다른 크기의 메모리 블록을 받으며, 실행 중 메모리 요구량 변화에도 대응할 수 있다.

미리 정한 크기의 파티션을 사용하는 고정 분할과 달리, 프로세스 크기에 맞춰 할당하므로 내부 단편화가 없다. 반면 가용 공간이 여러 위치에 흩어지는 외부 단편화가 생길 수 있고, 이를 다루기 위한 관리 알고리즘도 필요하다.

고정 분할은 부팅 시점에 메모리를 나누고 내부 단편화가 발생한다. 가변 분할은 프로세스 요청 시 할당하며 내부 단편화를 없애는 대신, 관리 복잡도와 외부 단편화 문제를 감수한다.

요청부터 실행까지 이어지는 할당 과정

프로세스가 메모리를 요청하면 운영체제는 가용 메모리에서 적절한 블록을 찾는다. 선택한 블록을 할당한 뒤 남은 공간을 관리하고, 프로세스 실행으로 이어진다.

⤢✕

가용 블록을 고르는 정책은 다음처럼 나뉜다.

First Fit: 충분한 크기를 가진 첫 번째 블록을 선택하며 검색 속도가 빠르다.
Best Fit: 조건을 만족하는 블록 가운데 가장 작은 것을 선택해 공간 효율성을 높인다.
Worst Fit: 가장 큰 블록을 선택하여 남은 공간의 활용 가능성을 높인다.
Next Fit: 마지막 할당 위치부터 검색을 시작하는 First Fit의 개선 방식이다.
Quick Fit: 자주 쓰는 크기별 리스트를 관리해 빠른 할당을 지원한다.

메모리를 해제할 때는 주변 가용 공간을 확인한다. 뒤쪽 가용 블록과 결합하는 전방 병합(Forward Coalescing), 앞쪽 블록과 결합하는 후방 병합(Backward Coalescing), 양쪽을 모두 통합하는 병합이 가능하다. 병합 결과는 가용 블록 리스트에 반영한다.

공간 효율과 관리 비용의 맞교환

프로세스 크기에 정확히 맞춰 할당하므로 불필요한 공간 낭비를 줄일 수 있다. 다양한 크기의 프로세스를 수용할 수 있고, 고정 분할보다 더 많은 프로세스를 실행할 여지도 생긴다. 실행 중 요구량 변화에 대응할 수 있다는 점도 가변 분할의 특성이다.

대신 작은 가용 공간이 메모리 전체에 분산되는 외부 단편화가 발생한다. 적합한 블록을 찾고 할당·해제를 관리하는 알고리즘이 복잡해지며, 블록 검색 시간도 늘어난다. 단편화가 누적되면 할당 실패가 늘어나 성능 저하로 이어질 수 있다.

흩어진 가용 공간을 다시 모으는 방법

메모리 압축(Compaction)은 단편화된 공간을 연속된 큰 블록으로 만드는 방법이다. 프로세스를 이동시키고 가용 공간을 병합한 뒤 새 프로세스를 할당할 수 있는 상태로 만든다.

⤢✕

압축은 모든 프로세스를 한쪽 끝으로 옮기는 이동 압축, 일부 프로세스를 디스크로 스왑한 뒤 재배치하는 교환 압축, 특정 영역만 대상으로 하는 부분 압축, 시스템 유휴 시간에 점진적으로 수행하는 증분 압축으로 나뉜다. 압축 중에는 프로세스 중단과 주소 갱신이 필요하다.

외부 단편화에 대응하는 다른 방식도 있다.

페이징(Paging): 고정 크기 페이지 단위로 관리해 외부 단편화를 제거한다.
세그멘테이이션: 논리적 단위 분할과 동적 할당을 결합한다.
버디 시스템(Buddy System): 2의 거듭제곱 단위로 분할해 병합 효율을 높인다.
슬랩 할당(Slab Allocation): 동일 객체 타입별 메모리 풀을 관리한다.
가상 메모리: 물리 메모리와 논리 메모리를 분리해 단편화 영향을 최소화한다.

운영체제와 런타임에서의 활용

IBM OS/360의 MVT(Multiprogramming with Variable Tasks)는 가변 분할을 사용했다. 다양한 크기의 작업을 동시에 실행하기 위해 동적 메모리 관리를 적용했고, First Fit 기반의 빠른 할당을 구현했다. 외부 단편화에 따른 메모리 낭비는 한계였으며, 이후 페이징과 세그멘테이션 기법으로 발전했다.

현대 시스템에서도 가변 크기 할당은 여러 계층에서 쓰인다. C/C++의 malloc/free 기반 힙 메모리 관리, Java와 Python 등의 가비지 컬렉터, 게임과 실시간 시스템의 메모리 풀이 그 예다. 페이징과 결합하는 하이브리드 접근도 사용되며, 리눅스 슬랩 할당자는 가변 크기 객체를 관리한다.