FIFO (페이지 교체 알고리즘)

FIFO(First-In, First-Out, 선입선출)는 가장 먼저 메모리에 올라온 페이지를 가장 먼저 제거하는 페이지 교체 알고리즘이다. 구조가 단순하고 구현이 쉬워 초기 운영체제에서 널리 사용되었지만, 페이지 교체 성능은 다른 알고리즘에 비해 낮을 수 있다.

1 개념

FIFO는 페이지가 메모리에 올라온 순서를 기억하고, 페이지 프레임이 가득 찼을 때 가장 오래전에 들어온 페이지부터 교체한다. 이는 큐(Queue) 자료구조와 유사한 방식이다.

• 교체 대상 결정 기준: 삽입 순서
• 페이지가 참조된 횟수나 시점은 고려하지 않음

2 동작 방식

1. 페이지 요청이 들어옴
   • 프레임에 공간이 있으면 페이지 삽입
   • 공간이 없으면 가장 오래된 페이지 제거 후 새 페이지 삽입

3 예시

페이지 프레임 수: 3 페이지 요청 순서: 7, 0, 1, 2, 0, 3, 0, 4

동작:

1. 7 → [7]
2. 0 → [7, 0]
3. 1 → [7, 0, 1]
4. 2 → [0, 1, 2] (7 제거)
5. 0 → [0, 1, 2] (히트)
6. 3 → [1, 2, 3] (0 제거)
7. 0 → [2, 3, 0] (1 제거)
8. 4 → [3, 0, 4] (2 제거)

→ 페이지 폴트: 6회

4 장점

• 구현이 단순하고 직관적임
• 추가적인 연산이나 자료구조가 거의 필요 없음

5 단점

• 페이지가 얼마나 자주 또는 최근에 사용되었는지를 고려하지 않음
• Belady의 역설이 발생할 수 있음:
  • 프레임 수가 증가했는데도 페이지 폴트 수가 늘어나는 비정상적인 현상

6 FIFO vs LRU vs LFU

알고리즘	교체 기준	장점	단점
FIFO	가장 오래된 페이지	단순함	사용 빈도 고려하지 않음
LRU (페이지 교체 알고리즘)	가장 오랫동안 사용되지 않은 페이지	지역성 반영	구현 복잡도 ↑
LFU (페이지 교체 알고리즘)	가장 적게 사용된 페이지	사용 빈도 반영	오래된 정보 유지 위험

7 같이 보기

• 페이지 교체 알고리즘
• LRU (페이지 교체 알고리즘)
• LFU (페이지 교체 알고리즘)
• OPT (최적 페이지 교체)
• Belady의 역설
• 가상 메모리

8 참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson