페이지 교체 알고리즘 (Page Replacement Algorithms)

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

본질: 페이지 교체 알고리즘(Page Replacement Algorithm)은 빈 프레임이 없을 때 발생하는 페이지 폴트 상황에서, 디스크로 내쫓을 희생양(Victim) 페이지를 결정하는 운영체제의 생존 수식이다.

가치: 10만 배의 지연을 일으키는 디스크 I/O를 최소화하기 위해 **"어떤 놈을 쫓아내야 앞으로 가장 오랫동안 폴트가 안 날까?"**를 통계적으로 예측하여 시스템 전체의 실질 접근 시간(EAT)을 방어한다.

융합: 이상적인 예측 불가의 OPT(최적) 알고리즘을 롤모델로 삼아, FIFO의 맹점을 깨고 '지역성(Locality)'에 기반한 **LRU(Least Recently Used)**가 등장했으며, 이는 다시 하드웨어의 지원을 받는 근사(Approximation) 알고리즘들로 융합되어 현대 OS에 안착했다.

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

개념: 램(RAM)이 꽉 찼을 때 1. 누굴 버릴 것인가?, 2. 그 빈자리에 뭘 가져올 것인가?를 정하는 철학이다. 수많은 페이지가 메모리에 깔려있을 때, 운영체제는 이 살생부 알고리즘을 돌려 단 한 장의 카드를 스왑(Swap) 디스크로 던져버린다.
필요성: 만약 OS가 무지성으로 "아무거나 맨 앞의 것을 지워!"라고 결정했는데, 하필 그 지워진 페이지가 0.1초 뒤에 또 쓰일 for 문의 핵심 변수였다면? 지운 지 0.1초 만에 또 페이지 폴트가 터져서 디스크를 긁어와야 한다(스래싱). 희생양 하나를 잘못 고른 대가는 무려 800만 나노초의 지연이다. 이 무시무시한 페널티를 막기 위해, OS는 과거의 기록을 샅샅이 뒤져 "가장 쓸모없는 쓰레기"를 골라내는 눈썰미가 필요했다.
💡 비유: 페이지 교체 알고리즘은 구단주의 방출 선수 명단 작성과 같다. 연봉 한도(RAM 용량)가 꽉 찼는데 초특급 유망주(새 페이지)를 데려오고 싶다면 누군가를 방출(Swap-out)해야 한다.
- FIFO 구단주: "제일 옛날에 입단한 늙은 선수부터 쳐내!" (-> 노련한 주장을 잘라서 팀이 망함).
- OPT 구단주: "나는 미래를 보는 초능력자다. 내년에 제일 안 뛸 선수를 쳐내!" (-> 불가능함).
- LRU 구단주: "최근 10경기 동안 한 번도 출전 안 한 놈을 쳐내자. 과거를 보면 미래가 보인다!" (-> 매우 합리적).
등장 배경 및 알고리즘의 진화 트랙:
1. 초창기 (FIFO): 구현이 쉬워서 그냥 들어온 순서대로 쫓아냈다. (Belady의 모순 터짐).
2. 이론적 한계점 (OPT): "미래를 안다면 완벽할 텐데..."라는 기준점을 세움.
3. 지역성(Locality)의 발견: "가까운 과거에 쓴 놈은 곧 또 쓴다"는 법칙을 깨닫고, 과거의 빈도(LFU)나 최근 사용 시점(LRU)을 추적하는 똑똑한 알고리즘으로 진화함.

┌───────────────────────────────────────────────────────────────────────────┐
│        페이지 교체 알고리즘의 목표: Page Fault 횟수 최소화 시각화         │
├───────────────────────────────────────────────────────────────────────────┤
│                                                                           │
│ [ 상황: 램 프레임 3개 / 호출 스트링: 1 -> 2 -> 3 -> 4 -> 1 ]              │
│                                                                           │
│ ▶ 멍청한 알고리즘 (예: FIFO)                                              │
│   [1] [2] [3] 까지 꽉 참.                                                 │
│   '4'가 들어오려 할 때 제일 오래된 '1'을 버림.                            │
│   [4] [2] [3] 상태가 됨.                                                  │
│   앗! 바로 다음 호출이 '1'이네? 또 '2'를 버리고 '1'을 가져옴! (폴트 폭발) │
│                                                                           │
│ ▶ 똑똑한 알고리즘 (예: LRU/OPT)                                           │
│   [1] [2] [3] 꽉 찬 상태에서 '4'가 올 때,                                 │
│   "1은 1초 뒤에 또 부르니까 절대 안 돼! 아까 쓴 '2'를 버리자!"            │
│   [1] [4] [3] 상태가 됨.                                                  │
│   그다음 호출 '1'이 들어올 때? 어, 램에 이미 있네! (Hit 적중!)            │
└───────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 짧은 예시가 모든 걸 말해준다. OS의 단 한 번의 판단 미스가 연쇄적인 폴트(Cascade Fault)를 낳는다. "누구를 버릴 것인가"는 결국 "누가 가장 오랫동안 내게 필요 없을 것인가"라는 치열한 통계적 미래 예측 게임이다.

📢 섹션 요약 비유: 냉장고(램)가 꽉 찼을 때 새 반찬(새 페이지)을 넣기 위해, 유통기한이 제일 오래 남은 반찬을 버리는 게 아니라 "우리 식구가 제일 안 먹을 것 같은 반찬"을 귀신같이 골라내서 버리는 엄마의 눈썰미가 바로 교체 알고리즘입니다.

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

Reference String (참조열) 기반의 성능 평가

알고리즘의 성능을 평가할 때는 실제 프로그램이 내뿜는 수백만 개의 주소를 다 보지 않는다. 페이지 교체는 '페이지 번호'가 바뀔 때만 일어나므로, 4KB 안에서의 오프셋 변동은 전부 무시하고 오직 **"페이지 번호의 순서(Reference String)"**만을 추출하여 시뮬레이션을 돌린다.

주소 트레이스: 0x0100, 0x0150, 0x0200, 0x0100, 0x0400...
이를 100단위 페이지 번호로 압축: 1, 1, 2, 1, 4...
연속된 중복 제거: 1, 2, 1, 4 (이것이 참조열!)
OS 학자들은 이 참조열을 각 알고리즘에 넣고 돌려서 "누가 폴트(Fault) 횟수가 제일 적은지"를 겨루어 챔피언을 가린다.

알고리즘의 분류와 진화 계보

현존하는 모든 교체 알고리즘은 아래 3가지 철학 중 하나에 뿌리를 두고 있다.

시간 기반 (Time-based):
- FIFO (First-In First-Out): 가장 먼저 들어온 페이지를 쫓아낸다. (멍청함)
- LRU (Least Recently Used): 가장 오랫동안 '사용(참조)'되지 않은 놈을 쫓아낸다. (대세)
빈도 기반 (Frequency-based):
- LFU (Least Frequently Used): 과거에 가장 '적게' 불린 놈을 쫓아낸다. (참조 횟수 카운트)
- MFU (Most Frequently Used): 가장 '많이' 불린 놈을 쫓아낸다. (역발상: 적게 불린 건 방금 올라온 놈일 테니 살려두자).
근사/하드웨어 보조 (Approximation):
- Clock (2차 기회 알고리즘): LRU가 너무 무거워서, 참조 비트(R 비트) 하나만 가지고 시계바늘을 돌리며 LRU를 '흉내' 낸다. (현대 OS의 실질적 지배자).

📢 섹션 요약 비유: 회사에서 구조조정을 할 때 "제일 오래 다닌 사람을 자르자(FIFO)", "실적이 제일 없는 사람을 자르자(LFU)", "최근 한 달 동안 제일 논 사람을 자르자(LRU)"라고 기준을 세우며 피 터지게 싸우는 인사팀의 회의와 같습니다.

Ⅲ. 융합 비교 및 다각도 분석

비교 1: 5대 페이지 교체 알고리즘 대격돌

면접과 실무를 관통하는 핵심 5대 알고리즘의 장단점 비교다.

알고리즘	교체 기준 (Victim)	장점	단점 및 한계
OPT (최적)	앞으로 가장 오랫동안 안 쓸 페이지	Page Fault 횟수가 수학적으로 가장 적음 (1등)	미래를 알 수 없어 구현 불가능 (비교 연구용)
FIFO	램에 가장 먼저 들어온 페이지	구현이 Queue 하나면 끝나서 매우 간단함	중요한 변수(가장 먼저 선언됨)가 자꾸 쫓겨나 성능 박살 남
LRU	가장 오랫동안 안 본 페이지	OPT에 가장 근접한 현실적 최강의 성능 달성	모든 페이지의 타임스탬프를 갱신해야 해서 오버헤드 최악
LFU	참조 횟수가 가장 적은 페이지	장기적인 빈도를 반영하여 합리적임	초반에 반짝 쓰인 찌꺼기 페이지가 카운트만 높아서 평생 안 쫓겨남
Clock (2차 기회)	참조 비트가 0인 (최근 안 쓴) 페이지	LRU와 성능은 비슷한데 오버헤드가 거의 없음	현대 OS(리눅스, 맥)가 채택한 최종 승리자

왜 빈도(LFU, MFU)는 멸종했는가?

LFU(최소 빈도)는 논리적으로 완벽해 보이지만, 실제 프로그램의 '페이즈 트랜지션(Phase Transition)'을 반영하지 못한다.

상황: 프로그램 초반에 Init() 함수가 불리며 1만 번 호출되었다(카운트 10000). 이후 게임이 시작되며 Draw() 함수가 100번 불렸다(카운트 100).
램이 모자라서 쫓아내야 할 때, LFU는 카운트가 100밖에 안 되는 Draw() 함수를 쫓아낸다!
정작 Init()은 초기화 끝나서 영원히 안 쓸 쓰레기인데 카운트가 10000이라서 램에 영원히 알박기를 해버린다. 이 치명적인 맹점 때문에 카운팅 기반 알고리즘은 교과서에서나 배우고 실제 커널에선 쓰이지 않는다.

┌──────────┬────────────┬────────────┬──────────────────────────────────────┐
│ 평가 요소  │ LRU (최근)  │ LFU (빈도)  │ Clock (근사)                     │
├──────────┼────────────┼────────────┼──────────────────────────────────────┤
│ 찌꺼기 처리│ 완벽 (즉시 버림)│ 최악 (알박기 함)│ 훌륭 (서서히 버림)       │
│ 하드웨어 짐│ 무거움 (시간 기록)│ 무거움 (숫자 더함)│ **가벼움 (비트 1개)**│
└──────────┴────────────┴────────────┴──────────────────────────────────────┘

[매트릭스 해설] 컴퓨터 알고리즘의 세계에서 "과거의 기억(Time)"이 "과거의 누적 횟수(Frequency)"를 이긴 대표적인 사례다. 그리고 그 무거운 시간 기록조차 버리고, "최근에 썼어(1) 안 썼어(0)?"라는 극단적 흑백 논리(Clock)로 최적화한 것이 공학의 승리다.

📢 섹션 요약 비유: 옷장 정리할 때 "내가 이 옷을 살면서 총 100번 입었지(LFU)" 하며 고집부리는 사람은 유행 지난 촌스러운 옷을 평생 못 버립니다. 반면 "이 옷 안 입은 지 1년 넘었네(LRU)" 하며 쿨하게 버리는 사람이 옷장을 항상 트렌디(Working Set)하게 유지합니다.

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

실무 시나리오: CDN 및 웹 캐시(Redis, Memcached)에서의 LRU 알고리즘

상황: OS의 커널 메모리뿐만 아니라, 백엔드 개발자가 쓰는 메모리 캐시 DB(Redis)에서도 이 페이지 교체 알고리즘이 100% 똑같이 적용된다.
Redis의 maxmemory-policy:
- Redis 램을 2GB로 제한해 두었는데 데이터가 꽉 찼다.
- 이때 Redis 설정에 allkeys-lru를 주면, 수백만 개의 Key 중 가장 오랫동안 조회(GET)되지 않은 Key부터 쓰레기통에 버리며 새로운 데이터를 받는다.
- 만약 volatile-lfu를 주면 조회 빈도(횟수)가 적은 놈부터 버린다.
- 결론: 캐시 시스템을 운영하는 엔지니어는 자신의 비즈니스가 '최근 뜬 핫이슈 뉴스(LRU 유리)'인지, '스테디셀러 상품(LFU 유리)'인지 파악하여 이 교체 알고리즘을 튜닝하는 것이 실무 1순위 역량이다.

Database 버퍼 풀(Buffer Pool)의 변종 LRU (Midpoint Insertion)

MySQL의 InnoDB 스토리지 엔진은 단순한 LRU를 쓰지 않는다.

누군가 100GB짜리 테이블을 SELECT *로 풀 스캔(Full Scan) 해버리면?
100GB의 쓰레기 데이터가 들어오면서 기존에 잘 쓰고 있던 캐시를 LRU 논리에 의해 모조리 다 밀어내버린다(Buffer Pool Pollution).
이를 막기 위해 MySQL은 LRU 리스트를 Old/New 구역으로 나누고, 새로 들어온 데이터는 머리(Head)가 아니라 중간(Midpoint)에 꽂아 넣어서, 진짜 자주 불리는 놈만 New 구역으로 살려주는 **'변형 LRU'**를 독자적으로 쓴다. (실무 DB 최적화의 정수다).
📢 섹션 요약 비유: 식당 매니저(MySQL)가 일반 손님(단순 LRU)은 문 앞 대기석(Old 구역)에 먼저 앉히고, 진짜 단골(자주 찔리는 데이터)인 걸 확인해야만 VIP석(New 구역)으로 모십니다. 웬 뜨내기 단체 손님(풀 스캔) 100명이 우르르 몰려와도 VIP석 손님은 절대 쫓겨나지 않게 보호하는 고급 관리 스킬입니다.

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

정량/정성 기대효과

구분	내용
EAT(실질 접근 시간) 방어	디스크 I/O를 유발하는 페이지 폴트 확률($p$)을 기하급수적으로 낮추어 메모리 성능을 램 스피드에 수렴시킴
워킹 셋(Working Set) 유지	프로세스의 런타임 행동 패턴(지역성)을 귀신같이 추적하여, 당장 필요한 핵심 데이터가 절대 램에서 쫓겨나지 않게 보호
캐시 경제학의 표준 정립	하드웨어 L1 캐시부터 CDN 클라우드 서버까지, 모든 '용량 제한 저장소'가 데이터를 관리하는 절대적인 알고리즘 뼈대를 제공

결론 및 미래 전망

페이지 교체 알고리즘 (Page Replacement Algorithms)은 "모든 것을 가질 수 없다면, 가장 쓸모없는 것부터 우아하게 버려라"라는 컴퓨터 과학의 미니멀리즘 철학이다. 완벽한 예지력(OPT)을 갈망했던 인간은 결국 하드웨어의 벽에 막혀 과거를 돌아보는 지혜(LRU)를 택했고, 그마저도 무거워 시곗바늘을 돌리는 근사치(Clock)와 타협했다. 이 타협의 역사는 완벽함보다 '가성비(Heuristics)'가 시스템 설계에서 얼마나 중요한지를 가르쳐 준다. 향후 기계학습(ML) 칩이 발전하면, CPU 내부에서 OS 대신 인공지능이 프로그램의 동작 패턴을 학습하여 "3초 뒤에 이 페이지를 버리게 될 거야"라고 OPT(최적 교체)에 한없이 수렴하는 예측을 던져주는 AI 기반 페이지 교체 시대가 열릴 것이다.

📢 섹션 요약 비유: 다이어트할 때 "이 세상 모든 맛있는 걸 먹으면서 살을 빼겠다(OPT)"는 불가능한 꿈을 버리고, "어제 안 먹은 야채를 먹고 오늘 찐 살은 버린다(LRU)"는 현실적인 타협을 통해 건강(시스템 성능)을 유지해 나가는 현명한 생존 전략입니다.

📌 관련 개념 맵 (Knowledge Graph)

OPT (Optimal Replacement) | 미래에 가장 오랫동안 안 쓸 놈을 버린다는, 현실에서 불가능하지만 모든 알고리즘이 도달하고 싶어 하는 꿈의 벤치마크
LRU (Least Recently Used) | 최근에 안 쓴 놈이 앞으로도 안 쓸 거라는 지역성에 기반한, 현대 캐시 시스템의 절대적인 바이블
Belady의 모순 (Belady's Anomaly) | FIFO를 쓸 때 램(프레임)을 더 늘려줬는데 오히려 페이지 폴트가 늘어나는 엽기적인 버그 현상
Clock Algorithm (2차 기회) | 1비트짜리 참조 비트 하나로 룰렛을 돌려 LRU를 미친 듯이 싼값에 흉내 내는 리눅스의 진짜 교체 엔진
스래싱 (Thrashing) | 이 훌륭한 교체 알고리즘들도 전체 램 용량이 턱없이 부족하면 결국 모두를 쫓아내며 시스템을 뻗게 만드는 한계점

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

페이지 교체 알고리즘이 뭔가요? 장난감 상자에 5개만 들어가는데 내가 6번째 장난감을 꺼내 놀고 싶을 때, "상자에 있는 5개 중 누굴 버려야 제일 후회를 안 할까?" 고민하는 똑똑한 공식이에요.
어떻게 고르면 되나요? 처음엔 그냥 "제일 먼저 들어간 장난감을 버리자(FIFO)"고 했는데, 그게 내가 젤 좋아하는 애착 인형이라 엉엉 울었어요.
그럼 어떻게 버려야 똑똑하나요? 엄마가 "최근 한 달 동안 네가 한 번도 안 쳐다본 낡은 로봇(LRU)을 버리자"라고 하니까, 내가 버린 줄도 모르고 행복하게 새 장난감을 놀 수 있었답니다!