274. FIFO (First-In, First-Out)

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

본질: FIFO (First-In, First-Out)는 캐시에 들어온 순서만 기억하고 가장 먼저 들어온 블록을 먼저 내보내는, 가장 단순한 교체 정책이다.

가치: 참조 이력을 계속 추적하지 않아도 되므로 하드웨어 회로와 전력 소모를 작게 유지할 수 있어, 단순 버퍼와 저비용 시스템에서 여전히 유효하다.

판단 포인트: FIFO는 시간적 지역성 (Temporal Locality)을 반영하지 못해 자주 쓰는 데이터도 오래 머물렀다는 이유로 제거할 수 있으며, 이 약점은 벨라디의 모순 (Bélády's Anomaly)으로까지 이어진다.

Ⅰ. 개요 및 필요성

FIFO는 캐시나 버퍼가 가득 찼을 때 가장 먼저 적재된 항목을 교체 대상으로 정하는 정책이다. 판단 기준이 "얼마나 자주 썼는가"도 아니고 "방금 썼는가"도 아니라 오직 들어온 순서뿐이라는 점이 핵심이다. 이 단순함 덕분에 복잡한 메타데이터 없이도 교체 결정을 내릴 수 있다.

이 정책이 필요한 이유는 모든 저장 구조가 고성능 교체 로직을 감당할 필요는 없기 때문이다. CPU (Central Processing Unit) 최상위 캐시처럼 극단적 적중률이 중요한 곳은 LRU (Least Recently Used) 계열이 더 유리하지만, 네트워크 큐나 센서 링 버퍼처럼 순서 보장과 구현 단순성이 더 중요한 구조도 많다. 이런 환경에서는 정교한 예측보다 "확실하고 빠른 처리"가 우선이다.

즉 FIFO는 최고의 적중률을 노리는 정책이라기보다, 최소한의 제어 비용으로 저장 공간을 순환시키는 정책으로 이해해야 한다. 오래된 것이 곧 덜 중요하다는 보장은 없지만, 적어도 누가 나갈지는 즉시 결정할 수 있다.

┌──────────────────────────────────────────────────────────────┐
│        FIFO가 필요한 상황: 판단은 단순하게, 교체는 즉시       │
├──────────────────────────────────────────────────────────────┤
│ 캐시/버퍼 가득 참                                             │
│      │                                                       │
│      ▼                                                       │
│ "최근 사용" 추적 없음  "빈도" 카운트 없음  "순서"만 관리     │
│      │                                                       │
│      ▼                                                       │
│ 가장 먼저 들어온 항목 선택  ───────────────▶ 즉시 교체         │
└──────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: FIFO는 식당 대기표와 같다. 자주 오는 단골인지, 방금 주문했는지는 보지 않고 번호표를 먼저 뽑은 순서만 기준으로 자리를 비운다.

Ⅱ. 아키텍처 및 핵심 원리

FIFO의 핵심 구현은 보통 큐 (Queue) 또는 원형 버퍼 (Circular Buffer)다. 새 블록이 들어오면 뒤쪽에 기록하고, 교체가 필요하면 앞쪽 포인터가 가리키는 블록을 내보낸다. 참조가 일어나더라도 그 블록의 위치를 다시 정렬하지 않으므로, 읽기 히트(hit) 시 추가 업데이트가 거의 없다.

이 구조는 회로 입장에서 매우 가볍다. LRU처럼 매 접근마다 순위를 재계산하거나, LFU (Least Frequently Used)처럼 참조 횟수 카운터를 증가시킬 필요가 없다. 결과적으로 비교기, 카운터, 상태 비트 수가 줄어들어 설계가 단순해지고, 접근 지연과 전력 부담도 낮아진다.

다만 단순함의 대가도 분명하다. FIFO는 어떤 블록이 방금 다시 쓰였는지를 반영하지 못한다. 따라서 오래전에 들어왔지만 지금도 반복 사용 중인 데이터가, 막 들어왔지만 다시는 쓰이지 않을 데이터보다 먼저 쫓겨나는 비합리적 상황이 발생할 수 있다.

다음 그림은 FIFO가 왜 빠르지만 둔감한지를 보여준다.

┌──────────────────────────────────────────────────────────────┐
│                FIFO 교체 흐름: 참조 이력은 무시               │
├──────────────────────────────────────────────────────────────┤
│ 현재 큐 상태                                                  │
│ Front                                                     Rear│
│  ┌──────┐  ┌──────┐  ┌──────┐  ┌──────┐                      │
│  │  A   │  │  B   │  │  C   │  │  D   │                      │
│  └──────┘  └──────┘  └──────┘  └──────┘                      │
│     ▲                                                        │
│     └─ 가장 먼저 들어온 블록 = 다음 희생자                    │
│                                                              │
│ 새 블록 E 도착                                               │
│                                                              │
│  A 제거  ───────────────────────────────────────▶  E 삽입      │
│                                                              │
│ 결과: [ B ][ C ][ D ][ E ]                                   │
└──────────────────────────────────────────────────────────────┘

항목	FIFO의 처리 방식	의미
삽입 기준	새 데이터는 뒤에 배치	시간 순서 유지
교체 기준	가장 먼저 들어온 블록 제거	구현 단순
히트 시 동작	위치 변경 없음	제어 오버헤드 낮음
약점	최근 재사용 여부 미반영	적중률 손해 가능

📢 섹션 요약 비유: FIFO는 회전문 달린 창고 같다. 물건이 들어온 차례대로 반대편에서 빠져나가니 관리자는 편하지만, 방금 다시 쓸 공구가 먼저 나가 버릴 수도 있다.

Ⅲ. 비교 및 연결

FIFO를 제대로 이해하려면 LRU, LFU와의 경계를 함께 봐야 한다. FIFO는 순서, LRU는 최근성, LFU는 빈도를 본다. 즉 FIFO는 기억해야 할 정보가 가장 적은 대신, 프로그램의 지역성(Locality)을 가장 덜 반영한다.

정책	판단 기준	장점	약점	대표 연결 개념
FIFO	먼저 들어온 순서	구현 가장 단순	자주 쓰는 블록도 제거 가능	큐, 링 버퍼
LRU	가장 오래 안 쓴 시점	시간적 지역성 반영 우수	구현 복잡도 증가	스택 알고리즘, Pseudo-LRU
LFU	가장 적게 사용한 빈도	장기 인기 데이터 보호	카운터 관리 부담 큼	캐시 오염 방지

특히 FIFO는 스택 알고리즘(Stack Algorithm) 이 아니기 때문에 캐시 크기를 키워도 항상 성능이 좋아진다고 보장할 수 없다. 같은 접근열에서 캐시를 3칸에서 4칸으로 늘렸는데도 미스가 증가하는 현상이 바로 벨라디의 모순이다. 이 점이 FIFO를 메인 CPU 캐시의 기본 정책으로 쓰기 어렵게 만든다.

운영체제(OS, Operating System)의 페이지 교체에서 쓰이는 Second Chance 또는 Clock 알고리즘은 FIFO의 약점을 보완한 대표 사례다. 기본 순서는 FIFO처럼 유지하되, 최근 참조 비트(reference bit)가 있으면 즉시 버리지 않고 한 번 더 기회를 준다. 즉 실무는 FIFO의 단순함을 버리지 않으면서도, 지역성을 조금이라도 반영하려는 방향으로 발전해 왔다.

📢 섹션 요약 비유: FIFO가 줄 선 순서만 보는 놀이공원이라면, LRU와 LFU는 "방금 탔는지"와 "얼마나 자주 타는지"까지 살피는 운영 방식이다. 기준이 늘수록 똑똑해지지만 관리도 복잡해진다.

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

실무에서 FIFO를 채택할지 여부는 "적중률 최적화"보다 제어 비용과 순서 보장이 더 중요한지로 판단해야 한다. 예를 들어 초당 대량 이벤트를 받는 네트워크 입력 버퍼나 오디오 스트리밍 버퍼는, 복잡한 교체 판단보다 빠른 순환과 예측 가능한 동작이 중요하다. 이런 곳에서 FIFO는 좋은 선택이다.

반면 CPU 캐시, 데이터베이스 버퍼 풀(Buffer Pool), 자주 재사용되는 인덱스 캐시처럼 지역성이 강한 데이터를 다루는 계층에서는 순수 FIFO를 조심해야 한다. 오래 머물렀다는 이유만으로 핵심 데이터를 내보내면 미스 패널티가 누적되고, 하위 메모리 접근 지연이 전체 성능을 망친다. 특히 DRAM (Dynamic Random Access Memory) 접근이 수십 ns 이상 걸리는 상황에서는 작은 정책 차이가 체감 성능 차이로 이어진다.

판단 체크리스트

데이터가 순서대로 소비되는가, 아니면 반복 재사용되는가?
참조 이력을 추적할 하드웨어/소프트웨어 비용을 감당할 수 있는가?
미스 패널티보다 제어 오버헤드 절감 효과가 더 큰가?
벨라디의 모순이 문제 될 정도로 워킹셋(Working Set) 변동이 큰가?

안티패턴

"구현이 쉬우니 캐시에도 일단 FIFO"라는 접근
반복 참조 데이터가 많은 환경에서 최근성 정보 없이 운영하는 설계
FIFO의 단순함만 보고, 미스 비용이 큰 하위 계층 영향을 무시하는 판단
📢 섹션 요약 비유: FIFO는 택배 상하차장에서 강하지만 도서관 서가 관리에는 약하다. 상자는 들어온 순서대로 빼도 되지만, 책은 사람들이 자주 찾는 것을 남겨둬야 하기 때문이다.

Ⅴ. 기대효과 및 결론

FIFO의 가장 큰 효과는 설계 명확성이다. 교체 규칙이 단순하므로 검증이 쉽고, 자원 사용량도 예측 가능하다. 작은 임베디드 시스템이나 스트리밍형 데이터 경로에서는 이 예측 가능성이 곧 안정성으로 이어진다.

하지만 FIFO를 "낡았으니 버린다"는 단일 관점으로만 이해하면 위험하다. 컴퓨터 구조에서 오래된 데이터가 곧 불필요한 데이터라는 뜻은 아니기 때문이다. 캐시 계층이 성능을 올리는 이유는 지역성을 잘 붙잡는 데 있는데, FIFO는 이 점에서 본질적으로 불리하다.

따라서 FIFO는 모든 캐시에 좋은 정책이 아니라, 순서 중심 구조에 특히 잘 맞는 정책으로 기억해야 한다. 현대 시스템은 필요에 따라 FIFO를 그대로 쓰기도 하고, Second Chance처럼 약간 보완해 쓰기도 하며, 더 높은 적중률이 필요하면 LRU 계열로 넘어간다. 핵심은 단순함과 적중률 사이의 균형을 어디에 둘 것인지 판단하는 것이다.

📢 섹션 요약 비유: FIFO는 가장 단순한 교통 신호와 같다. 규칙은 명확하고 운영은 쉽지만, 모든 교차로에 똑같이 적용하면 혼잡한 도심에서는 더 똑똑한 신호 체계가 필요해진다.

📌 관련 개념 맵

개념	연결 포인트
캐시 교체 알고리즘 (Replacement Policy)	FIFO는 가장 기본적인 교체 정책 축에 해당한다.
시간적 지역성 (Temporal Locality)	FIFO가 충분히 반영하지 못하는 핵심 성질이다.
LRU (Least Recently Used)	FIFO의 단순함과 대비되는 최근성 기반 정책이다.
벨라디의 모순 (Bélády's Anomaly)	FIFO가 대표적으로 드러내는 구조적 한계다.
Second Chance / Clock	FIFO에 참조 비트를 더해 실무적으로 개선한 형태다.

📈 관련 키워드 및 발전 흐름도

단순 순환 버퍼
    │
    ▼
FIFO (First-In, First-Out)
    │
    ├─ 장점: 구현 단순 · 저전력 · 예측 가능
    │
    └─ 한계: 지역성 미반영 · 벨라디의 모순
           │
           ▼
Second Chance / Clock
           │
           ▼
LRU (Least Recently Used) · Pseudo-LRU
           │
           ▼
적응형 교체 정책 (Adaptive Replacement)

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

FIFO는 줄을 먼저 선 친구가 먼저 앞으로 나가는 규칙이에요.
그래서 누가 제일 인기 많은 친구인지는 몰라도, 순서를 정하기는 아주 쉬워요.
하지만 자주 같이 놀던 친구도 먼저 왔다는 이유로 먼저 나가야 해서, 가끔은 똑똑하지 못한 선택을 할 수 있어요.