LFU (페이지 교체 알고리즘)
IT 위키
LFU(Least Frequently Used, 최소 사용 횟수 우선)는 가장 적게 참조된 페이지를 교체 대상으로 선택하는 페이지 교체 알고리즘이다. 페이지가 얼마나 자주 사용되었는지를 기준으로 판단하며, 사용 빈도가 낮은 페이지부터 제거하여 공간을 확보한다.
1 개념[편집 | 원본 편집]
LFU는 페이지 교체 시 다음 원칙에 따라 동작한다:
- 참조 횟수(사용 빈도)가 가장 낮은 페이지를 우선 제거
- 동일한 빈도일 경우, 보통 가장 오래된 페이지를 선택
이는 다음과 같은 가정을 따른다:
- 자주 사용되는 페이지는 앞으로도 자주 사용될 가능성이 높다
- 거의 참조되지 않은 페이지는 앞으로도 사용할 가능성이 낮다
2 동작 방식[편집 | 원본 편집]
- 페이지가 참조될 때마다 해당 페이지의 참조 횟수를 증가시킴
- 페이지 부재(page fault) 발생 시:
- 프레임에 공간이 있으면 삽입
- 공간이 없으면 참조 횟수가 가장 적은 페이지를 제거
- 횟수가 같을 경우 FIFO 방식으로 결정
3 예시[편집 | 원본 편집]
페이지 프레임 수: 3 페이지 요청 순서: 2, 3, 2, 1, 5, 2, 4, 5
동작 (괄호 안은 참조 횟수):
- 2 → [2(1)]
- 3 → [2(1), 3(1)]
- 2 → [2(2), 3(1)]
- 1 → [2(2), 3(1), 1(1)]
- 5 → [2(2), 1(1), 5(1)] (3 제거, 참조 횟수 가장 낮은 페이지 중 FIFO)
- 2 → [2(3), 1(1), 5(1)]
- 4 → [2(3), 5(1), 4(1)] (1 제거)
- 5 → [2(3), 5(2), 4(1)]
→ 페이지 폴트: 6회
4 장점[편집 | 원본 편집]
- 자주 사용하는 페이지를 오래 유지하여 교체 효율이 높을 수 있음
- 캐시 시스템, DB 페이지 관리 등에 응용 가능
5 단점[편집 | 원본 편집]
- 참조 횟수 기록 및 정렬을 위한 추가 자료구조 필요
- 과거의 사용 빈도가 미래에도 유효하다는 보장은 없음
- 캐시 오염(Cache Pollution) 문제 발생 가능
- 과거에 자주 사용되었지만 더 이상 필요 없는 페이지가 오래 남아 있음
6 개선 알고리즘[편집 | 원본 편집]
- LFU-K: 최근 K번의 참조를 기반으로 판단
- Aging 기법: 시간에 따라 참조 횟수 감쇠 처리
7 구현 방법[편집 | 원본 편집]
- 페이지마다 참조 횟수 카운터를 유지
- 우선순위 큐, 해시 + 이중 연결 리스트 등을 사용해 최소값 탐색 및 삭제
8 같이 보기[편집 | 원본 편집]
9 참고 문헌[편집 | 원본 편집]
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
- Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson
