페이지 교체 알고리즘

물리 메모리가 부족할 때 어떤 페이지를 내보낼지 결정하는 것은 가상 메모리 성능의 핵심입니다. 잘못된 선택은 곧바로 페이지 폴트 증가로 이어지고, 극단적으로는 시스템 전체가 디스크 I/O에 매몰되어 멈추는 스래싱으로 이어집니다.

평가 기준

페이지 교체 알고리즘의 성능은 참조 문자열(Reference String)에 대한 페이지 폴트 횟수로 측정합니다. 참조 문자열은 프로세스가 접근하는 페이지 번호의 시퀀스입니다.

예: 참조 문자열 [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1], 프레임 수 3.

일반적으로 프레임 수가 많을수록 페이지 폴트가 줄어듭니다(단, FIFO는 예외).

FIFO 알고리즘

FIFO(First-In, First-Out)는 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보냅니다. 큐로 간단하게 구현할 수 있습니다.

from collections import deque

def fifo_simulate(pages, num_frames):
    frames = deque(maxlen=num_frames)
    frame_set = set()
    page_faults = 0

    for page in pages:
        if page not in frame_set:
            page_faults += 1
            if len(frames) == num_frames:
                evicted = frames.popleft()
                frame_set.discard(evicted)
            frames.append(page)
            frame_set.add(page)

    return page_faults

pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
print(f"FIFO 페이지 폴트 (3프레임): {fifo_simulate(pages, 3)}")  # 15
print(f"FIFO 페이지 폴트 (4프레임): {fifo_simulate(pages, 4)}")  # 10

Belady의 모순 (Belady's Anomaly)

FIFO에는 기이한 현상이 있습니다. 프레임 수를 늘렸는데 오히려 페이지 폴트가 증가하는 경우가 발생합니다.

참조 문자열 [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]에서:

• 3프레임: 9번 폴트
• 4프레임: 10번 폴트 (프레임을 늘렸는데 폴트 증가!)

직관에 완전히 어긋나는 결과입니다. 이 문제 때문에 FIFO는 실무에서 거의 사용되지 않습니다.

최적 (OPT) 알고리즘

OPT(Optimal) 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 내보냅니다. 모든 교체 알고리즘 중 페이지 폴트가 가장 적습니다. Belady의 모순도 발생하지 않습니다.

하지만 미래의 접근 패턴을 알아야 하므로 실제로 구현할 수 없습니다. 다른 알고리즘의 성능을 비교하는 이론적 기준선(Baseline)으로만 사용됩니다.

def opt_simulate(pages, num_frames):
    frames = []
    page_faults = 0

    for i, page in enumerate(pages):
        if page not in frames:
            page_faults += 1
            if len(frames) == num_frames:
                # 앞으로 가장 늦게 사용될 페이지를 교체
                farthest = -1
                victim = 0
                for j, f in enumerate(frames):
                    try:
                        next_use = pages[i+1:].index(f)
                    except ValueError:
                        next_use = float('inf')  # 다시 사용 안 됨
                    if next_use > farthest:
                        farthest = next_use
                        victim = j
                frames[victim] = page
            else:
                frames.append(page)

    return page_faults

pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
print(f"OPT 페이지 폴트 (3프레임): {opt_simulate(pages, 3)}")  # 9

LRU 알고리즘

LRU(Least Recently Used)는 가장 오래 전에 사용된 페이지를 내보냅니다. 과거의 접근 패턴으로 미래를 예측합니다. "최근에 사용되지 않았으면 앞으로도 사용되지 않을 가능성이 높다"는 지역성 원리에 기반합니다.

LRU는 OPT에 가까운 성능을 보여주고, Belady의 모순도 발생하지 않습니다(스택 알고리즘이기 때문).

def lru_simulate(pages, num_frames):
    frames = []
    page_faults = 0

    for page in pages:
        if page in frames:
            frames.remove(page)
            frames.append(page)  # 가장 최근 사용으로 이동
        else:
            page_faults += 1
            if len(frames) >= num_frames:
                frames.pop(0)   # 가장 오래된 것 제거
            frames.append(page)

    return page_faults

pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
print(f"LRU 페이지 폴트 (3프레임): {lru_simulate(pages, 3)}")  # 12

LRU 구현의 어려움

완벽한 LRU는 모든 메모리 접근마다 순서 정보를 갱신해야 합니다.

타임스탬프 방식: 각 페이지 접근 시 현재 시각을 기록합니다. 교체 시 가장 작은 타임스탬프를 찾습니다. 모든 접근마다 메모리 쓰기가 필요하고, 교체 시 전체 탐색이 필요합니다.

스택(더블 링크드 리스트) 방식: 접근된 페이지를 리스트의 끝으로 옮깁니다. 교체 시 리스트 앞(가장 오래된)을 제거합니다. 리스트 갱신에 6개의 포인터 변경이 필요합니다.

하드웨어 지원 없이는 오버헤드가 크기 때문에, 실무에서는 LRU를 근사(Approximation)합니다.

근사 LRU: Clock 알고리즘 (Second Chance)

하드웨어가 제공하는 참조 비트(Reference Bit)를 활용합니다. 페이지가 접근되면 하드웨어가 참조 비트를 자동으로 1로 설정합니다. 이것은 추가 소프트웨어 오버헤드 없이 수행됩니다.

동작 방식

프레임들을 원형 리스트로 배열하고, 시계 바늘 포인터가 순회합니다.

1. 교체가 필요하면 포인터 위치의 페이지를 확인합니다.
2. 참조 비트 = 0이면: 이 페이지를 교체합니다.
3. 참조 비트 = 1이면: 0으로 바꾸고(두 번째 기회 부여), 다음 페이지로 이동합니다.
4. 모든 페이지가 참조 비트 1이면, 한 바퀴 돌면서 전부 0으로 바꾼 후 처음 만나는 페이지를 교체합니다.

최근에 접근된 페이지는 참조 비트가 1이므로 교체되지 않습니다. LRU의 근사입니다.

Enhanced Clock (수정된 시계 알고리즘)

참조 비트(R)와 더티 비트(M)를 함께 고려하여 4가지 클래스로 분류합니다.

클래스 0부터 찾아서 교체하면, 디스크 I/O(dirty page write back)를 최소화하면서 LRU를 근사합니다.

LFU 알고리즘

LFU(Least Frequently Used)는 사용 횟수가 가장 적은 페이지를 내보냅니다. 자주 사용된 페이지는 앞으로도 사용될 가능성이 높다는 가정입니다.

단점: 과거에 많이 사용되었지만 더 이상 사용되지 않는 페이지가 높은 카운트 때문에 오래 남습니다. 해결법으로 감쇠(Aging) 기법을 사용합니다 — 카운터를 주기적으로 오른쪽 시프트하여 오래된 접근의 가중치를 줄입니다.

반대로 MFU(Most Frequently Used)는 가장 많이 사용된 페이지를 내보냅니다. 적게 사용된 페이지는 방금 들어와서 아직 사용이 적은 것이라는 논리입니다. 실제로는 LFU, MFU 모두 OPT에 크게 근접하지 못합니다.

알고리즘 비교

스래싱 (Thrashing)

페이지 폴트가 극단적으로 많아져서 프로세스가 실제 작업보다 페이지 교체에 더 많은 시간을 쓰는 현상을 스래싱이라고 합니다.

발생 메커니즘

1. 물리 메모리에 비해 동시 실행 프로세스가 너무 많습니다.
2. 각 프로세스의 워킹 셋 합계가 물리 메모리를 초과합니다.
3. 모든 프로세스가 끊임없이 페이지 폴트를 일으킵니다.
4. CPU 이용률이 급락합니다 (I/O 대기 시간만 증가).
5. OS의 스케줄러는 CPU 이용률이 낮으니 더 많은 프로세스를 실행하자고 판단합니다.
6. 멀티프로그래밍 차수를 높이면 상황이 더 악화됩니다.
7. 악순환으로 시스템이 거의 멈춥니다.

워킹 셋 모델

워킹 셋(Working Set)은 시간 간격 $\Delta$ 동안 프로세스가 접근하는 페이지의 집합입니다.

$\Delta$가 너무 작으면 워킹 셋이 지역성을 반영하지 못합니다. 너무 크면 전체 프로그램을 포함합니다. 적절한 $\Delta$를 선택하면 프로세스의 활발한 메모리 사용 패턴을 포착합니다.

OS가 각 프로세스의 워킹 셋 크기 $WSS_i$를 추적합니다. 전체 워킹 셋의 합(D = $\sum WSS_i$)이 총 프레임 수(m)를 초과하면 스래싱이 발생합니다. 이때 OS는 일부 프로세스를 중단(Suspend)시켜 D ≤ m을 유지합니다.

실무에서 스래싱 진단

# Linux에서 스래싱 징후 확인 (개념 코드)
import subprocess

# vmstat으로 페이지 인/아웃 확인
# si: swap in, so: swap out, us: user CPU, sy: system CPU
# si/so가 높고 us가 낮으면 스래싱 의심
result = subprocess.run(["vmstat", "1", "5"], capture_output=True, text=True)
print(result.stdout)

# 정상: si=0, so=0, us=70%, id=25%
# 스래싱: si=5000, so=3000, us=5%, id=2%, wa=90%

스래싱 해결: 메모리 추가, 프로세스 수 감소, 메모리 누수 프로세스 종료, 스왑 파티션 SSD로 변경(임시 방편).

Linux의 OOM Killer

모든 페이지 교체와 스왑도 메모리 부족을 해결하지 못하면, Linux 커널은 최후의 수단으로 OOM(Out Of Memory) Killer를 실행합니다. 각 프로세스의 oom_score를 기반으로 희생자를 선택하고 강제 종료합니다. /proc/<pid>/oom_score로 점수를 확인하고, /proc/<pid>/oom_score_adj로 조절할 수 있습니다.

중요한 서비스는 oom_score_adj를 -1000으로 설정하여 OOM Killer로부터 보호합니다.

다음 장에서는 OS가 관리하는 또 다른 핵심 자원인 파일 시스템을 다루겠습니다.