LRU (페이지 교체 알고리즘)

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 선택하는 페이지 교체 알고리즘이다. 운영체제의 가상 메모리 관리, 캐시 시스템, 데이터베이스 등에서 효율적인 메모리 활용을 위해 사용된다.

1 개념

LRU 알고리즘은 다음과 같은 직관에 기반한다:

• 최근에 사용된 페이지는 앞으로도 다시 사용할 가능성이 높다
• 반대로, 오래 사용되지 않은 페이지는 앞으로도 사용되지 않을 가능성이 높다

따라서 페이지 프레임이 가득 찼을 때, 가장 오래 전에 사용된 페이지를 제거하고 새 페이지를 로드한다.

2 동작 방식

LRU는 각 페이지의 최근 사용 시점을 기억해야 하며, 일반적으로 다음과 같은 방식으로 구현된다:

1. 새 페이지가 요청되었을 때:
   • 이미 프레임에 있으면 → 단순히 최근 사용 시간 갱신
   • 없다면:
   1. 프레임이 비어 있으면 → 새 페이지 삽입
   2. 프레임이 가득 찼으면 → 가장 오래된 페이지 제거 후 새 페이지 삽입

3 구현 방법

• 카운터 방식
  • 각 페이지에 타임스탬프 저장
  • 가장 오래된 타임스탬프를 가진 페이지를 제거

• 스택 방식
  • 페이지를 스택(또는 리스트)으로 관리
  • 사용 시 스택의 맨 위로 이동, 가장 아래가 가장 오래된 페이지

• 해시 + 이중 연결 리스트 (실제 시스템 캐시에서 사용)
  • O(1) 시간에 접근/삭제 가능

4 예시

페이지 프레임 수: 3 페이지 요청 순서: 7, 0, 1, 2, 0, 3, 0, 4

동작:

1. 7 → [7]
2. 0 → [7, 0]
3. 1 → [7, 0, 1]
4. 2 → [0, 1, 2] (7 제거)
5. 0 → [1, 2, 0]
6. 3 → [2, 0, 3] (1 제거)
7. 0 → [2, 3, 0]
8. 4 → [3, 0, 4] (2 제거)

→ 페이지 폴트 6회

5 장점

• 페이지 교체 성능이 우수함 (참조 지역성 가정에 부합)
• 많은 시스템에서 실용적으로 사용 가능

6 단점

• 최근 사용 시간 추적을 위한 오버헤드 존재
• 완전한 구현은 하드웨어 또는 추가 자료구조 필요

7 같이 보기

• 페이지 교체 알고리즘
• FIFO (페이지 교체 알고리즘)
• OPT (최적 페이지 교체)
• 캐시
• 가상 메모리

8 참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson