페이지 교체 알고리즘: FIFO·LRU·OPT와 Belady anomaly

페이지 교체 알고리즘은 page fault가 발생했는데 사용할 수 있는 frame이 없을 때 어떤 page를 내보낼지 정한다. 애플리케이션 cache의 key eviction과 아이디어는 닮았지만, 운영체제의 page reclaim에는 dirty page, file-backed·anonymous memory, swap, cgroup, NUMA와 I/O 비용까지 개입한다. 교과서 알고리즘을 곧바로 Linux의 실제 구현이라고 받아들이면 안 되는 이유다.

기준이 되는 세 알고리즘

**FIFO(First-In, First-Out)**는 가장 먼저 들어온 page를 먼저 내보낸다. 도착 순서만 관리하므로 단순하지만, 최근에도 자주 쓰이는 page를 내보낼 수 있다. frame 수를 늘렸는데 오히려 page fault가 증가하는 Belady anomaly가 발생할 수 있다.

**LRU(Least Recently Used)**는 가장 오랫동안 참조되지 않은 page를 내보낸다. temporal locality를 반영하지만 모든 memory reference의 정확한 순서를 유지하려면 비용이 크다. 실제 운영체제는 accessed bit, generation, working set 같은 정보를 이용한 근사와 feedback을 사용한다.

OPT 또는 MIN은 앞으로 가장 늦게 참조될 page를 내보낸다. 미래 reference를 알아야 하므로 online system에서 그대로 구현할 수 없다. 대신 같은 reference string과 frame 수에서 다른 알고리즘의 fault 수가 최적 기준에서 얼마나 떨어지는지 비교하는 baseline이 된다.

LFU는 누적 참조 횟수가 낮은 page를, MRU는 가장 최근에 사용한 page를, Random은 무작위 page를 고른다. LFU에는 오래된 인기도가 계속 남는 문제와 tie-breaking이 있고, MRU는 특정 scan pattern에서만 유리할 수 있다. workload와 상태 관리 비용을 빼고 어느 하나가 항상 우수하다고 말할 수는 없다.

Belady anomaly를 직접 확인하기

고전적인 reference string은 다음과 같다.

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

FIFO로 실행하면 frame 3개에서 fault가 9번, frame 4개에서 10번 발생한다. memory를 더 줬는데 fault가 하나 늘었다. 다음 simulator로 교체 과정을 같은 조건에서 비교할 수 있다.

from collections import deque


def page_faults(reference, frame_count, policy):
    frames = []
    fifo = deque()
    last_used = {}
    faults = 0

    for index, page in enumerate(reference):
        if page in frames:
            last_used[page] = index
            continue

        faults += 1
        if len(frames) < frame_count:
            frames.append(page)
            fifo.append(page)
        elif policy == "FIFO":
            victim = fifo.popleft()
            frames[frames.index(victim)] = page
            fifo.append(page)
        elif policy == "LRU":
            victim = min(frames, key=lambda item: last_used[item])
            frames[frames.index(victim)] = page
        elif policy == "OPT":
            future = reference[index + 1 :]

            def next_use(item):
                return future.index(item) if item in future else float("inf")

            victim = max(frames, key=next_use)
            frames[frames.index(victim)] = page
        else:
            raise ValueError(f"unknown policy: {policy}")

        last_used[page] = index

    return faults


reference = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for policy in ("FIFO", "LRU", "OPT"):
    print(policy, page_faults(reference, 3, policy), page_faults(reference, 4, policy))

실행 결과는 다음과 같다.

FIFO 9 10
LRU 10 8
OPT 7 6

이 코드는 알고리즘 차이를 보기 위한 simulator다. Python process의 실제 virtual memory page를 교체하거나 kernel reclaim 정책을 구현하는 코드는 아니다.

stack algorithm은 왜 anomaly가 없는가

같은 reference string을 처리할 때 frame이 n개인 resident set이 매 시점 frame n+1개의 resident set에 포함된다면 stack property를 만족한다고 말한다. LRU와 OPT는 이 성질을 만족하는 대표적인 stack algorithm이다. frame을 하나 늘렸을 때 기존에 있던 page가 그 이유만으로 사라지지 않으므로 fault 수가 증가하지 않는다.

FIFO는 도착 순서와 queue 길이가 바뀌면서 두 resident set의 포함 관계가 깨질 수 있다. 그래서 위 예제처럼 anomaly가 가능하다. ‘최근 사용 정보를 대충 반영한다’는 사실만으로 stack property가 생기는 것은 아니다. 근사 LRU 구현은 별도로 그 성질을 확인해야 한다.

실제 운영체제와 연결할 때의 경계

Linux의 page reclaim을 ‘LRU 하나’로 요약하면 실제 결정을 놓친다. reclaim 대상에는 anonymous와 file page가 있고, dirty page writeback과 swap 가능 여부, memory cgroup 보호, refault 관찰 등이 영향을 준다. Multi-Gen LRU도 page를 access recency가 비슷한 generation으로 나누고 aging과 eviction feedback을 운영하는 구현이지, 교과서의 exact LRU queue를 그대로 만든 것이 아니다.

운영체제 문제를 볼 때는 다음 질문이 더 유용하다.

• workload의 working set이 가용 memory보다 큰가
• major fault와 storage I/O가 실제 latency를 만들고 있는가
• file cache와 anonymous memory 중 무엇이 pressure를 받는가
• 짧은 spike인지 지속적인 reclaim·thrashing인지
• container나 cgroup limit이 host memory보다 먼저 걸리는가

메모리 계층 전체와 page fault의 관계는 메모리 계층과 가상 메모리, process별 mapping과 RSS 해석은 프로세스 메모리 구조에서 이어서 볼 수 있다.

참고 자료

• OSTEP: Beyond Physical Memory, Policies
• IBM Research: Efficient stack distance computation for priority replacement policies
• Linux kernel: Page reclaim
• Linux kernel: Multi-Gen LRU