LRU
LRU(Least Recently Used)는 메모리가 부족할 때 가장 오랫동안 사용되지 않은 페이지를 우선 교체하는 페이지 교체 알고리즘이다. “최근에 쓰인 데이터는 곧 다시 쓰일 가능성이 높다”는 *시간 지역성(Temporal Locality)*에 기반한다.
동작 방식
각 페이지에 마지막 참조 시각 정보를 유지한다. 페이지 폴트가 발생하면 그 값이 가장 오래된 페이지를 교체한다.
참조 순서: A B C A B D
프레임 3개 가정:
A 적재 → [A]
B 적재 → [A, B]
C 적재 → [A, B, C]
A 참조 → [B, C, A] (A의 시각 갱신)
B 참조 → [C, A, B]
D 적재 → [A, B, D] (가장 오래된 C 교체)
구현
- 연결 리스트 + 해시맵: O(1) 접근/갱신, 가장 흔한 LRU 캐시 구현
- 카운터 기반: 매번 카운터 갱신, 단순하지만 비용 큼
- 스택: 참조마다 위로 이동, 단순 시각화에 좋음
장점
- 시간 지역성을 잘 반영해 FIFO보다 페이지 폴트가 적다
- Belady의 변칙이 발생하지 않는다
- 캐시(LRU 캐시)에서도 널리 사용
단점
- 모든 참조마다 정보를 갱신해야 해 오버헤드가 크다
- 하드웨어 지원 없이는 비용이 부담스럽다 → 근사 기법인 NUR 등이 등장한 이유
다른 알고리즘과의 비교
| 알고리즘 | 기준 | 특징 |
|---|---|---|
| LRU | 마지막 사용 시점 | 시간 지역성 활용 |
| FIFO | 들어온 순서 | 단순하지만 변칙 있음 |
| NUR | 최근 사용 여부 | LRU 근사 |
| LFU | 사용 빈도 | 빈도 지역성 활용 |
| OPT | 미래 사용 시점 | 이론상 최적, 구현 불가 |