[운영체제] 페이지 교체 알고리즘 비교: FIFO, LRU, LFU 차이점과 동작 원리

1. 페이지 교체 알고리즘이란?

컴퓨터는 가상 메모리를 사용하여, 주기억장치(RAM)보다 더 많은 데이터를 다룰 수 있습니다.
그러나 RAM의 크기는 한정되어 있기 때문에, 필요한 데이터를 디스크에서 RAM으로 불러오는 작업이 필요합니다. 이때 RAM이 가득 차게 되면, 새로운 데이터를 RAM에 적재할 때 기존의 데이터를 교체해야 합니다. 이때 사용하는 알고리즘이 바로 페이지 교체 알고리즘이에요!

📌 비유: 집에 제한된 공간이 있을 때, 서랍에 책을 넣고 빼는 방식을 생각할 수 있어요. 서랍이 가득 차면, 새로운 책을 넣기 위해 어떤 책을 빼야 할지 결정해야 하죠! 📚

---

2. 대표적인 페이지 교체 알고리즘

1️⃣ FIFO (First-In, First-Out)

• FIFO는 먼저 들어온 페이지를 먼저 교체하는 방식입니다.
• 즉, 가장 오래된 페이지를 제일 먼저 빼고, 새로운 페이지를 넣는 방식이에요.

📌 비유: FIFO는 학교 급식에서 줄 서서 차례대로 음식을 받는 방식처럼 생각할 수 있어요! 앞에 서 있는 사람이 먼저 음식을 받아가죠. 🍲

2️⃣ LRU (Least Recently Used)

• LRU는 가장 오래 전에 사용된 페이지를 교체하는 방식입니다.
• 즉, 가장 최근에 사용하지 않은 페이지를 빼고 새로운 페이지를 넣어요.

📌 비유: LRU는 책을 빌리는 도서관에서 가장 오랫동안 읽지 않은 책을 반납하는 것처럼 생각할 수 있어요! 📖

3️⃣ LFU (Least Frequently Used)

• LFU는 사용 빈도가 가장 적은 페이지를 교체하는 방식입니다.
• 가장 적게 사용된 페이지를 빼고 새로운 페이지를 넣습니다.

📌 비유: LFU는 가장 적게 읽은 책을 반납하는 도서관과 비슷해요. 자주 대출되지 않은 책이 먼저 반납되죠. 📚

---

3. 간단한 예시 코드

이제 Python 코드로 각 페이지 교체 알고리즘을 간단한 시뮬레이션을 통해 보여드릴게요! 각 알고리즘의 기본 동작을 확인할 수 있어요.

📌 FIFO 예시 코드

from collections import deque

# FIFO 알고리즘
def fifo(page_references, memory_size):
    memory = deque(maxlen=memory_size)
    page_faults = 0

    for page in page_references:
        if page not in memory:
            page_faults += 1  # 페이지 폴트 발생
            memory.append(page)  # 새로운 페이지 삽입
        print(f"현재 메모리 상태: {list(memory)}")

    return page_faults

# 페이지 참조 순서와 메모리 크기
page_references = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3]
memory_size = 3
faults = fifo(page_references, memory_size)
print(f"총 페이지 폴트: {faults}")

동작 설명:

• deque를 사용하여 메모리를 관리합니다.
• 페이지가 메모리에 없으면 새로운 페이지를 추가하고, 메모리가 꽉 차면 가장 오래된 페이지를 제거합니다.
• 페이지 참조 순서에 따라, 메모리가 어떤 페이지를 교체하는지 확인할 수 있습니다.

---

📌 LRU 예시 코드

from collections import OrderedDict

# LRU 알고리즘
def lru(page_references, memory_size):
    memory = OrderedDict()
    page_faults = 0

    for page in page_references:
        if page in memory:
            memory.move_to_end(page)  # 최근에 사용된 페이지는 끝으로 이동
        else:
            page_faults += 1  # 페이지 폴트 발생
            if len(memory) == memory_size:
                memory.popitem(last=False)  # 가장 오래된 페이지 제거
            memory[page] = True  # 새로운 페이지 추가

        print(f"현재 메모리 상태: {list(memory.keys())}")

    return page_faults

# 페이지 참조 순서와 메모리 크기
page_references = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3]
memory_size = 3
faults = lru(page_references, memory_size)
print(f"총 페이지 폴트: {faults}")

동작 설명:

• OrderedDict를 사용하여 메모리의 순서를 유지합니다.
• 페이지가 메모리에 있으면 가장 최근에 사용되었음을 표시하고, 없으면 새 페이지를 추가하며, 메모리가 꽉 차면 가장 오래된 페이지를 제거합니다.

---

📌 LFU 예시 코드

from collections import Counter

# LFU 알고리즘
def lfu(page_references, memory_size):
    memory = []
    page_faults = 0
    usage_count = Counter()

    for page in page_references:
        if page not in memory:
            page_faults += 1  # 페이지 폴트 발생
            if len(memory) == memory_size:
                # 가장 적게 사용된 페이지를 교체
                least_used_page = min(memory, key=lambda p: usage_count[p])
                memory.remove(least_used_page)
            memory.append(page)
        usage_count[page] += 1  # 페이지 사용 횟수 증가

        print(f"현재 메모리 상태: {memory}")

    return page_faults

# 페이지 참조 순서와 메모리 크기
page_references = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3]
memory_size = 3
faults = lfu(page_references, memory_size)
print(f"총 페이지 폴트: {faults}")

동작 설명:

• Counter를 사용하여 각 페이지의 사용 횟수를 추적합니다.
• 페이지가 메모리에 없으면 새 페이지를 추가하고, 메모리가 꽉 차면 가장 적게 사용된 페이지를 교체합니다.

---

4. 비유와 요약

알고리즘	동작 방식	비유
FIFO	가장 먼저 들어온 페이지를 먼저 교체	학교 급식 줄 서서 음식을 받는 방식
LRU	가장 오래 전에 사용된 페이지를 교체	가장 오랫동안 읽지 않은 책 반납
LFU	가장 적게 사용된 페이지를 교체	가장 적게 읽은 책을 반납하는 도서관

---

5. 컨셉 정리

• FIFO는 가장 먼저 들어온 페이지를 먼저 교체하는 방식입니다.
• LRU는 가장 오래 전에 사용된 페이지를 교체하는 방식입니다.
• LFU는 가장 적게 사용된 페이지를 교체하는 방식입니다.