페이지 교체 알고리즘

물리 메모리가 부족할 때 어떤 페이지를 내보낼지 결정하는 것은 가상 메모리 성능의 핵심입니다.

잘못된 선택은 곧바로 페이지 폴트 증가로 이어지고, 극단적으로는 시스템 전체가 디스크 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(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와 차이가 날 수 있습니다. 정확한 LRU는 스택 성질을 가지므로 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는 모든 메모리 접근마다 순서 정보를 갱신해야 합니다.

타임스탬프 방식: 각 페이지 접근 시 현재 시각을 기록합니다.

교체 시 가장 작은 타임스탬프를 찾습니다.

모든 접근마다 메모리 쓰기가 필요하고, 교체 시 전체 탐색이 필요합니다.

스택(더블 링크드 리스트) 방식: 접근된 페이지를 리스트의 끝으로 옮깁니다.

교체 시 리스트 앞(가장 오래된)을 제거합니다.

리스트 연결을 갱신하는 메모리 쓰기가 필요하며 정확한 연산 수는 구현에 따라 다릅니다.

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

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

하드웨어가 제공하는 참조 비트(Reference Bit)를 활용합니다.

페이지가 접근되면 하드웨어가 참조 비트를 자동으로 1로 설정합니다.

지원 하드웨어가 접근 흔적을 남기므로 매 접근마다 소프트웨어 목록을 갱신하는 부담을 줄입니다. 비트를 확인·초기화하고 후보를 순회하는 OS 비용은 남습니다.

동작 방식

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

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

참조 비트가 1인 페이지는 이번 검사에서 한 번 더 기회를 얻습니다. 이후 비트가 0인 채 다시 만나면 교체될 수 있습니다.

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의 유불리는 참조 패턴, 카운터 감쇠, 동률 처리에 따라 달라집니다.

알고리즘 비교

스래싱 (Thrashing)

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

발생 메커니즘

다음은 낮은 CPU 이용률만 보고 작업 투입을 늘리는 제어 정책을 가정한 악순환입니다. 모든 현대 OS 스케줄러가 이 정책을 사용한다는 뜻은 아닙니다.

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)를 넘으면 스래싱 위험이 커집니다. 공유 페이지와 reclaim 가능한 메모리는 별도로 고려합니다.

작업 투입을 제한하고 필요하면 일부 작업을 중단·회수해 활성 수요를 낮추는 것이 이 모델의 대응입니다.

실무에서 스래싱 진단

# 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%

위 vmstat 주석은 관측 결과가 아닌 설명용 수치입니다. 첫 보고는 부팅 이후 평균일 수 있으며, si/so는 스왑 전송이라 파일 페이지 재적재 전체를 나타내지 않습니다. 지속적인 지연·메모리 압박·I/O 대기를 함께 확인합니다.

스래싱 해결: 메모리 추가, 프로세스 수 감소, 메모리 누수 프로세스 종료, 스왑 파티션 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 희생자 선택에서 제외하는 설정입니다. 모든 작업에 적용할 일반 해법은 아니며, 다른 프로세스나 메모리 제어 정책에 미치는 영향을 함께 판단해야 합니다.

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