연속 메모리 할당

운영체제가 여러 프로세스를 메모리에 배치해야 합니다. 가장 직관적인 방법은 각 프로세스에게 연속된 메모리 블록을 하나씩 할당하는 것입니다. 하지만 이 단순한 방식에는 심각한 문제가 숨어 있습니다. 시간이 지나면서 메모리에 구멍이 뚫리기 시작하고, 결국 메모리가 충분한데도 프로세스를 적재하지 못하는 상황이 벌어집니다.

메모리 분할: 고정 vs 가변

고정 분할 (Fixed Partitioning)

초기의 다중 프로그래밍 시스템에서 사용한 방식입니다. 메모리를 미리 정해진 크기의 파티션(Partition)으로 나눕니다.

예를 들어 256MB 메모리를 8개의 32MB 파티션으로 나누면, 5MB짜리 프로세스도 32MB 파티션 하나를 차지합니다. 나머지 27MB는 사용할 수 없습니다. 이 낭비되는 공간이 내부 단편화(Internal Fragmentation)입니다.

고정 분할의 변형으로 크기가 다른 파티션을 사용할 수 있습니다(8MB, 16MB, 32MB, 64MB 등). IBM의 OS/360 MFT가 이 방식이었습니다. 내부 단편화는 줄어들지만 완전히 제거되지는 않습니다.

고정 분할의 더 심각한 문제: 가장 큰 파티션보다 큰 프로세스는 실행할 수 없습니다. 파티션 수가 동시 실행 가능한 프로세스 수의 상한입니다.

가변 분할 (Variable Partitioning)

프로세스가 요청한 크기에 맞는 연속 공간을 찾아 할당합니다. 구현에 따라 정렬 단위와 관리 메타데이터 때문에 작은 여유 공간은 생길 수 있지만, 고정 분할처럼 파티션 전체를 낭비하는 내부 단편화는 크게 줄어듭니다. IBM의 OS/360 MVT가 이 방식이었습니다.

그러나 프로세스가 종료되면 중간중간에 빈 구멍(Hole)이 생깁니다.

빈 공간의 총합은 85MB이지만, 연속된 최대 공간은 55MB입니다. 60MB 프로세스를 적재하려면 연속 공간이 부족합니다. 이것이 외부 단편화(External Fragmentation)입니다.

방식	내부 단편화	외부 단편화	동시 프로세스 제한
고정 분할	있음 (심각)	없음	파티션 수로 제한
가변 분할	거의 없음	있음 (심각)	메모리 한도까지 유동적

배치 전략 (Placement Strategy)

가변 분할에서 새 프로세스를 어느 빈 공간에 배치할지 결정하는 세 가지 전략이 있습니다.

최초 적합 (First Fit)

메모리를 처음부터 순서대로 탐색하여 프로세스가 들어갈 수 있는 첫 번째 빈 공간에 배치합니다.

장점: 탐색 시간이 짧습니다. 평균적으로 목록의 절반만 탐색합니다.

단점: 메모리 앞쪽에 작은 조각들이 쌓입니다.

최적 적합 (Best Fit)

프로세스 크기에 가장 가까운(가장 작은) 빈 공간에 배치합니다.

장점: 남는 공간을 최소화합니다.

단점: 아주 작은 조각(Tiny Fragments)이 많이 생깁니다. 이 조각들은 너무 작아서 어떤 프로세스도 사용할 수 없습니다. 단순 리스트라면 모든 빈 공간을 탐색해야 하므로 시간이 더 걸립니다. 크기별 자료구조를 유지하면 탐색은 줄일 수 있지만, 삽입·삭제와 병합 관리 비용이 추가됩니다.

최악 적합 (Worst Fit)

가장 큰 빈 공간에 배치합니다. 남는 조각이 커서 다른 프로세스가 사용할 가능성이 높아 보입니다.

단점: 대형 프로세스를 수용할 공간이 빨리 사라집니다. 실제 성능이 가장 나쁩니다.

placement_simulator.py

def first_fit(holes, process_size):
    for i, hole in enumerate(holes):
        if hole >= process_size:
            holes[i] -= process_size
            return i
    return -1  # 적합한 공간 없음

def best_fit(holes, process_size):
    best_idx = -1
    best_remain = float('inf')
    for i, hole in enumerate(holes):
        if hole >= process_size:
            remain = hole - process_size
            if remain < best_remain:
                best_remain = remain
                best_idx = i
    if best_idx >= 0:
        holes[best_idx] -= process_size
    return best_idx

def worst_fit(holes, process_size):
    worst_idx = -1
    worst_remain = -1
    for i, hole in enumerate(holes):
        if hole >= process_size:
            remain = hole - process_size
            if remain > worst_remain:
                worst_remain = remain
                worst_idx = i
    if worst_idx >= 0:
        holes[worst_idx] -= process_size
    return worst_idx

# 빈 공간: [100KB, 500KB, 200KB, 300KB, 600KB]
holes = [100, 500, 200, 300, 600]
print(f"First Fit(212KB): 구멍 {first_fit(holes[:], 212)}")  # 1 (500KB)
print(f"Best Fit(212KB):  구멍 {best_fit(holes[:], 212)}")   # 3 (300KB)
print(f"Worst Fit(212KB): 구멍 {worst_fit(holes[:], 212)}")  # 4 (600KB)

시뮬레이션 연구 결과, 최초 적합과 최적 적합이 최악 적합보다 좋은 성능을 보입니다. 최초 적합은 구현이 간단하고 속도가 빠르기 때문에 가장 많이 사용됩니다.

외부 단편화의 심각성

통계적으로, 최초 적합 전략에서 할당된 N개의 블록이 있으면 약 0.5N개의 빈 블록이 생기는 경향이 있습니다. 이것을 50% 규칙(50-percent Rule)이라고 합니다. 일정한 가정 아래에서는 전체 메모리의 약 1/3이 빈 공간이지만 충분히 큰 연속 블록으로 쓰기 어려운 상태가 될 수 있다는 뜻입니다.

배치 전략은 평균 탐색 시간과 남는 조각의 크기를 함께 보는 문제입니다.

압축 (Compaction)

외부 단편화의 해결책으로 압축이 있습니다. 모든 프로세스를 메모리의 한쪽 끝으로 몰아서 빈 공간을 하나의 큰 블록으로 합칩니다.

문제점

비용이 매우 큼: 프로세스의 메모리 전체를 복사해야 합니다. GB 단위의 메모리를 이동하면 상당한 시간이 소요됩니다.
실행 시 바인딩 필수: 프로세스가 이동하면 주소가 바뀌므로, 실행 시 바인딩이 지원되어야 합니다.
압축 전략 선택: 모든 프로세스를 무조건 옮길 수도 있지만, 비용을 줄이려면 어떤 블록을 어디까지 이동할지 정책을 정해야 합니다.

결국 연속 할당의 한계를 근본적으로 해결하려면, 프로세스의 메모리가 반드시 연속되어야 한다는 제약을 풀어야 합니다. 페이징처럼 고정 크기 조각으로 나누어 흩어서 배치하면 외부 단편화를 제거할 수 있습니다. 세그먼테이션은 논리 단위로 메모리를 나누지만 세그먼트 크기가 가변적이므로, 순수 세그먼테이션에서는 외부 단편화가 남을 수 있습니다.

버디 시스템 (Buddy System)

Linux 커널이 물리 메모리를 관리할 때 사용하는 방식입니다. 순수한 고정/가변 분할이 아닌 절충안입니다.

메모리를 $2^n$ 크기의 블록으로 관리합니다. 33KB 요청이 들어오면 64KB 블록을 할당합니다. 64KB 블록이 없으면 128KB 블록을 분할(Split)하여 64KB 두 개로 나눕니다. 이 두 블록이 서로의 버디(친구)입니다.

블록이 해제되면 같은 크기의 버디가 비어있는지 확인합니다. 비어있으면 합쳐서(Coalescing) 원래 크기의 블록으로 복원합니다. 이 합치기(coalescing)가 큰 연속 블록을 다시 만들기 쉽게 해 외부 단편화를 줄여줍니다.

내부 단편화는 존재합니다(33KB 요청에 64KB 할당 → 31KB 낭비). 하지만 분할과 합치기가 매우 빠르고( $O(\log n)$ ), 외부 단편화가 크게 줄어듭니다.

Linux에서 /proc/buddyinfo로 현재 버디 시스템의 상태를 확인할 수 있습니다.

다음 절에서는 프로그램의 논리적 단위로 메모리를 나누는 세그먼테이션을 다루겠습니다.

목차