워킹셋으로 이해하는 지역성 기반 메모리 관리

최근 참조 이력이 메모리 요구량을 말해준다

워킹셋(Working Set)은 Peter Denning이 1968년 제안한 메모리 관리 모델이다. 특정 시간 구간에 프로세스가 참조한 페이지를 모아, 현재 실행 흐름을 유지하는 데 필요한 메모리 범위를 나타낸다.

핵심은 프로그램의 지역성(Locality)이다. 최근 사용한 페이지가 다시 사용될 가능성이 높고, 그 주변 페이지도 함께 참조될 가능성이 있다. 워킹셋은 이런 활성 지역성을 동적인 페이지 집합으로 포착한다. 이 집합을 메모리에 유지하지 못하면 페이지 부재가 반복되고, 결국 트래싱(Thrashing)으로 이어질 수 있다.

시간 창 Δ에서 시각 t까지 참조한 고유 페이지 집합은 다음처럼 표현한다.

WS(t, Δ): 구간 [t - Δ, t]에서 참조된 페이지 집합
WSS(t, Δ): 워킹셋의 크기, 즉 페이지 개수
Δ: 시간 창의 크기이며 일반적으로 페이지 참조 횟수로 표현

WS(t, Δ) = {pages referenced in interval [t - Δ, t]}
WSS(t, Δ) = |WS(t, Δ)|

⤢✕

Δ는 현재 지역성을 얼마나 넓게 볼지 정한다

Δ가 작으면 워킹셋은 현재 지역성에 집중한다. WSS가 작아 메모리 사용에는 유리하지만, 지역성이 전환될 때 페이지 부재가 늘 수 있다. 창이 지나치게 짧으면 실제 지역성을 충분히 담아내지 못한다.

반대로 Δ가 크면 여러 지역성이 한 집합에 들어온다. 페이지 부재는 줄어들 수 있지만 WSS가 커지고, 비활성 페이지까지 포함해 메모리를 낭비할 수 있다. 그 결과 다중 프로그래밍 수준도 낮아질 수 있다.

따라서 Δ는 프로그램의 지역성 패턴과 시스템·애플리케이션 특성에 맞춰 조정해야 한다. 일반적으로 수백~수천 페이지 참조 단위가 사용되며, Δ를 동적으로 조절하는 적응형 기법도 연구된다.

⤢✕

WSS 합으로 메모리 압박을 판단한다

워킹셋 모델은 각 프로세스가 실행 중 지역성 패턴을 보며, 지역성마다 필요한 페이지 집합이 있다고 가정한다. 해당 워킹셋이 메모리에 머물면 페이지 부재를 최소화할 수 있고, 집합 밖의 페이지는 교체 후보가 된다.

전체 메모리 요구량은 모든 프로세스의 워킹셋 크기를 더한 값이다.

D = Σ WSS(i): 모든 프로세스의 워킹셋 크기 합
m: 사용할 수 있는 물리 메모리 페이지 프레임 수
D ≤ m: 모든 프로세스를 실행할 수 있음
D > m: 트래싱이 발생할 수 있어 일부 프로세스를 스왑 아웃해야 함

이 기준은 적정 다중 프로그래밍 수준을 정하는 데도 쓰인다. Σ WSS(i) ≤ m을 만족하는 최대 프로세스 수를 유지하고, 메모리가 부족하면 중기 스케줄러(Medium-term Scheduler)가 우선순위에 따라 프로세스를 선택해 관리한다.

⤢✕

페이지 교체에서는 오래전에 참조된 페이지를 찾는다

워킹셋 기반 교체는 페이지마다 최종 참조 시각(Last Reference Time)을 기록하는 방식으로 생각할 수 있다. 페이지가 참조될 때마다 시각을 갱신하고, 페이지 부재가 생기면 워킹셋 밖으로 판단된 페이지를 교체한다.

교체 과정은 현재 시각과 마지막 참조 시각의 차이를 확인하는 데서 시작한다. 그 차이가 Δ보다 큰 페이지를 찾고, 워킹셋 밖에 있는 페이지 중 가장 오래된 항목을 교체 대상으로 고른다.

하드웨어 참조 비트(Reference Bit)를 함께 쓰면 비용을 낮출 수 있다. 비트를 주기적으로 시프트해 참조 이력을 남기고, 이를 바탕으로 워킹셋을 근사한다.

// Working Set 교체 알고리즘 개념
for (each page in memory) {
    if (current_time - page.last_reference_time > delta) {
        // 페이지가 Working Set 밖에 있음
        if (page.reference_bit == 0) {
            // 교체 대상으로 선정
            replace(page);
        }
    }
}

정확도와 추적 비용 사이의 선택

모든 페이지 참조를 기록하고 참조 문자열(Reference String)을 유지하면 정확한 워킹셋을 계산할 수 있다. 다만 이 방식은 오버헤드가 매우 커서 실용적이지 않다.

실제 환경에서는 참조 비트 기반의 주기적 샘플링, 인터벌 타이머를 이용한 참조 비트 검사, 참조 빈도를 비트 패턴으로 기록하는 다중 비트 카운터를 사용해 근사한다. 정확한 추적보다 비용이 낮으면서도 합리적인 정확도를 제공한다.

MMU(Memory Management Unit)의 참조 비트, 페이지 테이블 엔트리의 타임스탬프 필드, TLB(Translation Lookaside Buffer) 정보는 이런 추적을 뒷받침하는 하드웨어 정보다.

⤢✕

Resident Set, LRU, PFF와 구분되는 지점

Working Set은 프로세스가 필요로 하는 논리적 페이지 집합이고, Resident Set은 실제 물리 메모리에 적재된 페이지 집합이다. 이상적인 상태는 Resident Set ⊇ Working Set이다.

LRU는 참조 순서에 따라 최근 사용한 페이지를 남기는 방식이다. 워킹셋은 시간 창을 기준으로 지역성을 명시적으로 모델링하며, 이론적으로는 더 정확하지만 구현이 복잡하다.

Page Fault Frequency(PFF)는 페이지 부재율에 따라 상태를 조정하는 반응적(Reactive) 접근이다. 워킹셋은 필요한 메모리 범위를 먼저 추정하는 사전 예방적(Proactive) 접근이며, 두 기법 모두 트래싱 방지가 목적이다.

운영 환경에서 보는 워킹셋

Windows는 Working Set Trimmer를 사용한다. Linux는 명시적 워킹셋 모델보다 LRU 변형을 사용하며, 실시간 OS에서는 정적 페이지 할당으로 워킹셋을 보장한다.

성능 튜닝에서는 프로세스별 워킹셋 크기를 모니터링하고, 메모리 압박 시 워킹셋을 기준으로 프로세스 우선순위를 조정할 수 있다. 데이터베이스 버퍼 풀 크기를 결정할 때도 활용된다.

가상화 환경에서는 VM(Virtual Machine)별 워킹셋을 추정해 메모리 벌룬(Balloon) 드라이버와 연계하고, 동적 메모리 할당 정책을 수립한다.

⤢✕

지역성 모델이 주는 기준과 구현 부담

워킹셋은 지역성 원리에 근거해 프로세스별 메모리 필요량을 제시하고, 트래싱 방지와 다중 프로그래밍 수준 조정에 기준을 제공한다. 필요량에 따라 메모리를 배분할 수 있다는 점에서도 의미가 있다.

다만 정확한 워킹셋 추적에는 큰 오버헤드가 따르며, 적절한 Δ를 고르기 어렵다. 지역성이 전환되는 순간에 즉시 대응하기도 쉽지 않고, 효율적인 구현에는 하드웨어 지원이 필요하다. 그래서 현실의 메모리 관리에서는 참조 비트와 샘플링을 이용한 근사 방식이 실용적인 선택지가 된다.