페이지 교체 알고리즘 정리

운영체제에서 페이지 교체 알고리즘은 메모리 관리에서 중요한 역할을 합니다. 프로세스 실행 중 페이지 부재(Page Fault)가 발생할 때, 기존 페이지 중 하나를 교체해야 하는 상황에서 어떤 페이지를 제거할지를 결정하는 다양한 알고리즘이 있습니다.

이 글에서는 LRU, FIFO, LFU, Optimal 등 주요 페이지 교체 알고리즘의 개념, 특징, 장단점, 실제 사용 사례를 자세히 살펴보겠습니다.

---

1. 주요 페이지 교체 알고리즘 개념과 특징

알고리즘	개념	특징
FIFO (First In First Out)	가장 먼저 들어온 페이지를 제거	단순하지만 효율이 낮음
LRU (Least Recently Used)	가장 오랫동안 사용되지 않은 페이지 제거	시간 지역성 고려, 구현 복잡
LFU (Least Frequently Used)	가장 적게 사용된 페이지 제거	빈도 기반, 장기적 사용 분석
Optimal (OPT)	앞으로 가장 오래 사용되지 않을 페이지 제거	이론적으로 최적, 현실적 구현 불가
MRU (Most Recently Used)	가장 최근에 사용된 페이지 제거	특수한 경우에 유리함
Random Replacement	임의의 페이지 제거	구현이 간단함

---

2. 각 알고리즘의 장단점 정리

2.1. FIFO (First In First Out)

장점:

• 구현이 쉽고 직관적이다.
• 추가적인 데이터 구조가 필요하지 않다.

단점:

• 오래된 페이지가 항상 제거되므로, 자주 사용되는 페이지가 교체될 수 있다.
• Belady's Anomaly(벨라디의 이상 현상)가 발생할 수 있음.

사용 사례:

• 간단한 시스템 메모리 관리

---

2.2. LRU (Least Recently Used)

장점:

• 시간 지역성(Locality of Reference)을 고려한다.
• 캐시 관리에 효율적이다.

단점:

• 구현이 복잡하며, 페이지 목록을 관리해야 한다.
• 높은 메모리 및 시간 오버헤드 발생

사용 사례:

• 운영체제 메모리 관리, 데이터베이스 캐싱 시스템, 웹 브라우저 캐시

---

2.3. LFU (Least Frequently Used)

장점:

• 자주 사용되는 페이지를 유지하므로 효율적이다.
• 장기적인 사용 패턴을 고려한다.

단점:

• 최근 사용이 아닌 전체 사용 빈도만 고려하므로 단기적인 페이지 부하에는 취약하다.
• 구현이 복잡하다.

사용 사례:

• 캐시 관리 시스템, 추천 시스템(사용자 행동 기반)

---

2.4. Optimal (OPT)

장점:

• 이론적으로 가장 적은 페이지 부재 발생
• 페이지 교체 효율이 최고

단점:

• 미래의 페이지 참조를 알아야 하므로 현실적이지 않음

사용 사례:

• 알고리즘 성능 비교와 연구

---

2.5. MRU (Most Recently Used)

장점:

• 특수한 워크로드에서는 효율적이다.

단점:

• 일반적인 경우 성능이 낮음
• 시간 지역성을 무시함

사용 사례:

• 특정 데이터베이스 쿼리 시스템

---

2.6. Random Replacement

장점:

• 구현이 매우 간단하다.
• 시간 복잡도가 낮다.

단점:

• 랜덤 교체로 인해 예측할 수 없는 성능

사용 사례:

• 메모리 부족 상황에서 빠른 대응이 필요한 시스템

---

3. 페이지 교체 알고리즘 실제 사용 사례 (파이썬 코드 예제)

다음은 LRU 페이지 교체 알고리즘의 간단한 파이썬 구현입니다:

from collections import OrderedDict

# LRU 페이지 교체 알고리즘
class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        # 사용된 키를 최신 상태로 갱신
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            # 이미 존재하는 키면 업데이트 후 최신 상태로 갱신
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 가장 오래된 항목 제거
            self.cache.popitem(last=False)

# 실행 예시
lru = LRUCache(3)
lru.put(1, "Page 1")
lru.put(2, "Page 2")
lru.put(3, "Page 3")
print("현재 캐시 상태:", lru.cache)

# 페이지 접근
lru.get(2)
lru.put(4, "Page 4")
print("페이지 교체 후 캐시 상태:", lru.cache)