알고리즘CacheMemoryOS

캐시 교체 알고리즘 (Cache Replacement)

한정된 메모리 슬롯에서 효율적으로 데이터를 교체하는 5가지 알고리즘 실시간 대조

시각화 로드 중...

알고리즘 복잡도

최선O(1)
평균O(1)
최악O(1) ~ O(log N)
공간O(N)

개요

Algorithm Overview

캐시 메모리는 한정된 고속 저장 공간이므로, 가용 슬롯이 꽉 찬 상태에서 새 데이터를 적재하려면 기존 데이터 중 하나를 방출(Eviction)해야 합니다.

01

FIFO (First-In, First-Out, 선입선출)

  • 방출 기준: 캐시에 가장 먼저 들어와 머문 시간이 가장 오래된 데이터를 방출합니다.
  • 특성: 구현이 큐(Queue)로 매우 간단하지만, 자주 조회되는 인기 데이터도 진입 시점이 오래되었다는 이유만으로 방출되는 벨레이디의 모순(Belady's Anomaly)이 발생할 수 있습니다.
02

LRU (Least Recently Used, 최근 최소 사용)

  • 방출 기준: 마지막으로 참조된 시점으로부터 가장 오랫동안 재사용되지 않은 데이터를 방출합니다.
  • 특성: 시간적 국소성(Temporal Locality)에 기반하여 실제 웹 브라우저, 웹 캐시 등에서 널리 활용되지만 실제 제품은 근사 LRU 등 변형 정책을 사용하기도 합니다. 더블 링크드 리스트와 해시맵으로 $O(1)$에 구현됩니다.
03

LFU (Least Frequently Used, 최저 빈도 사용)

  • 방출 기준: 캐시 진입 후 지금까지 누적 참조된 횟수가 가장 적은 데이터를 방출합니다.
  • 특성: 참조 횟수 카운터를 유지해야 하며, 초기에 일시적으로 집중 사용된 후 더 이상 쓰이지 않는 데이터가 캐시를 오래 점유하는 한계가 있습니다.
04

Clock / Second Chance (2차 기회 알고리즘)

  • 방출 기준: 원형 큐와 1비트 참조 비트(Reference Bit)를 사용하여 LRU를 저비용으로 근사(Approximate)하는 OS 가상 메모리 페이지 교체 알고리즘입니다.
  • 특성: 시계 바늘이 돌며 참조 비트가 1인 페이지는 0으로 내리고 2차 기회를 준 뒤, 비트가 0인 페이지를 찾아 방출합니다.
05

Random (무작위 방출)

  • 방출 기준: 캐시 슬롯 중 무작위 난수로 대상을 선택하여 즉시 방출합니다.
  • 특성: 우선순위나 사용 이력을 관리하는 연산 오버헤드가 제로($O(1)$)이며, 복잡한 워크로드에서 성능 기준선(Baseline) 대조군으로 유용합니다.

실행 예제로 확인하기

용량 3의 캐시에 A, B, C를 차례로 넣고 A를 다시 조회한 다음 D를 넣는다면, FIFO는 가장 먼저 삽입된 A를 버리고 LRU는 가장 오래 조회되지 않은 B를 버립니다. 같은 요청열에서도 정책에 따라 다음 캐시 적중률이 달라질 수 있습니다.

학습 목표

  • 같은 접근 기록에 대해 FIFO와 LRU의 퇴출 대상이 달라지는 이유를 설명할 수 있다.

자주 하는 오해

  • LRU는 가장 오래 전에 삽입된 항목이 아니라 가장 오래 전에 접근된 항목을 퇴출합니다. 실제 캐시 제품은 정확한 LRU 대신 근사 정책을 쓸 수 있습니다.

핵심 정리

  • 캐시 적중률은 교체 정책뿐 아니라 접근 패턴·슬롯 용량에 따라 달라집니다.

학습 확인

문제 1

캐시 [A,B,C]에 A를 재조회한 뒤 D가 들어오면 LRU의 퇴출 대상은?

핵심 단계

  1. 1

    Step 0: 초기 상태 - 크기가 3인 빈 캐시 슬롯에 데이터 유입을 대기합니다.

  2. 2

    Step 1: 데이터 A 로드 - 비어 있는 첫 번째 슬롯에 A가 저장됩니다 (Miss).

  3. 3

    Step 2: 데이터 B 로드 - 비어 있는 두 번째 슬롯에 B가 추가됩니다 (Miss).

  4. 4

    Step 3: 데이터 C 로드 - 비어 있는 세 번째 슬롯에 C가 추가됩니다 (Miss).

  5. 5

    Step 4: 데이터 A 재조회 - 이미 슬롯에 있는 A가 조회됩니다 (Hit). LRU는 A를 최근 사용으로 변경하고, LFU는 카운터를 증가시킵니다.

  6. 6

    Step 5: 데이터 D 로드 - 캐시가 꽉 차서 하나를 방출해야 합니다 (Miss). FIFO는 A, LRU/LFU는 B, Clock은 A를 방출하고 D를 저장합니다.

  7. 7

    Step 6: 데이터 B 로드 - 꽉 찬 상태에서 B가 다시 유입됩니다. FIFO는 Hit가 발생하지만 다른 알고리즘은 캐시 교체(Miss)가 일어납니다.

핵심 개념 및 실무 적용 분야

✓웹 브라우저 이미지 및 스크립트 캐시 정책
✓데이터베이스 버퍼 캐시 (Redis/DB Buffer Pool)
✓운영체제(OS) 가상 메모리 페이지 교체 정책

참고 자료

개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.