[Daily morning study] 페이지 교체 알고리즘 (FIFO, LRU, LFU, Clock)

16 Jun 2026 in Daily morning study / Operating System

#daily morning study

페이지 교체 알고리즘 (Page Replacement Algorithm)

왜 페이지 교체가 필요한가

가상 메모리는 실제 물리 메모리(RAM)보다 더 큰 주소 공간을 프로세스에게 제공한다. 프로세스가 접근하려는 페이지가 현재 물리 메모리에 없으면 페이지 폴트(Page Fault)가 발생하고, OS는 디스크(스왑 영역)에서 해당 페이지를 불러와야 한다.

문제는 물리 메모리가 꽉 찼을 때다. 새 페이지를 올리려면 기존 페이지 중 하나를 내보내야 한다. 이때 어떤 페이지를 교체할 것인가를 결정하는 것이 페이지 교체 알고리즘이다.

교체 알고리즘의 목표는 페이지 폴트 횟수를 최소화하는 것이다.

기본 개념 정리

페이지 프레임 (Page Frame)

물리 메모리를 고정 크기 단위로 나눈 슬롯이다. 예를 들어 물리 메모리에 프레임이 3개 있다면, 동시에 3개의 페이지만 올라가 있을 수 있다.

페이지 폴트 (Page Fault)

CPU가 참조하려는 페이지가 물리 메모리에 없는 상황이다. OS가 개입해 디스크에서 해당 페이지를 읽어오는데, 이 작업은 CPU 연산보다 수백만 배 느리다.

참조열 (Reference String)

페이지 교체 알고리즘 성능을 비교할 때 사용하는 페이지 접근 순서 목록이다.

예: 참조열 = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
    프레임 수 = 3

알고리즘 비교

1. FIFO (First-In, First-Out)

가장 오래전에 올라온 페이지를 먼저 내보낸다. 큐(queue) 구조로 구현하며 단순하다.

참조열: 7 0 1 2 0 3 0 4 2 3 0 3 2  (프레임 3개)

단계  | 참조 | 프레임 상태     | 폴트?
------|------|----------------|------
1     | 7    | [7, -, -]      | ✓
2     | 0    | [7, 0, -]      | ✓
3     | 1    | [7, 0, 1]      | ✓
4     | 2    | [2, 0, 1]      | ✓ (7 교체)
5     | 0    | [2, 0, 1]      |
6     | 3    | [2, 3, 1]      | ✓ (0 교체)
7     | 0    | [2, 3, 0]      | ✓ (1 교체)
8     | 4    | [4, 3, 0]      | ✓ (2 교체)
...

단점 — Belady의 역설(Belady’s Anomaly)

FIFO는 프레임 수를 늘렸는데 오히려 페이지 폴트가 증가하는 현상이 나타날 수 있다.

참조열: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 3개 → 폴트 9회
프레임 4개 → 폴트 10회  ← 더 많아짐!

2. Optimal (OPT, Bélády’s Algorithm)

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 미래를 미리 알아야 하기 때문에 실제 구현은 불가능하지만, 다른 알고리즘의 성능 비교 기준으로 쓰인다.

참조열: 7 0 1 2 0 3 0 4 2 3 0 3 2  (프레임 3개)

4를 참조할 때 프레임: [2, 0, 3]
  - 2는 이후 인덱스 12에서 사용
  - 0은 이후 인덱스 10에서 사용
  - 3은 이후 인덱스 11에서 사용
  → 가장 늦게 쓰이는 2를 교체

Optimal은 폴트 횟수가 가장 적다. 실제로 구현할 수 없지만 이론적 하한선으로 알고리즘 평가에 활용한다.

3. LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 교체한다. Optimal의 미래 참조 대신 과거 참조 이력을 사용한다. “최근에 쓰인 것은 앞으로도 쓰일 가능성이 높다”는 시간적 지역성(temporal locality) 원리를 기반으로 한다.

참조열: 7 0 1 2 0 3 0 4 2 3 0 3 2  (프레임 3개)

단계 | 참조 | 프레임 상태         | 폴트?
-----|------|---------------------|------
1    | 7    | [7]                 | ✓
2    | 0    | [7, 0]              | ✓
3    | 1    | [7, 0, 1]           | ✓
4    | 2    | [2, 0, 1] (7이 LRU) | ✓
5    | 0    | [2, 0, 1]           |
6    | 3    | [2, 0, 3] (1이 LRU) | ✓
7    | 0    | [2, 0, 3]           |
8    | 4    | [4, 0, 3] (2가 LRU) | ✓
...

구현 방식

완전한 LRU는 모든 페이지 접근 시 타임스탬프를 기록하거나, 더블리 링크드 리스트 + 해시맵 조합으로 구현한다.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, page: int) -> bool:
        if page in self.cache:
            self.cache.move_to_end(page)  # 최근 사용으로 갱신
            return True  # 히트
        return False  # 미스 (페이지 폴트)

    def put(self, page: int):
        if page in self.cache:
            self.cache.move_to_end(page)
        else:
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False)  # 가장 오래된 항목 제거
            self.cache[page] = True

단점: 완전한 LRU는 하드웨어 지원 없이 소프트웨어만으로 구현하면 모든 메모리 참조마다 오버헤드가 발생해 실용적이지 않다.

4. LFU (Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체한다. “많이 사용된 페이지는 앞으로도 사용될 가능성이 높다”는 가정이다.

참조열: 1 2 1 2 1 3 4  (프레임 2개)

페이지별 참조 횟수: 1→3, 2→2, 3→1, 4→(새로 들어옴)
4를 올릴 때 교체 대상: 3 (가장 적게 참조됨)

단점

오래전에 자주 사용됐지만 지금은 필요 없는 페이지가 메모리에 계속 남을 수 있다.
참조 횟수가 동일한 페이지가 여러 개일 때 추가 정책(예: FIFO, LRU)이 필요하다.

5. Clock Algorithm (Second Chance Algorithm)

FIFO의 단점을 보완한 LRU 근사 알고리즘으로, 실제 OS에서 가장 많이 쓰인다. 완전한 LRU의 오버헤드 없이 비슷한 성능을 낸다.

동작 방식

각 페이지 프레임에 참조 비트(Reference Bit, R) 를 둔다.
페이지가 참조될 때마다 R = 1로 설정한다.
교체 대상을 찾을 때 시계 방향으로 순회한다:
- R == 0이면 → 해당 페이지를 교체한다.
- R == 1이면 → R을 0으로 초기화하고 다음으로 넘어간다. (두 번째 기회)
한 바퀴를 돌면서 R == 0인 페이지를 찾아 교체한다.

초기 프레임 상태 (페이지: 참조비트):
[A:1] [B:0] [C:1] [D:0]
         ↑ (클락 포인터)

새 페이지 E를 올려야 할 때:
B의 R=0 → B를 교체, E를 넣음
포인터는 C로 이동

결과:
[A:1] [E:0] [C:1] [D:0]
              ↑

Why Clock? 참조 비트만 관리하면 되므로 하드웨어 지원이 쉽고 오버헤드가 작다. Linux의 실제 페이지 교체는 Clock 변형인 Active/Inactive 리스트 기반 알고리즘을 사용한다.

알고리즘 성능 비교

알고리즘	폴트 횟수 (예시)	구현 복잡도	실용성
Optimal	최소 (이론적 하한)	구현 불가	비교 기준
LRU	Optimal에 근접	높음	제한적
Clock	LRU에 근사	낮음	높음 (실제 OS 사용)
FIFO	보통	매우 낮음	단순 시스템
LFU	상황에 따라 다름	중간	캐시 시스템

스래싱 (Thrashing)

페이지 교체 알고리즘과 함께 알아야 할 개념이다. 프로세스에 할당된 프레임 수가 너무 적으면 페이지 폴트가 연속으로 발생하면서 CPU가 실제 작업은 거의 못 하고 페이지 교체만 반복한다. 이 현상을 스래싱이라 한다.

CPU 사용률
     |       *
     |     *   *
     |   *       *
     | *           *
     |_________________
       멀티프로그래밍 정도 →

스래싱을 해결하는 방법:

워킹셋(Working Set) 모델: 최근 일정 시간 동안 참조된 페이지 집합만 유지
페이지 폴트 빈도(PFF) 조절: 폴트가 너무 잦으면 프레임을 더 할당, 너무 적으면 회수

정리

개념	설명
페이지 폴트	요청 페이지가 물리 메모리에 없어 디스크에서 로드해야 하는 상황
FIFO	가장 오래 머문 페이지 교체, Belady의 역설 발생 가능
Optimal	이후 가장 안 쓰일 페이지 교체, 구현 불가 (이론적 기준)
LRU	가장 오래 사용 안 된 페이지 교체, 시간적 지역성 활용
LFU	참조 횟수가 가장 적은 페이지 교체
Clock	참조 비트로 LRU 근사, 실제 OS에서 사용
스래싱	페이지 폴트 과다로 CPU 효율이 급격히 떨어지는 현상

실무에서는 완전한 LRU보다 Clock이나 그 변형이 더 많이 쓰인다. 완전한 LRU는 이론적으로 우수하지만 모든 메모리 접근을 추적해야 하는 오버헤드가 실제 시스템에서는 너무 크기 때문이다.

[Daily morning study] 페이지 교체 알고리즘 (FIFO, LRU, LFU, Clock)

페이지 교체 알고리즘 (Page Replacement Algorithm)

왜 페이지 교체가 필요한가

기본 개념 정리

페이지 프레임 (Page Frame)

페이지 폴트 (Page Fault)

참조열 (Reference String)

알고리즘 비교

1. FIFO (First-In, First-Out)

2. Optimal (OPT, Bélády’s Algorithm)

3. LRU (Least Recently Used)

4. LFU (Least Frequently Used)

5. Clock Algorithm (Second Chance Algorithm)

알고리즘 성능 비교

스래싱 (Thrashing)

정리

🐒🇰🇷

Error

페이지 교체 알고리즘 (Page Replacement Algorithm)

왜 페이지 교체가 필요한가

기본 개념 정리

페이지 프레임 (Page Frame)

페이지 폴트 (Page Fault)

참조열 (Reference String)

알고리즘 비교

1. FIFO (First-In, First-Out)

2. Optimal (OPT, Bélády’s Algorithm)

3. LRU (Least Recently Used)

4. LFU (Least Frequently Used)

5. Clock Algorithm (Second Chance Algorithm)

알고리즘 성능 비교

스래싱 (Thrashing)

정리

Templates (for web app):

Error