260. 페이지 교체 (Page Replacement)

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

본질: 페이지 교체는 시스템의 물리적 메모리(RAM)가 꽉 찼을 때, CPU가 새로 요구한 페이지를 적재하기 위해 현재 램에 올라와 있는 페이지 중 하나를 골라 디스크(Swap)로 내쫓는(Swap-out) 운영체제의 생존 매커니즘이다.

가치: 이 메커니즘 덕분에 실제 물리 메모 용량의 한계를 초월하여 수백 GB의 가상 메모리(Virtual Memory)를 사용자에게 제공할 수 있는 궁극의 **다중 프로그래밍 환상(Illusion)**이 완성된다.

융합: "누구를 내쫓을 것인가?"를 결정하는 교체 알고리즘(LRU, LFU, Clock 등)은 참조의 지역성(Locality)이라는 통계적 법칙과 융합하여, 페이지 폴트(Page Fault)를 최소화하고 스래싱(Thrashing)을 방어하는 최전선 방어막 역할을 수행한다.

Ⅰ. 개요 및 필요성

개념: 빈 프레임(Free Frame)이 0개인 상태에서 페이지 폴트가 발생했을 때, OS가 희생양(Victim) 페이지를 선정하여 디스크에 쓰고 빈 공간을 확보한 뒤, 그 자리에 새로운 페이지를 올려놓는 일련의 과정이다.
필요성: 컴퓨터의 램(RAM)은 유한하지만 프로그램의 욕심은 무한하다. 16GB 램을 가진 컴퓨터에서 30GB짜리 게임과 10GB짜리 크롬을 동시에 실행하면 언젠가는 램이 100% 꽉 차게 된다. 꽉 찼다고 컴퓨터를 멈추거나 에러를 뱉게 할 순 없다. "안 쓰는 짐을 창고에 던져놓고 새 짐을 들여오자"는 우아한 타협이 필요했다.
등장 배경: 요구 페이징(Demand Paging) 시스템이 활성화되면서 "디스크에서 가져오는 기술"은 완성되었으나, "어떻게 자리를 비워줄 것인가"에 대한 최적화가 운영체제 성능의 99%를 좌우하게 되었다. 1970년대 벨 연구소 등에서 최적(Optimal) 교체부터 LRU까지 수많은 알고리즘이 쏟아져 나오며 학문적 전성기를 맞이했다.

  [페이지 교체(Page Replacement)의 4단계 라이프사이클]

  [ 🚨 물리 메모리(RAM) 100% Full 상태에서 Page Fault 발생! ]
  
  1. 희생자 선정 (Victim Selection)
     ▶ OS 스케줄러: "LRU 알고리즘 돌려봐! 제일 안 쓴 놈 누구야?"
     ▶ "Frame 3번에 있는 Page A가 1시간째 안 쓰였습니다!"
     
  2. Swap-Out (디스크 쓰기)
     ▶ Page A가 램에 올라온 이후로 값이 수정(Dirty)되었다면, 디스크에 덮어쓴다.
     ▶ (수정 안 됐으면 덮어쓸 필요 없이 그냥 버림. 속도 개이득!)
     ▶ 페이지 테이블에서 Page A의 상태를 Invalid(i)로 바꾼다.
     
  3. Swap-In (새 페이지 적재)
     ▶ 방금 비워진 Frame 3번 자리에, 지금 당장 필요한 Page B를 디스크에서 퍼 올린다.
     
  4. 테이블 갱신 및 재시작
     ▶ 페이지 테이블에 "Page B는 Frame 3에 있음"을 적고 Valid(v)로 켠다.
     ▶ 멈췄던 CPU 명령어를 다시 실행한다.

[다이어그램 해설] 페이지 교체는 단순히 자리를 바꾸는 게 아니다. "디스크 쓰기(Swap-Out)"와 "디스크 읽기(Swap-In)"라는 최악의 오버헤드가 연속으로 터지는(최대 2,000만 ns 소요) 끔찍한 과정이다. 운영체제가 이 과정을 얼마나 덜 일어나게(Page Fault Rate 감소) 알고리즘을 짜느냐가 아키텍트의 실력을 증명한다.

📢 섹션 요약 비유: 냉장고(RAM)가 꽉 찼는데 마트에서 수박(새 페이지)을 사 왔습니다. 수박을 넣으려면 유통기한이 지났거나 안 먹는 반찬(Victim)을 골라 쓰레기통(디스크)에 버려야 합니다. 이때, 내일 아침 당장 먹을 반찬을 버리면 낼 아침에 또 마트에 가야 하는 대참사가 일어납니다. 누구를 버릴지 고르는 센스가 교체의 핵심입니다.

Ⅱ. 아키텍처 및 핵심 원리

교체 대상 선정을 위한 2가지 하드웨어 비트 (Hardware Bits)

OS가 소프트웨어로만 "누가 가장 오래됐나?"를 추적하면 CPU가 터진다. 그래서 CPU 내장 MMU 하드웨어가 페이지 테이블에 2개의 힌트 비트를 몰래 적어둔다.

Reference Bit (참조 비트 / Accessed Bit)
- 의미: "최근에 이 페이지를 누군가 한 번이라도 읽거나 썼는가?"
- 동작: CPU가 이 페이지를 건드리는 순간 하드웨어가 0에서 1로 바꾼다. OS는 가끔씩 이걸 0으로 초기화해 주며, 교체 시 1인 놈은 살려주고 0인 놈을 죽인다.
Dirty Bit (수정 비트 / Modify Bit)
- 의미: "이 페이지가 램에 올라온 이후로 내용이 변경되었는가?"
- 동작: CPU가 이 페이지에 Write 명령을 때리는 순간 1로 바뀐다.
- 가치 (극강의 최적화): 만약 희생자로 선정된 페이지가 Dirty Bit = 0 이라면? 램과 디스크의 내용이 100% 똑같다는 뜻이므로, 굳이 디스크에 쓸(Swap-out) 필요 없이 그냥 램에서 지워버려도 무방하다. 디스크 I/O 시간을 절반으로 줄여주는 최고의 치트키다.

교체의 2대 철학: Global vs Local Replacement

램이 부족할 때 "누구의 것을 뺏을 것인가?"에 대한 운영체제의 철학적 선택이다.

전역 교체 (Global Replacement):
- "시스템 전체의 모든 페이지 중 만만한 놈 뺏어!"
- A가 메모리가 부족하면, 잘 돌고 있는 B나 C의 메모리도 뺏어버린다.
- 장점: 전체 램의 효율성이 극대화된다. 단점: A 때문에 C가 렉이 걸리는 연대 책임(스래싱 전염)이 발생한다. (현대 Windows, Linux의 기본 정책).
지엽적 교체 (Local Replacement):
- "너한테 할당된 프레임 풀 안에서만 뺏고 버려!"
- A가 메모리 부족하면 A가 쓰던 옛날 페이지만 버릴 수 있다.
- 장점: 한 놈의 렉이 다른 프로세스에 절대 전이되지 않는다(안정성). 단점: A는 터지기 일보 직전인데 B의 메모리가 텅텅 비어있어도 빌려 쓸 수 없어 전체 시스템 효율이 박살 난다.
📢 섹션 요약 비유: Global 교체는 공산주의식 징발입니다. "국가(OS)가 급하니까 옆집 부자의 쌀통(메모리)을 털어서 배고픈 놈한테 줘라!" Local 교체는 철저한 자본주의입니다. "네가 배고프면 네가 가진 낡은 구두를 팔아서 쌀을 사라, 남의 집 쌀은 절대 못 건드린다!"

Ⅲ. 비교 및 연결

페이지 교체 알고리즘 3대장 스펙 비교

"미래를 아는 신(OPT)" vs "과거를 기억하는 자(LRU)" vs "시계바늘을 돌리는 자(Clock)"

알고리즘	선정 기준 (누구를 쫓아내는가?)	구현 난이도	특징 및 한계
OPT (Optimal)	"미래에 가장 오~랫동안 안 쓸 놈"을 쫓아냄	구현 불가 (신만이 미래를 안다)	모든 알고리즘 성능 평가의 비교 기준점(Theoretical Bound) 역할.
FIFO	"메모리에 가장 먼저 들어온(오래된) 놈" 쫓아냄	극강 단순 (큐 구조)	Belady's Anomaly(모순) 발생! 램을 늘려줬는데 오히려 폴트가 더 터짐.
LRU (Least Recently Used)	"과거에 가장 오~랫동안 안 쓴 놈" 쫓아냄	이론상 쉬우나 실무에선 무거움	참조 지역성을 가장 잘 반영한 황제. (단, 연결 리스트 오버헤드가 큼).

LRU의 실무적 한계와 클럭(Clock) 알고리즘의 탄생

교과서에서는 LRU가 최고라고 배운다. 하지만 프로세스가 메모리를 참조할 때마다(1초에 수억 번) LRU 연결 리스트의 순서를 맨 뒤로 옮기는 짓을 OS가 하면 CPU는 다른 연산을 아무것도 못 한다. 현대 OS의 타협 (Clock / NUR 알고리즘):

OS는 1초에 수억 번 감시하는 걸 포기했다.
대신 프레임들을 시계 모양(원형 큐)으로 배치하고, 바늘(Pointer)이 빙글빙글 돈다.
바늘이 가리키는 페이지의 Reference Bit를 본다.
- 1이면? "최근에 썼구나, 기회를 한 번 더 줄게!" 하고 0으로 바꾼 뒤 다음 바늘로 넘어간다.
- 0이면? "내가 한 바퀴 돌고 올 때까지 한 번도 안 썼네? 넌 아웃!" 하고 즉시 교체해 버린다.
이 Clock(Second-Chance) 기법이 바로 현대 리눅스와 윈도우, 데이터베이스 버퍼 풀이 사용하는 실전용 LRU 근사치 알고리즘이다.
📢 섹션 요약 비유: 진짜 LRU는 백화점 주차요원이 "이 차가 정확히 몇 시 몇 분에 들어왔는지" 초 단위로 장부를 쓰는 겁니다(과로사). Clock 알고리즘은 요원이 주차장을 빙빙 돌면서, 차 유리에 먼지가 없으면(Ref=1) 먼지를 묻히고(Ref=0) 지나갑니다. 한 바퀴 돌고 왔는데 여전히 먼지가 쌓여있으면(Ref=0) 오랫동안 안 탔다고 확신하고 견인해 버리는 천재적인 꼼수입니다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

Linux 서버의 Swappiness 파라미터 튜닝: 시스템 엔지니어가 리눅스 서버 커널을 튜닝할 때 가장 먼저 건드리는 값이다.
- vm.swappiness (0 ~ 100): "OS야, 램이 부족할 때 파일 캐시(Page Cache)를 먼저 버릴래, 아니면 유저 애플리케이션의 메모리를 스왑 아웃(Swap-out) 시킬래?"를 결정하는 성향 값이다.
- 실무 튜닝: 디폴트 60을 쓰면 DB 서버가 수시로 앱 메모리를 디스크로 내쫓아버려(Swap-out) API 지연이 1초씩 튄다.
- 아키텍트 결단: Hadoop이나 Elasticsearch 같은 메모리 깡패 서버에서는 무조건 swappiness = 1 또는 0으로 세팅한다. "애플리케이션 메모리는 절대 내쫓지 말고(Swap 금지), 차라리 OS가 쥐고 있는 파일 캐시를 먼저 쫓아내라!"라고 강제하여 스래싱을 막는다.
LRU Cache (Redis, Memcached)의 만능화: OS의 페이지 교체 이론은 백엔드 애플리케이션의 아키텍처로 100% 이식되었다.
- Redis(인메모리 캐시)를 쓸 때, 메모리가 maxmemory에 도달하면 데이터를 어떻게 버릴지 정책을 정해야 한다.
- allkeys-lru: Redis에 들어있는 모든 키 중 가장 오래 안 쓴 놈을 지운다. (LRU의 완벽한 실무적 현현).
- 이 설정 하나만 잘 맞춰도 DB로 쏟아지는 트래픽의 90%를 막아내고 "스스로 오래된 찌꺼기를 치우며 자가 생존하는" 무한 캐시 시스템이 완성된다.

  ┌──────────────────────────────────────────────────────────────────────┐
  │     백엔드 In-Memory 시스템 캐시 교체 정책(Eviction Policy) 트리     │
  ├──────────────────────────────────────────────────────────────────────┤
  │                                                                      │
  │   [요구사항: 10GB 용량의 Redis 캐시 서버 운영. 꽉 찼을 때 어떡할까?] │
  │                                                                      │
  │   [ 1. No Eviction (버리지 않음) ]                                   │
  │     ▶ 작동: 10GB 꽉 차면 OOM 에러 뱉고 새 데이터 쓰기 거부!          │
  │     ▶ 사용처: 절대로 데이터가 유실되면 안 되는 '세션 저장소' 등.     │
  │                                                                      │
  │   [ 2. AllKeys-LRU (가장 안 쓰는 놈 버림) ]                          │
  │     ▶ 작동: 최근에 찾지 않은 오래된 캐시부터 조용히 날려버림.        │
  │     ▶ 사용처: 웹페이지 HTML 캐싱, 상품 정보 (90% 실무의 디폴트).     │
  │                                                                      │
  │   [ 3. AllKeys-LFU (가장 인기 없는 놈 버림) ]                        │
  │     ▶ 작동: 빈도수(Frequency)를 체크하여, 가장 조회수가 낮은 놈 처형.│
  │     ▶ 사용처: 최신순보다 "누적 인기순"이 중요한 랭킹 시스템 보드 등. │
  └──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "메모리가 부족하면 지워라"라는 OS의 철학을 100% 이해한 개발자는, Redis나 애플리케이션 로컬 캐시(Caffeine Cache)를 짤 때도 반드시 이 Eviction Policy(교체 정책)를 설계에 박아 넣는다. 쫓아내는 정책(LRU)이 없는 캐시는 캐시가 아니라 곧 서버를 찢어발길 '메모리 릭(Memory Leak)' 시한폭탄에 불과하다.

📢 섹션 요약 비유: 구글 포토 용량(15GB)이 꽉 찼을 때, 1번 정책은 "더 이상 사진 못 찍음(에러)"입니다. 2번 LRU 정책은 "10년 전에 찍고 한 번도 안 열어본 옛날 사진부터 몰래 지우기"입니다. 3번 LFU 정책은 "최근에 찍었더라도 내가 하트(빈도수)를 안 누른 인기 없는 사진부터 지우기"입니다. 목적에 맞게 버리는 기술이 캐싱의 전부입니다.

Ⅴ. 기대효과 및 결론

기대효과

페이지 교체 알고리즘(LRU, Clock)을 완벽하게 튜닝하면, 물리적 메모리가 16GB밖에 없는 서버라도 수십 명의 사용자가 체감하는 페이지 폴트(렉)를 1% 미만으로 억제하며 100GB급 서버처럼 느끼게 만드는 마술 같은 가용성 확장을 이룩할 수 있다.

결론 및 미래 전망

페이지 교체 기술은 하드 디스크 시대의 1,000만 나노초에 달하는 지연을 덮기 위해 잉태된 방어막이었다. 하지만 NVMe SSD가 RAM의 속도를 맹추격하고, 클라우드의 노드(서버) 스펙이 RAM 1TB를 우습게 넘기면서, 이 무거운 스왑-아웃(교체) 시스템은 오히려 계륵이 되고 있다. K8s 중심의 클라우드 네이티브 환경은 "느리게 램을 비우며(Swap) 버티지 말고, 차라리 쿨하게 죽고(OOM Kill) 새 컨테이너를 다른 노드에 띄워라(Fail-fast)"라는 철학으로 선회했다. 미래에는 디스크와 램이 교체되는 것이 아니라, CXL(Compute Express Link) 기반의 **메모리 풀링(Memory Pooling)**을 통해 여러 대의 서버가 하나의 거대한 RAM을 랙(Rack) 단위로 동적 공유하며, 페이지를 '디스크로 내쫓는' 대신 '옆 서버의 남는 램으로 빛의 속도로 이사 보내는' 진정한 초연결 메모리 시대로 진화할 것이다.

📢 섹션 요약 비유: 옛날엔 내 방(RAM)에 짐이 꽉 차면 무조건 지하 창고(디스크)에 버리고 왔습니다(페이지 교체). 미래의 시스템(CXL, 클라우드)은 내 방이 꽉 차면 벽이 스르륵 열리면서 옆집 빈방(다른 서버의 RAM)과 연결되어, 창고에 다녀올 필요 없이 1초 만에 짐을 옆방으로 밀어버리는 무한 확장의 공간 마법을 실현합니다.

📌 관련 개념 맵

개념	연결 포인트
스케줄러 일드 (sched_yield)	현재 개념으로 들어오기 전에 함께 이해하면 경계가 선명해지는 기반 개념이다.
ABA 문제	현재 개념이 등장하게 만든 직접적인 선행 흐름이다.
장벽 (Barrier) 동기화	현재 개념이 구현·세분화될 때 바로 연결되는 후속 개념이다.
양방향 랑데부 (Rendezvous)	확장 학습이나 심화 비교로 이어지는 다음 단계의 키워드다.

📈 관련 키워드 및 발전 흐름도

[ABA 문제]
    │
    ▼
[페이지 교체 (Page Replacement)]
    │
    ├──▶ [장벽 (Barrier) 동기화]
    └──▶ [양방향 랑데부 (Rendezvous)]

이 흐름도는 선행 개념에서 현재 개념으로 넘어온 뒤, 구현 세분화와 후속 확장으로 이어지는 학습 순서를 압축해 보여준다.

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

내 책상(RAM)에는 책을 3권만 놓을 수 있는데, 4번째 책을 보려면 어떻게 해야 할까요? 맞아요, 지금 책상에 있는 3권 중 1권을 서랍(디스크)에 넣어야 해요.
이때 **"어떤 책을 서랍에 넣을까?"**를 고민하는 게 바로 페이지 교체예요.
가장 똑똑한 방법(LRU 알고리즘)은 "가장 오~~래동안 한 번도 안 들여다본 먼지 쌓인 책"을 고르는 거랍니다. 그래야 당장 또 찾을 일이 적으니까요!