임베디드 스터디 - 페이지 교체 알고리즘

페이지 교체 알고리즘이란

• 빈 프레임이 없을 때 희생 페이지를 선택하여 교체하는 알고리즘
• 목표: 페이지 폴트 횟수 최소화

---

6가지 알고리즘 비교

OPT (Optimal)

• 앞으로 가장 사용되지 않는 페이지를 교체
• 성능이 이론적으로 가장 우수하나 미래 참조 순서를 알아야 하므로 구현 불가
• 다른 알고리즘의 성능 비교 기준(이론적 상한)으로 사용

FIFO (First In First Out)

• 메모리에 가장 먼저 들어온 페이지를 교체
• 단점: 자주 사용될 페이지도 교체될 수 있어 효율 낮음
• Belady의 모순: 프레임 수를 늘렸는데 오히려 페이지 폴트가 많이 발생하는 현상 (FIFO에서만 발생)

LRU (Least Recently Used)

• 최근에 가장 오래 사용되지 않은 페이지를 교체
• 과거 참조 이력 전체를 추적 → 성능 우수하나 매 참조마다 최근 사용 시점 기록 필요

LFU (Least Frequently Used)

• 참조 횟수가 가장 적은 페이지를 교체
• 매 참조마다 카운터 유지 필요

NRU (Not Recently Used)

• 최근 클록 인터럽트 주기 동안 참조되지 않은 페이지를 교체
• 참조 비트(R)와 변경 비트(M) 두 개로 4가지 등급 분류

등급	R	M	교체 우선순위
0	0	0	최우선 교체
1	0	1	높음
2	1	0	낮음
3	1	1	최후 교체

Clock 알고리즘

• 페이지를 원형으로 배치하고 시계 바늘처럼 순회
• 참조 비트 = 0이면 페이지 교체, 1이면 0으로 바꾸고 넘어감
• 실제 OS(Linux 등)에서 가장 많이 사용되는 이유: 오버헤드가 낮고 구현이 단순해서

---

알고리즘 특성 요약

알고리즘	핵심 특성
OPT	이론적 최적, 구현 불가 — 성능 비교 기준
FIFO	구현 단순, Belady의 모순 발생 가능
LRU	성능 우수, 타임스탬프 오버헤드 큼
LFU	성능 우수, 카운터 오버헤드 큼
NRU	R/M 두 비트로 등급 분류
Clock	참조 비트 하나 + 포인터, 오버헤드 적음