[CS300 #113] 스래싱과 워킹 셋 — 일은 안 하고 페이지만 나르는 상태

컴퓨터공학 300 주제 시리즈의 113번째 글이다. 전체 지도는 여기.

한 줄 요약

스래싱은 실행 중인 프로세스들이 자주 쓰는 페이지(워킹 셋)의 합이 물리 메모리를 넘어, 시스템이 페이지를 들이고 내보내는 데 대부분의 시간을 쓰며 실제 일은 거의 못 하는 상태이고, 워킹 셋 모델은 이를 막기 위해 “각 프로세스가 최소한 얼마를 가져야 하는가”를 정의한다.

왜 필요한가

메모리가 조금 부족하면 시스템은 조금 느려지는 것이 아니라, 어느 지점에서 절벽처럼 무너진다. 디스크 LED 는 쉬지 않고 깜박이고, 마우스 커서가 몇 초씩 멈추고, SSH 접속조차 되지 않는다. CPU 사용률은 오히려 낮다. 모두가 디스크를 기다리고 있기 때문이다.

초기 시분할 시스템은 여기서 치명적인 실수를 했다. CPU 사용률이 낮으니 “프로세스를 더 올리자”고 판단했고, 그러면 메모리가 더 모자라 폴트가 늘고 CPU 사용률은 더 떨어졌다. 악순환이다. 이 현상을 설명하고 처방한 것이 데닝(Peter J. Denning)의 워킹 셋 모델이다.

지금도 같은 일이 일어난다. 스왑을 켠 서버의 메모리 누수, 메모리 limit 에 바짝 붙은 컨테이너가 OOM 으로 죽기 직전 몇 분간 극도로 느려지는 현상이 모두 스래싱이다.

핵심 개념

다중 프로그래밍 정도와 CPU 사용률

CPU 사용률
  ^
  |            ____
  |          /     \
  |        /         \
  |      /             \        <- 스래싱 구간
  |    /                 \___
  |  /
  +-------------------------------> 동시에 올린 프로세스 수
              ^
          최적 지점

프로세스를 늘리면 처음에는 I/O 대기를 다른 프로세스가 메워 CPU 사용률이 오른다. 그러다 각 프로세스에 돌아가는 프레임이 워킹 셋보다 작아지는 순간 폴트가 폭증하고, 모두가 디스크 큐에 줄을 서며 사용률이 급락한다.

지역성(Locality)

프로그램은 주소 공간 전체를 고르게 쓰지 않는다. 특정 시간 구간에는 일부 페이지 묶음만 집중적으로 쓴다. 함수 하나를 실행하는 동안에는 그 함수의 코드, 지역 변수, 다루는 자료구조만 쓴다. 다른 함수로 넘어가면 묶음이 바뀐다. 이 성질 덕분에 메모리 전체가 아니라 묶음만 있으면 프로그램이 잘 돈다.

워킹 셋의 정의

데닝은 1968년 논문에서 다음과 같이 정의했다.

시각 t 에서 창 크기 Δ 의 워킹 셋 W(t, Δ) = 구간 (t − Δ, t] 동안 참조된 페이지들의 집합

참조열: ... 2 6 1 5 7 7 7 7 5 1 | 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 ...
                  <---Δ=10--->  t1         <---Δ=10--->  t2
W(t1) = {1, 2, 5, 6, 7}                    W(t2) = {3, 4}

Δ 가 너무 작으면 지역성 묶음을 다 담지 못한다.
Δ 가 너무 크면 이전 단계의 페이지까지 포함한다.

워킹 셋 원칙: 프로세스의 워킹 셋 전체를 메모리에 둘 수 있을 때만 그 프로세스를 실행한다. 모든 프로세스의 워킹 셋 합 D 가 가용 프레임 수를 넘으면, 프로세스 하나를 통째로 내보내(스왑 아웃) 남은 프로세스들이 제대로 돌게 한다. 몇 개를 확실히 돌리는 것이 모두를 조금씩 굶기는 것보다 낫다.

페이지 폴트 빈도(PFF) 방식

워킹 셋을 정확히 추적하는 것은 비싸다. 더 실용적인 방법은 페이지 폴트 빈도를 직접 보는 것이다.

폴트율	판단	조치
상한보다 높다	프레임이 모자란다	프레임을 더 준다
하한보다 낮다	프레임이 남는다	프레임을 회수한다
줄 프레임이 없다	전체 과부하	프로세스를 중단·스왑 아웃

현대 리눅스에서의 신호: PSI

리눅스는 PSI(Pressure Stall Information) 로 “자원 부족 때문에 작업이 멈춰 있던 시간의 비율”을 직접 보여 준다. /proc/pressure/memory 의 some 은 적어도 한 작업이 메모리 때문에 멈춘 시간 비율, full 은 모든 비유휴 작업이 동시에 멈춘 시간 비율이다. full 이 꾸준히 높다면 스래싱이다. cgroup v2 에서는 cgroup 별로 memory.pressure 파일이 있다.

직접 해 보기

지역성이 있는 참조열을 만들고, 프레임 수를 바꿔 가며 LRU 의 폴트율을 그린다. 단계마다 40개 페이지 묶음 안에서 98% 접근하고, 2% 는 넓은 범위에 무작위로 접근한다.

import random
from collections import OrderedDict

random.seed(1)
# 국소성이 있는 참조열: 단계마다 40개 페이지 묶음 안에서만 주로 접근한다
refs = []
for phase in range(10):
    base = phase * 25                      # 단계가 바뀌면 묶음이 조금씩 이동
    for _ in range(5000):
        refs.append(base + random.randrange(40) if random.random() < 0.98
                    else random.randrange(300))

def lru_faults(refs, k):
    mem, faults = OrderedDict(), 0
    for p in refs:
        if p in mem: mem.move_to_end(p); continue
        faults += 1
        if len(mem) == k: mem.popitem(last=False)
        mem[p] = True
    return faults

def working_set_sizes(refs, delta):
    return [len(set(refs[max(0, t - delta + 1): t + 1])) for t in range(0, len(refs), 1000)]

ws = working_set_sizes(refs, 1000)
print("워킹 셋 크기(Δ=1000) 표본:", ws[5:15], " 평균", round(sum(ws) / len(ws), 1))
print("프레임 수 -> 폴트율")
for k in (10, 20, 30, 35, 40, 45, 50, 60, 80):
    f = lru_faults(refs, k)
    bar = "#" * int(f / len(refs) * 60)
    print(f"{k:4d}  {f / len(refs):6.1%}  {bar}")

워킹 셋 크기(Δ=1000) 표본: [63, 61, 54, 57, 60, 62, 55, 63, 59, 60]  평균 56.8
프레임 수 -> 폴트율
 76.0%  #############################################
 52.7%  ###############################
 29.3%  #################
 17.9%  ##########
  7.5%  ####
  2.7%  #
  2.4%  #
  2.2%  #
  2.1%  #

핵심 묶음 크기인 40 프레임 근처를 경계로 폴트율이 급변한다. 45 프레임 이상에서는 2% 대에 머물고(남은 폴트는 무작위 접근 때문이다), 40 아래로 내려가면 폴트율이 가파르게 치솟는다. 프레임을 2배로 늘려도(40→80) 이득은 몇 퍼센트포인트뿐이지만, 조금만 줄여도(40→30) 폴트가 4배가 된다. 측정된 워킹 셋(평균 57)이 핵심 묶음 40보다 큰 것은 창 안에 섞인 무작위 접근 페이지까지 세기 때문이다. Δ 선택이 워킹 셋 크기를 좌우한다는 것을 보여 준다.

현업에서는

“느려진 뒤 OOM”의 정체: 컨테이너 메모리 사용량이 limit 에 다가가면 커널은 그 cgroup 안에서 페이지 캐시와(스왑이 있다면) 익명 페이지를 계속 회수한다. 실행 파일 코드 페이지까지 밀려나면 다시 읽어 오느라 응답이 극도로 느려지다가 결국 OOM kill 이 난다. 메트릭에서 OOM 직전 몇 분간 지연이 치솟았다면 이 패턴이다.
PSI 로 경보: 메모리 사용률 90% 같은 정적 임계값보다 memory.pressure 의 full avg10 같은 정체 시간 비율이 실제 고통을 더 잘 반영한다. systemd-oomd 같은 사용자 공간 OOM 처리기도 PSI 를 기준으로 동작한다.
쿠버네티스 노드 압박 퇴거: kubelet 은 노드 가용 메모리가 임계값 아래로 내려가면 파드를 퇴거시킨다. 커널 OOM killer 가 나서기 전에 사용자 공간에서 먼저 정리하려는 장치이고, “프로세스를 내보내 남은 것을 살린다”는 워킹 셋 원칙과 같은 생각이다.
requests 를 워킹 셋에 맞추기: 컨테이너 메모리 requests 를 평균 사용량이 아니라 안정 상태의 워킹 셋(cAdvisor 의 container_memory_working_set_bytes 같은 지표)에 맞추고, limit 에는 여유를 두는 것이 스래싱과 OOM 을 함께 줄인다.

확인 문제

스래싱이 일어날 때 CPU 사용률이 오히려 떨어지는 이유는?
워킹 셋 W(t, Δ) 의 정의를 쓰고, Δ 가 너무 크거나 작을 때의 문제를 설명하라.
워킹 셋 합이 가용 메모리를 넘었을 때 워킹 셋 모델이 권하는 조치는?
페이지 폴트 빈도(PFF) 방식이 워킹 셋을 직접 추적하는 것보다 실용적인 이유는?
리눅스에서 스래싱을 수치로 확인할 수 있는 인터페이스 하나를 들어라.

풀이

프로세스들이 대부분의 시간을 페이지 폴트 처리(디스크 I/O) 대기로 보내므로 CPU 에서 실행할 준비가 된 작업이 거의 없기 때문이다.
시각 t 이전 Δ 동안 참조된 페이지 집합이다. Δ 가 작으면 현재 지역성을 다 담지 못하고, 크면 지난 단계의 페이지까지 포함해 필요 이상으로 크게 잡는다.
일부 프로세스를 통째로 중단·스왑 아웃해서 나머지 프로세스들이 워킹 셋 전체를 메모리에 둘 수 있게 한다.
참조된 페이지 집합을 매 순간 계산하지 않고 폴트 횟수라는 싼 지표만으로 프레임을 늘리고 줄일 수 있기 때문이다.
PSI 의 /proc/pressure/memory(cgroup v2 에서는 memory.pressure). full 값이 높으면 모든 작업이 메모리 때문에 멈춰 있다는 뜻이다.

더 읽을거리 (References)

P. J. Denning, “The working set model for program behavior”, Communications of the ACM 11(5), 1968.
OSTEP, Beyond Physical Memory: Policies (PDF) — 스래싱 절
Linux kernel documentation, PSI - Pressure Stall Information
Kubernetes 문서, Node-pressure Eviction