페이지 교체 정책 완전정복 — FIFO, LRU, Clock, 그리고 최적 알고리즘까지
들어가며 — “페이지를 내보낼 때, 누구를 희생시킬까?”
물리 메모리가 넉넉할 땐 문제가 없지만, 여유 공간이 줄어들면 OS는 선택의 기로에 놓입니다. 새 페이지를 가져오기 위해 누군가를 내보내야 하죠. 이때 어떤 페이지를 내보낼지를 결정하는 것이 바로 페이지 교체 정책(Page Replacement Policy)입니다.
💬 한마디로, “누구를 쫓아낼지” 정하는 OS의 전략이 페이지 교체 정책입니다.
메모리는 결국 캐시다
물리 메모리는 전체 가상 메모리의 “캐시(cache)”라고 볼 수 있습니다. 따라서 OS의 목표는 단순합니다 — 디스크 접근(미스)을 최소화하고, 메모리 히트율을 최대화하는 것.
이를 계산하는 공식이 바로 평균 메모리 접근 시간(AMAT):
AMAT = TM + (Pmiss × TD)- TM : 메모리 접근 시간 (예: 100ns)
- TD : 디스크 접근 시간 (예: 10ms)
- Pmiss : 미스 확률 (예: 0.1 → 10%)
디스크 접근은 메모리보다 약 10⁵배 이상 느리기 때문에, 미스율이 0.1%만 되어도 성능이 수백 배 느려질 수 있습니다. 결국 “어떤 페이지를 남기고, 어떤 페이지를 내보내느냐”가 성능의 핵심이 되는 이유죠.
최적 교체 정책 (Optimal, aka Belady’s MIN)
1966년, Belady가 제안한 MIN 알고리즘은 “미래에 가장 늦게 사용될 페이지를 교체”하는 방식입니다. 이론적으로는 최적(Optimal)입니다. 하지만 문제는 — 미래를 모른다는 것!
💬 “미래를 볼 수만 있다면, 최고의 정책은 이미 존재한다.” — Belady
최적 알고리즘은 실제 구현은 불가능하지만, 모든 정책의 비교 기준으로 쓰입니다. 실험에서 FIFO, LRU 등이 최적 대비 얼마나 근접한지를 비교하는 식이죠. [oai_citation:1‡vm-beyondphys-policy.pdf](sediment://file_00000000060462068e775104998801f3)
FIFO (First-In, First-Out)
이름 그대로, 먼저 들어온 페이지를 먼저 내보내는 단순한 정책입니다. 구현은 쉽지만, 성능은 좋지 않습니다.
FIFO는 페이지의 중요도나 재사용 여부를 고려하지 않습니다. 즉, 방금까지 계속 쓰이던 페이지라도 단지 “먼저 들어왔다는 이유로” 내쫓길 수 있습니다.
⚠️ 대표적인 문제: Belady’s Anomaly 캐시 크기를 늘렸는데 오히려 성능이 나빠지는 현상입니다. FIFO에서 실제로 발생합니다. [oai_citation:2‡vm-beyondphys-policy.pdf](sediment://file_00000000060462068e775104998801f3)
Random 정책
말 그대로, 임의의 페이지를 랜덤하게 교체합니다. FIFO처럼 단순하지만, 의외로 특정 상황에서는 더 잘 작동하기도 합니다.
예를 들어 순차 접근(workload loop) 상황에서는 FIFO보다 랜덤이 덜 망가질 수 있습니다. 다만 운에 크게 좌우되고, 일관성이 떨어집니다. [oai_citation:3‡vm-beyondphys-policy.pdf](sediment://file_00000000060462068e775104998801f3)
LRU (Least Recently Used)
가장 널리 쓰이는 히스토리 기반 정책입니다. 과거에 “가장 오랫동안 접근되지 않은” 페이지를 내보내는 방식이죠.
💬 과거는 미래의 가장 좋은 예측자이다 — LRU의 철학
프로그램은 “지역성의 원리(Locality Principle)”를 따릅니다:
- 시간적 지역성: 최근에 접근한 데이터는 곧 다시 접근될 가능성이 높음
- 공간적 지역성: 어떤 페이지를 접근하면 그 주변 페이지도 곧 접근됨
LRU는 이 패턴을 활용하기 때문에, 대부분의 실제 프로그램에서 가장 효율적입니다.
정책 비교 예시
아래는 10번의 메모리 접근이 발생했을 때, 각 정책의 히트율 비교입니다.
| 정책 | 히트율 | 특징 |
|---|---|---|
| Optimal | ~85% | 미래를 알고 있으면 완벽 |
| LRU | ~80% | 현실적 + 효율적 |
| FIFO | ~55% | 단순하지만 비효율적 |
| Random | 가변적(40~60%) | 운에 좌우 |
실제로는 LRU가 거의 항상 FIFO나 Random보다 우수하지만, 구현 복잡도가 높은 편입니다.
LRU 구현의 어려움과 Clock 알고리즘
LRU를 완벽하게 구현하려면, 모든 메모리 접근마다 최근 순서를 갱신해야 합니다. 하지만 이건 너무 비쌉니다 — 수백만 개 페이지 중에서 매번 가장 오래된 걸 찾는 건 비현실적이죠.
그래서 나온 근사 알고리즘이 바로 Clock입니다.
- 모든 페이지를 원형 큐(시계) 형태로 관리
- 각 페이지에 use bit(참조 비트)를 둠
- 교체 시, 포인터가 가리킨 페이지의 use bit을 확인
- 1이면 0으로 리셋하고 다음 페이지로 이동
- 0을 만날 때까지 반복 → 그 페이지를 교체
결국 “최근에 쓰인 흔적(use bit=1)”이 있는 페이지는 보호되고, 한참 동안 안 쓰인 페이지(use bit=0)가 교체 대상이 됩니다. 완벽한 LRU는 아니지만 훨씬 가볍고 실용적입니다.
Dirty Bit — 쓰기된 페이지의 문제
페이지가 메모리에서 디스크로 나갈 때, 변경된 적이 있다면 디스크에 다시 써야 합니다. 이걸 표시하는 게 바로 Dirty Bit (Modified Bit)입니다.
Clock 알고리즘에 이 비트를 추가하면, 다음 순서로 교체 우선순위를 둘 수 있습니다:
- 사용 안 됨 + 깨끗한 페이지 (Clean)
- 사용 안 됨 + 더러운 페이지 (Dirty)
즉, 쓰기 작업이 필요 없는 페이지를 먼저 버림으로써 I/O 비용을 줄입니다.
기타 정책: 프리페치와 쓰기 정책
- 프리페칭(prefetching): 페이지를 “필요해질 것 같을 때” 미리 불러오기
- 클러스터링(clustering): 여러 더러운 페이지를 모아서 한 번에 디스크에 기록
이런 정책들은 모두 디스크 접근 횟수를 줄여 성능을 향상시키는 보조 전략입니다.
Thrashing — 스왑 폭주 현상
모든 프로세스의 메모리 요구량이 물리 메모리보다 많으면, 시스템은 계속해서 페이지를 교체하게 됩니다. 이 현상이 바로 Thrashing (스왑 폭주)입니다.
과거 OS들은 Admission Control 기법을 사용했습니다: 일부 프로세스를 중단시켜 나머지 프로세스의 “작업 집합(working set)”이 메모리에 들어오도록 하는 것이죠.
Linux에서는 좀 더 단호하게, OOM Killer가 동작합니다 — 메모리를 과점유한 프로세스를 강제로 종료시켜 공간을 확보합니다.
마무리 — 교체 정책의 진화
최근 SSD와 NVMe 같은 초고속 저장장치의 등장으로, 다시금 페이지 교체 알고리즘이 연구되고 있습니다. 대표적으로 ARC(Adaptive Replacement Cache) 같은 자기조정형 알고리즘이 발전 중입니다.
하지만 본질은 변하지 않습니다. “무엇을 버리고 무엇을 남길까?” — 이건 메모리 관리의 영원한 철학이죠.