LFU
LFU(Least Frequently Used)는 가장 적게 참조된 페이지를 우선 교체하는 페이지 교체 알고리즘이다. “자주 사용되는 페이지는 앞으로도 자주 쓰일 것”이라는 *빈도 지역성(Frequency Locality)*에 기반한다.
동작 방식
- 각 페이지마다 참조 횟수 카운터를 유지한다.
- 페이지 폴트가 발생하면 카운터 값이 가장 낮은 페이지를 교체한다.
- 카운터 값이 동일하면 보통 LRU로 타이브레이크.
장점
- 장기간 자주 사용된 페이지를 잘 유지한다.
- 안정적으로 높은 빈도를 보이는 데이터에 강하다.
단점
- 초기 참조 편향: 과거에 많이 썼지만 이제는 안 쓰는 페이지가 계속 남는다.
- 카운터 관리 비용이 발생한다.
- 이 단점을 보완하기 위해 주기적으로 카운터를 감쇠(aging)시키는 변형이 사용된다.
다른 알고리즘과의 비교
| 알고리즘 | 기준 | 적합한 상황 |
|---|---|---|
| LFU | 사용 빈도 | 인기 콘텐츠 캐시 |
| LRU | 마지막 사용 시점 | 시간 지역성 강한 경우 |
| NUR | 최근 사용 여부 | LRU 구현 부담이 큰 경우 |
| FIFO | 들어온 순서 | 단순성 우선 |
| OPT | 미래 사용 시점 | 벤치마크 기준 |