FIFO (First-In, First-Out) 교체 알고리즘

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

본질: FIFO(First-In, First-Out) 페이지 교체는 램(RAM)에 빈 프레임이 없을 때, 물리 메모리에 가장 '먼저' 올라와서 가장 오랫동안 자리를 차지하고 있었던 늙은 페이지부터 순서대로 쫓아내는 가장 단순 무식한 교체 알고리즘이다.

가치: 큐(Queue) 자료구조 하나와 포인터 하나만 있으면 구현이 끝나기 때문에 운영체제의 오버헤드(연산량)가 0(Zero)에 가깝다는 극강의 하드웨어적 단순함을 제공한다.

융합(한계): 하지만 자주 쓰이는 핵심 전역 변수(초기 데이터)마저 늙었다는 이유로 스왑(Swap)으로 내던져버리는 치명적 비효율을 낳으며, 프레임을 늘려줘도 페이지 폴트가 증가하는 **'벨라디의 모순(Belady's Anomaly)'의 주범으로 찍혀 현대 범용 OS에서는 단독으로 절대 쓰이지 않는 안티패턴(Anti-pattern)**이 되었다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 페이지 교체의 타겟(Victim)을 고르는 가장 원시적인 방식이다. 각 페이지가 메모리에 들어온 '시간'만 딱 기억해 둔다. 아니면 그냥 페이지들을 동그란 원형 큐(Circular Queue)에 줄 세워놓고 포인터(시곗바늘)가 가리키는 놈을 1순위로 쏴 죽인다. 해당 페이지가 방금 전까지 미친 듯이 쓰였든 말든, CPU의 '사용 빈도'나 '최근 사용 여부'는 1도 신경 쓰지 않는 피도 눈물도 없는 시간(Time) 중심의 룰이다.
필요성: 1970년대 초창기 운영체제를 만들 때, CPU는 너무 느리고 비쌌다. 복잡하게 "얘가 언제 마지막으로 썼더라? (LRU)", "몇 번 불렸더라? (LFU)" 같은 걸 계산할 여유가 없었다. 램이 모자랄 때 0.0001초 만에 "너 당첨! 나가!"를 외칠 수 있는 극한의 가성비 로직이 필요했다. "가장 먼저 식당에 들어와서 밥 먹은 놈이 제일 배부를 테니까, 그놈부터 쫓아내는 게 제일 공평하겠지!"라는 아주 단순한 1차원적 직관에서 출발했다.
💡 비유: FIFO 교체는 동네 빵집의 선입선출 쇼케이스와 같다. 주인이 진열대에 빵을 1번부터 5번까지 차례대로 올려둔다. 새 빵(6번)을 놓을 자리가 없으면, 손님이 방금까지 1번 빵을 들여다보고 살까 말까 고민하고 있든 말든 무조건 제일 먼저 만들어둔 1번 빵을 낚아채서 쓰레기통에 버리고 6번을 올려놓는다. 주인은 빵 굽는 순서만 기억하면 되니 머리 쓸 일이 없어서 엄청 편하지만, 정작 손님들이 제일 많이 찾는 '단팥빵(핵심 페이지)'이 일찍 만들어졌다는 이유로 버려져서 매출(성능)이 박살 난다.
등장 배경 및 참혹한 실패의 역사:
1. 쉬운 구현의 유혹: 포인터 하나로 큐를 뺑글뺑글 도는 것만으로 메모리 교체가 끝난다는 매력에 푹 빠짐.
2. 핵심 뼈대의 탈출: 프로그램 켤 때 할당받은 메인 함수나 전역 변수(1번 페이지)가 가장 먼저 들어왔다는 이유로 쫓겨났다가, 0.1초 뒤 다시 불려와 남을 쫓아내는 코미디가 벌어짐.
3. 퇴출 선고: 벨라디(Belady)가 이 알고리즘의 치명적 결함(모순)을 논문으로 증명하며 관짝에 못이 박힘.

┌──────────────────────────────────────────────────────────────────────┐
│        FIFO 알고리즘의 치명적 맹점 (자해 공갈) 시각화                │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│ [ 상황: 램 프레임 3개 / 들어오는 순서: 1 -> 2 -> 3 ]                 │
│   ┌─────┬─────┬─────┐                                                │
│   │ 1번 │ 2번 │ 3번 │ ◀ 1번 페이지가 가장 늙음 (고참)                │
│   └─────┴─────┴─────┘                                                │
│                                                                      │
│ [ 4번 페이지가 램에 들어오려 함 (Page Fault) ]                       │
│   OS: "누가 제일 오래됐지? 1번 너 나가!"                             │
│   ┌─────┬─────┬─────┐                                                │
│   │ 4번 │ 2번 │ 3번 │ ◀ 1번이 스왑으로 버려짐.                       │
│   └─────┴─────┴─────┘                                                │
│                                                                      │
│ [ 0.001초 뒤, CPU가 다시 1번 페이지를 불렀음! ]                      │
│   CPU: "야, 아까 쓰던 1번 내놔!"                                     │
│   OS: "헐, 방금 버렸는데... 이번엔 제일 오래된 2번 너 나가!"         │
│   ┌─────┬─────┬─────┐                                                │
│   │ 4번 │ 1번 │ 3번 │ ◀ 1번을 다시 가져오느라 지옥의 렉 발생!        │
│   └─────┴─────┴─────┘                                                │
│                                                                      │
│ 💥 뼈아픈 결과: 1번 페이지가 사실 1초마다 불리는 초핵심 변수였는데,  │
│    단지 "일찍 들어왔다"는 이유로 버려져서 스래싱(Thrashing)이 터짐.  │
└──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 짧은 예시가 FIFO의 무덤이다. FIFO는 데이터의 '활용 가치(Locality)'를 깡그리 무시한다. 프로그램 구조상 처음 들어오는 데이터들은 대부분 환경 설정이나 초기 데이터 베이스 연결 객체 등 끝날 때까지 쥐고 있어야 하는 코어 모듈이다. 이 코어 모듈들을 늙었다고 주기적으로 걷어차버리니 OS가 온종일 디스크를 긁으며 식은땀을 흘리게 되는 것이다.

📢 섹션 요약 비유: 회사에서 구조조정을 할 때 "성과(사용 빈도)나 능력(지역성)은 안 보고, 그냥 입사 제일 먼저 한 부장님, 이사님부터 순서대로 다 잘라라!"라고 명령하는 무능한 대표입니다. 결국 회사의 뼈대를 아는 핵심 인력이 쫓겨나 회사가 한 달 만에 망해버립니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

큐(Queue) 자료구조의 초고속 O(1) 교체 메커니즘

FIFO가 성능 면에서 까이면서도 계속 교과서 1장에 나오는 이유는, 구현의 아름다운 단순성 때문이다.

운영체제는 램에 들어오는 페이지들을 **연결 리스트(Linked List)**나 배열 큐의 맨 뒤(Tail)에 척척 꽂아 넣는다.
램이 꽉 차서 페이지 폴트가 터지면?
OS는 큐의 맨 앞(Head)에 있는 놈을 툭 빼서(Pop) 디스크로 날려버리고, 새로 가져온 놈을 다시 맨 뒤(Tail)에 꽂는다(Push).
소요 시간: $O(1)$. 무거운 루프를 돌며 타임스탬프를 비교하거나(LRU), 카운트를 더하고 빼는(LFU) 오버헤드가 단 1클럭도 발생하지 않는다. 이것이 이 멍청한 알고리즘이 가진 유일하고도 찬란한 무기다.

치명적 한계: '벨라디의 모순 (Belady's Anomaly)'

FIFO의 숨통을 끊어놓은 가장 무서운 수학적 버그다. (이전 키워드에서 상세 서술됨)

"램을 3장 줬을 때 페이지 폴트가 9번 났다면, 램을 4장 꽂아주면 9번 이하로 폴트가 떨어져야 정상이다."
하지만 FIFO를 돌리면 램을 4장 줬을 때 폴트가 10번으로 늘어나는 **기형적인 그래프(역전 현상)**가 특정 패턴(예: 1 2 3 4 1 2 5 1 2 3 4 5)에서 정확히 터져 나온다.
즉, 비싼 돈 주고 서버 램을 증설했는데 서버 렉이 더 심해지는 대재앙이 벌어진다. 이 예측 불가능성(Unpredictability) 때문에 현업 서버 엔지니어들은 FIFO를 절대 범용 페이지 교체용으로 쓰지 않게 되었다.
📢 섹션 요약 비유: 창고(램)가 좁아서 물건을 자꾸 빼고 넣는 게 힘들길래, 돈을 들여 창고 평수를 넓혀(프레임 증가) 줬습니다. 그런데 창고지기(FIFO)가 넓어진 창고 안에서 물건 빼는 순서를 완전히 헷갈려버려서 오히려 전보다 일처리를 더 멍청하게(폴트 증가) 해버리는 환장할 노릇입니다.

Ⅲ. 융합 비교 및 다각도 분석

비교 1: FIFO vs LRU (현실과 이상의 충돌)

수십 년간 이어진 운영체제 성능 대결의 영원한 라이벌이다.

비교 항목	FIFO (First-In First-Out)	LRU (Least Recently Used)
타겟 선정 기준	언제 램에 처음 들어왔는가? (과거 진입 시간)	언제 마지막으로 썼는가? (최근 접근 시간)
운영체제 짐(Overhead)	매우 가벼움 ($O(1)$ 큐 빼기)	매우 무거움 (수만 개 페이지의 랭킹을 매번 갱신)
지역성(Locality) 반영	0% (완전 무시, 자해 공갈 터짐)	100% (과거를 통해 미래 예측 완벽)
벨라디의 모순	☠️ 심심하면 터짐	🟢 스택 성질 덕분에 절대 안 터짐

하드웨어 설계자들의 피 튀기는 딜레마

CPU 안의 캐시(L1/L2)를 교체할 때 하드웨어 회로로 무거운 LRU를 100% 짜 넣으면 CPU 발열이 폭발하고 가격이 미친 듯이 올라간다.
"그럼 회로를 가장 싸게 칠 수 있는 FIFO 칩셋으로 때우면 안 돼?"
하지만 FIFO를 쓰면 CPU 캐시가 벨라디 모순에 걸려 뻗어버린다.
그래서 나온 타협안이 **"기본 틀은 FIFO(원형 큐)처럼 싸게 뱅글뱅글 돌리되, 쫓아내기 전에 한 번 쓱 눈치를 보고(참조 비트 검사), 한 번이라도 불린 놈은 봐주고 다음 놈을 쫓아내자!"**라는 것이다.
이것이 바로 Second-Chance (2차 기회) 알고리즘, 일명 Clock 알고리즘이다. FIFO의 껍데기에 LRU의 영혼을 강제로 주입한 현대 아키텍처의 구세주다. (다음 키워드에서 배울 내용의 떡밥이다).

┌──────────┬────────────┬────────────┬───────────────────────────────┐
│ 발전 단계  │ 알고리즘 뼈대 │ 오버헤드 부하 │ 실무(OS) 채택         │
├──────────┼────────────┼────────────┼───────────────────────────────┤
│ 1세대    │ 순수 FIFO   │ 깃털처럼 가벼움│ ❌ 폐기 처분             │
│ 2세대    │ 순수 LRU    │ 쇠구슬처럼 무거움│ ❌ 이론적 제왕         │
│ 3세대    │ **Clock (2차)**│ **가벼운데 똑똑함**│ 🟢 **최종 승리자**│
└──────────┴────────────┴────────────┴───────────────────────────────┘

[매트릭스 해설] FIFO는 스스로는 아무 쓸모 없는 실패작이었지만, 자기가 가진 둥그런 '원형 큐(Circular Queue)'라는 극강의 가성비 구조를 남김으로써 후대 알고리즘들이 하드웨어 제약(오버헤드)을 뚫고 실무에 안착할 수 있도록 뼈대를 제공해 준 위대한 밑거름이 되었다.

📢 섹션 요약 비유: 싸고 가벼운 자전거(FIFO)로는 짐을 못 나르고, 100톤짜리 트럭(LRU)은 기름값(오버헤드)이 너무 많이 듭니다. 결국 자전거 뒤에 작은 모터(1비트 참조 비트)를 단 '전기 자전거(Clock 알고리즘)'가 배달 시장(현대 OS)을 싹쓸이한 것과 같습니다. 전 자전거의 뼈대는 FIFO에서 온 것이죠.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오: FIFO가 아직도 살아 숨 쉬는 유일한 곳 (Varnish / CDN)

OS의 메인 메모리 관리에서는 쫓겨났지만, 특수한 웹 인프라 환경에서는 FIFO가 아직도 깡패 같은 효율을 뽐낸다.

상황: 넷플릭스나 유튜브의 엣지(Edge) 캐시 서버(CDN)에 수만 개의 영상 조각이 들어온다.
LRU의 실패: 동영상은 한 번 보면 끝이다. 영화를 앞에서부터 뒤로 1번 쭉 보고 치우는 패턴(Sequential Access)에서는, LRU를 써봐야 과거를 돌아보는 게 아무런 쓸모가 없다(한 번 본 영상을 뒤로 돌려보지 않으므로).
FIFO의 화려한 부활:
- 이런 환경에서는 "복잡하게 언제 마지막으로 봤는지 타임스탬프 찍지 말고, 그냥 서버에 들어온 지 10시간 지난 낡은 영상부터 무식하게 순서대로 밀어버려라!(FIFO)"
- 이 단순한 룰 하나가 거대 서버의 CPU 부하를 수십 % 덜어주며, Varnish Cache 같은 특수 목적 프록시 서버에서 FIFO는 LRU를 씹어 먹는 최강의 캐시 교체 엔진으로 돌변한다.

안티패턴: 페이지 스래싱과 맹목적 FIFO

만약 내가 짠 C++ 프로그램이 for 루프를 돌면서 배열의 0~10000번 인덱스를 뱅글뱅글 돈다고 치자. OS가 미쳐서 FIFO로 메모리를 교체한다면, 배열 0번지가 가장 먼저 들어왔으므로 루프가 한 바퀴 돌 때마다 0번지가 스왑으로 쫓겨난다. 0번지를 다시 부르면 1번지가 쫓겨난다. 최악의 자해 공갈(Thrashing)이 영원히 터지며 코드가 기어가게 된다. FIFO는 루프(Loop) 구조를 가진 거의 모든 현대 프로그래밍 언어의 앙숙이다.

📢 섹션 요약 비유: 한 번 읽고 버리는 신문지(동영상/스트리밍)는 어제 산 신문부터 순서대로 버리는 FIFO가 최고입니다. 하지만 수시로 뒤적거려야 하는 백과사전(변수/루프)을 어제 샀다고 해서 제일 먼저 쓰레기통에 버렸다가는 숙제할 때마다 서점에 다시 뛰어가야 하는 생고생을 치릅니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

정량/정성 기대효과

구분	내용
하드웨어 구현의 초단순화	포인터만 한 칸씩 전진시키면 되므로, 초기 트랜지스터 칩셋의 면적과 발열을 극적으로 억제한 일등 공신
순차적 워크로드의 극한 효율	한 번 훑고 버리는 대용량 로그 스캔, 스트리밍 미디어 서비스에서는 LRU의 오버헤드를 비웃으며 $O(1)$의 압도적 쾌속 처리량 달성
현대 융합 알고리즘의 골조	FIFO의 큐(Queue) 껍데기에 기회(Chance) 비트를 덧대어 만든 Clock(2차 기회) 알고리즘으로 진화하여 리눅스 커널의 심장으로 영원히 생존

결론 및 미래 전망

FIFO (First-In, First-Out) 교체 알고리즘은 가상 메모리의 태동기에 "일단 쫓아내고 보자"는 가장 원초적인 인간의 직관이 만들어낸 야생의 규칙이다. 하지만 프로그램은 시간의 순서대로 흐르는 1차원적 강물이 아니라, 앞뒤를 오가며 춤을 추는(Locality) 복잡한 왈츠였다는 사실을 벨라디의 모순을 통해 뼈저리게 증명해 낸 반면교사의 아이콘이 되었다. 비록 범용 운영체제(OS)의 페이지 살생부 자리에서는 쫓겨났지만, 그 깃털처럼 가벼운 속도(Zero-Overhead)의 매력은 사라지지 않아 빅데이터 스트리밍 버퍼 캐시나 초경량 IoT 하드웨어 칩셋 내부에서 여전히 자신만의 확고한 영토를 구축하고 있다. FIFO는 죽은 것이 아니라, 가장 단순한 것이 가장 빠른 곳을 찾아 진화의 곁가지를 탄 것일 뿐이다.

📢 섹션 요약 비유: 무기라고는 몽둥이(포인터 조작) 하나밖에 없는 힘센 바보(FIFO)가 머리를 써야 하는 마법사들의 체스 판(페이지 교체)에서는 처참하게 졌지만, 무식하게 돌만 부수면 되는 광산(스트리밍 캐시)으로 취직해서는 전 세계 최고의 광부가 된 통쾌한 인생 역전극입니다.

📌 관련 개념 맵 (Knowledge Graph)

벨라디의 모순 (Belady's Anomaly) | 램을 더 꽂아줬는데 FIFO가 멍청하게 핵심 페이지를 버려서 폴트가 폭발하는 역사적 버그 현상
LRU (Least Recently Used) | FIFO의 멍청함을 까발리고 왕좌를 차지한, 과거를 통해 미래를 예측하는 현대 캐시의 바이블
Clock Algorithm (2차 기회) | FIFO의 원형 큐 구조를 그대로 가져와 포인터를 뱅글뱅글 돌리며 LRU를 흉내 내는 천재적인 하이브리드 알고리즘
스래싱 (Thrashing) | FIFO가 초기 필수 전역 변수(핵심 뼈대)를 버렸다가 0.1초 뒤 다시 퍼오기를 반복하며 서버를 얼려버리는 최악의 패닉
지역성 (Locality) | 프로그램은 한 번 부른 걸 계속 뺑글뺑글 부른다는 성질로, 이것 때문에 시간만 재는 FIFO가 처참히 무너짐

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

FIFO가 무엇인가요? 줄 서서 햄버거를 살 때 "제일 먼저 온 사람부터 차례대로 하나씩 주세요!" 하는 아주 단순하고 공평한 규칙이에요.
페이지 교체에서 이걸 쓰면 왜 나빠요? 내 필통에 가장 먼저 넣은 게 '핵심 지우개'인데, 필통이 꽉 찼다고 "제일 먼저 넣은 지우개부터 쓰레기통에 버려!"라고 해버리니까, 글씨를 지울 때마다 지우개를 새로 사러 뛰어나가야 해서 바보가 되거든요.
그럼 언제 쓰면 좋아요? 다 본 만화책을 버릴 때, 1편부터 순서대로 버리면 아무 문제 없이 시원하게 책장을 비울 수 있을 때(스트리밍) 가장 좋답니다!