연속 메모리 할당
운영체제가 여러 프로세스를 메모리에 배치해야 합니다. 가장 직관적인 방법은 각 프로세스에게 연속된 메모리 블록을 하나씩 할당하는 것입니다. 하지만 이 단순한 방식에는 심각한 문제가 숨어 있습니다. 시간이 지나면서 메모리에 구멍이 뚫리기 시작하고, 결국 메모리가 충분한데도 프로세스를 적재하지 못하는 상황이 벌어집니다.
메모리 분할: 고정 vs 가변
고정 분할 (Fixed Partitioning)
초기의 다중 프로그래밍 시스템에서 사용한 방식입니다. 메모리를 미리 정해진 크기의 파티션(Partition)으로 나눕니다.
예를 들어 256MB 메모리를 8개의 32MB 파티션으로 나누면, 5MB짜리 프로세스도 32MB 파티션 하나를 차지합니다. 나머지 27MB는 사용할 수 없습니다. 이 낭비되는 공간이 내부 단편화(Internal Fragmentation)입니다.
고정 분할의 변형으로 크기가 다른 파티션을 사용할 수 있습니다(8MB, 16MB, 32MB, 64MB 등). IBM의 OS/360 MFT가 이 방식이었습니다. 내부 단편화는 줄어들지만 완전히 제거되지는 않습니다.
고정 분할의 더 심각한 문제: 가장 큰 파티션보다 큰 프로세스는 실행할 수 없습니다. 파티션 수가 동시 실행 가능한 프로세스 수의 상한입니다.
가변 분할 (Variable Partitioning)
프로세스 크기에 정확히 맞춰 메모리를 할당합니다. 5MB 프로세스에게 5MB를 할당합니다. 내부 단편화가 없습니다. IBM의 OS/360 MVT가 이 방식이었습니다.
그러나 프로세스가 종료되면 중간중간에 빈 구멍(Hole)이 생깁니다.
시간 0: | P1(10MB) | P2(20MB) | P3(15MB) | 빈(55MB) |
시간 1: | P1(10MB) | 빈(20MB) | P3(15MB) | 빈(55MB) | ← P2 종료
시간 2: | 빈(10MB) | 빈(20MB) | P3(15MB) | 빈(55MB) | ← P1 종료빈 공간의 총합은 85MB이지만, 연속된 최대 공간은 55MB입니다. 60MB 프로세스를 적재하려면 연속 공간이 부족합니다. 이것이 외부 단편화(External Fragmentation)입니다.
| 방식 | 내부 단편화 | 외부 단편화 | 동시 프로세스 제한 |
|---|---|---|---|
| 고정 분할 | 있음 (심각) | 없음 | 파티션 수로 제한 |
| 가변 분할 | 없음 | 있음 (심각) | 메모리 한도까지 유동적 |
배치 전략 (Placement Strategy)
가변 분할에서 새 프로세스를 어느 빈 공간에 배치할지 결정하는 세 가지 전략이 있습니다.
최초 적합 (First Fit)
메모리를 처음부터 순서대로 탐색하여 프로세스가 들어갈 수 있는 첫 번째 빈 공간에 배치합니다.
장점: 탐색 시간이 짧습니다. 평균적으로 목록의 절반만 탐색합니다.
단점: 메모리 앞쪽에 작은 조각들이 쌓입니다.
최적 적합 (Best Fit)
프로세스 크기에 가장 가까운(가장 작은) 빈 공간에 배치합니다.
장점: 남는 공간을 최소화합니다.
단점: 아주 작은 조각(Tiny Fragments)이 많이 생깁니다. 이 조각들은 너무 작아서 어떤 프로세스도 사용할 수 없습니다. 모든 빈 공간을 탐색해야 하므로 시간이 더 걸립니다(정렬된 리스트를 유지하면 ).
최악 적합 (Worst Fit)
가장 큰 빈 공간에 배치합니다. 남는 조각이 커서 다른 프로세스가 사용할 가능성이 높아 보입니다.
단점: 대형 프로세스를 수용할 공간이 빨리 사라집니다. 실제 성능이 가장 나쁩니다.
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)
외부 단편화의 해결책으로 압축이 있습니다. 모든 프로세스를 메모리의 한쪽 끝으로 몰아서 빈 공간을 하나의 큰 블록으로 합칩니다.
압축 전: | P1 | 빈 | P3 | 빈 | P5 | 빈 |
압축 후: | P1 | P3 | P5 | 큰 빈 공간 |문제점
- 비용이 매우 큼: 프로세스의 메모리 전체를 복사해야 합니다. GB 단위의 메모리를 이동하면 상당한 시간이 소요됩니다.
- 실행 시 바인딩 필수: 프로세스가 이동하면 주소가 바뀌므로, 실행 시 바인딩이 지원되어야 합니다.
- 최적 압축 전략: 어떤 프로세스를 어디로 옮길지 결정하는 것도 NP-hard 문제입니다.
결국 연속 할당의 한계를 근본적으로 해결하려면, 프로세스의 메모리가 반드시 연속되어야 한다는 제약을 풀어야 합니다. 프로세스의 메모리를 작은 조각으로 나누어 흩어서 배치하면 외부 단편화가 사라집니다. 이 아이디어가 페이징과 세그먼테이션입니다.
버디 시스템 (Buddy System)
Linux 커널이 물리 메모리를 관리할 때 사용하는 방식입니다. 순수한 고정/가변 분할이 아닌 절충안입니다.
메모리를 크기의 블록으로 관리합니다. 33KB 요청이 들어오면 64KB 블록을 할당합니다. 64KB 블록이 없으면 128KB 블록을 분할(Split)하여 64KB 두 개로 나눕니다. 이 두 블록이 서로의 버디(친구)입니다.
블록이 해제되면 버디가 비어있는지 확인합니다. 비어있으면 합쳐서(Coalescing) 원래 크기의 블록으로 복원합니다. 이 합치기(coalescing)가 외부 단편화를 줄여줍니다.
내부 단편화는 존재합니다(33KB 요청에 64KB 할당 → 31KB 낭비). 하지만 분할과 합치기가 매우 빠르고(), 외부 단편화가 크게 줄어듭니다.
Linux에서 /proc/buddyinfo로 현재 버디 시스템의 상태를 확인할 수 있습니다.
다음 절에서는 프로그램의 논리적 단위로 메모리를 나누는 세그먼테이션을 다루겠습니다.