LRU (Least Recently Used) 페이지 교체

핵심 인사이트 (3줄 요약)

본질: LRU (Least Recently Used)는 메모리(RAM)가 꽉 차서 페이지를 내쫓아야 할 때, **"가장 오랫동안 사용되지 않은(Least Recently Used) 페이지를 1순위 희생양으로 삼아 교체"**하는 통계 기반의 교체 알고리즘이다.

가치: "과거에 오랫동안 안 쓴 데이터는 미래에도 안 쓸 확률이 높다"는 참조의 지역성(Locality of Reference) 원리를 가장 충실히 반영하여, FIFO의 치명적 결함인 Belady의 모순을 해결하고 실제 워크로드에서 최적 알고리즘(OPT)에 가장 근접한 완벽한 적중률(Hit Rate)을 자랑한다.

융합: 하지만 메모리에 접근할 때마다 시간을 기록하거나 링크드 리스트(Linked List)를 갱신해야 하는 $O(N)$의 거대한 오버헤드를 동반하므로, 순수 LRU는 OS 커널 레벨에서는 쓸 수 없고 하드웨어 지원을 받는 클럭(Clock / Second-Chance) 알고리즘 형태로 우회 융합되어 사용된다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 페이지 교체의 시점을 미래가 아닌 '과거'의 기록에 의존하는 알고리즘이다. 메모리에 있는 모든 페이지의 '마지막 참조 시간'을 추적하여, 그 시간이 가장 먼(오래된) 페이지를 가차 없이 버린다.
필요성: FIFO(선입선출) 알고리즘은 먼저 들어온 놈을 무조건 내쫓았다. 하지만 먼저 들어왔어도 1초에 한 번씩 계속 쓰이는 "핵심 변수" 페이지를 쫓아내는 바람에 페이지 폴트가 터지는 멍청한 짓(Belady's Anomaly)을 반복했다. 이를 막으려면 단순히 '들어온 시간'이 아니라 **'마지막으로 사용된 시간'**을 기준으로 가치를 재평가하는 똑똑한 매니저가 필요했다.
💡 비유: 옷장(RAM)이 꽉 찼을 때 헌옷수거함(디스크)에 버릴 옷을 고르는 기준과 같다. FIFO가 **'가장 먼저 산 10년 된 명품 코트'**를 버린다면, LRU는 **'산 지 1달밖에 안 됐지만 지난주부터 한 번도 안 입은 유행 지난 티셔츠'**를 버리는 현실적이고 합리적인 판단법이다.
등장 배경: 이상적인 최적(Optimal) 알고리즘은 "미래에 가장 늦게 쓰일 놈"을 버리는 것이지만, OS는 미래를 볼 수 없다. 그래서 컴퓨터 공학자들은 "과거를 보면 미래를 알 수 있다"는 지역성의 원리를 빌려와, 과거의 최장 미사용 데이터를 미래의 최장 미사용 데이터로 '근사(Approximation)'하는 방식으로 LRU를 정립했다.

  [LRU 페이지 교체 알고리즘의 동작 메커니즘]

  [ 초기 상태: 빈 프레임 3개 존재 ]
  페이지 요청 순서: 1 ─▶ 2 ─▶ 3 ─▶ 1 ─▶ 4
  
  [ 메모리 큐 상태 변화 (가장 최근에 쓴 놈이 맨 뒤, 가장 안 쓴 놈이 맨 앞) ]
  1 요청: [ 1 ] 
  2 요청: [ 1, 2 ] 
  3 요청: [ 1, 2, 3 ] (여기서 가장 안 쓴 놈은 1번)
  
  1 요청: 어라? 1번을 또 쓰네? 1번을 최근 사용한 것으로 갱신! (맨 뒤로 보냄)
         [ 2, 3, 1 ] (이제 가장 안 쓴 놈은 2번으로 바뀜!)
         
  4 요청: 🚨 메모리 꽉 참! 제일 안 쓴 맨 앞의 '2'를 버리고 '4'를 넣음.
         [ 3, 1, 4 ] (폴트 발생)

[다이어그램 해설] LRU의 핵심은 "과거의 세탁(갱신)"이다. FIFO였다면 4번이 들어올 때 제일 처음 들어온 1번을 버렸을 것이다. 하지만 LRU는 1번이 방금 전에 다시 쓰였다는 사실을 인지하고 1번의 생명(수명)을 연장해 주며, 그동안 한 번도 안 불린 2번을 가차 없이 처단한다. 이 작은 차이가 캐시 히트율(Hit Rate)을 수십 배 끌어올린다.

📢 섹션 요약 비유: 회사에서 구조조정을 할 때, FIFO는 "입사한 지 가장 오래된 부장님"을 자릅니다. 부장님이 회사 핵심 인재라도 예외는 없습니다. LRU는 "입사일과 상관없이, 최근 1달 동안 실적이 가장 없는(안 쓰인) 사람"을 자릅니다. 철저한 성과(참조) 주의 룰입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

순수 LRU를 구현하기 위한 2가지 끔찍한 오버헤드

LRU 알고리즘이 동작하려면 OS는 메모리에 있는 페이지들의 순위를 완벽히 매겨야 한다. 이를 소프트웨어로 구현하는 방법은 두 가지지만, 둘 다 OS에겐 악몽이다.

1. 카운터 (Counter / Timestamp) 구현

원리: 각 페이지 테이블 항목에 시간(Time) 필드를 추가한다. CPU가 메모리를 참조할 때마다 현재 시간(클럭)을 그 필드에 적는다.
교체 시: 램이 꽉 차면, OS는 모든 페이지의 시간 필드를 하나씩 다 까보고 가장 작은 값(가장 옛날 시간)을 가진 놈을 찾아 죽인다.
한계: $O(N)$의 탐색 시간이 걸린다. 100만 개의 페이지를 다 뒤져야 하므로 1ms 안에 교체를 끝내야 하는 OS 스케줄러가 버티지 못한다.

2. 스택 (Linked List Stack) 구현

원리: 페이지를 더블 링크드 리스트(Doubly Linked List)로 관리한다. 페이지가 참조될 때마다 그 페이지의 노드를 끊어내서 무조건 리스트의 맨 위(Top)로 끌어올린다.
교체 시: 리스트의 맨 바닥(Bottom)에 있는 놈이 제일 안 쓰인 놈이므로 묻지도 따지지도 않고 바로 죽인다. ($O(1)$ 탐색).
한계: 탐색은 빠르지만, CPU가 메모리를 참조할 때마다 포인터 6개를 바꿔 끼우는(링크드 리스트 업데이트) 연산을 동반해야 한다. 메모리 엑세스는 1나노초 단위인데 이 오버헤드는 배보다 배꼽이 100배 큰 짓이다.

  ┌────────────────────────────────────────────────────────────────────────┐
  │         LRU의 스택(Linked List) 구현 시 발생하는 연산 병목 시각화      │
  ├────────────────────────────────────────────────────────────────────────┤
  │                                                                        │
  │   [ 현재 스택 상태 ] (Top이 최근, Bottom이 옛날)                       │
  │   TOP ─▶ [Page 3] ─▶ [Page 5] ─▶ [Page 1] ─▶ [Page 2] ◀─ BOT           │
  │                                                                        │
  │   [ CPU가 갑자기 Page 1을 읽음 (참조 발생!) ]                          │
  │   1. Page 1의 앞뒤 포인터(5와 2)를 서로 연결해 줌.                     │
  │   2. Page 1의 이전 노드를 NULL로, 다음 노드를 Page 3으로 변경.         │
  │   3. Top 포인터를 Page 1로 변경.                                       │
  │                                                                        │
  │   🚨 딜레마: 메모리를 읽을 때마다 OS가 이런 무거운 포인터 조작을       │
  │      소프트웨어 락(Lock)을 걸어가며 해야 한다? (시스템 마비 확정)      │
  └────────────────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 도서관(LRU)에서 책을 완벽하게 인기순으로 정리하려면, 누군가 책을 1페이지 넘길 때마다 사서가 달려와서 그 책을 뽑아 도서관 맨 앞 책장으로 옮겨 꽂아야 합니다. 책을 읽는 시간보다 사서가 책을 옮기는 시간(오버헤드)이 더 오래 걸려서 도서관이 마비됩니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

최적(OPT) vs LRU vs FIFO 의 수학적 성능 궤적

어떤 알고리즘이 스래싱을 잘 막고 페이지 폴트를 덜 내는지 비교한다.

비교 항목	OPT (최적 알고리즘)	LRU (최근 최소 사용)	FIFO (선입 선출)
철학	미래를 보고 버린다	과거를 보고 버린다	나이(시간)만 보고 버린다
페이지 폴트 수	가장 적음 (절대적 최저치)	OPT에 매우 근접함 (훌륭함)	가장 많음 (쓰레기)
모순 발생	없음 (Stack 알고리즘)	없음 (Stack 알고리즘)	발생함 (Belady's Anomaly)
실무 사용	❌ 구현 불가능 (비교 잣대로만 씀)	❌ OS 커널에선 오버헤드로 못 씀 ✅ DB, 웹 캐시에선 표준으로 씀	❌ 안 씀

LRU의 약점: 한 번만 읽고 버리는 스캔(Scan) 작업

LRU는 "자주 쓰는 놈"을 우대하는 데 특화되어 있다. 하지만 "용량이 엄청나게 큰 파일을 처음부터 끝까지 한 번만 쭉 읽고 끝내는(Sequential Scan)" 작업이 들어오면 LRU는 완벽하게 무너진다.

바이러스 백신이 10GB짜리 C드라이브를 풀 스캔했다.
LRU 로직은 "오! 지금 읽고 있으니 최신 데이터네!"라며 10GB어치 쓰레기 데이터를 캐시의 Top에 다 올려버린다.
결과적으로 진짜 매일 쓰던 크롬, 카카오톡 메모리가 다 바닥으로 쫓겨나 삭제(Swap-out)되는 캐시 오염(Cache Pollution) 현상이 발생한다.
📢 섹션 요약 비유: LRU는 방금 들어온 사람을 무조건 귀빈 대접합니다. 단골손님(크롬)이 10명 앉아있는 식당에, 지나가다 한 번 들른 관광객(풀 스캔) 100명이 우르르 들어오면, 주인이 단골을 다 쫓아내고 관광객을 앉히는 멍청한 짓을 저지릅니다. 관광객은 밥 먹고 영원히 떠나버리므로, 식당은 단골을 잃고 망합니다(캐시 파괴).

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

Clock (Second-Chance) 알고리즘: OS 커널의 현실적 타협: 리눅스와 윈도우는 무거운 진짜 LRU(Linked List)를 버리고, 하드웨어 비트를 활용한 가짜 LRU(Pseudo-LRU)를 쓴다.
- 원리: 페이지마다 1비트짜리 Reference Bit를 둔다. CPU가 메모리를 읽으면 하드웨어가 0을 1로 바꿔준다. (포인터 갱신 오버헤드 0%).
- 교체 시: OS 시곗바늘이 페이지를 빙빙 돌며 1이면 0으로 깎고 한 번 살려준다(Second Chance). 0이면 쫓아낸다.
- 결과: 리스트를 갱신할 필요 없이, 가장 최근에 안 쓴 놈을 $O(1)$에 가깝게 찾아내는 현대 OS 페이지 교체의 절대 표준이 되었다.
Redis 및 백엔드 애플리케이션의 LRU 아키텍처: OS 커널에서는 무거워서 못 쓰지만, Java나 C++로 짠 사용자 애플리케이션(User Space) 에서는 LRU가 만병통치약이다.
- Redis allkeys-lru: 초당 10만 건을 처리하는 Redis는 해시 테이블(Hash Table)과 이중 연결 리스트(Doubly Linked List)를 결합하여 $O(1)$의 속도로 순수 LRU를 완벽히 구현해 냈다. 10GB 메모리가 꽉 차면 얄짤없이 꼬리에 있는 놈을 날려버려 영원히 죽지 않는 불사의 캐시 서버를 만든다.
- LRU-K 와 ARC의 진화: 앞서 말한 "풀 스캔 시 캐시가 다 날아가는(Cache Pollution)" 버그를 막기 위해, 실무 DB(Oracle 등)는 LRU 큐를 2개 둔다. 한 번 읽은 놈은 '임시 큐'에 두고, 2번 이상 읽힌 진짜 단골손님만 '진짜 LRU 큐'에 올려주는 LRU-2 (혹은 ARC) 하이브리드 아키텍처를 짜서 완벽한 방어망을 구축한다.

  ┌───────────────────────────────────────────────────────────────────┐
  │     백엔드 아키텍트의 인메모리 캐시(Cache) 정책 설계 가이드라인   │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [요구사항: 초당 100만 조회가 일어나는 쇼핑몰 상품 캐시 메모리]  │
  │                                                                   │
  │   [ ❌ 단순 FIFO 또는 Random 적용 ]                               │
  │     ▶ 판정: 히트율(Hit Rate) 50% 미만. DB 부하 폭주로 서버 즉사.  │
  │                                                                   │
  │   [ 🟡 순수 LRU (Least Recently Used) 적용 ]                      │
  │     ▶ 판정: 히트율 80% 달성. 훌륭함.                              │
  │     ▶ 약점: 심야 시간에 "전체 상품 재고 동기화 배치"가 도는 순간, │
  │             캐시가 다 털려버리고 아침에 DB가 뻗음 (Pollution).    │
  │                                                                   │
  │   [ 🚀 W-TinyLFU (Caffeine Cache 등 최신 기술) 적용 ]             │
  │     ▶ 판정: 최근성(LRU)과 빈도수(LFU)를 결합한 현대 캐시의 끝판왕.│
  │     ▶ 효과: 한 번 쓱 지나가는 배치 작업은 메인 캐시에 못 들어오게 │
  │             방어하여(Admission Window), 히트율 99%를 철통 보장!   │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 단순히 LinkedHashMap으로 LRU를 짜서 실무에 올리는 시대는 지났다. 백엔드 시스템은 항상 예상치 못한 어뷰저(크롤링 봇)나 백그라운드 스캔 작업의 공격을 받는다. 진정한 아키텍트는 LRU의 약점(최근성 맹신)을 보완하기 위해 LFU(빈도수)의 철학을 한 스푼 섞은 하이브리드 캐시 엔진(Caffeine, Guava)을 선택하여 DB를 완벽히 보호한다.

📢 섹션 요약 비유: 순수 LRU는 10년 단골(자주 찾는 데이터)이든 어제 처음 온 손님이든 무조건 '어제 온 손님'을 더 우대하는 단기 기억상실증 사장님입니다. 현대의 캐시 아키텍처는 단골장부(LFU)를 따로 둬서, 어제 한 번 온 손님이 단골의 자리를 빼앗지 못하게 철저히 입구 컷(Admission Control)을 하는 똑똑한 매니저 시스템입니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

LRU 알고리즘(또는 그 파생형인 Clock)을 메모리 시스템에 적용하면, 한정된 램(RAM) 용량으로도 미래의 데이터 접근 패턴을 90% 이상 정확히 예측해 냄으로써 페이지 폴트(디스크 I/O) 빈도를 획기적으로 줄여 시스템 스루풋(Throughput)을 수백 배 상승시킬 수 있다.

결론 및 미래 전망

LRU는 "참조의 지역성(Locality)"이라는 컴퓨터 공학의 신성한 법칙을 교체 알고리즘으로 치환해 낸 영원한 마스터피스다. 1970년대에 발명되었지만 50년이 지난 지금도 CPU의 L1 캐시부터 웹 브라우저의 이미지 캐시, CDN(Content Delivery Network)의 에지 캐시까지 모든 IT 인프라의 데이터를 버리는(Eviction) 절대 1원칙으로 군림하고 있다. 미래에는 이 LRU의 약점인 "오버헤드"와 "스캔 공격 취약점"을 해결하기 위해, 인공지능(Machine Learning)이 메모리 접근 패턴을 실시간으로 학습하여 미래에 쓸 페이지를 미리 예측해 프리패치(Prefetch)하고, 안 쓸 페이지를 알아서 밀어버리는 **'머신러닝 기반 캐시 교체(ML-based Cache Replacement)'**가 차세대 클라우드 인프라의 표준이 될 것이다.

📢 섹션 요약 비유: LRU는 '과거의 통계'로 내일을 예측하는 일기예보입니다. 완벽하진 않지만 이것 없이 항해를 할 순 없습니다. 미래에는 과거 통계뿐만 아니라 기압과 바람의 방향까지 AI가 분석하여 1분 뒤의 날씨를 100% 맞춰내는 슈퍼 일기예보(AI 스케줄링)의 시대로 진화할 것입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
페이지 교체 (Page Replacement)	LRU가 자신의 진가를 뽐내는 잔혹한 생존 서바이벌 무대다.
참조의 지역성 (Locality)	LRU 알고리즘이 "방금 쓴 놈은 나중에도 쓴다"며 맹신하고 기대는 위대한 통계적 법칙이다.
클럭 알고리즘 (Clock / NUR)	LRU가 너무 무거워서 커널이 쓸 수 없자, 하드웨어 비트를 이용해 LRU를 흉내 내도록 만든 실무형 짝퉁(?) LRU다.
FIFO (First-In, First-Out)	최근성(Recency)을 개나 줘버리고 들어온 순서대로 쫓아냈다가 벨라디의 모순에 빠진 LRU의 한심한 선배다.
Belady의 모순 (Anomaly)	LRU는 이 모순(램 늘렸는데 느려짐)에 절대 빠지지 않는다는 수학적 면역력(Stack Algorithm)을 가지고 있다.

👶 어린이를 위한 3줄 비유 설명

장난감 상자에 장난감을 3개만 넣을 수 있는데 4번째 새 장난감이 생겼어요. 누굴 버려야 할까요?
멍청한 규칙(FIFO)은 "제일 먼저 산 1번 로봇 버려!"라고 해요. 근데 1번 로봇은 내가 매일 가지고 노는 제일 좋아하는 장난감이라 버리면 매일 슬퍼요.
똑똑한 LRU 규칙은 "산 지 얼마나 됐는지는 상관없고, 최근 한 달 동안 한 번도 안 꺼내 놀았던 먼지 쌓인 팽이를 버리자!"라고 판단하는 아주 합리적인 방법이랍니다!