운영체제 메모리 관리 정책과 페이지 교체 알고리즘

메모리가 모자랄 때 운영체제가 결정하는 것

여러 프로세스가 동시에 실행되는 환경에서는 제한된 메모리를 배분하고, 사용이 끝난 공간을 회수하며, 부족한 경우에는 남아 있는 페이지 중 하나를 내보내야 한다. 이 선택은 시스템의 처리량과 응답 시간에 직접 영향을 준다.

메모리 관리 정책은 보통 할당, 배치, 인입, 교체라는 네 질문으로 나눠 볼 수 있다. 각각은 프로세스에 줄 공간의 양, 그 공간의 위치, 메모리로 가져올 시점, 내보낼 대상을 다룬다.

⤢✕

프로세스마다 줄 메모리의 양

할당 정책은 각 프로세스에 얼마만큼의 메모리를 제공할지 정한다. 고정 할당은 프로세스를 만들 때 정해진 양을 배정한다. 가변 할당은 실행 중 필요에 따라 할당량을 조정한다.

이때 Working Set 크기와 프로세스 우선순위를 고려하고, 특정 프로세스에 치우치지 않도록 시스템 전체의 메모리 사용률도 함께 봐야 한다.

빈 공간 중 어느 곳을 선택할지

배치 정책은 프로세스를 메모리의 어디에 둘지 결정한다. First Fit은 처음 발견한 충분한 공간을 사용하므로 빠르다. Best Fit은 적합한 공간 가운데 가장 작은 곳을 고르고, Worst Fit은 가장 큰 공간을 선택한다. Next Fit은 직전 할당 위치부터 탐색을 다시 시작한다.

이 선택에는 외부 단편화와 탐색 시간의 교환 관계가 있다. 공간을 촘촘히 쓰려는 정책이 항상 검색 비용까지 낮추는 것은 아니다.

필요한 페이지를 언제 가져올지

인입 정책은 프로세스 또는 페이지를 메모리에 올리는 시점을 다룬다. 요구 반입 기법(Demand Paging)은 Page Fault가 발생한 시점에 페이지를 로드한다. 초기 시작 시간이 빠르고 필요한 페이지만 가져와 메모리를 아낄 수 있지만, Page Fault 오버헤드는 남는다.

예측 반입 기법(Prepaging)은 Locality 원리를 바탕으로 이후에 필요할 페이지를 미리 적재한다. Page Fault를 줄일 수 있는 반면, 쓰이지 않을 페이지까지 로드할 가능성이 있다.

부족한 메모리에서 내보낼 페이지

교체 정책은 여유 메모리가 없을 때 어떤 페이지를 교체할지 정한다. FIFO, LRU, LFU, NUR, OPT, SCR 같은 알고리즘은 모두 Page Fault Rate를 낮추는 데 목적이 있지만, 실제 사용 패턴을 반영하는 정도와 구현 복잡도가 다르다.

분할과 할당 방식이 만드는 단편화

고정 분할은 메모리를 고정 크기의 파티션으로 나누고, 각 파티션에는 하나의 프로세스만 적재한다. 구현이 간단하고 오버헤드가 적지만, 프로세스 크기가 파티션보다 작을 때 내부 단편화가 생긴다. 동시에 실행할 수 있는 프로세스 수도 제한되며, 초기 일괄 처리 시스템에서 사용됐다.

가변 분할은 프로세스 크기에 맞춰 파티션을 동적으로 만든다. 필요한 만큼만 할당하므로 내부 단편화는 없지만 외부 단편화가 발생한다. 인접한 빈 공간을 병합(Coalescing)해야 하고, 주기적인 압축(Compaction) 작업도 필요하다. 이는 현대적인 메모리 관리의 기초가 된다.

연속 할당에서는 프로세스가 이어진 메모리 공간에 적재된다. 주소 계산이 단순하고 빠르며 Base Register + Limit Register로 보호할 수 있다. 반면 외부 단편화가 심각해질 수 있고 압축 작업의 오버헤드도 크다.

불연속 할당은 프로세스를 여러 조각으로 나눠 적재한다. Paging은 고정 크기의 페이지와 프레임을 사용하고, Segmentation은 논리적 단위에 따라 가변 크기를 사용한다. Paged Segmentation은 두 방식을 결합한다. 이 방식은 외부 단편화 문제를 해결하지만 주소 변환 오버헤드를 수반한다.

⤢✕

2의 거듭제곱 블록으로 관리하는 버디 시스템

버디 시스템(Buddy System)은 고정 분할과 가변 분할 사이의 절충안이다. 메모리를 2의 거듭제곱 크기로 나누고, 요청 크기보다 큰 최소 블록을 할당한다. 해제된 블록은 같은 크기의 인접한 버디 블록과만 병합할 수 있다.

초기 메모리는 하나의 큰 블록으로 시작한다. 요청이 들어오면 적절한 크기가 될 때까지 블록을 절반씩 나눈다. 블록을 해제할 때는 인접 버디와 병합하고, 이 과정을 재귀적으로 반복해 더 큰 블록을 만든다.

빠른 할당과 해제가 가능하고 버디 여부만 확인하면 효율적으로 병합할 수 있어 외부 단편화를 줄인다. 다만 2의 거듭제곱 제약 때문에 내부 단편화가 생긴다. 예를 들어 65KB를 요청하면 128KB가 할당될 수 있다.

요청 크기 S에 대한 할당 크기는 다음과 같다.

할당 크기 = 2^⌈log₂(S)⌉

⤢✕

빈 공간 탐색 방식의 차이

First Fit

First Fit은 메모리의 앞부분부터 탐색해 처음으로 조건을 만족하는 빈 공간에 할당한다. 평균적으로 절반만 검색하므로 빠르고 구현도 가장 간단하다. 대신 메모리 앞쪽에 작은 단편이 쌓일 수 있다. 일반적으로 가장 빠르고 효율적인 방식으로 본다.

시간 복잡도는 O(n)이며, 평균 O(n/2)이다.

Best Fit

Best Fit은 모든 빈 공간을 확인한 뒤 요청에 맞는 공간 중 가장 작은 곳을 고른다. 메모리 낭비를 줄이는 데는 유리하지만 전체 탐색이 필요해 느리다. 작은 단편이 메모리 전체에 분산될 수 있으며, 정렬된 리스트를 사용하면 성능을 개선할 수 있다.

시간 복잡도는 O(n)이고, 공간 효율성은 가장 좋다. 문제는 많은 작은 단편이 만들어질 수 있다는 점이다.

Worst Fit

Worst Fit은 가장 큰 빈 공간에 할당한다. 남은 공간이 충분히 크기 때문에 재사용 가능성을 높이려는 방식이지만, 전체 검색이 필요하고 큰 단편화를 빠르게 소진한다. 실제로는 거의 사용되지 않는다.

시간 복잡도는 O(n)이며, 효율성은 일반적으로 가장 낮다.

Next Fit

Next Fit은 이전 할당 위치부터 탐색을 시작한다. First Fit보다 메모리 사용을 균등하게 만들 수 있지만 검색 포인터를 관리해야 한다. 메모리 끝부분의 큰 블록을 빠르게 소진할 수 있고, 성능은 First Fit과 비슷하거나 약간 낮다.

페이지 교체 알고리즘을 고르는 기준

FIFO

FIFO(First In First Out)는 가장 먼저 메모리에 들어온 페이지를 먼저 교체한다. Queue를 사용하므로 구현이 매우 단순하다. 그러나 실제 사용 패턴을 반영하지 못하며, 프레임이 늘어도 Page Fault가 증가할 수 있는 Belady's Anomaly가 발생할 수 있다. 초기화 코드처럼 한 번만 쓰는 페이지에는 유리하다.

장점은 단순성과 공정성이고, 단점은 성능을 예측하기 어렵고 Belady's Anomaly가 가능하다는 점이다.

LRU

LRU(Least Recently Used)는 가장 오래 사용되지 않은 페이지를 교체한다. Temporal Locality를 잘 반영하며 Stack Algorithm이므로 Belady's Anomaly가 없다. 다만 시간 스탬프나 이중 연결 리스트가 필요해 구현 복잡도가 높고, 하드웨어 지원이 필요하면 비용이 늘어난다.

구현에는 다음 방식이 있다.

Counter 방식: 각 페이지 접근 시 카운터 갱신
Stack 방식: 접근 시 페이지를 스택 최상위로 이동
근사 방법: Reference Bit + 주기적 검사

적절한 자료구조를 사용하면 시간 복잡도는 O(1)이다.

LFU

LFU(Least Frequently Used)는 참조 횟수가 가장 적은 페이지를 교체한다. 장기적인 사용 패턴을 반영하지만, 초기에 많이 사용된 페이지가 계속 남을 수 있다. 카운터 관리 오버헤드는 Aging 기법으로 보완할 수 있다.

변형으로는 주기적으로 카운터를 줄이는 LFU with Aging과 특정 시간 내 참조만 세는 LFU with Time Window가 있다.

NUR

NUR(Not Used Recently)은 LRU의 근사 알고리즘으로, Reference Bit와 Modified Bit를 사용한다. 페이지는 다음 클래스로 분류하며 낮은 클래스부터 교체한다.

Class 0: (R=0, M=0) - 최근 미사용, 미수정
Class 1: (R=0, M=1) - 최근 미사용, 수정됨
Class 2: (R=1, M=0) - 최근 사용, 미수정
Class 3: (R=1, M=1) - 최근 사용, 수정됨

Reference Bit는 주기적으로 초기화한다. 구현이 간단하면서 LRU에 가까운 성능을 기대할 수 있지만, 정확도는 LRU보다 낮다.

OPT

OPT(Optimal)는 미래에 가장 오래 사용되지 않을 페이지를 교체한다. 이론적으로는 최적 성능을 내지만 미래를 예측할 수 없으므로 실제 구현은 불가능하다. 시뮬레이션에서만 사용할 수 있으며, 다른 알고리즘의 성능을 비교하는 Upper Bound 역할을 한다.

SCR

SCR(Second Chance Replacement / Clock)은 FIFO에 Reference Bit를 더한 방식이다. 원형 큐(Circular Queue)에서 포인터가 가리키는 페이지의 Reference Bit가 0이면 교체한다. 1이면 0으로 바꾸고 다음 페이지로 이동시켜 두 번째 기회를 준다.

동작은 다음과 같다.

포인터가 가리키는 페이지 검사
R=0이면 교체
R=1이면 R=0으로 변경하고 포인터 이동
2-3 반복

FIFO보다 성능이 우수하면서 구현은 간단하다. 다만 최악의 경우 전체 스캔이 필요하다.

⤢✕

구현 비용과 Page Fault 특성

알고리즘	구현 복잡도	Page Fault	오버헤드	Belady's Anomaly
FIFO	낮음	높음	낮음	있음
LRU	높음	낮음	높음	없음
LFU	중간	중간	중간	없음
NUR	낮음	중간	낮음	없음
OPT	불가능	최소	-	없음
SCR	낮음	중간	낮음	없음

단순한 시스템에서 메모리 접근 패턴이 균등하고 오버헤드를 최소화해야 한다면 FIFO가 맞을 수 있다. 성능이 중요하고 Temporal Locality가 강하며 하드웨어 지원이 가능하다면 LRU를 고려할 수 있다.

일반적인 범용 시스템에서 성능과 복잡도의 균형이 필요하면 NUR 또는 SCR이 적합하다. 데이터베이스 버퍼나 캐시 시스템처럼 장기 패턴이 중요한 경우에는 LFU를 사용할 수 있다. 제한된 메모리를 효율적으로 쓰려면 할당, 배치, 인입, 교체 정책과 분할·할당 방식을 시스템 특성에 맞춰 조합해야 한다.