요약
- FIFO 페이지 교체 알고리즘이란?
- FIFO 알고리즘 동작 원리
- FIFO 알고리즘의 장점과 단점
- FIFO 알고리즘의 동작 예시
- FIFO 알고리즘과 스레싱
- FIFO 알고리즘 시간 복잡도
- FIFO 알고리즘을 사용한 메모리 관리 예시
1. FIFO 페이지 교체 알고리즘이란?
FIFO(First-In, First-Out) 페이지 교체 알고리즘은 가장 오래 전에 메모리에 적재된 페이지를 제거하는 기법입니다. 가장 먼저 들어온 페이지가 가장 먼저 나가는 원리를 따르며, 큐(Queue) 자료구조를 사용하여 페이지 프레임을 관리합니다.
2. FIFO 알고리즘 동작 원리
FIFO 알고리즘은 페이지 부재(page fault)가 발생하면 가장 먼저 메모리에 적재된 페이지를 제거합니다. 새 페이지를 적재할 때는 가장 오래된 페이지를 대체하는 방식으로 동작합니다. 큐 자료구조를 사용하여 페이지 프레임을 관리하며, 먼저 들어온 페이지가 큐의 맨 앞에 위치하게 됩니다.
3. FIFO 알고리즘의 장점과 단점
장점: 구현이 간단하며, 페이지 교체 비용을 줄일 수 있습니다. 또한, 페이지의 이용 빈도와 상관없이 항상 공평한 기회를 가지게 됩니다.
단점: FIFO 알고리즘은 페이지의 이용 패턴을 고려하지 않기 때문에, 최적의 페이지 교체 알고리즘보다 성능이 낮을 수 있습니다. 이러한 특성으로 인해 스레싱(thrashing) 현상을 유발할 수 있습니다.
4. FIFO 알고리즘의 동작 예시
가정: 페이지 프레임 크기가 3인 상황에서의 FIFO 알고리즘 예시입니다.
페이지 참조 순서: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3
--------------------------------------------------
페이지 프레임 현재 상태 페이지 부재 수
--------------------------------------------------
1 1 1
1, 2 1, 2 2
1, 2, 3 1, 2, 3 3
2, 3, 4 2, 3, 4 4
3, 4, 1 2, 3, 4 5
4, 1, 2 2, 3, 4 6
1, 2, 5 3, 4, 1 7
2, 5, 1 3, 4, 2 8
5, 1, 2 4, 2, 5 9
1, 2, 3 2, 5, 1 10
--------------------------------------------------
5. FIFO 알고리즘과 스레싱
FIFO 알고리즘은 페이지 이용 패턴을 고려하지 않기 때문에 스레싱(thrashing) 현상을 유발할 수 있습니다. 스레싱은 프로세스가 너무 많은 페이지 부재로 인해 실제 작업보다 페이지 교체에 시간을 더 많이 소비하는 상황을 의미합니다. FIFO 알고리즘은 이러한 스레싱 현상을 예방하지 못하는 단점이 있습니다.
6. FIFO 알고리즘 시간 복잡도
FIFO 알고리즘의 시간 복잡도는 페이지 부재가 발생할 때마다 가장 오래된 페이지를 교체하는 작업을 수행합니다. 이 작업은 페이지 프레임의 크기와 무관하며, O(1)의 시간 복잡도를 갖습니다.
7. FIFO 알고리즘을 사용한 메모리 관리 예시
FIFO 알고리즘은 메모리 관리에서 가장 간단한 형태의 페이지 교체 알고리즘 중 하나입니다. 예를 들어, 운영체제에서 프로세스 간에 메모리를 할당할 때 FIFO 알고리즘을 사용하여 페이지 프레임을 교체할 수 있습니다.