페이지 교체와 Buddy·Slab 할당자의 메모리 관리 방식

페이지 교체와 할당자는 서로 다른 층위의 병목을 다룬다

운영체제와 하이퍼바이저에서 메모리 관리는 성능과 안정성에 직접 영향을 준다. 물리 프레임이 부족할 때는 페이지 교체 정책이 희생 대상을 고르고, 연속 물리 메모리가 필요할 때는 Buddy System이 블록을 관리한다. 같은 타입의 커널 객체를 반복적으로 다루는 경로에서는 Slab Allocation이 재사용 비용을 낮춘다.

페이지 교체(Page Replacement)는 가상 메모리 환경에서 물리 프레임이 모자랄 때 적용하는 희생 페이지 선택 정책이다. FIFO(First-In-First-Out), LRU(Least Recently Used), Optimal이 대표적이다.

Buddy System은 2의 거듭제곱 크기의 블록을 분할하고 병합하는 연속 물리 메모리 할당자다. 할당과 반환은 O(log N) 시간에 처리하며, 외부 단편화를 줄이는 대신 내부 단편화가 생길 수 있다.

Slab Allocation은 동일한 타입의 커널 객체를 slab 단위로 캐시해 재사용하는 소형 객체 할당 방식이다. 객체 초기화·소멸 비용을 줄이고 캐시 친화적인 접근을 제공한다.

희생 페이지를 고르는 정책의 차이

LRU는 최근 접근 이력을 이용해 워킹셋을 유지하려 하므로 일반 워크로드에서 높은 적중률을 기대할 수 있다. 다만 접근할 때마다 이력을 갱신해야 하며, 리스트와 해시 조합을 쓰는 경우 핫 패스에 오버헤드가 생긴다.

FIFO는 큐에 순서만 보관한다. 페이지 접근 시 별도 갱신 비용이 없고 구현도 단순하지만, Belady anomaly로 기대와 다른 결과가 나올 수 있다.

Optimal은 미래 참조를 안다고 가정해 최적의 희생 대상을 고르는 이론적 경계다. 실제 구현은 불가능하며 다른 정책을 평가하는 기준으로 쓰인다. 운영 환경에서는 Clock/Second-Chance, NRU, 2Q, ARC처럼 LRU를 근사한 정책으로 비용과 효율을 조절한다.

항목	FIFO	LRU	Optimal
성능(적중률)	중간(변동 큼)	높음(일반 워크로드 강함)	최상(이론상 상한)
확장성	높음(구현 단순)	중간(메타데이터 갱신 비용)	낮음(실사용 불가)
일관성	낮음(Belady anomaly 가능)	높음(지역성 반영)	최상(미래 정보 가정)
안정성	중간(스래싱 취약)	높음(워킹셋 유지)	이론적
운영 편의	높음(튜닝 적음)	중간(파라미터/근사 선택 필요)	N/A

쓰기 비중이 큰 워크로드에서는 dirty page 비율과 백그라운드 writeback 스로틀을 함께 관리해야 한다. 스래싱을 막으려면 워킹셋 추정, cgroup 메모리 한도, NUMA 바인딩, 파일 캐시 압력을 살펴야 한다. 교체 이후에는 PTE 갱신과 TLB flush 범위를 최소화하는 일도 중요하다.

연속 메모리와 소형 객체를 나누어 다루는 방식

Buddy System은 요청 크기 이상인 최소 2^k 블록을 할당한다. 반환된 블록은 buddy를 확인해 병합하고, 가능하면 상위 블록으로 되돌린다. 이 구조는 hugepage처럼 큰 연속 할당을 다루기 쉽다.

반면 요청 크기와 2^k 블록 크기의 차이만큼 내부 단편화가 생긴다. 고정 크기 객체를 대량으로 할당하는 경로에서는 비효율적일 수 있으므로 Slab Allocation과 함께 사용한다. 영역·노드별(Zone/NUMA) free list와 per-CPU 캐시를 두면 락 경합을 줄일 수 있으며, 실시간·고성능 환경에서는 예측 가능한 지연을 제공한다.

Slab Allocation은 동일 타입 객체를 여러 개 묶은 slab으로 관리한다. partial, empty, full 리스트로 slab 상태를 추적하고, constructor/destructor를 통해 캐시 적중 시 초기화 비용을 낮춘다. per-CPU slab은 동시성 확장과 false sharing 최소화에 도움이 되며, coloring과 정렬은 캐시·페이지 캐시 지역성을 높인다.

슬랩 포이즈닝(slab poisoning), 객체 제로잉, freelist 랜덤화는 UAF와 정보 노출을 완화하는 수단이다. net, inode 같은 격리 캐시는 파편화와 오염의 전파를 막는 데 사용한다.

페이지 폴트 이후에는 회수와 오류 경로까지 이어진다

⤢✕

페이지 폴트 처리에서는 페이지 테이블과 역매핑 락의 범위를 줄이고 per-CPU 데이터를 활용해 경합을 완화한다. NUMA 환경에서는 로컬 노드를 우선하며, 실패하면 인터리브나 원격 노드 폴백을 고려한다.

I/O가 실패하면 재시도, 백오프, 프로세스 종료·시그널, 오류 페이지 표시 경로가 필요하다. OOM 상황에서는 메모리 회수(kswapd/direct reclaim), cgroup OOM, 시스템 OOM이 순차적으로 처리된다.

커널과 서비스의 메모리 경로

리눅스는 Active/Inactive list와 workingset refault를 포함한 LRU 근사를 사용하고, buddy+slab 조합으로 페이지와 객체를 나누어 관리한다. 하이퍼바이저에서는 ballooning에 따른 페이지 회수와 guest LRU, host 정책의 상호작용이 문제에 포함된다.

데이터베이스와 스토리지 계층은 Clock/2Q/ARC 기반 버퍼 풀 교체 정책으로 I/O 적중률을 높이고 writeback 스로틀을 관리한다. 페이지 캐시와 DB 버퍼의 중복은 swappiness, readahead 같은 튜닝 대상이다.

NIC, RPC, 파일시스템 메타데이터 객체는 슬랩 캐시 재사용으로 관리할 수 있다. CDN과 프록시 캐시도 교체 정책을 통해 메모리 적중률을 높이며, 임베디드·실시간 환경에서는 buddy의 예측 가능한 지연과 고정 슬랩으로 동적 할당과 스래싱 원인을 줄인다.

성능과 단편화에서 얻는 효과

일반 OLTP/웹 워크로드에서는 LRU 계열 도입 시 FIFO 대비 페이지 적중률이 10~~30%p 개선될 수 있으며, 환경에 따라 달라진다. 슬랩 캐시는 커널 객체 할당 지연 p95를 30~~60% 줄이고 CPU 캐시 미스를 낮출 수 있다.

슬랩 재사용은 내부 단편화를 20~40% 완화하고 객체 초기화 비용을 줄인다. buddy+hugepage 조합은 TLB 미스 감소와 메모리 대역폭 효율 개선에 연결된다. 워킹셋 유지와 TLB flush 범위 축소는 스래싱과 지연 스파이크를 완화하며, 제로잉·포이즈닝·랜덤화는 UAF 및 정보 노출 리스크를 낮춘다.

FIFO, LRU, Optimal을 비교하는 시뮬레이션

아래 코드는 Python 3.10+ 환경에서 외부 라이브러리 없이 페이지 참조열(list[int])과 프레임 개수(int)를 입력받아 hit/miss와 miss rate를 출력한다.

from collections import deque, OrderedDict

def simulate_fifo(refs, frames):
    q, inmem = deque(), set()
    hits = misses = 0
    for i, p in enumerate(refs):
        if p in inmem:
            hits += 1
        else:
            misses += 1
            if len(inmem) < frames:
                inmem.add(p); q.append(p)
            else:
                victim = q.popleft()
                inmem.remove(victim)
                inmem.add(p); q.append(p)
    return hits, misses, misses / len(refs)

def simulate_lru(refs, frames):
    od = OrderedDict()  # page -> None
    hits = misses = 0
    for p in refs:
        if p in od:
            hits += 1
            od.move_to_end(p)  # most recently used at end
        else:
            misses += 1
            if len(od) >= frames:
                od.popitem(last=False)  # evict least recently used
            od[p] = None
    return hits, misses, misses / len(refs)

def simulate_optimal(refs, frames):
    inmem = set()
    hits = misses = 0
    for i, p in enumerate(refs):
        if p in inmem:
            hits += 1
            continue
        misses += 1
        if len(inmem) < frames:
            inmem.add(p); continue
        # choose victim used farthest in future (or never)
        future = refs[i+1:]
        farthest, victim = -1, None
        for x in inmem:
            try:
                idx = future.index(x)
            except ValueError:
                victim = x; break  # not used again
            if idx > farthest:
                farthest, victim = idx, x
        inmem.remove(victim)
        inmem.add(p)
    return hits, misses, misses / len(refs)

if __name__ == "__main__":
    refs = [7,0,1,2,0,3,0,4,2,3,0,3,2]  # sample
    frames = 3
    for name, fn in [("FIFO", simulate_fifo),
                     ("LRU", simulate_lru),
                     ("Optimal", simulate_optimal)]:
        h, m, mr = fn(refs, frames)
        print(f"{name}: hits={h}, misses={m}, miss_rate={mr:.3f}")

Optimal은 미래 참조를 바탕으로 한 상한선을 제공하므로 실무 정책의 평가 벤치마크가 된다. LRU는 일반적으로 FIFO보다 높은 적중률을 보이지만 접근 이력 갱신 비용이 따른다.

운영 중 확인할 조건

일반 서버에서는 Clock/Active-Inactive 같은 LRU 근사를 우선 검토하고, swappiness를 통해 파일 캐시와 익명 메모리의 균형을 조정한다. 순차 접근이나 스캔이 많은 워크로드라면 2Q, ARC, 시퀀스 감지로 캐시 오염을 막는 선택지가 있다.

소형 객체는 Slab과 캐시 분리, constructor 활용에 적합하다. 큰 연속 할당은 buddy+hugepage를 고려하되, 실패 시 compaction과 defrag 비용을 감수해야 한다. per-CPU 캐시, 노드 선호도 바인딩, cross-node TLB shootdown 최소화도 NUMA 환경의 핵심 조건이다.

고부하에서는 kswapd와 direct reclaim 간 경합을 관리한다. 페이지 제로잉, 슬랩 포이즈닝, freelist 랜덤화, 격리 캐시를 적용하고 I/O 오류와 OOM 정책을 명시해야 한다. page fault/sec, reclaim rate, page cache hit, slab usage, fragmentation을 관측하며, 재현 가능한 트레이스에서 정책을 비교하고 Optimal 대비 상대 성능을 확인한다.