FIFO
FIFO(First In First Out, 선입선출)는 가장 먼저 들어온 것을 가장 먼저 처리하는 순서 방식이다. 일상의 줄 서기와 같은 직관적인 모델로, 큐(Queue) 자료구조와 페이지 교체 알고리즘 등 다양한 분야의 기본 원리로 쓰인다.
적용 영역
자료구조 — 큐(Queue)
한쪽 끝(rear)에 데이터를 넣고, 반대쪽 끝(front)에서 꺼낸다.
페이지 교체 알고리즘
메모리에 가장 오래 머무른 페이지를 가장 먼저 교체.
메시지 큐
이벤트·작업이 도착한 순서대로 처리해 공정성을 보장.
장점
- 단순함: 구현이 매우 쉽다.
- 공정성: 모든 요청이 도착 순서대로 처리됨.
- 예측 가능성: 처리 순서가 명확하다.
단점 — Belady의 변칙
페이지 교체에서 FIFO는 프레임 수를 늘렸는데 페이지 폴트가 더 늘어나는 직관에 반하는 현상이 발생할 수 있다. 이를 Belady의 변칙(Belady’s Anomaly)이라고 한다. 따라서 페이지 교체에는 보통 LRU, NUR 같은 기법을 더 선호한다.