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

개요

페이지 교체 알고리즘은 운영체제의 가상 메모리 관리에서 중요한 역할을 하며, 제한된 물리 메모리 공간에 가상 메모리 페이지를 효율적으로 배치하는 방식입니다. 프로세스 실행 중 페이지 부재(Page Fault)가 발생했을 때, 어떤 페이지를 제거하고 새로운 페이지를 메모리에 적재할지를 결정하는 전략으로 시스템 성능에 직결됩니다. 본 글에서는 대표적인 페이지 교체 알고리즘의 개념, 동작 방식, 비교 및 실무 적용 시 고려사항 등을 체계적으로 설명합니다.

---

1. 개념 및 필요성

가상 메모리 환경에서는 프로세스가 사용하는 모든 페이지를 물리 메모리에 올릴 수 없습니다. 이로 인해 페이지 부재가 발생하면, 기존에 있던 페이지 중 하나를 제거하고 새로운 페이지를 적재해야 합니다. 이때 어떤 페이지를 교체할지를 정하는 기준이 바로 페이지 교체 알고리즘입니다.

---

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

알고리즘	설명	장점	단점
FIFO (First-In First-Out)	가장 먼저 들어온 페이지를 교체	구현 간단	Belady’s anomaly 발생 가능
LRU (Least Recently Used)	가장 오랫동안 사용되지 않은 페이지 교체	실제 사용과 유사	시간/공간 오버헤드 큼
Optimal (OPT)	앞으로 가장 오랫동안 사용되지 않을 페이지 교체	최소 페이지 부재 수	실제 구현 불가 (예측 필요)
Clock (Second Chance)	FIFO + 참조 비트로 기회 부여	LRU 근사값	하드웨어 지원 필요
LFU (Least Frequently Used)	사용 횟수가 가장 적은 페이지 교체	비활성 페이지 제거에 적합	최근 급증한 페이지는 과보호 가능

각 알고리즘은 메모리 접근 패턴과 시스템 특성에 따라 선택되어야 합니다.

---

3. 알고리즘 동작 예시 (페이지 프레임 3개, 요청 순서: 7 0 1 2 0 3 0 4 2 3 0 3)

알고리즘	총 Page Fault 수
FIFO	9
LRU	8
OPT	7 (이론상 최소)

같은 입력에서도 알고리즘에 따라 페이지 부재 횟수가 달라지며, LRU는 현실적인 선택지로 널리 사용됩니다.

---

4. 비교 및 선택 기준

기준	FIFO	LRU	OPT	Clock
구현 난이도	낮음	높음	매우 높음 (이론)	중간
성능	중간	우수	최고 (불가능)	준수
오버헤드	적음	큼 (시간 추적 필요)	큼	낮음 (비트만 활용)
실무 사용도	제한적	높음	없음	매우 높음 (Linux, Windows 등)

실제 운영체제는 Clock 알고리즘 또는 LRU의 근사 알고리즘을 사용하여 성능과 구현 효율을 균형 있게 맞춥니다.

---

5. 실무 적용 사례

시스템	적용 알고리즘	설명
Linux Kernel	Clock 기반(LRU Approximation)	Active/Inactive 리스트로 LRU 유사 구현
Windows OS	LRU 기반 + Working Set 관리	프로세스별 페이지 교체 조절 가능
Oracle DB	LRU + MRU 조합	읽기/쓰기 패턴에 따라 동적 조정
가상 머신 하이퍼바이저	Ballooning + Clock 방식	VM 간 메모리 스케줄링 최적화

이처럼 알고리즘은 하드웨어 자원, 운영체제 설계 목적, 성능 요구에 따라 달라집니다.

---

6. 성능 고려사항 및 최적화

항목	고려사항
페이지 크기	너무 작으면 오버헤드, 너무 크면 낭비 발생
TLB 적중률	LRU 사용 시 캐시 친화적인 구조 유리
Swapping 빈도	스래싱 방지 위해 적절한 프레임 확보 필수
페이지 액세스 패턴	반복성, 지역성(Temporal/Spatial Locality) 고려

알고리즘 선택과 함께, 메모리 관리 정책 최적화도 함께 고려해야 합니다.

---

7. 결론

페이지 교체 알고리즘은 가상 메모리 시스템의 성능과 안정성을 좌우하는 핵심 요소입니다. 다양한 알고리즘은 각각의 장단점을 가지며, 시스템 환경에 맞는 전략적 선택이 중요합니다. 운영체제 설계뿐만 아니라, 데이터베이스, 하이퍼바이저, 고성능 컴퓨팅에서도 그 적용이 확장되고 있으며, 성능 향상을 위한 알고리즘 최적화 연구는 지속적으로 발전하고 있습니다.