FIFO 페이지 교체 알고리즘

📘 FIFO 페이지 교체 알고리즘

📖 페이지 교체란 무엇인가?

컴퓨터는 프로그램을 실행할 때 메모리에 데이터를 불러와서 작업합니다.
하지만 메모리의 크기는 무한하지 않습니다.
예를 들어 메모리가 동시에 최대 3개의 데이터만 저장할 수 있다고 가정했을 때, 새로운 데이터를 불러와야 하면 기존 데이터 중 하나를 내리고 그 자리에 새로운 데이터를 올려야 합니다.
이때 어떤 데이터를 내릴지를 결정하는 규칙을 페이지 교체 알고리즘이라고 합니다.
이 글에서는 그중에서도 가장 단순하고 기본적인 FIFO (First In First Out) 알고리즘에 대해 알아보겠습니다.

📖 FIFO란 무엇인가?

FIFO는 영어로 First In First Out, 즉 먼저 들어온 것이 먼저 나간다는 뜻입니다.
줄을 서서 기다리는 상황을 생각해 보면 쉽습니다.
가장 먼저 줄에 선 사람이 가장 먼저 처리되고, 가장 늦게 줄 선 사람은 가장 늦게 처리됩니다.
FIFO는 이 원리를 그대로 메모리에 적용한 것입니다.
메모리에 저장된 데이터 중에서 가장 오래 전에 들어온 데이터를 제거하고, 그 자리에 새로운 데이터를 넣습니다.

📖 FIFO가 왜 필요한가?

메모리에서 데이터를 무작위로 지우면 성능이 크게 떨어질 수 있습니다.
방금 전에 들어온 중요한 데이터를 지우면 바로 다시 불러와야 하기 때문입니다.
FIFO는 규칙이 단순하고 구현이 쉽기 때문에, 운영체제 입문 단계에서 널리 사용됩니다.
하지만 자주 사용되던 데이터라도 오래됐다는 이유만으로 제거될 수 있다는 단점이 있습니다.

📖 FIFO의 작동 원리

FIFO의 동작은 매우 단순합니다.

• ✅ 메모리에 데이터가 들어올 때마다 순서를 기록합니다.
• ✅ 메모리에 여유가 있으면 새로운 데이터를 넣습니다.
• ✅ 메모리가 가득 찼다면, 가장 오래된 데이터를 제거합니다.
• ✅ 새로운 데이터는 항상 가장 최근 위치에 추가됩니다.

중요: 메모리 상태를 표로 표현할 때는 항상 왼쪽이 가장 오래된 데이터이고, 오른쪽이 가장 최근에 들어온 데이터입니다.
예: [7, 0, 1] → 가장 오래된 데이터는 7, 가장 최신 데이터는 1

📖 예시로 배우기

이제 구체적인 예시를 통해 FIFO가 어떻게 동작하는지 단계별로 살펴보겠습니다.

📄 전제 조건

• 메모리 크기: 3개(프레임 3개)
• 페이지 참조 순서:

7, 0, 1, 2, 0, 3, 0, 4

데이터를 불러올 때 메모리에 없으면 페이지 폴트, 메모리에 있으면 페이지 히트가 발생합니다.

📖 단계별 과정 — 매 단계마다 남은 데이터부터 보기

🔷 1단계

• 📜 남은 참조 순서: 7, 0, 1, 2, 0, 3, 0, 4
• 🔗 이번에 불러올 데이터: 7
• 행동: 메모리에 7이 없으니 추가합니다. (페이지 폴트)
• 📌 메모리 상태: [7]

🔷 2단계

• 📜 남은 참조 순서: 0, 1, 2, 0, 3, 0, 4
• 🔗 이번에 불러올 데이터: 0
• 행동: 메모리에 0이 없으니 추가합니다. (페이지 폴트)
• 📌 메모리 상태: [7, 0]

🔷 3단계

• 📜 남은 참조 순서: 1, 2, 0, 3, 0, 4
• 🔗 이번에 불러올 데이터: 1
• 행동: 메모리에 1이 없으니 추가합니다. (페이지 폴트)
• 📌 메모리 상태: [7, 0, 1]

🔷 4단계

• 📜 남은 참조 순서: 2, 0, 3, 0, 4
• 🔗 이번에 불러올 데이터: 2
• 행동: 메모리가 가득 찼습니다. 가장 오래된 7을 제거하고 2를 넣습니다. (페이지 폴트)
• 📌 메모리 상태: [0, 1, 2]

🔷 5단계

• 📜 남은 참조 순서: 0, 3, 0, 4
• 🔗 이번에 불러올 데이터: 0
• 행동: 0은 메모리에 이미 있습니다. (페이지 히트)
• 📌 메모리 상태: [0, 1, 2]

🔷 6단계

• 📜 남은 참조 순서: 3, 0, 4
• 🔗 이번에 불러올 데이터: 3
• 행동: 메모리가 가득 찼습니다. 가장 오래된 0을 제거하고 3을 넣습니다. (페이지 폴트)
• 📌 메모리 상태: [1, 2, 3]

🔷 7단계

• 📜 남은 참조 순서: 0, 4
• 🔗 이번에 불러올 데이터: 0
• 행동: 메모리가 가득 찼습니다. 가장 오래된 1을 제거하고 0을 넣습니다. (페이지 폴트)
• 📌 메모리 상태: [2, 3, 0]

🔷 8단계

• 📜 남은 참조 순서: 4
• 🔗 이번에 불러올 데이터: 4
• 행동: 메모리가 가득 찼습니다. 가장 오래된 2를 제거하고 4를 넣습니다. (페이지 폴트)
• 📌 메모리 상태: [3, 0, 4]

📖 최종 결과

• 최종 메모리 상태: [3, 0, 4]
• 페이지 폴트 발생 횟수: 7회
• 페이지 히트 발생 횟수: 1회

📖 FIFO의 장점과 단점

장점

• ✅ 규칙이 단순하고 이해하기 쉽습니다.
• ✅ 구현이 빠르고 쉽습니다.
• ✅ 특별한 계산이 필요하지 않습니다.

단점

• ❌ 자주 사용되던 데이터라도 오래됐다는 이유로 제거될 수 있습니다.
• ❌ 최근에 사용되지 않은 데이터가 남아 있을 수도 있습니다.
• ❌ 프로그램의 데이터 접근 패턴과 맞지 않으면 성능이 떨어질 수 있습니다.

📖 마무리

• ✅ ``` FIFO는 먼저 들어온 데이터를 먼저 내보내는 페이지 교체 알고리즘입니다.
• ✅ 단계별로 남아 있는 참조 순서를 먼저 보여주면 진행 상황을 직관적으로 이해하기 쉽습니다.
• ✅ 규칙이 단순해서 배우기 쉽고, 구현하기도 쉽습니다.
• ✅ 다만, 자주 쓰이는 데이터도 오래됐다는 이유로 제거될 수 있다는 점을 이해해야 합니다.