OS Page Replacement Policies

물리 메모리가 부족할 때 OS Memory Management가 어떤 페이지를 디스크로 내보낼지 결정하는 정책이 이 페이지의 주제다. InnoDB Buffer Pool의 LRU 전략은 DB 조회 읽기 성능 최적화에서 다루는 이 정책의 응용 사례다.

핵심 문제: AMAT

물리 메모리는 가상 메모리 페이지의 캐시다. 교체 정책의 목표는 AMAT(Average Memory Access Time)를 최소화하는 것, 즉 캐시 미스(Page Fault)를 최소화하는 것이다.^[1]

AMAT = T_memory + (P_miss × T_disk)

T_memory는 약 100ns, T_disk는 약 10ms 수준이다. 미스율 0.1%만 되어도 AMAT이 약 100배 증가하므로 교체 정책이 임계적으로 중요하다.^[1:1]

캐시 미스의 3가지 종류 (Three C's)

이 분류는 컴퓨터 구조 분야에서 미스를 유형별로 구분할 때 때때로 유용하게 쓰는 분류이며, Three C's라고도 부른다.^[2]

교체 정책 비교

Optimal (MIN) — 이론적 상한

앞으로 가장 오래 사용되지 않을 페이지를 제거한다. 이론적 최솟값의 miss rate를 달성하지만, 미래를 알아야 하므로 실제 구현은 불가능하다. 다른 정책의 비교 기준으로만 쓰인다.^[3]

FIFO — 가장 단순

가장 먼저 들어온 페이지를 제거한다. 자주 쓰이는 페이지라도 일찍 들어왔으면 제거된다는 문제가 있다. 캐시 크기를 늘렸는데 히트율이 오히려 낮아지는 Belady's Anomaly가 발생할 수 있다.^[4] LRU는 Stack property(크기 N+1 캐시는 항상 크기 N 캐시의 내용을 포함)를 만족하므로 이 이상 현상이 없다.^[5]

Random

무작위로 페이지를 선택한다. 구현이 단순하고 corner-case가 없다는 장점이 있지만, 운에 의존하며 평균적으로 LRU보다 낮은 히트율을 보인다.^[6]

LRU (Least Recently Used) — 표준 정책

가장 최근에 사용되지 않은 페이지를 제거한다. 근거는 Temporal locality — 최근에 접근한 페이지는 곧 다시 접근될 가능성이 높다는 것이다. 대부분의 workload에서 FIFO/Random보다 우수하다.^[5:1]

이 workload별 차이도 같은 근거에서 나온다.^[7]

Locality의 두 종류

• Temporal locality: 최근 접근한 페이지 → 곧 다시 접근 가능성 높음 (LRU의 근거).
• Spatial locality: 페이지 P에 접근 → 인근 P±1 페이지도 곧 접근 가능성 높음.^[8]

LRU 구현 문제와 해결: Clock Algorithm

완전한 LRU는 매 메모리 접근마다 LRU 리스트를 갱신해야 해서 오버헤드가 매우 크다. 4GB / 4KB = 100만 페이지라면 최소 사용 페이지를 스캔하는 데만도 너무 오랜 시간이 걸린다.^[9]

Clock Algorithm은 하드웨어의 use bit(reference bit)를 활용한 LRU 근사다.^[10]

flowchart LR
    A[교체 필요] --> B{현재 페이지 use bit = 1?}
    B -- Yes --> C[use bit = 0 으로 초기화\n다음 페이지로 이동]
    C --> B
    B -- No --> D[이 페이지를 victim으로 선택]

페이지 접근 시 하드웨어가 use bit = 1을 설정한다. OS는 이 bit를 절대 직접 1로 설정하지 않고 0으로만 초기화한다. Clock hand가 순환하며 use bit=1이면 0으로 초기화한 뒤 통과하고, use bit=0이면 victim으로 선택한다. 성능은 LRU보다 약간 낮지만, 완전한 LRU보다 훨씬 낮은 overhead를 가진다.^[10:1]

Dirty bit (Modified bit)

페이지가 수정됐으면 eviction 시 디스크에 써야 하므로 비용이 크고, 수정되지 않았으면 그냥 버릴 수 있다. Clock 알고리즘의 개선판은 use=0 && clean을 우선 선택하고, use=0 && dirty를 그 다음으로, use=1을 마지막으로 선택한다.^[11]

기타 VM 정책

이 세 정책도 같은 vm-beyondphys-policy 자료가 다루는 범위다.^[12]

Thrashing

메모리가 심각하게 부족할 때 발생한다: 프로세스들의 working set 합이 물리 메모리를 초과하면 지속적으로 swap in/out이 일어난다.^[13]

대응책은 다음과 같다.

• Admission control: 실행 프로세스 수를 줄여 각 working set이 메모리에 맞게 한다.
• OOM Killer (Linux): 메모리 과다 소비 프로세스를 강제 종료한다.^[13:1]

흔히 놓치는 지점

• Looping-sequential workload에 LRU를 그대로 적용하면 0% 히트율이 나올 수 있다.
• 완전한 LRU 구현(모든 접근 시 리스트 갱신)은 오버헤드가 캐시 이득을 상쇄할 수 있다.
• dirty page를 고려하지 않고 eviction 순서를 정하면 불필요한 디스크 write가 늘어난다.
• Thrashing 상황에서 교체 정책만 개선해서는 근본 해결이 안 된다 — admission control이 필요하다.

관련

• OS Memory Management — 물리 메모리가 부족할 때 OS가 어떤 페이지를 디스크로 내보낼지 결정하는 정책의 상위 맥락.
• DB 조회 읽기 성능 최적화 — InnoDB Buffer Pool의 LRU 전략이 이 정책의 응용 사례다.

출처

테스트 질문

• FIFO와 LRU의 성능 차이가 가장 두드러지는 workload는 어떤 상황인가?
• Belady's Anomaly가 LRU에서는 발생하지 않는 이유는 무엇인가?
• Clock Algorithm이 완전한 LRU의 대안이 될 수 있는 이유는?
• Thrashing이 발생할 때 교체 정책을 개선하는 것이 왜 근본 해결이 안 되는가?