FIFO(First-In, First-Out, 선입선출)는 가장 먼저 메모리에 올라온 페이지를 가장 먼저 제거하는 페이지 교체 알고리즘이다. 구조가 단순하고 구현이 쉬워 초기 운영체제에서 널리 사용되었지만, 페이지 교체 성능은 다른 알고리즘에 비해 낮을 수 있다.
개념
FIFO는 페이지가 메모리에 올라온 순서를 기억하고, 페이지 프레임이 가득 찼을 때 가장 오래전에 들어온 페이지부터 교체한다. 이는 큐(Queue) 자료구조와 유사한 방식이다.
- 교체 대상 결정 기준: 삽입 순서
- 페이지가 참조된 횟수나 시점은 고려하지 않음
동작 방식
- 페이지 요청이 들어옴
- 프레임에 공간이 있으면 페이지 삽입
- 공간이 없으면 가장 오래된 페이지 제거 후 새 페이지 삽입
예시
페이지 프레임 수: 3 페이지 요청 순서: 7, 0, 1, 2, 0, 3, 0, 4
동작:
- 7 → [7]
- 0 → [7, 0]
- 1 → [7, 0, 1]
- 2 → [0, 1, 2] (7 제거)
- 0 → [0, 1, 2] (히트)
- 3 → [1, 2, 3] (0 제거)
- 0 → [2, 3, 0] (1 제거)
- 4 → [3, 0, 4] (2 제거)
→ 페이지 폴트: 6회
장점
- 구현이 단순하고 직관적임
- 추가적인 연산이나 자료구조가 거의 필요 없음
단점
- 페이지가 얼마나 자주 또는 최근에 사용되었는지를 고려하지 않음
- Belady의 역설이 발생할 수 있음:
- 프레임 수가 증가했는데도 페이지 폴트 수가 늘어나는 비정상적인 현상
FIFO vs LRU vs LFU
| 알고리즘 | 교체 기준 | 장점 | 단점 |
|---|---|---|---|
| FIFO | 가장 오래된 페이지 | 단순함 | 사용 빈도 고려하지 않음 |
| LRU (페이지 교체 알고리즘) | 가장 오랫동안 사용되지 않은 페이지 | 지역성 반영 | 구현 복잡도 ↑ |
| LFU (페이지 교체 알고리즘) | 가장 적게 사용된 페이지 | 사용 빈도 반영 | 오래된 정보 유지 위험 |
같이 보기
참고 문헌
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
- Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson