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

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

  1. 본질: 페이지 교체 알고리즘 (Page Replacement Algorithm)은 물리 메모리(RAM)에 빈 프레임이 없을 때, 새로 필요한 페이지를 위해 기존에 상주하던 페이지 중 누구를 희생양(Victim)으로 쫓아낼지 결정하는 OS의 지능형 생존 룰이다.
  2. 가치: 잘못된 선택으로 당장 다음에 쓰일 페이지를 쫓아내면 시스템이 페이지 나르기만 반복하다 멈추는 **스래싱(Thrashing)**이 발생하므로, 미래의 참조를 가장 정확하게 예측하여 페이지 폴트율을 최소화하는 것이 핵심 목표다.
  3. 융합: 이론상 최적인 OPT부터 현실적인 타협안인 LRU와 Clock까지, 하드웨어 오버헤드와 적중률 사이의 끊임없는 저울질을 통해 현대 멀티태스킹 OS의 안정성을 지탱한다.

Ⅰ. 개요 및 필요성

  • 개념: 가상 메모리 시스템에서 요구 페이징(Demand Paging)을 수행하다 보면 언젠가 물리 메모리가 가득 차게 된다. 이때 새로운 페이지를 디스크에서 가져오기 위해, 현재 램에 있는 페이지 중 하나를 골라 디스크로 내보내는(Page-out) 판단 기법이다.

  • 필요성: 램 자원은 유한하다. 수많은 프로세스가 각자 자신의 주소 공간이 무한하다고 믿고 데이터를 요구할 때, OS는 한정된 램이라는 '의자'에 누구를 앉히고 누구를 '대기실(디스크)'로 보낼지 결정해야 한다. 이 결정이 1%만 어긋나도 시스템 속도는 1,000배 이상 느려질 수 있다.

  • 💡 비유: 붐비는 식당(RAM)에서 대기 손님(새 페이지)을 받기 위해, 식사를 다 마쳤거나 가장 오래 자리를 비운 손님(Victim)을 골라 정중히 퇴장을 부탁하는 식당 매니저의 운영 노하우와 같습니다.

  • 등장 배경: 1960년대 초 가상 메모리가 발명된 직후, "어떤 페이지를 버려야 시스템이 덜 버벅댈까?"에 대한 연구가 쏟아졌다. 벨라디(Bélády)의 모순 발견 등을 거치며, 단순히 오래된 놈을 버리는 것(FIFO)보다 최근에 안 쓰인 놈을 버리는 것(LRU)이 훨씬 유리하다는 정설이 확립되었다.

┌──────────────────────────────────────────────────────────────┐
│              페이지 교체(Page Replacement)의 메커니즘 도식             │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│  [1] 페이지 폴트 발생 -> [2] 램 가득 참 확인 -> [3] 교체 알고리즘 가동    │
│                                                              │
│  [4] 희생자(Victim) 선정 ──▶ [5] Dirty Bit 확인 ──▶ [6] 필요 시 디스크 쓰기 │
│                                                              │
│  [7] 빈 프레임 확보 ──▶ [8] 새 페이지 적재 ──▶ [9] 페이지 테이블 갱신     │
└──────────────────────────────────────────────────────────────┘
  • 📢 섹션 요약 비유: 영화관이 꽉 찼을 때, 새로 들어오려는 VIP 관객을 위해 누구를 내보낼지 결정하는 규칙입니다. 짐이 적은 사람을 내보내면 뒷정리(디스크 쓰기)가 빨라져서 영화관 회전율이 좋아집니다.

Ⅱ. 아키텍처 및 핵심 원리

희생자(Victim) 선정의 경제학: Dirty Bit의 영향

페이지를 쫓아낼 때 OS는 단순히 '인기도'만 보지 않고 '비용'도 계산한다.

  • Clean Page (Dirty Bit = 0): 램에 올라온 뒤 한 번도 수정되지 않은 페이지. 디스크에 이미 똑같은 원본이 있으므로, 그냥 램에서 삭제만 하면 된다. (I/O 비용 0)
  • Dirty Page (Dirty Bit = 1): 램에서 내용이 수정된 페이지. 그냥 삭제하면 수정본이 영영 사라지므로, 쫓아내기 전에 반드시 디스크에 기록(Write-back)해야 한다. (I/O 비용 발생)
  • 결론: 알고리즘은 성능이 비슷하다면 가능하면 Clean Page를 우선적으로 쫓아내어 시스템 지연을 최소화하려 노력한다.

주요 알고리즘의 철학 분류

알고리즘선정 기준 (Victim)특징
FIFO가장 먼저 들어온 페이지구현이 쉽지만, 중요한 페이지도 쫓아내는 멍청함.
OPT미래에 가장 늦게 쓰일 페이지이론상 완벽하지만, 미래 예측이 불가능해 구현 불가.
LRU가장 오랫동안 안 쓰인 페이지과거의 이력이 미래를 대변한다는 믿음. 사실상 표준.
LFU참조 횟수가 가장 적은 페이지과거의 인기도를 중시하나, 초반에만 반짝한 데이터에 취약.
Clock참조 비트가 0인 페이지LRU를 흉내 낸 '가성비' 최강의 실무 알고리즘.
  • 📢 섹션 요약 비유: 전학생을 위해 한 명을 전학 보내야 할 때, 제일 먼저 입학한 애(FIFO)를 보낼지, 앞으로 공부 제일 안 할 애(OPT)를 보낼지, 요새 제일 조용한 애(LRU)를 보낼지 정하는 학급 회의와 같습니다.

Ⅲ. 비교 및 연결

FIFO의 저주: 벨라디의 모순 (Bélády's Anomaly)

상식적으로 램 용량(프레임 수)을 늘려주면 페이지 부재가 줄어들어야 한다. 하지만 FIFO 알고리즘은 램을 늘려줬는데 오히려 페이지 부재가 늘어나는 역설적인 현상이 발생한다. 이를 통해 컴퓨터 공학자들은 "단순히 시간순으로 버리는 것은 위험하다"는 교훈을 얻었고, 반드시 **포함 성질(Inclusion Property)**을 가진 LRU 계열의 스택 알고리즘을 써야 한다는 결론에 도달했다.

캐시 교체 vs 페이지 교체

둘은 같은 뿌리를 가진 쌍둥이 기술이지만, 환경이 다르다.

  • 캐시 교체: 하드웨어가 1나노초(ns) 안에 결정해야 하므로 극도로 단순한 알고리즘(Pseudo-LRU)을 쓴다.

  • 페이지 교체: 소프트웨어(OS)가 수 밀리초(ms)의 디스크 I/O를 앞두고 결정하므로, 다소 복잡하더라도 정교한 알고리즘(Clock)을 쓴다.

  • 📢 섹션 요약 비유: 100m 달리기 도중 신발 끈이 풀리면 대충 묶고 달려야 하지만(캐시), 마라톤 시작 전에 신발을 고를 때는 1시간 동안 고민해서 완벽한 신발을 골라야 하는 것(페이지 교체)과 같습니다.

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

실무 시나리오

  1. 리눅스 서버의 'kswapd' 프로세스 감시

    • 상황: 서버의 CPU 점유율은 낮은데, kswapd0라는 커널 프로세스가 CPU를 10% 이상 먹고 있음.
    • 판단: 시스템 메모리가 부족하여 OS가 페이지 교체 대상을 찾느라 바쁘게 리스트를 훑고(Scan) 있다는 증거다.
    • 조치: 이는 스래싱의 전조 증상이다. 가용 메모리 임계치(min_free_kbytes)를 조정하거나, 불필요한 캐시를 비우고 궁극적으로는 램을 증설해야 한다.

  2. 데이터베이스 버퍼 캐시 교체 정책

    • PostgreSQL이나 Oracle 같은 DB는 OS의 페이지 교체와 별개로 자신들만의 교체 알고리즘을 가진다. DB는 특정 인덱스가 무한 반복 사용되는 특성이 있으므로, 일반적인 LRU보다 더 정교한 **ARC (Adaptive Replacement Cache)**나 LIRS 같은 알고리즘을 써서 OS보다 훨씬 높은 적중률을 방어한다.

도입 체크리스트

  • 기술적: 사용 중인 OS의 교체 알고리즘이 해당 워크로드(순차적 vs 무작위)에 적합한가?
  • 성능적: sar -B 명령을 통해 초당 페이지 방출(pgout/s) 빈도가 디스크 쓰기 대역폭을 압박하고 있지 않은가?

안티패턴

  • 스왑 없이 페이지 교체만 믿기: 리눅스에서 스왑 영역을 아예 꺼버리면(Swap-off), 페이지 교체를 할 공간이 없어 메모리 부족 시 OS가 가장 소중한 프로세스를 강제로 죽여버리는 OOM Killer가 작동한다. 페이지 교체 알고리즘이 숨 쉴 구멍(스왑)을 반드시 열어두어야 한다.

  • 📢 섹션 요약 비유: 식당 매니저가 손님을 내보낼 대기실(스왑)도 없이 무작정 퇴장만 시키려다가는, 손님이 밥 먹다 말고 쫓겨나 싸움(OOM Kill)이 나는 법입니다.

Ⅴ. 기대효과 및 결론

정량/정성 기대효과

  • 시스템 가용성 유지: 램이 99% 차 있어도 시스템이 뻗지 않고 계속 돌아가게 만드는 마법의 조율 장치다.
  • TCO (총 소유 비용) 절감: 모든 데이터를 램에 때려 박지 않아도 되므로, 하드웨어 투자 비용을 획기적으로 낮춰준다.

결론

페이지 교체 알고리즘은 "무엇을 잊을 것인가"를 다루는 컴퓨터의 철학이다. 모든 것을 기억하려는 욕심은 스래싱이라는 파멸을 부르고, 아무거나 잊으려는 게으름은 성능 저하를 부른다. 과거를 통해 미래를 짐작하는 LRU와 그 실질적 대안인 Clock 알고리즘은, 유한한 자원 속에서 무한한 프로세스를 꽃피우게 한 현대 컴퓨팅의 가장 영리한 타협점이다.

  • 📢 섹션 요약 비유: 페이지 교체는 인생의 '정리 정돈'과 같습니다. 새 옷을 사기 위해 안 입는 옷을 과감히 버리는 용기가 있어야만, 옷장(메모리)은 항상 최신 트렌드(CPU 연산)를 유지하며 빛날 수 있습니다.

📌 관련 개념 맵

개념 명칭관계 및 시너지 설명
LRU가장 오랫동안 안 쓰인 놈을 버리는, 현대 모든 교체 알고리즘의 정신적 지주.
Clock 알고리즘LRU의 성능을 내면서도 하드웨어 부담을 0으로 만든 실무형 표준.
더티 비트수정된 페이지를 쫓아낼 때 디스크 쓰기 작업을 유발하게 만드는 판단 근거.
벨라디의 모순램을 늘려도 미스가 느는 기현상으로, FIFO 알고리즘의 치명적 결함을 상징.
스래싱교체 알고리즘이 실패하여 시스템이 페이지 교체만 반복하다 멈추는 재앙.

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

  1. 내 보물 상자가 꽉 찼는데 새로운 장난감을 넣고 싶으면, 원래 있던 장난감 중 하나를 밖으로 빼야 해요. 이게 '페이지 교체'예요.
  2. 이때 어제까지 재미있게 놀았던 인형을 버리면 슬프니까, 한 달 동안 한 번도 안 만진 낡은 로봇을 골라서 버리는 게 제일 똑똑한 방법이죠.
  3. 이렇게 어떤 장난감을 버릴지 잘 골라야만, 내 보물 상자에는 항상 내가 제일 좋아하는 장난감들만 가득 찰 수 있답니다!