먼저 들어온 것을 먼저 내보내는 처리 순서다. 줄을 선 순서대로 처리한다고 보면 되고, 이 규칙을 구현한 자료구조가 큐(queue) 다. 반대는 나중에 들어온 것을 먼저 꺼내는 LIFO 이고, stack 이 그쪽이다.
어디에 쓰나
BFS — 시작점에서 가까운 정점부터 층층이 방문하려면 “먼저 발견한 정점을 먼저 처리” 해야 한다. 큐에 넣고 앞에서 꺼내는 것이 곧 FIFO 다. 반면 DFS 는 마지막에 발견한 쪽으로 더 파고들어야 하므로 스택을 쓴다.
페이지 교체 알고리즘 — 메모리가 꽉 찼을 때 가장 오래전에 적재된 Page 를 내보낸다. 구현이 단순하고 적재 시각만 기록하면 되지만, 오래 있었다는 것과 앞으로 안 쓰인다는 것은 다른 이야기다. 자주 쓰이는 페이지도 오래됐다는 이유로 쫓겨나 곧바로 다시 Page Fault 가 나는 일이 생긴다. 그래서 실제로는 마지막 사용 시각을 보는 LRU 나 사용 빈도를 보는 LFU 를 더 쓴다.
FIFO 에는 프레임 수를 늘렸는데 오히려 page fault 가 늘어나는 Belady’s anomaly 라는 현상도 있다.