요구 페이징 (Demand Paging)

Jan 23, 2026 · Updated Jan 27, 2026

핵심 개념

요구 페이징(Demand Paging)은 페이지를 프로그램 시작 시 모두 적재하지 않고, 실제로 필요할 때(접근할 때)만 메모리에 적재하는 기법입니다. 프로그램의 지역성(locality) 원리에 기반하여, 최근 사용된 페이지가 다시 사용될 가능성이 높다는 가정 하에 동작합니다.

동작 원리

기본 메커니즘

각 페이지 테이블 항목에 valid-invalid bit를 사용합니다.

valid: 페이지가 메모리에 존재
invalid: 페이지가 메모리에 없음 (보조 저장장치에 존재)

invalid 페이지 접근 시 page fault 트랩이 발생합니다:

프로세스의 내부 테이블 검사 (유효한 참조인지 확인)
유효하면 free frame 확보
보조 저장장치에서 해당 페이지를 free frame으로 로드
페이지 테이블 갱신 (valid로 설정)
트랩을 발생시킨 명령어 재시작

성능 분석

$$\text{effective access time} = (1 - p) \times ma + p \times \text{page_fault_time}$$

p: 페이지 폴트 확률 (0 ≤ p ≤ 1)
ma: 메모리 접근 시간

ma=200ns, page_fault_time=8ms일 때, 10% 미만 성능 저하를 유지하려면 p < 0.0000025 (약 40만 번 접근에 1번)

역사적 구현

Atlas 시스템(1950년대 후반~1960년대 초반, 맨체스터 대학)에서 최초로 구현되었습니다.

가상 주소 공간: 24비트 → 100만 워드 주소 가능
물리 메모리: 드럼 98KB + 코어 16KB, 512워드 페이지 → 32개 프레임
연관 메모리(associative memory) 32개 레지스터로 가상→물리 주소 매핑
페이지 폴트 발생 시 페이지 교체 알고리즘 호출

Virtual Address Space (100만 워드)
          ↓ 매핑
┌─────────────────────────────────┐
│   Associative Memory (32 reg)  │
└─────────────────────────────────┘
          ↓
┌──────────────────┐    ┌──────────────────┐
│ Core Memory 16KB │ ←→ │ Drum 98KB        │
│ (32 frames)      │    │ (backing store)  │
└──────────────────┘    └──────────────────┘

Atlas의 페이지 교체 알고리즘

참조 비트(reference bit)를 1,024 명령마다 읽어 최근 32개 값 보관합니다.

t₁ = 가장 최근 참조 이후 시간
t₂ = 마지막 두 참조 사이 간격

교체 우선순위:

t₁ > t₂ + 1인 페이지 → 더 이상 사용되지 않는다고 판단하여 교체
모든 페이지가 t₁ ≤ t₂이면 → t₂ - t₁이 가장 큰 페이지 교체

예시

책상 위(코어)와 책장(드럼)의 비유: 자주 보는 책만 책상에 두고, 필요하면 책장에서 가져옵니다.

루프 가정 시나리오:

t₂ = 100 (100 명령마다 한 번 참조)
t₁ = 50 (50 명령 전에 참조됨)
예상 다음 참조: 50 명령 후 → 이 페이지는 유지
만약 t₁ = 150이면 → 이미 예상 시점 지남 → 교체 대상

BSD 구현

3BSD(1979)에서 VAX용으로 디맨드 페이징이 도입되었습니다. 프로세스는 한 시점에 전체 주소 공간의 일부(워킹셋)만 필요하다는 가정하에 동작합니다.

pagedaemon (프로세스 2)

주기적으로 깨어나 free 프레임 수를 확인하고, free < lotsfree이면 페이지 교체를 시작합니다.

메모리 임계값:
┌─────────────────────────────────────────────┐
│ lotsfree (1/4 메모리) ─ 충분한 여유          │
├─────────────────────────────────────────────┤
│ desfree ─ 바람직한 여유                      │
├─────────────────────────────────────────────┤
│ minfree ─ 최소 여유 (인터럽트용)             │
└─────────────────────────────────────────────┘

free < lotsfree → pagedaemon 활성화
free < desfree (지속) → 스케줄러가 프로세스 스왑아웃
free < minfree → 인터럽트 시 즉시 사용 가능한 여유 확보

수정된 clock(second-chance) 알고리즘

클록 핸드가 core map을 순회하며 교체 대상을 결정합니다.

1차 패스: reference bit 끄기
2차 패스: reference bit이 여전히 꺼진 페이지를 free list로
dirty 페이지는 먼저 디스크에 쓴 후 free

Clock 알고리즘:
  ┌───────────────────┐
  │    Clock Hand     │
  │        ↓          │
  │ [R=1]→[R=0]→[R=0]→[R=1]→...
  │                    ↑
  │            교체 대상
  └───────────────────┘

page coloring

L1/L2 캐시 최적화를 위한 프레임 할당 기법입니다.

트레이드오프

prepaging 옵션으로 초기 페이지 폴트 감소
pagedaemon이 시스템 부하에 따라 적응적 동작
단점: 스래싱 위험(메모리 부족 시), clock 알고리즘 오버헤드(대용량 메모리에서)