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

한 줄 정의: 메모리가 꽉 찼을 때 어떤 데이터를 내보내고 새 데이터를 들여올지 정하는 규칙으로, 운영체제가 가상메모리를 관리할 때 사용합니다.

쉽게 풀면

냉장고가 이미 꽉 찼는데 새 음식을 넣어야 한다면 무언가는 빼야 합니다. 이때 "가장 오래전에 넣은 것부터 뺄지(FIFO)", "가장 오랫동안 안 꺼내 먹은 것부터 뺄지(LRU, Least Recently Used)", "앞으로 가장 안 먹을 것 같은 걸 예측해서 뺄지(최적 교체)" 등 여러 기준이 있을 수 있습니다. 컴퓨터도 마찬가지입니다. 프로그램이 쓰는 데이터(페이지)를 메모리(RAM)에 올려두는데, 메모리 공간이 부족해지면 어떤 페이지를 디스크로 내보내고 어떤 페이지를 새로 들여올지 결정해야 합니다. 이 결정 규칙이 페이지 교체 알고리즘이며, LRU가 가장 널리 쓰이는 방식 중 하나입니다.

왜 중요한가

페이지 교체 알고리즘은 운영체제의 가상메모리 관리 성능을 좌우하는 핵심 요소로, 시스템이 실제 물리 메모리보다 많은 데이터를 다뤄야 할 때 얼마나 효율적으로 동작하는지를 결정합니다. 이 때문에 운영체제 연구뿐 아니라 데이터베이스 버퍼 관리, CPU 캐시 설계, 분산 스토리지 시스템 등 메모리 계층 구조를 다루는 다양한 시스템 분야 논문에서 유사한 아이디어가 반복적으로 응용됩니다.

논문에서는 이렇게 쓰입니다

"제안한 캐시 교체 기법은 전통적인 LRU 페이지 교체 알고리즘 대비 캐시 적중률(hit ratio)을 12% 향상시켰다."

이 문장은 "새로 제안한 방법이 기존의 LRU 방식보다 필요한 데이터가 메모리에 이미 있을 확률을 더 높였다"는 뜻입니다.

"플래시 기반 스토리지 환경에서는 쓰기 마모(wear leveling)를 고려한 페이지 교체 정책이 기존 LRU보다 장치 수명을 늘리는 데 유리함을 보였다."

메모리 계층 구조 연구가 순수 성능뿐 아니라 저장매체의 물리적 특성까지 함께 고려하는 방향으로 확장된 사례이다.

"데이터베이스 버퍼 풀 관리에서는 순차 스캔에 의한 캐시 오염을 막기 위해 LRU 대신 LRU-K 또는 클럭 기반 변형 알고리즘을 채택하는 경우가 많다."

동일한 교체 알고리즘 아이디어가 운영체제를 넘어 데이터베이스 시스템 설계에도 적용되는 예시를 보여준다.

조금 더 깊게 보면

페이지 교체 알고리즘의 성능은 흔히 캐시 적중률(hit ratio) 또는 페이지 폴트(page fault) 발생 횟수로 측정되며, 실제 프로그램의 접근 패턴을 기록한 참조열(reference string)을 시뮬레이션에 사용해 알고리즘 간 성능을 비교합니다. LRU를 근사하되 구현 비용을 줄인 Clock(2차 기회) 알고리즘, 접근 빈도까지 함께 고려하는 LFU나 ARC(Adaptive Replacement Cache) 같은 변형들도 자주 등장하므로, 논문에서 어떤 근사 방식을 채택했는지와 그 이유(정확도 대 연산 오버헤드의 균형)를 살펴보는 것이 중요합니다.

주의할 점

이론적으로 가장 이상적인 방법은 "앞으로 가장 오랫동안 쓰이지 않을 페이지"를 미리 알고 내보내는 것(최적 교체, OPT)이지만, 미래를 알 수 없으므로 실제 시스템에서는 쓸 수 없고 성능 비교의 기준선으로만 사용됩니다. 실무에서는 LRU, FIFO, Clock 알고리즘처럼 과거 사용 이력을 근거로 미래를 추정하는 방식을 씁니다.