LRU 페이지 교체 (Least Recently Used)

Jan 27, 2026

핵심 개념

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다. OPT(Optimal)는 미래 정보가 필요해서 구현 불가능하므로, LRU는 과거 사용 패턴으로 미래를 예측한다.

핵심 가정은 시간적 지역성(temporal locality): 최근에 참조된 페이지는 가까운 미래에도 참조될 가능성이 높다. OPT가 미래를 보는 것의 거울상으로, LRU는 과거를 본다.

비유하면, 옷장 정리에서 가장 오래 안 입은 옷을 기부하는 것과 같다.

동작 원리

각 페이지의 마지막 참조 시간을 기록
교체가 필요하면 가장 오래 전에 참조된 페이지 선택

구현 방법 1: Counter (시간 기록) 방식

각 페이지 테이블 엔트리에 time-of-use 필드 추가
CPU에 논리적 클럭/카운터 유지
모든 메모리 참조 시 카운터 값을 해당 페이지에 복사
교체 시 가장 작은 카운터 값을 가진 페이지 선택

장점: 개념적으로 단순. 단점: 매 참조마다 페이지 테이블 쓰기, 교체 시 전체 검색 필요.

구현 방법 2: Stack (스택) 방식

이중 연결 리스트로 페이지 번호 스택을 유지한다.

페이지 참조 시 해당 페이지를 스택 맨 위로 이동
스택 상단: 가장 최근 사용 (MRU)
스택 하단: 가장 오래된 사용 (LRU) → victim

참조: 4  7  0  7  1  0  1  2  1  2  7  1  2

스택 변화 (위 → 아래 = 최근 → 오래됨):
4 → 7,4 → 0,7,4 → 7,0,4 → 1,7,0,4 → 0,1,7,4 → ...

장점: 교체 시 검색 불필요 (tail이 LRU). 단점: 매 참조마다 최대 6개 포인터 변경 필요.

하드웨어 지원 필요성

순수 LRU는 매 메모리 참조마다 시간 정보 갱신 필요
소프트웨어로 구현 시 매 참조에 인터럽트 → 10배 이상 성능 저하
하드웨어 지원 없이는 실용적 구현 불가
실제 시스템에서는 LRU 근사 알고리즘 사용 (예: Second-Chance/Clock)

예시

reference string = 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1, 3 프레임

참조: 7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     ─────────────────────────────────────────────────────────
f0:  7  7  7  2  2  2  2  4  4  4  0  0  0  1  1  1  1  1  1  1
f1:     0  0  0  0  0  0  0  0  3  3  3  3  3  3  0  0  0  0  0
f2:        1  1  1  3  3  3  2  2  2  2  2  2  2  2  2  7  7  7
     ─────────────────────────────────────────────────────────
폴트: F  F  F  F     F     F  F  F  F        F     F     F

총 12번의 페이지 폴트 (OPT의 9번보다는 많지만, FIFO의 15번보다 적음)

Stack Algorithm 특성

LRU는 스택 알고리즘에 속함
n 프레임 시 메모리 페이지 ⊆ (n+1) 프레임 시 메모리 페이지
Belady’s anomaly 발생 안 함
흥미로운 성질: reference string S에 대한 LRU 폴트 수 = S의 역순에 대한 LRU 폴트 수