FIFO 페이지 교체에서 메모리 증설이 역효과를 내는 이유
FIFO 페이지 교체 알고리즘에서 프레임을 늘렸는데도 페이지 폴트가 증가하는 Belady's Anomaly의 원인과 대응 방식을 정리한다.
2026-08-14 · 최초 발행 2025-12-28
프레임을 늘렸는데 페이지 폴트가 늘어나는 경우
페이지 프레임 수가 많아지면 페이지 폴트는 줄어들 것처럼 보인다. 그러나 FIFO 페이지 교체 알고리즘에서는 프레임을 추가한 뒤 오히려 폴트가 늘어나는 경우가 있다. Laszlo Belady가 1969년에 발견한 Belady's Anomaly는 자원을 늘리는 일만으로 성능 개선을 보장할 수 없다는 사실을 보여준다.
가상 메모리 시스템 연구가 활발하던 1960년대에는 구현이 단순한 FIFO가 널리 쓰였다. 이 현상은 메모리 증가가 언제나 성능 향상으로 이어진다는 가정을 깨뜨렸고, 페이지 교체 알고리즘 연구의 방향에도 영향을 주었다.
FIFO는 적재 순서만 기준으로 페이지를 내보낸다
FIFO(First-In, First-Out)는 가장 먼저 메모리에 들어온 페이지를 먼저 교체한다. 일반적으로 큐 자료구조로 구현하므로 단순하고 오버헤드가 낮지만, 페이지가 얼마나 자주 사용되는지는 고려하지 않는다.
페이지 요청이 들어오면 메모리 존재 여부를 확인한다. 없으면 페이지 폴트가 발생하고, 메모리가 가득 찼다면 가장 오래 전에 적재된 페이지를 제거한 뒤 새 페이지를 넣고 큐를 갱신한다.
이 방식에서는 자주 쓰이는 페이지라도 오래 메모리에 있었다는 이유만으로 교체될 수 있다. 프로그램 초기 설정에 필요했던 페이지가 계속 참조되더라도 먼저 적재됐다는 사실이 교체 순서를 결정한다. 곧 다시 사용할 페이지를 내보내는 선택도 가능하다.
같은 참조 문자열에서 달라지는 결과
다음 참조 문자열을 FIFO로 처리해 보자.
A, B, C, D, A, B, E, A, B, C, D, E프레임이 3개일 때의 페이지 상태는 다음과 같다.
| 참조 | Frame 1 | Frame 2 | Frame 3 | 폴트 |
|---|---|---|---|---|
| A | A | - | - | F |
| B | A | B | - | F |
| C | A | B | C | F |
| D | D | B | C | F |
| A | D | A | C | F |
| B | D | A | B | F |
| E | E | A | B | F |
| A | E | A | B | - |
| B | E | A | B | - |
| C | E | C | B | F |
| D | E | C | D | F |
| E | E | C | D | - |
이 경우 총 페이지 폴트는 9회다.
프레임을 4개로 늘리면 결과는 다음처럼 바뀐다.
| 참조 | Frame 1 | Frame 2 | Frame 3 | Frame 4 | 폴트 |
|---|---|---|---|---|---|
| A | A | - | - | - | F |
| B | A | B | - | - | F |
| C | A | B | C | - | F |
| D | A | B | C | D | F |
| A | A | B | C | D | - |
| B | A | B | C | D | - |
| E | E | B | C | D | F |
| A | E | A | C | D | F |
| B | E | A | B | D | F |
| C | E | A | B | C | F |
| D | D | A | B | C | F |
| E | D | E | B | C | F |
총 페이지 폴트는 10회다. 프레임 3개에서는 9회였지만, 프레임 4개에서는 10회가 발생한다. 메모리가 33% 증가했는데 페이지 폴트는 11% 증가한 결과다.
포함 속성이 깨지는 FIFO의 교체 패턴
프레임이 3개인 환경에서는 공간이 제한돼 페이지가 빠르게 순환한다. 이 순환이 특정 참조 문자열에서는 우연히 효율적인 교체 순서를 만든다. 반대로 프레임이 4개이면 더 많은 페이지를 보유하는 동안 교체 시점이 달라지고, 비효율적인 페이지가 오래 남을 수 있다.
스택 알고리즘은 n 프레임에서 메모리에 있는 페이지 집합이 n+1 프레임의 집합에 포함되는 포함 속성을 만족한다. FIFO는 이 성질을 보장하지 않는다. 더 큰 메모리 집합이 더 작은 메모리 집합에 있던 필요한 페이지를 포함하지 못하는 상황이 생길 수 있고, 이것이 이상현상의 직접적인 원인이다.
FIFO는 페이지의 나이만 보고 미래 참조 패턴을 예측하지 않는다. 따라서 참조 문자열의 순서와 타이밍이 결과에 크게 작용한다. 이 현상은 모든 참조 문자열에서 나타나는 것은 아니지만, 특정 워크로드에서는 뚜렷하게 관찰될 수 있다.
스택 알고리즘과 프레임별 페이지 집합
스택 알고리즘은 다음 조건을 만족한다.
M_n(t) ⊆ M_{n+1}(t) for all t여기서 M_n(t)는 n 프레임에서 시간 t의 페이지 집합이다. LRU와 OPT는 이 성질을 만족하므로 Belady's Anomaly가 발생하지 않는다. FIFO는 이 조건을 만족하지 않는 알고리즘이다.
참조 문자열이 길어질수록, 고유 페이지 수와 프레임 수의 관계가 복잡해질수록 이상현상이 나타날 가능성도 커진다. 특히 순환적 참조 패턴은 FIFO의 순서 의존성을 드러내기 쉽다.
메모리 증설 전에 확인할 운영 조건
FIFO를 사용하는 환경에서는 메모리를 늘린다고 성능이 항상 개선되는 것은 아니다. 실제 워크로드를 대상으로 여러 메모리 크기에서 테스트하고, 페이지 교체 알고리즘까지 함께 평가해야 한다.
데이터베이스 시스템에서는 FIFO 기반 버퍼 관리를 사용한 뒤 버퍼 풀 크기를 키웠을 때 성능 저하가 관찰될 수 있다. 원본 사례에서는 LRU로 변경한 뒤 문제가 해결됐다. 운영체제 페이징에서도 특정 워크로드에서 메모리 증설 효과가 없고 Belady's Anomaly가 확인될 수 있으며, 이때 적응적 알고리즘을 도입하는 접근이 가능하다.
회피 방법으로는 LRU, OPT, Clock Algorithm을 고려할 수 있다. FIFO에 참조 비트를 더하는 Second Chance, 사용 빈도를 추적하는 방식, 워크로드에 맞춰 프레임을 동적으로 할당하는 방식도 선택지다. 페이지 폴트 비율을 추적하고 메모리 크기별 실험과 워크로드 변화 감지를 운영 지표로 삼을 수 있다.
FIFO와 LRU에서 확인되는 차이
동일한 참조 문자열을 기준으로 FIFO와 LRU의 페이지 폴트를 비교하면 다음과 같다.
| 프레임 수 | FIFO 폴트 | LRU 폴트 |
|---|---|---|
| 2 | 11 | 11 |
| 3 | 9 | 10 |
| 4 | 10 | 8 |
| 5 | 8 | 7 |
LRU는 프레임이 증가할 때 페이지 폴트가 감소하거나 동일하게 유지된다. FIFO에서는 이러한 일관성을 기대할 수 없다.
알고리즘을 선택할 때는 Optimal, LRU, Clock, Second Chance FIFO, FIFO 순으로 검토할 수 있다. Optimal은 이론적 최선이지만 구현할 수 없고, LRU는 오버헤드가 있다. Clock은 LRU의 근사 방식이며, Second Chance FIFO는 FIFO를 개선한 접근이다.
자원 확대와 알고리즘 선택은 별개의 문제다
Belady's Anomaly는 자원이 늘면 성능도 좋아진다는 단순한 가정의 한계를 드러낸다. 이 발견은 스택 알고리즘이라는 분류를 확립하는 데 기여했고, 스택 거리 분석, 작업 집합 모델, 워크로드에 맞춘 적응적 알고리즘 연구로 이어졌다.
메모리 시스템을 설계하거나 조정할 때는 증설 자체보다 교체 알고리즘과 참조 패턴을 함께 봐야 한다. FIFO의 단순성은 장점이지만, 포함 속성을 보장하지 않는다는 특성은 성능 검증이 필요한 이유가 된다.