FIFO, LRU, OPT? 페이지 교체 알고리즘 완벽 비교 정리!

운영체제에서 메모리 관리는 매우 중요한 개념이다.
그중에서도 페이지 교체 알고리즘은 CPU가 필요한 페이지를 메모리에 올릴 때,

기존 페이지를 어떤 기준으로 내릴지를 결정하는 핵심 로직이다.

가장 많이 언급되는 알고리즘은 FIFO, LRU, OPT다.
이 글에서는 이 세 가지 알고리즘의 개념, 특징, 차이점을 정리해본다.

---

✅ FIFO (First In First Out)

가장 먼저 메모리에 올라온 페이지를 가장 먼저 제거한다.
선입선출 방식이라 구현은 간단하지만, Belady의 역설과 같이 비효율적인 결과를 초래할 수 있다.

• 장점: 구현이 쉽다.
• 단점: 최근에 자주 쓰이던 페이지가 제거될 수 있다.
• 예시: 페이지 참조열이 [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] 일 때
  3프레임일 경우 부재 횟수는 9회.

---

✅ LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 제거한다.
현실적인 정책으로 널리 쓰이지만, 최근 사용 이력을 저장해야 하기 때문에 구현이 복잡하다.

• 장점: 실제 사용 패턴과 유사한 방식
• 단점: 구현 비용이 큼
• 예시: 위와 같은 참조열에서 LRU 적용 시 부재 횟수는 8회.

---

✅ OPT (Optimal)

앞으로 가장 오래 사용되지 않을 페이지를 제거하는 방식이다.
가장 효율적인 방법이지만, 실제 미래를 알 수 없기 때문에 현실에서는 사용되지 않는다.

• 장점: 최적의 페이지 교체
• 단점: 미래 예측이 불가능 → 이론적 알고리즘
• 예시: 부재 횟수는 7회로 가장 낮다.

---

📊 요약 비교표

알고리즘	원리	장점	단점
FIFO	먼저 들어온 페이지 제거	구현 쉬움	효율성 낮음
LRU	가장 오래 안 쓰인 페이지 제거	현실적	구현 복잡
OPT	미래에 가장 늦게 쓰일 페이지 제거	최적	현실 적용 불가

---

📌 예시 코드 (자바)

import java.util.*;

public class FIFOExample {
    public static void main(String[] args) {
        int[] pages = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
        Queue<Integer> memory = new LinkedList<>();
        int capacity = 3;
        int faults = 0;

        for (int page : pages) {
            if (!memory.contains(page)) {
                if (memory.size() == capacity) memory.poll();
                memory.add(page);
                faults++;
            }
        }

        System.out.println("Page Faults: " + faults);
    }
}

---

📌 매일 간단히 IT 관련 개념을 익히고 싶다면 구독하세요!👇👇👇

http://www.youtube.com/@itbite_daily

오늘의 IT한입