연속 메모리 할당

운영체제가 여러 프로세스를 메모리에 배치해야 합니다.

가장 직관적인 방법은 각 프로세스에게 연속된 메모리 블록을 하나씩 할당하는 것입니다.

하지만 이 단순한 방식에는 심각한 문제가 숨어 있습니다.

시간이 지나면서 메모리에 구멍이 뚫리기 시작하고, 결국 메모리가 충분한데도 프로세스를 적재하지 못하는 상황이 벌어집니다.

메모리 분할: 고정 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)이 생깁니다.

예를 들어 P1 40MB, P2 70MB, P3 50MB 사이에 20MB·55MB·10MB의 빈 공간이 남았다고 합시다. 전체 85MB가 비어 있어도 한 덩어리로 필요한 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)

코드의 세 호출은 각각 원래 목록의 복사본을 받습니다. 다음 결과는 주어진 212KB 요청 하나를 손으로 계산한 것이며 장기 성능 비교는 아닙니다.

212KB 요청이 고르는 빈 공간
전략	선택한 원래 공간	할당 후 그 공간
최초 적합	인덱스 1 · 500KB	288KB 남음
최적 적합	인덱스 3 · 300KB	88KB 남음
최악 적합	인덱스 4 · 600KB	388KB 남음

최초 적합: 선택한 원래 공간: 인덱스 1 · 500KB
할당 후 그 공간: 288KB 남음
최적 적합: 선택한 원래 공간: 인덱스 3 · 300KB
할당 후 그 공간: 88KB 남음
최악 적합: 선택한 원래 공간: 인덱스 4 · 600KB
할당 후 그 공간: 388KB 남음

원래 목록은 [100, 500, 200, 300, 600]KB입니다. 인덱스는 0부터 세며 다른 빈 공간은 각 호출에서 그대로 남습니다.

외부 단편화의 심각성

특정 할당·반납 가정에서, 최초 적합의 할당 블록 N개에 대해 빈 블록 수가 약 0.5N개가 되는 근사 관계를 설명할 수 있습니다.

이것을 50% 규칙(50-percent Rule)이라고 합니다.

이는 블록 개수의 관계입니다. 빈 블록과 할당 블록의 평균 크기를 모르면 낭비되는 바이트 비율을 1/3로 결론 내릴 수 없습니다.

압축 (Compaction)

외부 단편화의 해결책으로 압축이 있습니다.

이상적인 압축은 이동 가능한 할당 블록을 한쪽으로 모아 빈 공간을 합칩니다.

총 빈 공간과 연속 할당 가능량
메모리 상태	빈 공간과 최대 블록	60MB 요청
압축 전	20 + 55 + 10 = 85MB · 최대 55MB	한 블록에 담을 수 없음
모두 이동 가능한 압축 후	85MB 한 블록 · 최대 85MB	60MB 할당 후 25MB 남음

압축 전: 빈 공간과 최대 블록: 20 + 55 + 10 = 85MB · 최대 55MB
60MB 요청: 한 블록에 담을 수 없음
모두 이동 가능한 압축 후: 빈 공간과 최대 블록: 85MB 한 블록 · 최대 85MB
60MB 요청: 60MB 할당 후 25MB 남음

할당된 160MB와 빈 85MB의 합은 변하지 않습니다. 압축은 공간을 새로 만드는 대신 흩어진 빈 공간을 합칩니다.

문제점

비용이 매우 큼: 프로세스의 메모리 전체를 복사해야 합니다. GB 단위의 메모리를 이동하면 상당한 시간이 소요됩니다.
재배치 지원: 이동 후에도 같은 데이터를 가리키도록 주소 참조나 매핑을 갱신해야 합니다. 실행 시 바인딩이 이를 돕지만, 고정된 I/O 버퍼 등 옮길 수 없는 영역은 별도 제약입니다.
압축 전략 선택: 모든 프로세스를 무조건 옮길 수도 있지만, 비용을 줄이려면 어떤 블록을 어디까지 이동할지 정책을 정해야 합니다.

결국 연속 할당의 한계를 근본적으로 해결하려면, 프로세스의 메모리가 반드시 연속되어야 한다는 제약을 풀어야 합니다.

페이징은 한 프로세스 전체에 큰 연속 물리 공간을 요구하지 않습니다. 다만 커널이 큰 연속 물리 블록을 요청하는 경우에는 여전히 외부 단편화가 문제일 수 있습니다.

세그먼테이션은 논리 단위로 메모리를 나누지만 세그먼트 크기가 가변적이므로, 순수 세그먼테이션에서는 외부 단편화가 남을 수 있습니다.

버디 시스템 (Buddy System)

Linux 커널이 물리 메모리를 관리할 때 사용하는 방식입니다.

순수한 고정/가변 분할이 아닌 절충안입니다.

개념적으로 메모리를 2의 거듭제곱 크기로 나눕니다. Linux 페이지 할당자의 order는 바이트 지수가 아니라 $2^{order}$ 개의 연속 페이지를 뜻합니다.

33KB 요청이 들어오면 64KB 블록을 할당합니다.

64KB 블록이 없으면 128KB 블록을 분할(Split)하여 64KB 두 개로 나눕니다.

이 두 블록이 서로의 버디(친구)입니다.

블록이 해제되면 같은 분할에서 나온 짝인 버디가 비어 있는지 확인합니다. 크기가 같고 이웃한다는 이유만으로 임의의 두 블록을 합치지는 않습니다.

비어있으면 합쳐서(Coalescing) 원래 크기의 블록으로 복원합니다.

이 합치기(coalescing)가 큰 연속 블록을 다시 만들기 쉽게 해 외부 단편화를 줄여줍니다.

내부 단편화는 존재합니다(33KB 요청에 64KB 할당 → 31KB 낭비).

분할·병합은 크기 단계(order)를 따라 수행합니다. 최대 블록까지의 단계 수가 비용을 제한하지만, 사용 중인 버디가 있으면 더 큰 블록으로 합칠 수 없습니다.

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

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

이 페이지의 목차