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

핵심 인사이트 (3줄 요약)

가상 메모리에서 페이지 폴트 발생 시 어떤 페이지를 내보낼지 결정하는 알고리즘. OPT(최적)는 이론적 기준, LRU가 실무 표준. Belady 이상 현상으로 FIFO는 프레임 늘려도 폴트 증가 가능.

📝 기술사 모의답안 (2.5페이지 분량)

📌 예상 문제

"페이지 교체 알고리즘 (Page Replacement Algorithm)의 개념과 주요 메커니즘을 설명하고, 운영체제 성능 및 안정성 관점에서의 적용 방안을 기술하시오."

Ⅰ. 개요

1. 개념

물리 메모리(RAM) 공간이 부족할 때, 새 페이지를 적재하기 위해 기존 페이지 중 하나를 내보내는(swap out) 전략이다.

비유: "책상 위 교과서 관리" - 공간 제한에서 자주 쓸 책만 올려두고 덜 쓰는 책은 가방에 넣기

Ⅱ. 구성 요소 및 핵심 원리

2. 주요 알고리즘 비교

페이지 참조 순서: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 (프레임 3개)

─────────────────────────────────────────────────────────────
OPT (Optimal):   가장 오랫동안 사용되지 않을 페이지 교체
→ 미래를 알아야 하므로 실제 구현 불가 (이론적 최적 기준)
폴트 횟수: 최소 (비교 기준)

FIFO:  가장 먼저 들어온 페이지 교체
→ 구현 가장 쉬움, Belady 이상 현상 발생
폴트 횟수: 많음

LRU (Least Recently Used): 가장 오랫동안 사용 안 한 페이지 교체
→ 시간 지역성 활용, OPT에 근사
폴트 횟수: 중간 (실무 표준)

LFU (Least Frequently Used): 참조 횟수 가장 적은 페이지 교체
→ LRU보다 복잡, 과거 다회 참조 페이지 교체 지연 문제

Clock (2차 기회): FIFO + 참조 비트 사용
→ LRU 근사, 순환 큐 구조 (실제 OS에서 많이 사용)

3. 알고리즘별 폴트 예시 (프레임 3개)

참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

FIFO:
시간: 1  2  3  4  1  2  5  1  2  3  4  5
F1:   1  1  1  4  4  4  5  5  5  5  4  4
F2:      2  2  2  1  1  1  1  1  1  1  5
F3:         3  3  3  2  2  2  2  3  3  3
폴트:  F  F  F  F  F  F  F        F  F  F  → 9회 폴트

LRU:
시간: 1  2  3  4  1  2  5  1  2  3  4  5
F1:   1  1  1  4  1  1  5  1  1  3  4  5
F2:      2  2  2  2  2  2  2  2  2  2  2  (틀림)
폴트: 줄어듦

[Belady 이상 현상]
FIFO에서 프레임 수를 늘려도 폴트가 더 늘어나는 현상
→ LRU, OPT는 이 현상 없음 (스택 알고리즘)

4. Clock 알고리즘 (실제 OS 구현)

순환 연결 리스트 + 참조 비트(R):

페이지 교체 시:
1. 시계 바늘이 가리키는 페이지의 R 확인
2. R=1: R=0으로 변경 후 다음 페이지 (2차 기회 부여)
3. R=0: 이 페이지를 교체

Linux의 Clock 알고리즘 (변형):
- Active 리스트 / Inactive 리스트 두 개 운영
- 참조 안 되면 Active → Inactive로 이동
- Inactive에서 또 참조 안 되면 교체 대상

5. 스래싱 (Thrashing)

징    ┌───────────────────────────────────────────────┐
호    │                                               │
율    │          ██████████                           │
      │      ████         ████                        │
      │   ███                 ████                    │
      │ ██                        ██████████████████  │
      └───────────────────────────────────────────────┘
        적음                              많음
                    동시 실행 프로세스 수

다중 프로그래밍 정도 ↑ → 페이지 폴트 ↑ → CPU 낭비 → 스래싱

스래싱 원인: 각 프로세스에 충분한 프레임 미할당
해결책:
- 워킹 셋(Working Set) 모델: 최근 참조 페이지 집합 유지
- 페이지 폴트 빈도(PFF) 제어: 폴트율 목표 범위 설정

Ⅲ. 기술 비교 분석

비교표를 통해 주요 기술과 차이점을 분석한다.

Ⅳ. 실무 적용 방안

6. 실무에선? (기술사적 판단)

• Linux/Windows: Clock 알고리즘 변형 사용
• SSD 시대: 스왑 비용 감소로 페이지 교체 부담 줄어듦
• 컨테이너: 메모리 제한 설정 → OOM Killer
• 기술사 포인트: OPT가 기준, LRU가 실무, Belady 이상은 FIFO

Ⅴ. 기대 효과 및 결론

결론

**페이지 교체 알고리즘 (Page Replacement Algorithm)**은(는) 운영체제의 핵심 메커니즘들은 클라우드·컨테이너 시대에도 동일한 원리로 작동하며, eBPF 등 새로운 커널 확장 기술과 결합하여 더 유연하고 관측 가능한 시스템으로 진화하고 있다.

※ 참고 표준: POSIX (IEEE 1003.1), Linux Kernel Documentation, Windows Internals

어린이를 위한 종합 설명

페이지 교체 알고리즘를 쉽게 이해해보자!

가상 메모리에서 페이지 폴트 발생 시 어떤 페이지를 내보낼지 결정하는 알고리즘. OPT(최적)는 이론적 기준, LRU가 실무 표준. Belady 이상 현상으로 FIFO는 프

왜 필요할까?
  기존 방식의 한계를 넘기 위해

어떻게 동작하나?
  복잡한 문제 → 페이지 교체 알고리즘 적용 → 더 빠르고 안전한 결과!

핵심 한 줄:
  페이지 교체 알고리즘 = 똑똑하게 문제를 해결하는 방법

비유: 페이지 교체 알고리즘은 마치 요리사가 레시피를 따르는 것과 같아. 혼란스러운 재료들을 정해진 순서대로 조합하면 → 맛있는 요리(최적 결과)가 나오지! 🍳