[운영체제] 가상 메모리(Virtual Memory) 개념과 페이지 교체 알고리즘(FIFO, LRU, LFU) 완전 정리

컴퓨터공학과 운영체제 과목이나 기술 면접, 정보처리기사 시험에서 "메모리 관리 기법의 꽃"으로 항상 출제되는 주제가 있습니다. 바로 가상 메모리(Virtual Memory)와 페이지 교체 알고리즘(Page Replacement Algorithm)입니다.

"실제 물리 메모리(RAM)보다 더 큰 프로그램을 어떻게 실행할 수 있을까?"

"메모리가 가득 찼을 때 어떤 페이지를 내보내야(Swap-out) 가장 효율적일까?"

가상 메모리의 기본 원리부터 페이지 부재(Page Fault), 그리고 시험 단골 계산 문제로 나오는 FIFO, LRU, LFU 페이지 교체 알고리즘의 동작 방식과 차이점까지 깔끔하게 정리해 드립니다!

1. 가상 메모리(Virtual Memory)란?

가상 메모리는 프로세스 전체가 물리 메모리에 올랐지 않아도 실행 가능하도록 하는 메모리 관리 기법입니다.

실제 물리 메모리(RAM) 크기의 한계를 극복하기 위해 보조기억장치(SSD/HDD)의 일부를 마치 RAM처럼 사용하는 기법입니다.

가상 메모리 환경에서의 페이지 교체 메커니즘. 출처: 운동개발좋아 - 티스토리

💡 가상 메모리의 주요 개념

• 요구 페이징 (Demand Paging): 프로그램 실행 시 필요한 페이지(Page)만 필요한 시점에 메모리에 적재하는 방식입니다.
• 페이지 부재 (Page Fault): CPU가 참조하려는 페이지가 현재 물리 메모리(RAM)에 없어 보조기억장치에서 가져와야 하는 현상입니다.
• 스왑 아웃 / 스왑 인 (Swap-out / Swap-in):
  • Swap-out: 물리 메모리가 가득 찼을 때, 새 페이지를 올리기 위해 기존 페이지를 보조기억장치(스왑 영역)로 내보내는 작업
  • Swap-in: 필요한 페이지를 보조기억장치에서 물리 메모리로 가져오는 작업

2. 페이지 교체 알고리즘(Page Replacement Algorithm) 종류

메모리가 가득 찬 상태에서 페이지 부재가 발생하면, 메모리에 있는 기존 페이지 중 하나를 선택해 내보내야(Swap-out) 합니다. 이때 내보낼 희생 페이지(Victim Page)를 결정하는 규칙이 바로 페이지 교체 알고리즘입니다.

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

• 개념: 메모리에 가장 먼저 들어온 페이지를 가장 먼저 교체하는 방식입니다.
• 장점: 구현이 매우 간단하고 오버헤드가 적습니다.
• 단점: 자주 사용되는 중요한 페이지라도 오래되었다는 이유로 교체될 수 있습니다.
• ★ Belady의 모순 (Belady's Anomaly): 할당된 페이지 프레임 수가 늘어났음에도 불구하고 오히려 페이지 부재(Page Fault) 발생 횟수가 증가하는 이상 현상이 발생할 수 있습니다.

2️⃣ LRU (Least Recently Used)

• 개념: 가장 오랫동안 참조(사용)되지 않은 페이지를 교체하는 방식입니다. (시간 지역성 활용)
• 장점: 실무 및 OS에서 널리 쓰이는 매우 효율적인 방식이며, Belady의 모순이 발생하지 않습니다.
• 단점: 각 페이지마다 마지막 참조 시간을 기록하거나 카운터/스택 자료구조를 유지해야 하므로 오버헤드가 발생합니다.

3️⃣ LFU (Least Frequently Used)

• 개념: 참조 횟수가 가장 적은 페이지를 교체하는 방식입니다.
• 장점: 자주 사용되는 페이지를 장기적으로 메모리에 유지할 수 있습니다.
• 단점: 프로그램 초기에만 집중적으로 쓰이고 이후에는 쓰이지 않는 페이지가 메모리에 계속 남아있을 수 있으며, 참조 횟수를 기록하는 추가 비용이 발생합니다.

4️⃣ OPT (Optimal Page Replacement, 최적 교체)

• 개념: 앞으로 가장 먼 미래에 참조될 페이지를 교체하는 방식입니다.
• 특징: 페이지 부재 횟수를 최소화할 수 있는 가장 이상적인 알고리즘입니다.
• 한계: 실제 환경에서는 미래의 프로세스 메모리 참조 패턴을 사전에 알 수 없으므로 실현 불가능(Unrealizable)합니다. (다른 알고리즘의 성능 평가 기준/비교군으로 활용)

3. 한눈에 비교하는 알고리즘 핵심 요약 (★시험 필수)

알고리즘	희생 페이지(Victim) 결정 기준	핵심 키워드 / 특징
OPT	가장 먼 미래에 사용될 페이지	이론상 최적, 실현 불가능
FIFO	가장 먼저 적재된 페이지	Belady의 모순 발생 가능
LRU	가장 오랫동안 사용되지 않은 페이지	시간 지역성 기반, 가장 널리 사용
LFU	참조 횟수가 가장 적은 페이지	사용 빈도 기반

4. 성능 저하의 주범: 스레싱 (Thrashing)

시험 문제로 페이지 교체 알고리즘과 함께 반드시 세트로 나오는 개념입니다!

• 스레싱(Thrashing): 프로세스에 할당된 프레임 수가 부족하여 페이지 부재(Page Fault)가 빈번하게 발생하고, 이에 따라 CPU 이용률이 급격히 떨어지는 현상
• 원인: 페이지 교체(Swap-in/Swap-out) 작업에 대부분의 시간이 소비되어 정작 CPU가 실제 일을 하지 못함
• 해결책:
  • 워킹셋 (Working Set) 모델: 프로세스가 일정 시간 동안 자주 참조하는 페이지 집합을 메모리에 유지
  • PFF (Page Fault Frequency) 방식: 페이지 부재 비율의 상한선과 하한선을 정해 할당 프레임 수를 동적으로 조절

5. 시험 단골 출제 유형 체크

1. Q. 페이지 프레임 수를 늘렸음에도 페이지 부재 횟수가 오히려 증가하는 현상과 연관된 알고리즘은?
2. 👉 Belady의 모순(Belady's Anomaly) 현상이며, FIFO 알고리즘에서 발생합니다.
3. Q. 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘은?
4. 👉 LRU (Least Recently Used) 알고리즘입니다.
5. Q. 이론상 페이지 부재 횟수를 최소화하지만 미래의 참조를 예측해야 하므로 구현이 불가능한 알고리즘은?
6. 👉 OPT (Optimal, 최적 교체) 알고리즘입니다.