페이지 교체 알고리즘: FIFO, LRU, LFU

책상이 꽉 찼을 때 뭐부터 버려야 할까

메모리 관리 공부하다가 처음엔 "페이지 교체 알고리즘이 뭐 그렇게 중요하냐"고 생각했습니다. RAM이 부족하면 디스크에서 가져오면 되는 거 아닌가? 근데 이게 정말 큰 착각이었습니다.

회사 다닐 때 사무실 책상을 생각해보면 와닿습니다. 책상(RAM)은 좁은데 프로젝트 서류가 산더미입니다. 지금 당장 필요한 서류만 책상에 올려놓고, 나머지는 캐비닛(HDD)에 넣어둡니다. 그런데 막상 버렸던 서류를 다시 꺼내는 일이 생기면 너무 짜증납니다. 캐비닛까지 왕복하는 시간이 아깝거든요.

OS도 똑같습니다. RAM은 한정적이고 프로그램이 요구하는 메모리 페이지는 많습니다. 새로운 페이지를 불러와야 하는데(Page Fault) 공간이 없으면 누군가는 희생되어야 합니다(Swap Out). "누굴 내보낼까?" 이게 바로 페이지 교체 알고리즘의 핵심입니다.

목표는 단순합니다. "쫓아냈는데 바로 다시 필요해지는 놈만 아니면 된다." 방금 버린 페이지를 또 불러오면 디스크 I/O가 발생해서 시스템이 멈춥니다. 이걸 최소화하는 게 전부입니다.

처음엔 뭐가 그렇게 복잡한가 싶었는데

대학 교재나 블로그를 보면 FIFO, LRU, LFU 같은 알고리즘들이 나열되어 있습니다. 근데 솔직히 첫 느낌은 "이게 다 뭐가 다른데?"였습니다. 어차피 안 쓰는 놈 버리면 되는 거 아닌가요?

특히 Belady's Anomaly라는 개념이 이해가 안 갔습니다. 책에서는 "FIFO는 메모리 프레임을 늘려줘도 Page Fault가 오히려 증가하는 역설적 현상이 있다"고 설명하는데, 이게 직관적으로 말이 안 됐습니다. 상식적으로 생각하면 책상이 넓어질수록(Frame 증가) 교체 횟수가 줄어야 정상 아닙니까?

그리고 LRU(Least Recently Used)가 "사실상 표준"이라는데, 왜 다른 알고리즘도 존재하는 건지 의문이었습니다. LRU가 그렇게 좋으면 다 LRU만 쓰면 되는 거 아닌가?

냉장고 비유에서 무릎을 쳤습니다

이해가 확 된 순간은 냉장고 비유를 접했을 때입니다.

냉장고(RAM)가 꽉 찼습니다. 새로운 재료를 넣으려면 뭔가를 버려야 합니다. 어떻게 할까요?

FIFO: 가장 오래 전에 산 음식 버리기

"먼저 들어온 놈부터 나간다."

로직은 단순합니다. 냉장고에 들어온 순서대로 큐(Queue)를 관리하고, 공간이 필요하면 맨 앞에 있는 놈을 버립니다. 구현이 쉬워서 좋습니다.

하지만 치명적인 문제가 있습니다. 냉장고에 2주 전 들어온 우유와 어제 들어온 케이크가 있다고 칩시다. FIFO는 무조건 우유를 먼저 버립니다. 그런데 어제 케이크는 한 번 봤고, 우유는 아침마다 먹는 필수품일 수 있습니다. 버렸는데 바로 다시 사러 가야 하는 상황이 생깁니다.

더 웃긴 건 Belady's Anomaly입니다. 냉장고를 더 크게 바꿨는데(Frame 증가) 오히려 마트 왕복 횟수(Page Fault)가 늘어나는 기이한 현상입니다. 이걸 직접 시뮬레이션 돌려보고 나서 이해했습니다.

def fifo_page_replacement(pages, frame_count):
    """FIFO 페이지 교체 시뮬레이션"""
    frames = []
    page_faults = 0

    for page in pages:
        if page not in frames:
            page_faults += 1
            if len(frames) < frame_count:
                frames.append(page)
            else:
                # 가장 오래된 페이지 제거 (Queue의 맨 앞)
                frames.pop(0)
                frames.append(page)

    return page_faults

# Belady's Anomaly 실험
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]

print(f"3 Frames: {fifo_page_replacement(pages, 3)} Page Faults")  # 9
print(f"4 Frames: {fifo_page_replacement(pages, 4)} Page Faults")  # 10 (더 많음!)

결과를 보고 충격받았습니다. 프레임이 3개일 때보다 4개일 때 Page Fault가 더 많이 발생했습니다. "공간을 늘렸는데 효율이 떨어진다고?" 이게 FIFO의 멍청함입니다.

LRU: 가장 오래 안 먹은 음식 버리기

"최근에 사용하지 않은 놈을 버리자."

이건 훨씬 합리적입니다. 냉장고에서 우유는 어제도 오늘도 먹었고, 케이크는 2주 동안 한 번도 안 먹었습니다. 그럼 케이크를 버리는 게 맞습니다. 시간 지역성(Temporal Locality) 원리입니다. 최근에 쓴 건 곧 또 쓸 확률이 높고, 오래 안 쓴 건 앞으로도 안 쓸 확률이 높다는 논리입니다.

실제 프로그램 동작 패턴이 이렇습니다. 반복문(loop)에서 같은 변수를 계속 참조하고, 함수 호출 스택에서 최근 함수일수록 다시 호출될 가능성이 큽니다. 그래서 LRU는 실제로 성능이 제일 좋습니다.

from collections import OrderedDict

def lru_page_replacement(pages, frame_count):
    """LRU 페이지 교체 시뮬레이션"""
    frames = OrderedDict()
    page_faults = 0

    for page in pages:
        if page not in frames:
            page_faults += 1
            if len(frames) >= frame_count:
                # 가장 오래 사용하지 않은 페이지 제거 (OrderedDict 맨 앞)
                frames.popitem(last=False)
            frames[page] = True
        else:
            # 이미 있으면 최근 사용으로 갱신
            frames.move_to_end(page)

    return page_faults

# 같은 테스트
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]

print(f"3 Frames (LRU): {lru_page_replacement(pages, 3)} Page Faults")  # 10
print(f"4 Frames (LRU): {lru_page_replacement(pages, 4)} Page Faults")  # 8 (정상 감소)

LRU는 프레임을 늘리면 정상적으로 Page Fault가 줄어듭니다. 상식적입니다.

하지만 단점은 비용입니다. 모든 페이지마다 "마지막 접근 시간"을 기록해야 합니다. 메모리 접근이 일어날 때마다 타임스탬프를 업데이트해야 하니 오버헤드가 큽니다. 서랍장에 음식 넣고 뺄 때마다 일일이 날짜 스티커를 붙이고 갱신하는 격입니다. 귀찮습니다.

LFU: 가장 횟수가 적은 음식 버리기

"가장 적게 먹은 음식을 버리자."

논리는 이렇습니다. 100번 먹은 우유와 1번 먹은 케이크가 있으면 케이크가 덜 중요한 음식 아닐까요? 그래서 참조 횟수(Frequency)를 기준으로 합니다.

근데 이게 불합리한 상황이 있습니다. 방금 막 냉장고에 넣은 신선한 재료는 참조 횟수가 0~1입니다. 예전에 100번 먹었지만 이제 상한 재료보다 참조 횟수가 적어서 바로 버려질 수 있습니다. "신입 페이지가 즉시 퇴출당하는 불합리함"입니다.

실제로는 LFU보다 LRU가 압도적으로 많이 쓰입니다. Redis나 캐싱 서버에서도 LRU 계열을 기본으로 합니다.

Clock 알고리즘 - LRU의 가성비 버전

여기서 또 깨달은 게 있습니다. "LRU가 좋긴 한데, 실제 하드웨어에서 구현하려면 너무 비싸다."

CPU는 메모리 접근할 때마다 타임스탬프 업데이트하기 싫어합니다. 그래서 실제 OS(Linux, Windows)는 Clock 알고리즘(Second-Chance Algorithm)이라는 꼼수를 씁니다.

Clock 알고리즘 작동 원리

냉장고 음식마다 스티커를 붙입니다. "최근 먹음: ✅" 또는 "안 먹음: ❌"

1. 시계 바늘처럼 뺑뺑 돌면서 음식을 체크합니다.
2. "최근 먹음(1)?" → "좋아, 이번엔 봐준다(0으로 바꿈)." 다음으로 넘어갑니다.
3. "안 먹음(0)?" → "너 나가." 즉시 제거합니다.

정확한 LRU는 아닙니다. 하지만 비슷하게 동작하고, 비용은 1/10입니다. 타임스탬프 업데이트 대신 1비트(Reference Bit) 플래그만 관리하면 됩니다.

def clock_algorithm(pages, frame_count):
    """Clock 알고리즘 시뮬레이션"""
    frames = [None] * frame_count
    reference_bits = [0] * frame_count
    pointer = 0
    page_faults = 0

    for page in pages:
        # 이미 존재하면 Reference Bit만 설정
        if page in frames:
            idx = frames.index(page)
            reference_bits[idx] = 1
            continue

        # Page Fault 발생
        page_faults += 1

        # 빈 공간이 있으면 바로 삽입
        if None in frames:
            idx = frames.index(None)
            frames[idx] = page
            reference_bits[idx] = 1
            continue

        # Clock 알고리즘: 희생자 찾기
        while True:
            if reference_bits[pointer] == 0:
                # Reference Bit가 0이면 교체
                frames[pointer] = page
                reference_bits[pointer] = 1
                pointer = (pointer + 1) % frame_count
                break
            else:
                # Reference Bit가 1이면 Second Chance (0으로 변경 후 넘어감)
                reference_bits[pointer] = 0
                pointer = (pointer + 1) % frame_count

    return page_faults

pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(f"Clock Algorithm: {clock_algorithm(pages, 3)} Page Faults")  # LRU와 비슷한 결과

Linux 커널에서 실제로 쓰는 방식이 이겁니다. 완벽하진 않지만 "가성비" 때문에 사실상 표준입니다.

Optimal Algorithm: 이론상 최선이지만 쓸 수 없는 알고리즘

공부하다 보니 Optimal Algorithm(Belady's Algorithm)이라는 게 나옵니다. 이론상 가장 적은 Page Fault를 보장하는 신의 알고리즘입니다.

"앞으로 가장 오래 사용되지 않을 페이지를 버린다."

미래를 보는 알고리즘입니다. 냉장고 음식 중에서 "이번 주에 절대 안 먹을 음식"을 정확히 알고 버립니다. 당연히 최적입니다.

하지만 치명적 결함이 있습니다. "미래를 어떻게 알아?"

프로그램이 앞으로 어떤 페이지를 참조할지 미리 알 수 있어야 합니다. 현실에선 불가능합니다. 그래서 Optimal Algorithm은 "벤치마크 용"으로만 씁니다. 다른 알고리즘의 성능을 평가할 때 "이론적 최댓값"과 비교하는 기준점입니다.

def optimal_algorithm(pages, frame_count):
    """Optimal 알고리즘 시뮬레이션 (미래를 안다는 가정)"""
    frames = []
    page_faults = 0

    for i, page in enumerate(pages):
        if page not in frames:
            page_faults += 1
            if len(frames) < frame_count:
                frames.append(page)
            else:
                # 미래를 보고 가장 늦게 사용될 페이지 찾기
                future_uses = {}
                for frame in frames:
                    try:
                        # 이 페이지가 앞으로 언제 다시 사용되는지 찾기
                        future_uses[frame] = pages[i+1:].index(frame)
                    except ValueError:
                        # 앞으로 사용 안 됨 = 무한대
                        future_uses[frame] = float('inf')

                # 가장 늦게 사용될 페이지 제거
                victim = max(future_uses, key=future_uses.get)
                frames[frames.index(victim)] = page

    return page_faults

pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(f"Optimal: {optimal_algorithm(pages, 3)} Page Faults")  # 가장 적은 결과

이 코드는 pages[i+1:]로 미래 참조를 미리 본다는 치팅을 합니다. 현실에선 불가능합니다. 하지만 이론상 최선이기 때문에 "우리 LRU가 Optimal 대비 90% 효율"이라는 식으로 비교할 때 씁니다.

Page Fault 과정 - 왜 이게 시스템을 멈추는가

페이지 교체가 왜 중요한지 이해하려면 Page Fault가 얼마나 느린지 알아야 합니다.

Page Fault 발생 시나리오

1. CPU가 특정 가상 주소에 접근 시도
2. MMU(Memory Management Unit)가 페이지 테이블 확인
3. "이 페이지가 RAM에 없습니다(Present Bit = 0)"
4. Page Fault Interrupt 발생 → CPU가 하던 일 멈춤
5. OS가 디스크에서 페이지를 찾아서 RAM에 로드
6. 근데 RAM이 꽉 참 → 교체 알고리즘 실행
7. 희생자 페이지를 디스크에 저장(Dirty Bit가 1이면)
8. 새 페이지를 RAM에 적재
9. 페이지 테이블 업데이트
10. CPU가 다시 명령어 실행

이 과정이 밀리초 단위입니다. 메모리 접근(나노초)보다 100만 배 느립니다. 그래서 Page Fault를 최소화하는 게 성능의 핵심입니다.

적용 - Redis Eviction Policy와의 연결

제가 서비스를 운영하면서 처음 Redis를 도입할 때 설정 파일에 maxmemory-policy라는 옵션이 있었습니다. 옵션 목록을 보니 allkeys-lru, allkeys-lfu 같은 값들이 있었습니다.

"왜 LRU랑 LFU가 여기 나오지?" 싶었는데, 알고 보니 페이지 교체 알고리즘과 똑같은 로직이었습니다.

Redis도 메모리가 꽉 차면 누군가를 내보내야 합니다. 이때 어떤 Key를 지울지 결정하는 게 Eviction Policy입니다.

Redis Eviction Policy 종류

Policy	설명	페이지 교체 대응
allkeys-lru	모든 Key 중 가장 오래 사용 안 한 것 제거	LRU
allkeys-lfu	모든 Key 중 가장 적게 사용한 것 제거	LFU
volatile-lru	TTL 있는 Key 중 LRU 제거	LRU (조건부)
allkeys-random	랜덤 제거	FIFO 비슷

결국 이거였습니다. "캐시도 페이지도 한정된 공간에서 최적의 희생자를 고르는 문제"라는 본질은 같았습니다.

실제로는 allkeys-lru를 주로 씁니다. 이유는 페이지 교체 알고리즘과 동일합니다. 시간 지역성이 실제 워크로드와 잘 맞아떨어지기 때문입니다.

Linux는 어떻게 구현했을까

리눅스 커널 코드를 살펴보니 페이지 교체는 Two-List Strategy (Active/Inactive List)를 씁니다. Clock 알고리즘의 변형입니다.

리눅스 페이지 교체 전략

1. Active List: 최근 참조된 "뜨거운(hot)" 페이지들
2. Inactive List: 참조가 뜸한 "차가운(cold)" 페이지들

페이지가 참조되면 Active List로 올라가고, 시간이 지나면 Inactive List로 내려옵니다. 교체 대상은 Inactive List에서 고릅니다.

Reference Bit 하나로 관리하는 단순 Clock보다 정교합니다. "Second Chance"가 아니라 "Multiple Chance"를 주는 셈입니다. 자주 쓰는 페이지는 Active List에 계속 살아남고, 진짜 안 쓰는 페이지만 Inactive로 떨어져서 희생됩니다.

// 리눅스 커널 간략 의사코드
struct page {
    unsigned long flags;  // PG_active, PG_referenced 등
    // ...
};

// 페이지 접근 시
mark_page_accessed(page) {
    if (PageReferenced(page)) {
        // 이미 Referenced였으면 Active로 승급
        activate_page(page);
    } else {
        // 첫 참조는 Referenced만 마킹
        SetPageReferenced(page);
    }
}

// 교체 대상 선정 (Inactive List에서)
shrink_inactive_list() {
    for_each_page_in_inactive_list(page) {
        if (PageReferenced(page)) {
            // Second Chance
            ClearPageReferenced(page);
            continue;
        }
        // Referenced가 0이면 희생자
        evict_page(page);
    }
}

이 구조 덕분에 리눅스는 LRU에 가까운 성능을 내면서도 오버헤드를 최소화합니다.

Thrashing: 교체 알고리즘도 못 막는 지옥

페이지 교체 알고리즘을 아무리 잘 짜도 Thrashing(스래싱)이 오면 시스템이 죽습니다.

Thrashing은 "Page Fault가 너무 자주 발생해서 실제 작업보다 페이지 교체에 더 많은 시간을 쓰는 상태"입니다. RAM이 프로세스 작업 세트(Working Set)보다 작을 때 발생합니다.

냉장고 비유로 보면 이렇습니다. 오늘 저녁 요리에 필요한 재료가 10가지인데, 냉장고엔 5개밖에 못 들어갑니다. 재료 꺼내고 → 다른 재료 넣고 → 방금 넣은 재료 또 필요해서 꺼내고 → 무한 반복. 요리는 안 되고 마트 왕복만 합니다.

해결책은 단순합니다. "RAM을 늘리거나, 프로세스 수를 줄인다." 교체 알고리즘 개선으로는 못 막습니다. 근본적으로 메모리가 부족하기 때문입니다.

정리하면서 든 생각

페이지 교체 알고리즘을 공부하면서 깨달은 건 "완벽한 알고리즘은 없다"는 사실입니다.

• FIFO: 구현은 쉽지만 Belady's Anomaly 때문에 멍청합니다.
• Optimal: 완벽하지만 미래를 볼 수 없어서 쓸 수 없습니다.
• LRU: 성능은 좋지만 비용이 비쌉니다.
• Clock: 가성비가 좋아서 실제로 많이 씁니다.

결국 실제로는 "적당히 좋고, 싸게 구현 가능한" Clock/LRU 변형을 씁니다. 이론상 최선보다는 현실적 차선을 택하는 겁니다.

그리고 Redis나 캐시 서버를 설계할 때도 이 원리가 그대로 적용된다는 걸 이해하니, OS 공부가 실제와 동떨어진 게 아니라는 확신이 들었습니다. 결국 한정된 자원에서 무엇을 희생할 것인가라는 본질은 같았습니다.

다음엔 Working Set과 Thrashing을 깊이 파봐야겠습니다. RAM이 부족할 때 어떻게 프로세스 개수를 조절할지도 궁금해졌습니다.