페이지 교체는 어떤 페이지를 버릴지의 알고리즘 문제이면서, 현재 작업 집합을 메모리에 담을 수 있는지의 용량 문제입니다. 이 노트는 작은 참조열로 FIFO·LRU·Clock의 차이를 확인하고, cold fault와 지속 스래싱, 회수·writeback 비용을 분리합니다.
페이지 재접근과 스래싱
참조열을 A B C D A B C D처럼 반복할 때 프레임 수가 작업 집합보다 작으면 같은 페이지를 계속 읽게 됩니다. 처음 한 번의 cold fault와 반복 구간의 fault율·저장장치 대기를 분리해 측정해야, 초기 준비 비용을 스래싱으로 잘못 진단하지 않습니다.
프로세스가 곧 다시 사용할 페이지들이 메모리에 남지 못하면 회수·fault·읽기가 반복됩니다. 유용한 계산보다 페이지 교체와 저장장치 대기가 지배하는 상태가 스래싱입니다. 페이지 폴트가 많다는 사실만으로 단정하지 않고 처음 접근의 준비 비용인지 지속 재읽기인지 구분해야 합니다.
세 작업이 서로 공유하지 않는 페이지를 각각 4개씩 번갈아 사용하고 가용 프레임이 8개라면 필요한 작업 집합의 합은 12페이지입니다. 일부 페이지를 내보내 다른 작업을 넣어도, 곧 내보낸 페이지를 다시 쓰는 순간 fault와 재준비 비용이 생겨 교체가 계속될 수 있습니다. 따라서 교체 알고리즘을 바꾸기 전에 작업 집합과 동시 실행 수가 프레임 예산에 맞는지 먼저 봅니다.
페이지 교체 대상 추정 방식
정책 선택은 “가장 좋은 알고리즘”보다 접근 패턴과 관측 비용에 맞춥니다. 순차 스캔이 핫 페이지를 밀어내는 환경에서는 prefetch·캐시 분리·지역 제한을 함께 고려하고, FIFO의 프레임 증가에도 fault가 늘 수 있는 참조열을 직접 재생해 단조 개선을 가정하지 않습니다.
| 정책 | 선택 기준 | 한계 |
|---|---|---|
| FIFO | 가장 먼저 들어온 페이지 | 자주 쓰는 오래된 페이지도 제거 |
| LRU | 가장 오래 접근하지 않은 페이지 | 정확한 모든 접근 순서 관리 비용 |
| Clock | 접근 비트와 회전 포인터 | 최근성의 근사, 순서 정보 손실 |
| 미래 최적 | 다음 사용이 가장 먼 페이지 | 미래를 알아야 하므로 비교 기준 |
FIFO에서는 프레임을 늘렸는데 특정 참조열의 fault가 늘어나는 Belady anomaly도 가능하므로 용량과 결과의 관계를 모든 정책에서 단순하게 보지 않습니다. 실제 OS는 dirty·참조·공유·메모리 압력 등을 조합하며 교과서 정책을 그대로 쓰지 않을 수 있습니다.
Clock의 참조 비트와 두 번째 기회
A·B·C를 넣고 A만 다시 접근한 뒤 hand가 A에서 시작하는 실습의 예측은 Clock이 A를 고를 수 있고 정확한 LRU는 B를 고르는 것입니다. 참조 비트가 “최근 접근이 있었음”만 기억한다는 점과 hand 위치를 고정해야 재현 결과가 같다는 점을 함께 기록합니다.
페이지를 접근하면 참조 비트가 1이 됩니다. 교체할 때 hand가 가리키는 페이지의 비트가 1이면 0으로 지우고 다음으로 이동합니다. 0인 후보를 만나면 제거합니다. 정확한 마지막 접근 순번을 저장하지 않으므로 LRU와 다른 결과가 나올 수 있습니다.
그림을 글로 읽기
- A · ref=1: hand 시작, 0으로 변경
- B · ref=1: 0으로 변경
- C · ref=1: 0으로 변경
- 다시 A · ref=0: 추가 접근 없으면 교체
- A · ref=1 → B · ref=1: 기회 부여
- B · ref=1 → C · ref=1: 기회 부여
- C · ref=1 → 다시 A · ref=0: 한 바퀴 완료
A·B·C를 넣은 뒤 A만 다시 접근했어도 비트는 여전히 모두 1입니다. hand가 A를 가리킨다면 추가 접근 없는 교체 탐색에서 Clock은 A를 제거할 수 있지만 정확한 LRU는 B를 고릅니다. 한 비트는 접근 여부를 기억할 뿐 세부 순서를 기억하지 않습니다.
작업 집합과 시간 창 선택
시간 창을 바꿔 작업 집합 크기를 계산하면 너무 짧은 창은 미래 재접근을 놓치고 너무 긴 창은 과거 phase의 페이지를 남기는 모습을 볼 수 있습니다. 전역 교체와 지역 제한을 비교할 때는 프로세스별 resident set과 전체 완료율을 함께 봐야 한 작업의 개선이 다른 작업의 starvation으로 바뀌는지 알 수 있습니다.
최근 일정 시간 또는 참조 횟수 안에서 접근한 페이지 집합을 작업 집합으로 볼 수 있습니다. 창이 너무 짧으면 곧 다시 사용할 페이지를 놓치고, 너무 길면 이제 필요 없는 스캔 페이지까지 포함합니다. 접근 빈도와 phase 변화도 봐야 합니다.
전역 교체는 한 작업의 메모리 폭증이 다른 작업의 프레임을 빼앗게 할 수 있습니다. 지역적 제한은 간섭을 줄이지만 한 작업의 부족을 다른 곳의 여유로 해결하지 못할 수 있습니다. cgroup·프로세스·호스트 예산과 실제 정책을 구분합니다.
Fault 감소와 실제 처리 비용
fault 수만 줄인 정책이 항상 빠른 것은 아닙니다. dirty victim의 writeback, major fault 저장장치 지연, prefetch로 인한 불필요한 eviction을 같은 trace에서 측정하고 유용한 완료 작업과 p99를 최종 지표로 둡니다.
미리 읽기는 순차 접근의 fault 대기를 줄일 수 있지만 안 쓸 페이지를 가져와 다른 핫 페이지를 밀어낼 수도 있습니다. dirty 페이지는 writeback이 필요하므로 같은 victim 개수라도 비용이 다릅니다. 파일 스캔과 앱 캐시가 서로 메모리를 차지하는 것도 봅니다.
measure_under_same_trace:
useful_completed_work
minor_and_major_faults
reclaim_and_writeback_time
resident_working_set
storage_latency_and_request_p99
동시 작업 수를 줄이거나 접근 지역성을 높인 뒤 유용한 완료율과 p99가 회복되는지 확인합니다. CPU 사용률만 낮다고 여유가 있다고 보지 않습니다. 저장장치를 기다리느라 계산을 못 하고 있을 수 있습니다.
동일 참조열 기반 교체 정책·부하 회복 비교
검증 실습은 같은 참조열과 같은 프레임 수로 FIFO·LRU·Clock의 fault 수를 먼저 비교한 뒤, 실제 부하를 낮추고 재읽기 지연이 회복되는지 봅니다. 부하를 줄인 뒤에도 resident working set이 예산을 넘으면 정책 교체보다 동시성 제한·데이터 구조·메모리 예산 조정이 원인에 맞는 대응입니다.
작은 페이지 참조열을 FIFO·LRU·Clock 모형으로 재생해 각 교체를 추적합니다. Clock의 hand 위치·비트 초기값·추가 접근 시점을 고정해야 결과를 재현할 수 있습니다. 실제 시스템에서는 cold 시작과 반복 안정 부하를 나누고, 부하를 내린 뒤에도 재읽기·지연이 계속되는지 확인합니다.
더 많은 프로세스를 실행해 메모리 압박을 키우는 것이 처리량 개선이라고 가정하지 않습니다. 교체 정책은 제한된 메모리 안의 예측이며, 필요한 작업 집합을 담을 수 없는 지속 부하는 별도의 진입 제어·메모리·데이터 구조 개선이 필요합니다.