# 캐시 대체 정책 (Cache Replacement Policies)

## 개요
캐시 대체 정책이란 캐시 메모리가 가득 찼을 때, 새로운 데이터를 저장하기 위해 기존에 저장되어 있던 데이터 중 어떤 것을 제거하고 교체할지 결정하는 알고리즘을 말합니다. 캐시의 크기는 한정되어 있으므로, 향후 참조될 가능성이 가장 낮은 데이터를 효율적으로 선택하여 제거함으로써 캐시 적중률(Cache Hit Rate)을 극대화하는 것이 이 정책의 핵심 목적입니다.

## 주요 캐시 대체 알고리즘

### FIFO (First-In-First-Out)
FIFO는 가장 먼저 캐시에 들어온 데이터를 가장 먼저 제거하는 방식입니다. 큐(Queue) 구조를 사용하여 구현하며, 데이터가 입력된 순서를 기준으로 교체 대상을 결정합니다.
- **작동 원리**: 가장 오래전에 캐시에 적재된 블록을 제거합니다.
- **특징**: 구현이 매우 간단하지만, 자주 사용되는 데이터라도 적재된 지 오래되었다면 제거될 수 있다는 단점이 있습니다.

### LRU (Least Recently Used)
LRU는 가장 오랫동안 참조되지 않은 데이터를 제거하는 방식입니다. "최근에 사용된 데이터가 가까운 미래에 다시 사용될 가능성이 높다"는 시간 지역성(Temporal Locality) 원리에 기반합니다.
- **작동 원리**: 데이터가 참조될 때마다 해당 데이터를 '최신' 상태로 갱신하며, 교체 시점에는 가장 오랫동안 참조되지 않은 데이터를 제거합니다.
- **특징**: 대부분의 일반적인 워크로드에서 높은 효율성을 보이며, 가장 널리 사용되는 정책 중 하나입니다.

### LFU (Least Frequently Used)
LFU는 참조 횟수가 가장 적은 데이터를 제거하는 방식입니다. 데이터의 사용 빈도를 기록하여 빈도가 낮은 데이터를 교체 대상으로 삼습니다.
- **작동 원리**: 각 데이터마다 참조 횟수를 카운트하며, 교체 시점에 카운트 값이 가장 낮은 데이터를 제거합니다.
- **특징**: 빈번하게 사용되는 데이터를 유지하는 데 유리하지만, 초기에 일시적으로 많이 사용된 후 더 이상 사용되지 않는 데이터가 캐시에 계속 남아있을 수 있는 문제가 있습니다.

### Random Replacement
Random Replacement는 특별한 기준 없이 무작위로 제거 대상을 선택하는 방식입니다.
- **작동 원리**: 캐시 내의 임의의 슬롯을 선택하여 데이터를 교체합니다.
- **특징**: 알고리즘 구현 비용이 거의 없으며, 특정 패턴의 데이터 접근으로 인해 발생할 수 있는 최악의 성능 저하(예: FIFO의 Belady's Anomaly)를 피할 수 있습니다.

## 알고리즘 비교 및 선택 기준

| 정책 | 장점 | 단점 | 시간 복잡도 | 적합한 사용 사례 |
| :--- | :--- | :--- | :---: | :--- |
| **FIFO** | 구현이 매우 단순함 | 적중률이 낮을 수 있음 | $O(1)$ | 단순한 데이터 흐름 처리 |
| **LRU** | 높은 적중률, 지역성 활용 | 구현 복잡도 및 오버헤드 발생 | $O(1)$ | 일반적인 웹 캐시, OS 페이지 교체 |
| **LFU** | 빈번한 데이터 유지에 유리 | 과거 데이터의 잔류 문제 | $O(\log n)$ | 빈도 기반의 정적 데이터 캐싱 |
| **Random** | 오버헤드 최소, 예측 불가능성 제거 | 일관된 성능 보장 어려움 | $O(1)$ | 하드웨어 제약이 심한 환경 |

## 참고 문헌/관련 문서
- 캐시 메모리 (Cache Memory)
- 시간 지역성과 공간 지역성 (Locality of Reference)
- 페이지 교체 알고리즘 (Page Replacement Algorithm)