운영체제 메모리 할당 알고리즘과 단편화 관리

메모리 공간을 나누는 기준

운영체제의 메모리 할당은 제한된 물리 메모리를 여러 프로세스에 배분하는 방식이다. 설계의 핵심은 단편화, 할당 속도, 메모리 활용률 사이의 균형에 있다.

크기 기준으로 보면 고정 크기 방식과 가변 크기 방식으로 나뉜다. 고정 크기 할당은 메모리를 동일한 크기의 단위로 잘라 관리하므로 할당과 해제가 단순하고 빠르다. 대신 할당 단위가 실제 요구량보다 클 때 내부 단편화가 생긴다. 페이징이 대표적인 형태다.

가변 크기 할당은 프로세스가 필요한 크기만큼 공간을 받는다. 메모리 활용률은 높아질 수 있지만, 빈 공간이 흩어지는 외부 단편화를 피하기 어렵다. 세그먼테이션이 여기에 속한다.

위치 기준으로는 연속 할당과 불연속 할당을 구분한다. 연속 할당에서는 프로세스가 이어진 메모리 구간을 차지하므로 Base + Offset 계산이 간단하다. 반면 외부 단편화가 심해지면 압축(Compaction)이 필요하다. 불연속 할당은 프로세스를 여러 조각으로 나누어 적재해 외부 단편화를 해결하지만, Page Table이나 Segment Table 같은 주소 변환 테이블과 그 오버헤드를 감수해야 한다.

⤢✕

미리 정한 파티션을 쓰는 고정 분할

고정 분할은 부팅 시 메모리를 정해진 개수의 파티션으로 나누고, 파티션 하나에 프로세스 하나를 수용하는 방식이다. 파티션 크기는 모두 같을 수도, 서로 다를 수도 있다. 가장 단순한 다중 프로그래밍 메모리 관리 기법에 속한다.

운영 흐름도 단순하다. 부팅 때 파티션을 만들고, 프로세스가 도착하면 크기에 맞는 파티션을 배정한다. 프로세스가 끝나면 해당 파티션을 빈 공간으로 표시하며, 다음 프로세스가 그 공간을 사용한다.

이 방식은 구현이 단순하고 할당·해제 오버헤드가 작으며 외부 단편화가 없다. 보호와 재배치도 비교적 쉽다. 그러나 프로세스가 파티션보다 작으면 내부 단편화가 발생하고, 동시에 실행할 수 있는 프로세스 수는 파티션 수에 묶인다. 파티션보다 큰 프로세스는 실행할 수 없다.

초기 일괄 처리 시스템, 제한된 환경의 임베디드 시스템, 예측 가능성이 필요한 실시간 시스템에서 적용할 수 있다.

가변 분할에서는 빈 공간을 어떻게 찾는지가 달라진다

가변 분할은 프로세스 크기에 맞추어 메모리 공간을 동적으로 할당한다. 실행 중 파티션의 크기와 개수가 바뀌며, 내부 단편화는 없지만 외부 단편화가 생긴다. 빈 공간을 고르는 전략으로 First Fit, Best Fit, Worst Fit, Next Fit을 사용한다.

First Fit은 충분히 큰 첫 번째 빈 공간을 선택한다. 평균 검색 시간은 O(n/2)이며, 메모리 앞부분에 작은 빈 공간이 집중될 수 있다. 일반적으로 빠르고 효율적인 방식이다.

Best Fit은 요구량을 만족하는 공간 가운데 가장 작은 곳을 고른다. 메모리 낭비를 줄이는 대신 전체 리스트를 검색해야 하므로 O(n)이 필요하고, 매우 작은 단편이 많이 남을 수 있다.

Worst Fit은 가장 큰 빈 공간을 할당 대상으로 삼는다. 남는 공간을 재사용 가능한 크기로 남기려는 방식이지만, 전체 리스트를 검색해야 하는 O(n) 비용이 들고 큰 빈 공간을 빠르게 소진한다. 실제로는 거의 사용되지 않는다.

Next Fit은 이전 할당 지점부터 탐색을 시작하는 First Fit의 변형이다. 메모리 사용을 전체적으로 분산하며 First Fit과 비슷한 성능을 보인다.

⤢✕

외부 단편화는 압축과 통합으로 다룬다. 압축은 모든 프로세스를 한쪽으로 이동시켜 빈 공간을 하나의 큰 블록으로 합친다. 모든 프로세스를 옮겨야 하므로 오버헤드가 매우 크고, 재배치 가능한 코드가 필요하다.

통합(Coalescing)은 인접한 빈 공간을 하나로 병합하는 방법이다. 메모리 해제 시 즉시 수행할 수 있으며 압축보다 오버헤드가 적다. 다만 외부 단편화를 부분적으로만 해결한다.

페이지 단위로 분산 적재하는 페이징

페이징은 논리 메모리를 고정 크기의 페이지(Page)로 나누고, 물리 메모리를 같은 크기의 프레임(Frame)으로 분할한다. 일반적인 페이지 크기는 4KB, 8KB, 16KB이며, 페이지 테이블이 논리 주소와 물리 주소를 연결한다.

논리 주소는 페이지 테이블의 인덱스인 Page Number (p)와 페이지 내부 상대 주소인 Page Offset (d)로 구성된다. 페이지 테이블에서 Page Table[p] = Frame Number (f)를 찾으면 물리 주소는 (f, d), 즉 f × 페이지크기 + d로 계산된다.

페이지 크기가 4KB = 4096 bytes인 예에서는 논리 주소 32비트가 20비트의 페이지 번호와 12비트의 오프셋으로 나뉜다. 페이지 수는 2^20 = 1M이고, 각 페이지 크기는 2^12 = 4KB다.

⤢✕

페이징은 외부 단편화를 완전히 제거하고, 불연속 메모리 할당으로 유연성을 얻는다. 페이지 단위의 보호와 공유도 가능하다. 대신 평균 0.5페이지의 내부 단편화, 페이지 테이블의 메모리 오버헤드, 주소 변환 시간이 발생한다. TLB가 없으면 메모리 접근은 2배로 증가한다.

페이지 테이블 자체를 줄이기 위한 방식도 있다. 계층적 페이지 테이블은 테이블을 여러 단계로 나누며, 2단계나 3단계 구조에서 사용하지 않는 부분은 할당하지 않아 메모리를 절약한다. 해시 페이지 테이블은 해시 함수를 사용해 큰 주소 공간에 대응하지만 충돌 처리가 필요하다. 역 페이지 테이블은 프레임 단위로 테이블을 구성하므로 크기가 물리 메모리 크기에 비례하며, 검색 시간이 길어질 수 있어 해시 테이블과 함께 사용한다.

프로그램 구조를 반영하는 세그먼테이션

세그먼테이션은 프로그램을 논리적 단위인 세그먼트로 나누는 방식이다. 각 세그먼트는 가변 크기를 가지며 코드, 데이터, 스택, 힙이 대표적인 단위다. 프로그래머가 보는 프로그램 구조를 메모리 관리에 반영한다.

코드 세그먼트는 실행 가능한 명령어를 담고 읽기 전용으로 공유할 수 있다. 데이터 세그먼트에는 전역 변수와 정적 변수가 들어가며, 초기화된 데이터와 미초기화 데이터(BSS)가 분리된다. 스택 세그먼트는 지역 변수, 함수 매개변수, 반환 주소를 관리하며 위에서 아래로 증가하는 LIFO 구조다. 힙 세그먼트는 malloc, new 등의 동적 메모리 할당에 사용되고 아래에서 위로 크기가 변하며 명시적 관리가 필요하다.

논리 주소는 Segment Number (s)와 Segment Offset (d)로 구성한다. 세그먼트 테이블 엔트리는 시작 물리 주소인 Base와 세그먼트 길이이자 보호 기준인 Limit을 가진다. 주소를 변환할 때는 Segment Table[s]에서 Base와 Limit을 얻고, Offset(d) < Limit인지 검사한 뒤 Base + d로 물리 주소를 계산한다.

세그먼트별 보호와 공유가 쉽고, 논리적 단위가 명확하며 동적 크기 조정도 가능하다. 하지만 가변 크기 할당이므로 외부 단편화가 발생한다. 세그먼트 테이블 관리와 압축 작업이 필요할 수 있고, 할당 알고리즘도 복잡해진다.

세그먼트와 페이지를 함께 쓰는 구조

페이지드 세그먼테이션은 세그먼테이션과 페이징을 결합한다. 논리적으로는 세그먼트로 나누되, 각 세그먼트를 다시 페이지로 분할한다. Intel x86 아키텍처에서 사용된다.

주소 변환은 세그먼트 번호로 세그먼트 테이블에 접근하고, 세그먼트 안의 페이지 번호로 페이지 테이블을 찾은 뒤, 프레임 번호와 오프셋으로 물리 주소를 계산하는 순서다.

• Segment Number → Segment Table
• Page Number → Page Table
• Page Offset → Physical Address

페이징으로 외부 단편화를 제거하면서 세그먼테이션의 논리적 분할을 유지할 수 있고, 보호와 공유도 유연하다. 큰 세그먼트도 지원한다. 반면 주소 변환은 3단계가 되어 복잡하고 느리며, 두 종류의 테이블로 메모리 오버헤드가 증가한다. 페이지 단위의 내부 단편화도 남는다.

2의 거듭제곱 블록을 병합하는 버디 시스템

버디 시스템은 메모리를 2의 거듭제곱 크기 블록으로 나눈다. 요청 크기보다 큰 최소 블록을 할당하고, 해제한 블록은 인접한 버디 블록과 병합한다. 빠른 할당·해제와 효율적인 병합을 목표로 한다.

할당할 때 요청 크기 S에 대해 2^k 크기의 블록이 필요하며, 조건은 2^(k-1) < S ≤ 2^k다. 해당 크기의 빈 블록이 있으면 할당하고, 없으면 더 큰 블록을 절반씩 나눈다. 적절한 크기가 될 때까지 이 과정을 반복한다.

해제 후에는 버디 주소를 계산한다.

• Buddy Address = Block Address XOR Block Size

버디가 비어 있고 같은 크기인지 확인한 뒤 조건을 만족하면 병합해 더 큰 블록을 만든다. 이 과정을 재귀적으로 반복해 가능한 만큼 병합한다.

⤢✕

버디 시스템의 할당과 해제는 O(log n)이며, 버디 계산이 단순해 병합도 효율적이다. 외부 단편화는 줄어들고 구현 복잡도도 비교적 낮다. 다만 2의 거듭제곱 제약 때문에 내부 단편화가 생기며, 메모리 낭비는 최대 50%까지 가능하다. 페이징보다 복잡하다.

Linux Kernel의 Page Frame 할당, 일부 동적 메모리 할당기, 임베디드 시스템에서 활용된다.

요구사항에 따른 선택

기법	내부 단편화	외부 단편화	할당 속도	메모리 효율	구현 복잡도
고정 분할	높음	없음	매우 빠름	낮음	낮음
가변 분할	없음	높음	중간	높음	중간
페이징	낮음	없음	빠름	높음	중간
세그먼트	없음	중간	중간	높음	높음
버디 시스템	중간	낮음	빠름	중간	중간

고정 분할은 임베디드 시스템이나 예측 가능성이 필요한 실시간 시스템처럼 단순한 환경에 맞는다. 가변 분할은 프로세스 수가 적고 메모리 활용률이 중요한 환경에서 선택할 수 있다.

페이징은 범용 운영체제와 가상 메모리 시스템, 현대적인 대부분의 시스템에 적합하다. 세그먼테이션은 보호와 공유가 중요하고 프로그램의 논리적 분할이 뚜렷할 때 쓰며, 페이징과 결합할 수 있다. 버디 시스템은 커널 메모리 할당이나 중간 규모 블록 관리처럼 빠른 할당과 해제가 필요한 상황에 맞는다.

현대 운영체제는 대부분 페이징을 기본으로 사용한다. 필요에 따라 세그먼테이션을 결합하거나, 커널 메모리 관리에 버디 시스템을 활용해 서로 다른 기법의 특성을 조합한다.