데이터베이스 인터널스 - Belady’s Anomaly

개요

데이터베이스 인터널스를 읽고 있다. 책에서 소개되는 개념 중에서 처음 알게 되거나 명확히 알지 못했던 개념들을 하나씩 정리해본다.

Belady’s Anomaly

페이지 교체 알고리즘

비유로 이해하기

컴퓨터의 메모리는 책상 서랍, 디스크는 사물함, 페이지는 책 한 권이라고 생각해보자.

학생은 서랍에 최대 3권의 책을 넣어둘 수 있다.

수업 중 선생님이 말한다.

• “영어책 꺼내자” - 사물함에서 가져온다. 페이지 부재
• “수학책 꺼내자” - 사물함에서 가져온다. 페이지 부재
• “과학책 꺼내자” - 사물함에서 가져온다. 페이지 부재
• “다시 영어책 꺼내자” - 서랍에 있으니 바로 꺼낼 수 있다.
• “미술책 꺼내자” - 서랍에 없으니 책 한권을 사물함에 넣어두고 가져와야 한다. 페이지 부재

이처럼 메모리에 없는 페이지를 디스크에서 불러오는 것을 **페이지 부재(Page Fault)**라고 한다.

왜 페이지 교체 알고리즘이 필요한가?

서랍의 공간이 한정되어 있으므로, 새로운 페이지(책)를 넣을 때 기존의 하나를 제거해야 한다.

이때 어떤 페이지를 제거할지를 결정하는 방식이 페이지 교체 알고리즘이다.

벨레이디 어노말리란?

헝가리 출신의 컴퓨터 과학자인 라슬로 “레스” 벨레이디(László “Les” Bélády)가 처음 발견하고 발표하였다.
메모리를 늘렸는데, 위의 비유로 보면 서랍에 최대 4권을 넣을 수 있도록 해줬는데 오히려 페이지 부재가 늘어나는 현상을 말한다. 성능이 좋아지겠거니 생각하는 직관과 달리 오히려 느려져서 이상현상(anomaly)이라 이름붙인 것이다.

벨레이디 어노말리 예시

조건

• 페이지 참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 페이지 교체 알고리즘: FIFO (First-In, First-Out)
• 프레임 수: 3개와 4개로 비교

프레임 수 3일 때 (FIFO)

참조 프레임 상태 (FIFO 순서) 페이지 부재 여부

1	1 _ _	발생
2	1 2 _	발생
3	1 2 3	발생
4	2 3 4	발생 (1 제거)
1	3 4 1	발생 (2 제거)
2	4 1 2	발생 (3 제거)
5	1 2 5	발생 (4 제거)
1	1 2 5	없음
2	1 2 5	없음
3	2 5 3	발생 (1 제거)
4	5 3 4	발생 (2 제거)
5	3 4 5	없음

총 페이지 부재: 9회

프레임 수 4일 때 (FIFO)

참조 프레임 상태 (FIFO 순서) 페이지 부재 여부

1	1 _ _ _	발생
2	1 2 _ _	발생
3	1 2 3 _	발생
4	1 2 3 4	발생
1	1 2 3 4	없음
2	1 2 3 4	없음
5	2 3 4 5	발생 (1 제거)
1	3 4 5 1	발생 (2 제거)
2	4 5 1 2	발생 (3 제거)
3	5 1 2 3	발생 (4 제거)
4	1 2 3 4	발생 (5 제거)
5	2 3 4 5	발생 (1 제거)

총 페이지 부재: 10회

이처럼 프레임 수를 늘렸는데도 페이지 부재 횟수가 늘어나는 현상이 바로 벨레이디 어노말리다. FIFO처럼 최근 사용 이력을 고려하지 않는 방식에서 발생할 수 있다.

해법

벨레이디 어노말리는 FIFO처럼 단순한 페이지 교체 알고리즘에서 발생하며, 이를 피하려면 스택 기반 알고리즘을 사용하는 것이 효과적이다. 대표적인 해법은 다음과 같다.

1. LRU (Least Recently Used): 가장 오래 사용하지 않은 페이지를 제거 → 최근 사용 이력을 고려함.
2. Optimal: 앞으로 가장 오랫동안 사용되지 않을 페이지를 제거 → 이론적으로 가장 효율적임.

이러한 알고리즘은 프레임 수가 늘어날수록 페이지 부재가 줄어들기 때문에, 벨레이디 어노말리가 발생하지 않는다.