가상 메모리와 페이지 교체 알고리즘 완벽 가이드

이전 글에서 프로세스와 스레드의 차이, 데드락의 발생 원리와 해결 전략을 다루었다. 이번 글에서는 운영체제의 또 다른 핵심 주제인 가상 메모리(Virtual Memory)를 깊이 있게 정리한다.

현대 운영체제에서 모든 프로세스는 자신이 전체 메모리를 독점하고 있다고 “착각”한다. 4GB 물리 메모리를 가진 컴퓨터에서 3GB짜리 프로그램 두 개를 동시에 실행할 수 있는 이유, 그것이 가상 메모리이다. 주소 변환의 메커니즘, 페이지 폴트 처리, 다양한 페이지 교체 알고리즘, 그리고 스래싱까지 — 면접에서 빈출되는 핵심 개념을 코드와 다이어그램으로 정리한다.

1. 가상 메모리의 개념과 필요성

1.1 물리 메모리의 한계

물리 메모리(RAM)만으로 프로그램을 실행하면 세 가지 문제가 발생한다.

용량 한계: 물리 메모리(4GB, 8GB 등)보다 큰 프로그램을 실행할 수 없다.
보호 부재: 프로세스 A가 프로세스 B의 메모리 영역을 직접 접근할 수 있다.
단편화: 프로세스의 생성과 종료가 반복되면서 메모리에 사용하기 어려운 작은 빈 공간(외부 단편화)이 생긴다.

1.2 가상 메모리란

가상 메모리는 물리 메모리를 추상화하여 각 프로세스에게 독립적인 연속 주소 공간을 제공하는 기법이다.

가상 메모리의 핵심 아이디어:

  프로세스 A의 시각:              프로세스 B의 시각:
  ┌──────────────┐              ┌──────────────┐
  │ 0x0000 ~ 4GB │              │ 0x0000 ~ 4GB │
  │ "내가 메모리를  │              │ "내가 메모리를  │
  │  전부 쓰고 있다"│              │  전부 쓰고 있다"│
  └──────┬───────┘              └──────┬───────┘
         │                             │
         │     주소 변환 (MMU)           │
         ▼                             ▼
  ┌─────────────────────────────────────────┐
  │              물리 메모리 (RAM)            │
  │  [A의 페이지들]  [B의 페이지들]  [빈 공간]   │
  └─────────────────────────────────────────┘
  │                                         │
  └──── 부족하면 디스크(스왑 영역)에 저장 ──────┘

핵심 이점:

이점	설명
메모리 확장	물리 메모리 + 디스크 스왑 영역을 합쳐 더 큰 주소 공간 사용
프로세스 격리	각 프로세스가 독립적인 주소 공간을 가지므로 다른 프로세스 메모리 접근 불가
효율적 메모리 관리	실제로 사용하는 페이지만 물리 메모리에 적재 (Demand Paging)
공유 메모리	같은 물리 프레임을 여러 프로세스의 가상 주소에 매핑 (라이브러리 공유)

1.3 32비트 vs 64비트 가상 주소 공간

32비트 시스템:
  가상 주소 공간 = 2^32 = 4GB
  ┌──────────────────────┐ 0xFFFFFFFF (4GB)
  │    커널 영역 (1GB)     │
  ├──────────────────────┤ 0xC0000000 (3GB)
  │                      │
  │  사용자 영역 (3GB)     │
  │                      │
  └──────────────────────┘ 0x00000000

64비트 시스템:
  가상 주소 공간 = 2^48 = 256TB (현재 실제 사용)
  이론적으로는 2^64 = 16EB (엑사바이트)

2. 주소 변환 (Address Translation)

2.1 가상 주소의 구조

가상 주소는 페이지 번호(Page Number)와 오프셋(Offset)으로 분리된다.

가상 주소 (32비트, 페이지 크기 4KB):

  ┌──────────────────────┬────────────┐
  │   페이지 번호 (20비트)  │ 오프셋 (12비트)│
  └──────────────────────┴────────────┘
        │                      │
        │                      └─── 페이지 내 위치 (0 ~ 4095)
        │
        └─── 총 2^20 = 약 100만 개의 페이지

4KB 페이지 크기일 때: 오프셋 = 12비트(2^12 = 4096), 나머지가 페이지 번호.

2.2 페이지 테이블 (Page Table)

페이지 테이블은 가상 페이지 번호 → 물리 프레임 번호의 매핑을 저장하는 자료구조이다. 프로세스마다 하나씩 존재한다.

주소 변환 과정:

  CPU가 생성한 가상 주소: 0x00403004
  → 페이지 번호: 0x00403 (1027)
  → 오프셋: 0x004

  ┌─────────────────────────────────────────────┐
  │               페이지 테이블                    │
  │  가상 페이지 번호  │  물리 프레임 번호  │ 유효 비트 │
  │  ─────────────────────────────────────────── │
  │       0          │       5          │   1    │
  │       1          │       -          │   0    │ ← 디스크에 있음
  │      ...         │      ...         │  ...   │
  │     1027         │       3          │   1    │ ← 이 엔트리!
  └─────────────────────────────────────────────┘

  물리 주소 = 프레임 번호(3) × 페이지 크기(4KB) + 오프셋(0x004)
            = 0x3000 + 0x004
            = 0x3004

2.3 페이지 테이블 엔트리 (PTE)

페이지 테이블 엔트리의 구조:

┌──────────────┬───┬───┬───┬───┬───┬───────────────────┐
│ 물리 프레임 번호 │ V │ R │ M │ P │ RW│      기타 비트       │
└──────────────┴───┴───┴───┴───┴───┴───────────────────┘
                  │   │   │   │   │
                  │   │   │   │   └─ Read/Write (읽기/쓰기 권한)
                  │   │   │   └──── Protection (보호 비트)
                  │   │   └─────── Modified/Dirty (수정 여부)
                  │   └────────── Referenced (최근 참조 여부)
                  └───────────── Valid (유효 비트: 메모리에 있는가?)

비트	이름	설명
V (Valid)	유효 비트	1이면 물리 메모리에 있음, 0이면 디스크에 있음(페이지 폴트)
R (Referenced)	참조 비트	최근 접근되었는지 여부 (Clock 알고리즘에서 사용)
M (Modified/Dirty)	수정 비트	적재 후 수정되었는지 여부 (교체 시 디스크 쓰기 필요 여부)
RW	읽기/쓰기	읽기 전용(0) vs 읽기+쓰기(1)

3. 페이징 (Paging)

3.1 페이지와 프레임

용어 정리:

  가상 메모리                      물리 메모리
  ┌──────────┐                   ┌──────────┐
  │ 페이지 0  │ ────매핑────►    │ 프레임 5  │
  ├──────────┤                   ├──────────┤
  │ 페이지 1  │ ────매핑────►    │ 프레임 2  │
  ├──────────┤                   ├──────────┤
  │ 페이지 2  │ (디스크에 있음)    │ 프레임 3  │ ← 다른 프로세스
  ├──────────┤                   ├──────────┤
  │ 페이지 3  │ ────매핑────►    │ 프레임 7  │
  └──────────┘                   └──────────┘

  페이지(Page): 가상 메모리의 고정 크기 블록 (보통 4KB)
  프레임(Frame): 물리 메모리의 고정 크기 블록 (페이지와 같은 크기)

페이징의 핵심은 가상 주소 공간의 페이지가 물리 메모리의 임의의 프레임에 매핑될 수 있다는 것이다. 연속적인 가상 주소가 물리적으로는 불연속적으로 배치될 수 있으며, 이를 통해 외부 단편화가 완전히 제거된다.

3.2 내부 단편화 (Internal Fragmentation)

페이징은 외부 단편화를 해결하지만, 내부 단편화는 여전히 발생한다. 프로세스가 필요한 메모리가 페이지 크기의 정확한 배수가 아닐 때, 마지막 페이지에 낭비되는 공간이 생긴다.

프로세스가 10,500 바이트 필요 (페이지 크기 = 4KB = 4096 바이트):
  페이지 0: 4096 바이트 (전부 사용)
  페이지 1: 4096 바이트 (전부 사용)
  페이지 2: 2308 바이트 사용, 1788 바이트 낭비 ← 내부 단편화

평균 내부 단편화 = 페이지 크기 / 2. 페이지 크기가 4KB면 평균 2KB 낭비.

3.3 다단계 페이지 테이블

32비트 시스템에서 4KB 페이지를 사용하면 페이지 테이블 엔트리가 2^20 ≈ 100만 개 필요하다. 각 엔트리가 4바이트면 프로세스당 4MB의 페이지 테이블이 필요하다. 이것은 프로세스가 실제로 소량의 메모리만 사용하더라도 동일하다.

다단계 페이지 테이블은 사용하지 않는 가상 주소 범위에 대한 페이지 테이블을 생성하지 않아 메모리를 절약한다.

2단계 페이지 테이블 (32비트, 4KB 페이지):

  가상 주소:
  ┌──────────┬──────────┬────────────┐
  │ 1단계 인덱스│ 2단계 인덱스│   오프셋    │
  │  (10비트)  │  (10비트)  │  (12비트)   │
  └─────┬────┴─────┬────┴────────────┘
        │          │
        ▼          │
  ┌──────────┐    │
  │ 1단계      │    │
  │ 페이지 테이블│    │
  │ (1024 엔트리)│    │
  ├──────────┤    │
  │   ─────►├────┘
  │          │
  │  NULL    │ ← 사용 안 하는 영역은 2단계 테이블 없음
  │          │
  └──────────┘
        │
        ▼
  ┌──────────┐
  │ 2단계      │
  │ 페이지 테이블│
  │ (1024 엔트리)│
  ├──────────┤
  │  프레임 번호│ → 물리 주소 계산
  └──────────┘

64비트 시스템에서는 4단계 또는 5단계 페이지 테이블을 사용한다. Linux x86-64에서는 4단계(PGD → PUD → PMD → PTE)를 사용하며, Linux 4.11+에서는 5단계(P4D 추가)를 선택적으로 지원한다.

3.4 역 페이지 테이블 (Inverted Page Table)

일반 페이지 테이블은 가상 페이지 수만큼 엔트리가 필요하다. 역 페이지 테이블은 물리 프레임 수만큼만 엔트리를 유지한다.

역 페이지 테이블:

  ┌───────────┬─────────┬───────────┐
  │ 프레임 번호 │ PID     │ 가상 페이지  │
  ├───────────┼─────────┼───────────┤
  │     0     │  P1     │    42     │
  │     1     │  P3     │    17     │
  │     2     │  P1     │    43     │
  │     3     │  P2     │     8     │
  │    ...    │  ...    │   ...     │
  └───────────┴─────────┴───────────┘

  장점: 메모리 절약 (물리 프레임 수에만 비례)
  단점: 검색이 느림 → 해시 테이블로 보완

4. TLB (Translation Lookaside Buffer)

4.1 TLB의 필요성

페이지 테이블은 메모리에 저장되어 있다. 모든 메모리 접근마다 페이지 테이블을 참조하면 메모리 접근이 두 배로 늘어난다 (1번: 페이지 테이블 조회, 2번: 실제 데이터 접근).

TLB는 최근 사용된 페이지 테이블 엔트리를 캐싱하는 하드웨어 캐시이다. CPU 내부 또는 MMU 내부에 위치하며, 접근 속도가 매우 빠르다.

TLB를 활용한 주소 변환:

  CPU ──► 가상 주소
            │
            ▼
      ┌──────────┐
      │   TLB    │ ← 매우 빠른 하드웨어 캐시 (보통 64~1024 엔트리)
      └─────┬────┘
            │
       TLB Hit?
      ┌─────┴─────┐
     YES          NO (TLB Miss)
      │            │
      ▼            ▼
  물리 주소      페이지 테이블 조회 (메모리 접근)
  즉시 결정         │
                   ▼
              TLB에 등록
                   │
                   ▼
              물리 주소 결정

4.2 유효 접근 시간 (Effective Access Time) 계산

TLB의 효과를 수치로 확인해보자.

메모리 접근 시간: 100ns
TLB 접근 시간: 10ns
TLB 히트율: 98%

TLB Hit 시: TLB 접근(10ns) + 메모리 접근(100ns) = 110ns
TLB Miss 시: TLB 접근(10ns) + 페이지 테이블(100ns) + 메모리 접근(100ns) = 210ns

유효 접근 시간 (EAT):
= 히트율 × Hit 시간 + (1 - 히트율) × Miss 시간
= 0.98 × 110 + 0.02 × 210
= 107.8 + 4.2
= 112ns

TLB 없을 때: 200ns (페이지 테이블 + 데이터 접근)
TLB 있을 때: 112ns → 약 44% 성능 향상

4.3 TLB와 컨텍스트 스위칭

프로세스마다 페이지 테이블이 다르므로, 컨텍스트 스위칭 시 TLB의 내용은 무효화(flush)되어야 한다. 이것이 컨텍스트 스위칭 비용의 일부이다.

컨텍스트 스위칭 시 TLB:

  프로세스 A 실행 중:
    TLB: [A의 페이지 0 → 프레임 5] [A의 페이지 1 → 프레임 2] ...

  → 컨텍스트 스위칭 → 프로세스 B로 전환

    TLB flush! (전부 비움)
    프로세스 B 시작 시 TLB가 비어있음 → 연속적인 TLB Miss → 성능 저하

  개선: ASID (Address Space ID)
    TLB 엔트리에 프로세스 ID를 태깅하여 flush 없이 구분
    [ASID=A, 페이지 0 → 프레임 5] [ASID=B, 페이지 3 → 프레임 8] ...

5. 요구 페이징 (Demand Paging)

5.1 개념

프로세스 실행 시 모든 페이지를 메모리에 올리지 않고, 실제로 접근하는 시점에 비로소 메모리에 적재하는 기법이다. “Lazy Loading”과 같은 원리이다.

요구 페이징의 동작:

  프로그램 시작 시:
    모든 페이지의 유효 비트 = 0 (메모리에 없음)

  실행 중 페이지 3 접근:
    유효 비트 = 0 → 페이지 폴트 발생!
    → OS가 디스크에서 페이지 3을 물리 메모리에 적재
    → 유효 비트 = 1로 변경
    → 명령어 재실행

장점: 사용하지 않는 코드/데이터는 메모리를 차지하지 않는다. 예를 들어 에러 처리 코드가 실행되지 않으면 해당 페이지는 영영 적재되지 않을 수 있다.

5.2 페이지 폴트 (Page Fault) 처리 과정

페이지 폴트 처리 단계:

  ① CPU가 가상 주소 접근
  ② MMU가 페이지 테이블 확인 → 유효 비트 = 0
  ③ 페이지 폴트 트랩 발생 → OS에 제어 전달
     │
     ▼
  ④ OS가 디스크에서 해당 페이지의 위치 확인
     │
     ▼
  ⑤ 빈 프레임이 있는가?
     ├── YES → ⑥ 디스크에서 해당 프레임으로 페이지 적재
     │
     └── NO → 페이지 교체 알고리즘으로 희생 페이지 선택
              │
              ├── 희생 페이지가 Dirty(수정됨)? → 디스크에 쓰기
              │
              └── 프레임 확보 → ⑥ 적재
     │
     ▼
  ⑥ 디스크 → 메모리 전송 (DMA)
     │
     ▼
  ⑦ 페이지 테이블 업데이트 (유효 비트 = 1, 프레임 번호 설정)
     │
     ▼
  ⑧ 페이지 폴트를 일으킨 명령어를 재실행

5.3 페이지 폴트의 비용

페이지 폴트 발생 시 비용:

  일반 메모리 접근: ~100ns
  페이지 폴트 처리: ~8ms (디스크 I/O 포함)

  페이지 폴트 확률: p

  유효 접근 시간:
  EAT = (1 - p) × 100ns + p × 8,000,000ns

  p = 0.001 (1000번 중 1번 폴트):
  EAT = 0.999 × 100 + 0.001 × 8,000,000
      = 99.9 + 8,000
      = 8,099.9ns ≈ 8.1μs

  → 폴트율 0.1%만 되어도 접근 시간이 80배 증가!
  → 페이지 교체 알고리즘의 목표: 폴트율 최소화

6. 페이지 교체 알고리즘

물리 메모리가 가득 찼을 때 새 페이지를 적재하려면, 기존 페이지 중 하나를 내보내야(교체해야) 한다. 어떤 페이지를 교체할 것인가? 이것이 페이지 교체 알고리즘의 핵심 문제이다.

6.1 참조 문자열 (Reference String)

알고리즘 비교를 위해 사용되는 표준 입력이다.

참조 문자열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
프레임 수: 3

6.2 FIFO (First-In First-Out)

가장 먼저 들어온 페이지를 교체한다. 구현이 단순하지만 성능이 좋지 않다.

참조 문자열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
프레임 수: 3

  참조  │ 프레임 1 │ 프레임 2 │ 프레임 3 │ 폴트?
  ──────┼────────┼────────┼────────┼──────
 │   7    │        │        │  F
 │   7    │   0    │        │  F
 │   7    │   0    │   1    │  F
 │   2    │   0    │   1    │  F (7 교체)
 │   2    │   0    │   1    │  Hit
 │   2    │   3    │   1    │  F (0 교체)
 │   2    │   3    │   0    │  F (1 교체)
 │   4    │   3    │   0    │  F (2 교체)
 │   4    │   2    │   0    │  F (3 교체)
 │   4    │   2    │   3    │  F (0 교체)
 │   0    │   2    │   3    │  F (4 교체)
 │   0    │   2    │   3    │  Hit
 │   0    │   2    │   3    │  Hit
 │   1    │   2    │   3    │  F (0 교체)
 │   1    │   2    │   3    │  Hit
 │   0    │   2    │   3    │  F (1 교체)  -- 순서상 1이 가장 오래됨
 │   0    │   1    │   3    │  F (2 교체)
 │   0    │   1    │   7    │  F (3 교체)
 │   0    │   1    │   7    │  Hit
 │   0    │   1    │   7    │  Hit

  총 페이지 폴트: 15

6.3 Belady’s Anomaly (벨라디의 모순)

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

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

  3 프레임: 9 페이지 폴트
  4 프레임: 10 페이지 폴트  ← 프레임 늘었는데 폴트 증가!

  → FIFO는 "오래된 것"을 교체하지만, 오래된 것이 자주 사용되는 것일 수 있다
  → FIFO의 근본적 한계

LRU, OPT 등 스택 알고리즘에서는 Belady’s Anomaly가 발생하지 않는다. 스택 알고리즘이란 n개 프레임에서의 메모리 상태가 n+1개 프레임에서의 메모리 상태의 부분 집합인 알고리즘이다.

6.4 OPT (Optimal / Belady’s Algorithm)

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이론적으로 최적이지만, 미래를 알아야 하므로 실제 구현이 불가능하다. 다른 알고리즘의 성능 비교 기준(Upper Bound)으로 사용한다.

참조 문자열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
프레임 수: 3

  참조  │ 프레임 1 │ 프레임 2 │ 프레임 3 │ 폴트? │ 교체 이유
  ──────┼────────┼────────┼────────┼──────┼─────────────
    7   │   7    │        │        │  F   │
    0   │   7    │   0    │        │  F   │
    1   │   7    │   0    │   1    │  F   │
    2   │   2    │   0    │   1    │  F   │ 7 교체 (가장 먼 미래)
    0   │   2    │   0    │   1    │  Hit │
    3   │   2    │   0    │   3    │  F   │ 1 교체 (다음 사용이 가장 먼 미래)
    0   │   2    │   0    │   3    │  Hit │
    4   │   2    │   0    │   4    │  F   │ 3 교체
    2   │   2    │   0    │   4    │  Hit │
    3   │   3    │   0    │   4    │  F   │ 2 교체? ...
    ...

  총 페이지 폴트: 9 (이론적 최솟값)

6.5 LRU (Least Recently Used)

가장 최근에 사용되지 않은(가장 오래 전에 사용된) 페이지를 교체한다. OPT의 근사 알고리즘으로, “최근에 사용된 페이지는 가까운 미래에도 사용될 가능성이 높다”는 시간적 지역성(Temporal Locality)을 활용한다.

참조 문자열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
프레임 수: 3

  참조  │ 프레임 상태       │ 폴트? │ 교체 이유
  ──────┼─────────────────┼──────┼─────────────
 │ [7]              │  F   │
 │ [7, 0]           │  F   │
 │ [7, 0, 1]        │  F   │
 │ [0, 1, 2]        │  F   │ 7 교체 (가장 오래 전 사용)
 │ [1, 2, 0]        │  Hit │ 0을 최근으로 이동
 │ [2, 0, 3]        │  F   │ 1 교체
 │ [2, 3, 0]        │  Hit │ 0을 최근으로 이동
 │ [3, 0, 4]        │  F   │ 2 교체
 │ [0, 4, 2]        │  F   │ 3 교체
 │ [4, 2, 3]        │  F   │ 0 교체
 │ [2, 3, 0]        │  F   │ 4 교체
 │ [2, 0, 3]        │  Hit │
 │ [0, 3, 2]        │  Hit │
 │ [3, 2, 1]        │  F   │ 0 교체
 │ [3, 1, 2]        │  Hit │
 │ [1, 2, 0]        │  F   │ 3 교체
 │ [2, 0, 1]        │  Hit │
 │ [0, 1, 7]        │  F   │ 2 교체
 │ [1, 7, 0]        │  Hit │
 │ [7, 0, 1]        │  Hit │

  총 페이지 폴트: 12 (FIFO의 15보다 우수)

LRU 구현 방법

방법 1: 카운터 (Counter) 각 페이지에 접근 시 타임스탬프(카운터)를 기록한다. 교체 시 가장 작은 카운터 값을 가진 페이지를 선택한다. 단점: 교체 시 O(n) 검색.

방법 2: 스택 (Doubly Linked List + Hash Map)

LRU 스택 구현:

  접근 순서: A, B, C, D, B, A

  A 접근: [A]
  B 접근: [A, B]
  C 접근: [A, B, C]
  D 접근: [A, B, C, D]  ← 프레임 가득
  B 접근: [A, C, D, B]  ← B를 top으로 이동
  A 접근: [C, D, B, A]  ← A를 top으로 이동

  교체 필요 시: 바닥(C)을 교체

  ┌───┬───┬───┬───┐
  │ C │ D │ B │ A │
  └───┴───┴───┴───┘
  ↑               ↑
  LRU             MRU
  (교체 대상)     (가장 최근 사용)

Java에서의 LRU 구현 — LinkedHashMap:

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder = true: 접근 순서로 정렬 (LRU 핵심!)
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // 용량 초과 시 가장 오래된 엔트리 제거
    }
}

// 사용 예시
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A");    // {1=A}
cache.put(2, "B");    // {1=A, 2=B}
cache.put(3, "C");    // {1=A, 2=B, 3=C}
cache.get(1);         // {2=B, 3=C, 1=A}  ← 1이 최근으로 이동
cache.put(4, "D");    // {3=C, 1=A, 4=D}  ← 2 제거 (LRU)

6.6 LFU (Least Frequently Used)

사용 빈도가 가장 낮은 페이지를 교체한다. 빈도가 같으면 LRU로 결정한다.

장점: 자주 사용되는 페이지를 잘 보존한다. 단점: 과거에 많이 사용되었지만 지금은 불필요한 페이지가 오래 남을 수 있다 (초기 집중 접근 후 안 쓰는 경우). 구현이 LRU보다 복잡하다.

6.7 Clock Algorithm (Second Chance)

LRU를 하드웨어적으로 근사하는 알고리즘이다. FIFO의 단순함과 LRU의 성능을 절충한다.

Clock 알고리즘:

  원형 버퍼 + 참조 비트(Reference Bit) + 시계 바늘(Clock Hand)

         시계 바늘
            ↓
  ┌───┬───┬───┬───┬───┐
  │ A │ B │ C │ D │ E │
  │ 1 │ 0 │ 1 │ 0 │ 1 │  ← 참조 비트
  └───┴───┴───┴───┴───┘

  교체 과정:
  1. 시계 바늘이 가리키는 페이지의 참조 비트 확인
  2. 참조 비트 = 1 → 0으로 변경하고 다음으로 이동 (두 번째 기회 부여)
  3. 참조 비트 = 0 → 이 페이지를 교체!

  위 예시에서:
  C(1) → 0으로 변경, 다음
  D(0) → 교체 대상!

Clock 알고리즘 상세 동작:

  교체 필요 → 시계 바늘 시작

  Step 1: A(참조비트=1) → 참조비트=0으로 변경, 바늘 이동
  Step 2: B(참조비트=0) → 교체 대상! B를 새 페이지로 교체

핵심: 최근에 참조된 페이지(참조 비트=1)는 “두 번째 기회(Second Chance)”를 받는다. 참조 비트가 0인 페이지만 교체 대상이 된다. 한 바퀴를 돌아도 모든 비트가 1이면, 결국 처음 방문한 페이지의 비트가 0이 되어 FIFO처럼 동작한다.

6.8 Enhanced Clock (개선된 Clock)

참조 비트(R)뿐 아니라 수정 비트(M, Dirty Bit)도 함께 고려한다.

우선순위 (R, M):
  (0, 0) → 최우선 교체: 참조 안 됨 + 수정 안 됨 (쓰기 불필요)
  (0, 1) → 2순위: 참조 안 됨 + 수정됨 (쓰기 필요)
  (1, 0) → 3순위: 참조됨 + 수정 안 됨
  (1, 1) → 최후 교체: 참조됨 + 수정됨

수정된 페이지(Dirty Page)를 교체하면 디스크에 써야 하므로 비용이 크다. 따라서 수정되지 않은 페이지를 우선 교체하는 것이 효율적이다.

6.9 알고리즘 비교 요약

알고리즘	폴트 수	구현 난이도	Belady’s Anomaly	비고
FIFO	많음	매우 쉬움	발생 가능	큐로 구현
OPT	최소	구현 불가	없음	성능 비교 기준
LRU	적음	중간	없음	LinkedHashMap
LFU	적음	높음	없음	빈도 카운터 필요
Clock	중간	쉬움	발생 가능	LRU 근사, 실무 사용

면접에서 자주 나오는 질문: “LRU와 FIFO의 차이를 설명하세요.” → FIFO는 적재 순서만 보고, LRU는 사용 순서를 본다. 같은 페이지를 다시 접근해도 FIFO는 순서를 갱신하지 않지만 LRU는 가장 최근으로 올린다.

7. 프레임 할당 전략

7.1 균등 할당 (Equal Allocation)

모든 프로세스에 동일한 수의 프레임을 할당한다.

물리 프레임 100개, 프로세스 5개
→ 각 프로세스에 20 프레임씩

문제: 크기가 500KB인 프로세스와 50MB인 프로세스에 같은 수를 할당하는 것은 비효율적

7.2 비례 할당 (Proportional Allocation)

프로세스 크기에 비례하여 프레임을 할당한다.

프로세스 A: 10MB, 프로세스 B: 127MB
총 프레임: 62개

A의 할당 = 62 × (10 / 137) ≈ 5 프레임
B의 할당 = 62 × (127 / 137) ≈ 57 프레임

7.3 전역 교체 vs 지역 교체

방식	설명	장점	단점
전역 교체	모든 프레임 중에서 교체 대상 선택	전체 처리량 최적화	프로세스 간 간섭
지역 교체	자신에게 할당된 프레임 내에서만 교체	프로세스 독립성	전체 최적화 어려움

전역 교체가 일반적으로 더 좋은 처리량을 보이지만, 하나의 프로세스가 다른 프로세스의 프레임을 빼앗을 수 있어 성능 예측이 어렵다.

8. 스래싱 (Thrashing)

8.1 정의

프로세스가 충분한 프레임을 확보하지 못해 페이지 폴트가 과도하게 발생하고, 실제 작업보다 페이지 교체에 더 많은 시간을 쓰는 현상이다.

스래싱 상태:

  CPU 이용률
  ↑
  │        ╱╲
  │       ╱  ╲
  │      ╱    ╲
  │     ╱      ╲
  │    ╱        ╲
  │   ╱          ╲───────── 스래싱 발생
  │  ╱
  │ ╱
  └──────────────────────────► 다중 프로그래밍 정도 (프로세스 수)

  프로세스가 많아지면:
  → 각 프로세스의 프레임 부족 → 페이지 폴트 증가
  → 디스크 I/O 대기 → CPU 유휴
  → OS가 "CPU 이용률이 낮다"고 판단 → 프로세스 추가 투입
  → 더 심한 프레임 부족 → 악순환!

8.2 Working Set Model

Working Set은 특정 시간 구간(Working Set Window, Δ) 동안 프로세스가 참조한 페이지의 집합이다.

참조 문자열 (Δ = 10):

  ... 2 6 1 5 7 7 7 7 5 1 │ 6 2 3 4 1 2 3 4 4 4 ...
                            ← ──── Δ = 10 ──── →
                            Working Set = {1, 2, 3, 4, 6}

  각 프로세스의 Working Set Size(WSS) 합 ≤ 물리 프레임 수
  → 이 조건을 유지하면 스래싱을 방지할 수 있다

8.3 PFF (Page Fault Frequency)

Working Set보다 직관적인 방법이다. 페이지 폴트 빈도를 직접 모니터링한다.

PFF (Page Fault Frequency):

  페이지 폴트율
  ↑
  │                    상한 (Upper Bound)
  │  ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
  │
  │           적정 범위
  │
  │  ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
  │                    하한 (Lower Bound)
  └──────────────────────────────► 프레임 수

  폴트율 > 상한 → 프레임 추가 할당
  폴트율 < 하한 → 프레임 회수 (다른 프로세스에 재분배)

9. Copy-on-Write (COW)

9.1 fork()에서의 활용

fork() 시스템 호출은 부모 프로세스의 복사본을 만든다. 전체 메모리를 복사하면 비용이 크다. COW는 실제로 수정이 발생하기 전까지는 부모와 자식이 같은 물리 프레임을 공유하는 기법이다.

fork() 직후:

  부모 프로세스                    자식 프로세스
  ┌──────────┐                  ┌──────────┐
  │ 페이지 0  │──┐              │ 페이지 0  │──┐
  ├──────────┤  │              ├──────────┤  │
  │ 페이지 1  │──┤── 공유 ──►   │ 페이지 1  │──┤── 공유
  ├──────────┤  │              ├──────────┤  │
  │ 페이지 2  │──┘              │ 페이지 2  │──┘
  └──────────┘                  └──────────┘
                    │
                    ▼
              ┌──────────┐
              │ 물리 프레임 │ ← 읽기 전용으로 공유
              │ (공유)     │
              └──────────┘

자식이 페이지 1에 쓰기 시:

  → 페이지 폴트 발생 (읽기 전용이므로)
  → OS가 해당 페이지만 복사하여 새 프레임에 저장
  → 자식의 페이지 테이블을 새 프레임으로 업데이트

  부모 프로세스                    자식 프로세스
  ┌──────────┐                  ┌──────────┐
  │ 페이지 0  │──── 공유 ────── │ 페이지 0  │
  ├──────────┤                  ├──────────┤
  │ 페이지 1  │── 프레임 A      │ 페이지 1  │── 프레임 B (복사본)
  ├──────────┤                  ├──────────┤
  │ 페이지 2  │──── 공유 ────── │ 페이지 2  │
  └──────────┘                  └──────────┘

9.2 Java에서의 COW — CopyOnWriteArrayList

Java의 CopyOnWriteArrayList는 같은 아이디어를 자료구조에 적용한 것이다. 읽기는 락 없이 자유롭고, 쓰기 시에만 내부 배열을 복사한다.

import java.util.concurrent.CopyOnWriteArrayList;

// 읽기가 압도적으로 많고, 쓰기가 드문 상황에 적합
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

// 쓰기: 내부 배열을 복사하고 새 배열에 추가
list.add("A");  // 배열 복사 발생

// 읽기: 현재 배열의 스냅샷을 읽음 (락 없음, 빠름)
for (String item : list) {
    // 순회 중에 다른 스레드가 add해도 ConcurrentModificationException 없음
    // 순회는 순회 시작 시점의 스냅샷을 보기 때문
    System.out.println(item);
}

CopyOnWriteArrayList 동작 원리:

  쓰기 시 (add):
    ① 현재 배열을 새 배열로 복사
    ② 새 배열에 원소 추가
    ③ 참조를 새 배열로 교체 (volatile 쓰기)

  읽기 시 (get, iterator):
    ① 현재 배열 참조를 읽음 (volatile 읽기)
    ② 별도의 락 없이 읽기

  장점: 읽기에 락 없음 → 읽기 성능 최대화
  단점: 쓰기마다 배열 복사 → 쓰기 빈번하면 성능 저하
  적합: 리스너 목록, 설정값 목록 등 (읽기 >>> 쓰기)

10. 메모리 매핑 파일 (Memory-Mapped File)

파일을 프로세스의 가상 주소 공간에 직접 매핑하는 기법이다. 파일 I/O를 메모리 접근처럼 처리할 수 있다.

일반 파일 I/O:
  read() → 커널 버퍼로 복사 → 사용자 버퍼로 복사 (2회 복사)

메모리 매핑:
  mmap() → 파일이 가상 주소 공간에 매핑
  → 페이지 폴트 시 디스크에서 직접 물리 메모리로 적재 (1회 복사)
  → 메모리 접근으로 파일 읽기/쓰기

// Java NIO의 MappedByteBuffer
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.*;

public class MemoryMappedFileExample {
    public static void main(String[] args) throws Exception {
        Path path = Path.of("large-file.dat");

        try (FileChannel channel = FileChannel.open(path,
                StandardOpenOption.READ, StandardOpenOption.WRITE)) {

            // 파일을 메모리에 매핑
            MappedByteBuffer buffer = channel.map(
                    FileChannel.MapMode.READ_WRITE, 0, channel.size());

            // 메모리 접근처럼 파일 읽기
            byte firstByte = buffer.get(0);

            // 메모리 접근처럼 파일 쓰기
            buffer.put(0, (byte) 0xFF);

            // 변경사항을 디스크에 동기화
            buffer.force();
        }
    }
}

11. 실무에서의 가상 메모리

11.1 JVM 메모리와 OS 가상 메모리의 관계

JVM 메모리 구조와 OS 가상 메모리:

  JVM 프로세스의 가상 주소 공간:
  ┌──────────────────────────────┐
  │         Native Memory         │  ← JVM 내부, 메타스페이스 등
  ├──────────────────────────────┤
  │         JVM Heap              │  ← -Xmx로 설정 (GC 관리)
  │  ┌─────────┬─────────────┐  │
  │  │  Young   │    Old      │  │
  │  │  Gen     │    Gen      │  │
  │  └─────────┴─────────────┘  │
  ├──────────────────────────────┤
  │         Stack (스레드별)       │
  ├──────────────────────────────┤
  │         Code Cache           │  ← JIT 컴파일된 코드
  └──────────────────────────────┘
      │
      │  OS 가상 메모리 위에서 동작
      ▼
  ┌──────────────────────────────┐
  │    물리 메모리 (RAM)           │
  ├──────────────────────────────┤
  │    스왑 영역 (디스크)           │
  └──────────────────────────────┘

JVM의 Heap 메모리는 OS 가상 메모리의 일부이다. -Xmx로 설정한 최대 힙 크기는 가상 주소 공간에서 예약되지만, 실제 물리 메모리는 요구 페이징에 의해 사용 시점에 할당된다.

11.2 GC와 페이지 폴트

Full GC 발생 시 JVM은 전체 힙을 순회한다. 힙이 물리 메모리보다 크거나 스왑 영역에 일부가 있으면, GC 도중 대량의 페이지 폴트가 발생하여 GC 시간이 급격히 증가한다.

GC와 페이지 폴트의 악순환:

  힙 크기 > 물리 메모리
  → 힙 일부가 스왑 아웃됨
  → Full GC 시 스왑된 영역 접근 → 대량 페이지 폴트
  → GC 시간 급증 (수 초 → 수십 초)
  → STW(Stop-The-World) 길어짐 → 서비스 장애

  해결: JVM 힙을 물리 메모리 범위 내로 설정
        스왑을 비활성화하거나 swappiness를 낮게 설정

# Linux에서 swappiness 확인/설정
cat /proc/sys/vm/swappiness    # 기본값 60 (0~100)
sudo sysctl vm.swappiness=10   # JVM 서버에서는 낮게 설정 권장

11.3 리눅스 OOM Killer

물리 메모리와 스왑이 모두 소진되면 Linux 커널의 OOM(Out of Memory) Killer가 메모리를 많이 사용하는 프로세스를 강제 종료한다.

# OOM Killer 로그 확인
dmesg | grep -i "oom"

# 프로세스의 OOM 점수 확인 (높을수록 kill 대상)
cat /proc/<PID>/oom_score

# JVM 프로세스의 OOM 점수 조정 (-1000 ~ 1000, 낮을수록 보호)
echo -17 > /proc/<PID>/oom_score_adj

12. 면접에서 자주 나오는 가상 메모리 질문과 답변

Q1: 가상 메모리란 무엇이고, 왜 필요한가요?

가상 메모리는 물리 메모리를 추상화하여 각 프로세스에게 독립적인 연속 주소 공간을 제공하는 기법입니다. 필요한 이유는 세 가지입니다. 첫째, 물리 메모리보다 큰 프로그램을 실행할 수 있습니다(디스크를 확장 저장소로 활용). 둘째, 프로세스 간 메모리 격리를 보장합니다. 셋째, 실제로 사용하는 페이지만 물리 메모리에 올려 메모리 효율을 높입니다.

Q2: 페이지 폴트가 발생하면 어떤 일이 일어나나요?

CPU가 유효 비트가 0인 페이지에 접근하면 페이지 폴트 트랩이 발생합니다. OS가 디스크에서 해당 페이지의 위치를 확인하고, 빈 프레임이 있으면 해당 프레임에 적재합니다. 빈 프레임이 없으면 페이지 교체 알고리즘으로 희생 페이지를 선택합니다. 희생 페이지가 수정되었다면(Dirty Bit=1) 디스크에 먼저 써야 합니다. 적재가 완료되면 페이지 테이블을 업데이트하고, 페이지 폴트를 일으킨 명령어를 재실행합니다.

Q3: LRU와 FIFO의 차이를 설명하세요.

FIFO는 가장 먼저 메모리에 적재된 페이지를 교체합니다. 적재 순서만 보고, 이후에 얼마나 자주 사용되었는지는 고려하지 않습니다. LRU는 가장 최근에 사용되지 않은 페이지를 교체합니다. 페이지에 접근할 때마다 사용 시간을 갱신하므로, 자주 사용되는 페이지는 교체되지 않습니다. LRU가 시간적 지역성을 활용하므로 일반적으로 FIFO보다 페이지 폴트가 적습니다. 또한 FIFO는 Belady’s Anomaly가 발생할 수 있지만 LRU는 스택 알고리즘이므로 발생하지 않습니다.

Q4: Belady’s Anomaly란 무엇인가요?

FIFO 알고리즘에서 물리 프레임 수를 늘렸는데 오히려 페이지 폴트가 증가하는 현상입니다. 직관에 반하지만, FIFO는 “오래된 것”을 교체하기 때문에 자주 사용되는 페이지가 교체될 수 있어 이런 현상이 발생합니다. LRU, OPT 같은 스택 알고리즘에서는 발생하지 않습니다.

Q5: TLB란 무엇이고, 왜 필요한가요?

TLB(Translation Lookaside Buffer)는 최근 사용된 페이지 테이블 엔트리를 캐싱하는 하드웨어 캐시입니다. 페이지 테이블이 메모리에 있으므로, TLB 없이는 모든 메모리 접근이 두 번의 메모리 접근을 필요로 합니다(페이지 테이블 + 실제 데이터). TLB 히트율이 98%이고 메모리 접근 시간이 100ns일 때, 유효 접근 시간은 약 112ns로 TLB 없는 200ns 대비 44% 향상됩니다.

Q6: 스래싱(Thrashing)이란 무엇이고, 어떻게 해결하나요?

프로세스가 충분한 프레임을 확보하지 못해 페이지 폴트가 과도하게 발생하고, 실제 작업보다 페이지 교체에 더 많은 시간을 쓰는 현상입니다. 해결 방법으로는 Working Set Model(시간 구간 내 참조된 페이지 집합 크기만큼 프레임 보장)과 PFF(페이지 폴트 빈도를 모니터링하여 프레임 동적 조정)가 있습니다. 근본적으로는 다중 프로그래밍 정도를 줄이는 것이 해결책입니다.

Q7: Copy-on-Write란 무엇인가요?

fork() 시 부모 프로세스의 전체 메모리를 즉시 복사하는 대신, 부모와 자식이 같은 물리 프레임을 읽기 전용으로 공유합니다. 어느 한 쪽이 쓰기를 시도하면 그때 해당 페이지만 복사합니다. 대부분의 페이지가 수정되지 않으므로 메모리와 시간을 크게 절약합니다. Java에서는 CopyOnWriteArrayList가 같은 원리를 적용한 자료구조로, 읽기에는 락이 없고 쓰기 시에만 내부 배열을 복사합니다.

Q8: 페이지 크기가 크면 어떤 장단점이 있나요?

큰 페이지의 장점은 페이지 테이블 크기 감소(엔트리 수 감소), TLB 커버리지 증가(하나의 엔트리가 더 많은 주소 공간 커버), 디스크 I/O 효율 향상(한 번에 큰 블록 전송)입니다. 단점은 내부 단편화 증가(평균 낭비 = 페이지 크기 / 2)와, 불필요한 데이터도 함께 적재될 수 있다는 것입니다. Linux에서는 기본 4KB 페이지 외에 2MB, 1GB의 Huge Page를 지원합니다.

Q9: JVM의 힙 메모리와 OS 가상 메모리의 관계는?

JVM 힙은 OS 가상 메모리의 일부입니다. -Xmx로 설정한 최대 힙은 가상 주소 공간에서 예약되지만, 물리 메모리는 요구 페이징으로 실제 사용 시점에 할당됩니다. 주의할 점은 힙 크기가 물리 메모리를 초과하면 스왑이 발생하고, Full GC 시 대량 페이지 폴트로 GC 시간이 급증할 수 있다는 것입니다. 따라서 JVM 서버에서는 힙을 물리 메모리 범위 내로 설정하고 swappiness를 낮게 조정하는 것이 권장됩니다.

Q10: Clock 알고리즘이 실무에서 많이 사용되는 이유는?

LRU는 이론적으로 좋지만, 매 메모리 접근마다 사용 시간을 갱신하는 것은 하드웨어 비용이 큽니다. Clock 알고리즘은 참조 비트 하나만으로 LRU를 근사합니다. 하드웨어가 자동으로 참조 비트를 설정하고, 교체 시에만 검사하면 되므로 오버헤드가 매우 낮습니다. 성능은 LRU에 가깝고 구현은 FIFO만큼 단순하여, Linux를 비롯한 대부분의 OS에서 변형된 Clock 알고리즘을 사용합니다.

정리

가상 메모리의 핵심을 정리하면 다음과 같다.

기본 개념: 가상 메모리는 물리 메모리를 추상화하여 프로세스에게 독립적인 주소 공간을 제공한다. 페이지 테이블이 가상 주소를 물리 주소로 변환하며, TLB가 이 변환을 캐싱하여 성능을 보장한다.

요구 페이징: 모든 페이지를 미리 적재하지 않고, 실제 접근 시점에 적재한다. 페이지 폴트는 디스크 I/O를 수반하므로 비용이 크며(메모리 접근의 약 80,000배), 폴트율을 최소화하는 것이 페이지 교체 알고리즘의 목표이다.

페이지 교체 알고리즘: OPT는 이론적 최적이지만 구현 불가. LRU는 시간적 지역성을 활용하여 좋은 성능을 보이며, Clock 알고리즘이 하드웨어 수준에서 LRU를 근사한다. FIFO는 단순하지만 Belady’s Anomaly가 발생할 수 있어 실무에서는 사용하지 않는다.

스래싱: 프레임 부족으로 과도한 페이지 폴트가 발생하는 현상이다. Working Set Model이나 PFF로 프레임을 동적으로 조절하여 방지한다. JVM 환경에서는 힙 크기를 물리 메모리 범위 내로 설정하는 것이 근본적인 예방책이다.