페이지 교체 알고리즘과 가상 메모리의 희생 페이지 선택

빈 프레임이 없을 때 시작되는 선택

가상 메모리에서 새 페이지가 필요하지만 물리 메모리 프레임이 모두 사용 중이면 페이지 부재(Page Fault)가 발생한다. 이때 시스템은 기존 페이지 가운데 희생 페이지(Victim Page)를 고르고, 필요하면 이를 디스크로 스왑 아웃(Swap-out)한 뒤 새 페이지를 스왑 인(Swap-in)한다.

이 선택은 단순히 오래된 데이터를 비우는 일이 아니다. 자주 다시 참조될 페이지를 내보내면 페이지 부재와 디스크 I/O가 늘어나며 전체 성능이 흔들릴 수 있다. 페이지 교체 정책은 페이지 부재율을 낮추고, 디스크 I/O를 줄여 처리량을 높이며, 프로세스 간 메모리 할당의 공정성과 희생 페이지 선택 비용까지 함께 고려한다.

성능은 보통 다음 지표로 본다.

페이지 부재율(Page Fault Rate): 부재 횟수 / 총 참조 횟수
평균 메모리 접근 시간(AMAT): 메모리 접근 시간 + (페이지 부재율 × 페이지 부재 처리 시간)
스왑 횟수: 디스크 I/O 발생 빈도

적재 순서만 따르는 FIFO

FIFO(First-In-First-Out)는 메모리에 가장 먼저 들어온 페이지부터 교체한다. 적재 순서를 큐(Queue)에 기록해 두었다가, 교체가 필요하면 큐의 맨 앞 페이지를 제거하고 새 페이지를 맨 뒤에 넣는다.

구현은 매우 간단하고 오버헤드도 낮다. 적재 순서대로 처리한다는 점에서 공정하게 보이지만, 실제 참조 패턴은 고려하지 않는다. 오래 전에 적재됐더라도 계속 사용되는 페이지가 교체될 수 있다.

FIFO의 대표적인 한계는 Belady의 이상 현상이다. 프레임 수를 늘렸는데도 페이지 부재가 증가할 수 있으며, 지역성(Locality)을 반영하지 못해 성능이 좋지 않다.

미래를 알아야 가능한 Optimal

Optimal(OPT, MIN)은 앞으로 가장 늦게 참조될 페이지를 희생 페이지로 택한다. 더 이상 참조되지 않을 페이지가 있다면 그것을 우선적으로 선택한다.

이 정책은 Belady가 증명한 최소 페이지 부재 알고리즘이며, 이론적으로 가장 낮은 페이지 부재율을 보장한다. 다른 알고리즘의 성능을 비교하는 기준으로도 쓰인다.

문제는 다음 참조 시점을 미리 알아야 한다는 점이다. 미래의 참조 패턴을 알 수 없으므로 구현할 수 없고, 오프라인 알고리즘으로서 연구와 비교 목적에 머문다.

최근 사용 이력을 추적하는 LRU

LRU(Least Recently Used)는 가장 오래 전에 참조된 페이지를 교체한다. 과거의 참조 이력을 미래 참조의 단서로 삼으며, 시간적 지역성(Temporal Locality)을 이용하는 방식이다.

페이지마다 최종 참조 시각을 기록하고, 교체 시점에는 가장 오래된 시각을 가진 페이지를 고른다. 페이지가 참조될 때마다 타임스탬프도 갱신해야 한다.

구현에는 카운터 방식과 스택 방식이 사용된다. 카운터 방식은 각 페이지에 논리적 시계(Logical Clock) 값을 두고, 참조 때마다 현재 시계 값으로 갱신한다. 교체할 때는 가장 작은 값을 가진 페이지를 선택한다.

스택 방식은 이중 연결 리스트(Doubly Linked List)로 페이지를 관리한다. 참조된 페이지를 스택 최상단으로 이동시키고, 교체가 필요하면 최하단 페이지를 제거한다.

LRU는 지역성 원리에 부합하고 Optimal에 근접한 성능을 낸다. Belady의 이상 현상도 없다. 반면 타임스탬프 갱신, 스택 관리, 하드웨어 지원이 필요해 구현 복잡도와 매 참조의 오버헤드가 커진다.

참조 빈도를 기준으로 하는 LFU와 MFU

LFU(Least Frequently Used)는 참조 횟수가 가장 적은 페이지를 교체한다. 페이지별 참조 카운터를 유지하고, 참조될 때마다 값을 증가시킨 뒤 가장 작은 카운터를 가진 페이지를 희생 페이지로 선택한다. 공간적 지역성을 고려하며, 자주 사용되는 페이지를 보호하고 장기적인 참조 패턴을 반영한다.

하지만 먼저 적재된 페이지가 오랫동안 남을 수 있고, 최근 참조 패턴 변화에는 느리게 반응한다. 카운터 관리 비용과 같은 카운터 값을 가진 페이지를 처리하는 문제도 있다.

MFU(Most Frequently Used)는 LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체한다. 많이 사용된 페이지는 이미 충분히 사용됐다고 가정하는 전략이며, 동작 자체는 최대 카운터 값을 선택한다는 점만 다르다. 일반적으로 성능이 좋지 않아 이론적 관심사로 남아 있고 실무에서는 거의 사용하지 않는다.

참조 비트로 LRU를 근사하는 Clock

Clock(Second Chance)은 FIFO의 단순한 구조에 LRU의 효율성을 결합한 방식이다. 페이지를 순환 리스트(Circular List)로 관리하고, 각 페이지의 참조 비트(Reference Bit)를 이용한다.

포인터가 순환하면서 페이지를 검사할 때 참조 비트가 1이면 이를 0으로 바꾸고 다음 페이지로 이동한다. 페이지에 두 번째 기회를 주는 셈이다. 참조 비트가 0인 페이지를 만나면 해당 페이지를 교체 대상으로 선택한다.

Clock은 LRU에 근접한 성능을 비교적 단순하게 제공하며, 필요한 하드웨어 지원이 적고 오버헤드도 낮다. 다만 최악의 경우 모든 페이지를 검사할 수 있고, 성능은 LRU보다 낮다.

변경 여부까지 반영하는 Enhanced Clock

Enhanced Clock은 NRU(Not Recently Used)로도 불리며, Clock 알고리즘에 참조 비트(R)뿐 아니라 변경 비트(M)까지 더한 방식이다. 변경된 페이지는 교체 전에 기록이 필요하므로, 참조 여부와 변경 여부를 함께 고려해 우선순위를 정한다.

페이지는 다음 순서로 분류된다.

(R=0, M=0): 최근 미참조, 미변경 → 교체 최적
(R=0, M=1): 최근 미참조, 변경됨 → 기록 필요
(R=1, M=0): 최근 참조, 미변경 → 곧 재참조 가능
(R=1, M=1): 최근 참조, 변경됨 → 교체 최악

먼저 클래스 1의 페이지를 찾고, 없으면 참조 비트를 초기화하며 클래스 2를 찾는다. 이어서 클래스 3, 클래스 4 순으로 검색한다. Dirty 페이지를 기록하는 비용까지 반영하므로 실용성과 성능 사이의 균형을 맞추는 정책이다.

선택 기준에 따른 차이

알고리즘	성능	구현	오버헤드	Belady 이상	실용성
FIFO	낮음	매우 쉬움	낮음	발생	낮음
Optimal	최고	불가능	-	없음	없음
LRU	높음	어려움	높음	없음	중간
LFU	중간	중간	중간	없음	낮음
MFU	낮음	중간	중간	-	없음
Clock	중상	쉬움	낮음	없음	높음
Enhanced Clock	높음	중간	중간	없음	높음

운영체제와 버퍼 풀에서의 활용

Linux는 2Q(Two Queue), Active/Inactive 리스트, LRU 근사 알고리즘을 사용한다. Windows는 Working Set 기반 관리, Clock 알고리즘 변형, Age-based 교체 방식을 사용한다.

데이터베이스 시스템도 버퍼 풀 관리에서 LRU 변형을 활용한다. ARC(Adaptive Replacement Cache), 2Q, LRU-K 등이 이에 해당한다. 기본 알고리즘은 같더라도 실제 시스템은 메모리 특성과 접근 패턴에 맞춰 이를 변형해 사용한다.