벨라디의 이상현상: FIFO에서 프레임을 늘렸는데 page fault가 증가하는 이유

가상 메모리의 page frame을 늘리면 보통 page fault가 줄어들 것이라고 예상한다. 그러나 FIFO 같은 일부 교체 정책에서는 같은 page reference string에 프레임을 더 줬는데도 fault가 늘어날 수 있다. 이를 벨라디의 이상현상(Belady's anomaly)이라고 한다.

기존 글은 이 현상을 설명하면서 정작 예제 계산이 틀려 3개 프레임에서 12회, 4개 프레임에서 10회라고 적었다. 올바르게 계산하면 3개일 때 9회, 4개일 때 10회다. 프레임을 늘렸는데 fault가 하나 증가하므로 이 reference string이 바로 이상현상의 예가 된다.

먼저 용어를 맞춘다

• page: 프로세스의 가상 주소 공간을 일정 크기로 나눈 단위
• page frame: 물리 메모리에서 page 하나를 담는 공간
• page fault: 참조한 page가 현재 물리 메모리에 없어 운영체제가 처리해야 하는 사건
• replacement policy: 빈 frame이 없을 때 어느 page를 내보낼지 고르는 규칙
• reference string: 시간 순서대로 참조한 page 번호의 나열

FIFO(First-In, First-Out)는 메모리에 가장 먼저 들어온 page를 먼저 내보낸다. 최근에 자주 쓴 page인지 여부는 고려하지 않는다.

고전적인 reference string

다음 순서를 FIFO로 처리해 보자.

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

표의 frame은 왼쪽이 가장 오래된 page, 오른쪽이 가장 최근에 들어온 page다. hit에서는 FIFO 순서가 바뀌지 않는다.

프레임이 3개일 때: fault 9회

요청	FIFO queue	결과	누적 fault
1	[1]	fault	1
2	[1, 2]	fault	2
3	[1, 2, 3]	fault	3
4	[2, 3, 4]	fault, 1 교체	4
1	[3, 4, 1]	fault, 2 교체	5
2	[4, 1, 2]	fault, 3 교체	6
5	[1, 2, 5]	fault, 4 교체	7
1	[1, 2, 5]	hit	7
2	[1, 2, 5]	hit	7
3	[2, 5, 3]	fault, 1 교체	8
4	[5, 3, 4]	fault, 2 교체	9
5	[5, 3, 4]	hit	9

중간의 1, 2, 마지막 5가 hit이므로 모든 요청이 fault라는 계산은 잘못이다.

프레임이 4개일 때: fault 10회

요청	FIFO queue	결과	누적 fault
1	[1]	fault	1
2	[1, 2]	fault	2
3	[1, 2, 3]	fault	3
4	[1, 2, 3, 4]	fault	4
1	[1, 2, 3, 4]	hit	4
2	[1, 2, 3, 4]	hit	4
5	[2, 3, 4, 5]	fault, 1 교체	5
1	[3, 4, 5, 1]	fault, 2 교체	6
2	[4, 5, 1, 2]	fault, 3 교체	7
3	[5, 1, 2, 3]	fault, 4 교체	8
4	[1, 2, 3, 4]	fault, 5 교체	9
5	[2, 3, 4, 5]	fault, 1 교체	10

결과를 한 줄로 놓으면 이상현상이 선명해진다.

FIFO, 같은 reference string
3 frames → 9 faults
4 frames → 10 faults

왜 프레임 하나가 늘었는데 결과가 나빠질까

FIFO의 상태는 단순히 “현재 어떤 page가 들어 있는가”만으로 결정되지 않는다. 어느 page가 먼저 들어왔는지라는 queue 순서도 다음 교체를 결정한다. 프레임 수가 달라지면 초기 hit와 교체 시점이 달라지고, 이후 queue 순서가 전혀 다른 궤적으로 진행될 수 있다.

3개 프레임에서는 요청 5 뒤에 [1, 2, 5]가 남아 다음 1, 2를 연속 hit한다. 4개 프레임에서는 같은 지점에 [2, 3, 4, 5]가 남아 이후 1, 2, 3, 4, 5가 연달아 서로를 밀어낸다. 더 큰 메모리가 미래에 유용한 page를 포함한다는 보장이 없기 때문이다.

벨라디, 넬슨, 셰들러는 1969년 논문 An anomaly in space-time characteristics of certain programs running in a paging machine에서 이 현상을 다루고 FIFO에 대한 형식적 분석을 제시했다.

LRU와 OPT에서는 왜 이 현상이 생기지 않을까

LRU와 OPT는 stack property를 갖는 정책이다. 같은 reference string을 처리할 때 n개 frame의 resident set이 n+1개 frame의 resident set에 포함된다.

resident_set(n) ⊆ resident_set(n + 1)

작은 메모리에서 hit한 page는 더 큰 메모리에도 들어 있으므로, frame을 늘렸을 때 fault가 증가할 수 없다. LRU는 가장 오래 참조되지 않은 page를 내보내고, OPT는 미래에 가장 늦게 다시 쓰일 page를 내보낸다. OPT는 미래를 알아야 하므로 실제 구현 정책이라기보다 비교 기준으로 사용한다.

반대로 FIFO와 Random은 일반적으로 이 포함 관계를 보장하지 않는다. 그래서 특정 reference string에서 이상현상이 가능하다. OSTEP의 Beyond Physical Memory: Policies도 같은 12개 reference string으로 FIFO와 stack property의 차이를 설명한다.

“메모리를 늘려도 느려진다”로 일반화하면 안 된다

벨라디의 이상현상은 특정 교체 정책과 reference string에서 page fault 수가 증가할 수 있다는 이론적 성질이다. 다음 문장으로 확대하면 부정확하다.

• RAM을 추가하면 시스템 성능이 전반적으로 나빠진다.
• 실제 운영체제는 순수 FIFO 하나로 모든 page를 교체한다.
• frame 수만 알면 애플리케이션 latency를 예측할 수 있다.

현대 운영체제의 reclaim은 active/inactive 목록, 접근 정보, dirty page, file-backed·anonymous page, cgroup 압력 등 훨씬 많은 조건을 다룬다. 실제 성능 문제에서는 major/minor fault, reclaim, swap I/O, working set, 메모리 압력을 함께 관측해야 한다.

페이지 교체 알고리즘 정리에서는 FIFO·LRU·OPT의 선택 기준을, 메모리 계층과 가상 메모리에서는 page fault가 저장장치 접근과 연결되는 과정을 이어서 볼 수 있다.

직접 검산하는 짧은 코드

표가 길어질수록 손으로 계산한 결과를 한 번 더 검산하는 편이 좋다.

from collections import deque


def fifo_faults(references, capacity):
    frames = set()
    queue = deque()
    faults = 0

    for page in references:
        if page in frames:
            continue

        faults += 1
        if len(frames) == capacity:
            victim = queue.popleft()
            frames.remove(victim)

        frames.add(page)
        queue.append(page)

    return faults


refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(fifo_faults(refs, 3))  # 9
print(fifo_faults(refs, 4))  # 10

이 예제가 주는 교훈은 “자원은 많을수록 무조건 좋다”의 반대도 아니다. 정책이 monotonic한 성질을 보장하는지, 그리고 측정한 지표가 정말 개선하려는 결과와 연결되는지를 확인해야 한다는 점이다.

참고 자료

• IBM Research: An anomaly in space-time characteristics of certain programs running in a paging machine
• OSTEP: Beyond Physical Memory — Policies