페이지 교체 알고리즘과 스래싱(thrashing) · 해설

난이도: 중상

모범답안

1. 상황과 목표

디맨드 페이징에서 프로세스는 필요한 페이지만 물리 프레임에 올린다. 빈 프레임이 없는데 새 페이지가 필요하면 기존 페이지 하나를 victim 으로 골라 (더티면 디스크에 쓰고) 내보낸 뒤 그 프레임을 재사용한다. 교체 알고리즘의 목표는 페이지 폴트율(특히 디스크 I/O를 유발하는 major fault)을 최소화하는 것. 폴트 1회는 수십 µs~수 ms 로 메모리 접근보다 수천~수만 배 느리다.

2. 알고리즘 비교

OPT(Belady): "앞으로 가장 오래 안 쓰일 페이지"를 내보냄 → 이론적 최소 폴트. 미래를 알아야 하므로 실현 불가. 다른 알고리즘의 성능 상한 기준으로 사용.
FIFO: 들어온 순서로 내보냄. 구현 단순하나 "오래된 = 안 쓰임"이 아니라서 자주 쓰는 페이지도 쫓아낸다. Belady의 역설: 프레임을 늘렸는데 폴트가 오히려 늘 수 있다(스택 알고리즘이 아니기 때문). LRU/OPT 는 이 역설이 없다.
LRU: "가장 오래 안 쓰인" 페이지를 내보냄. 시간 지역성 가정에 잘 맞아 성능이 좋다. 그러나 정확한 LRU 는 매 접근마다 타임스탬프/리스트 갱신이 필요해 하드웨어 지원 없이는 비용이 크다(모든 메모리 접근에 개입 불가).
Clock(2차 기회): LRU 근사. 프레임을 원형으로 두고 각 페이지에 reference 비트를 둔다. 접근 시 하드웨어가 R=1 로 세팅. victim 탐색 시 포인터가 돌며 R=1 이면 0으로 지우고 한 번 더 기회를 주고(넘어감), R=0 인 첫 페이지를 내보냄. 오버헤드가 작아 실제 OS 가 널리 사용(변형: 더티 비트까지 보는 enhanced clock).

3. 워킹셋과 스래싱

워킹셋 W(t, Δ) = 최근 Δ 시간 동안 참조된 페이지 집합 = 프로세스가 "지금 활발히 쓰는" 페이지들. 이 크기가 그 프로세스에 할당된 물리 프레임 수보다 크면, 활발히 쓰는 페이지조차 상주하지 못하고 서로를 쫓아내며 끊임없이 페이지 폴트가 난다 → 스래싱. 증상: CPU 이용률은 낮은데 디스크가 100%, 처리량 급락. 원인: 다중 프로그래밍 정도(동시 실행 프로세스 수)가 과해 총 워킹셋 합이 물리 메모리를 초과하는 것. CPU 유휴를 보고 프로세스를 더 올리면 악화되는 피드백 루프.

4. 방지·완화

워킹셋 기반 할당: 각 프로세스에 그 워킹셋을 담을 만큼 프레임을 보장하고, 워킹셋 합이 물리 메모리를 넘으면 일부 프로세스를 통째로 스왑아웃(suspend) 해 다중 프로그래밍 정도를 낮춘다.
PFF(page-fault frequency) 제어: 폴트율이 상한을 넘으면 프레임을 더 주고, 하한 밑이면 회수. 폴트율을 목표 범위로 유지.
프리페치/지역성 개선: 순차 접근 패턴이면 미리 읽어 major fault 를 줄임.
메모리 증설/작업 분산: 근본적으로 워킹셋 합 ≤ 물리 메모리를 유지.

5. 게임 서버 적용

핫 데이터 상주성: 매 틱 접근하는 시뮬레이션 상태·인덱스는 항상 상주해야 하며, 스와핑되면 틱 지터가 폭증한다. 필요 시 mlock/mlockall 로 핵심 영역을 페이지 아웃 금지, 거대 페이지(huge page) 로 TLB 미스·페이징 오버헤드 절감.
mmap 에셋: 대용량 맵/에셋을 mmap 하면 접근 시 디맨드 페이징으로 로드된다. 접근 지역성(연속 배치, SoA) 이 좋으면 폴트가 적고 프리페치가 잘 먹는다.
컨테이너 제한과 OOM: cgroup 메모리 한도 근처에선 커널이 페이지 캐시를 회수하다 결국 OOM Killer 가 프로세스를 죽인다. 워킹셋을 한도 안에 설계.
GC 언어의 위험: GC 는 힙 전체를 훑어(mark) 나쁜 지역성으로 접근한다. 힙이 스왑되어 있으면 GC 가 대량 major fault 를 유발해 stop-the-world 가 수 초로 늘 수 있다. 컨테이너 한도·GC 힙 크기를 물리 메모리에 맞춰 페이징을 피해야 한다.

면접 포인트

OPT(기준)·FIFO(Belady 역설)·LRU(비용)·Clock(실무 근사)의 트레이드오프.
워킹셋 모델과 스래싱의 피드백 루프, 다중 프로그래밍 정도 조절.
게임 서버에서 핫 데이터 상주(mlock/huge page)와 GC×페이징의 위험.