메모리 계층과 가상 메모리: 캐시·TLB·페이지 폴트·스래싱

2022년 7월 26일, 메모리 계층과 메모리 관리 주제로 발표했다. 당시 28장의 자료에는 CPU 캐시부터 가상 메모리, 페이지 교체, 브라우저 저장소와 Redis까지 넓은 범위가 들어 있었다. 다시 정리하면서 보니 모두 “캐시”나 “메모리”라는 단어를 쓰지만 같은 층위의 기술은 아니다.

이번 글은 하드웨어와 운영체제가 프로그램의 메모리 접근을 처리하는 흐름에 집중한다.

CPU 명령
  ↓ 레지스터
  ↓ CPU 캐시
  ↓ 주 메모리(RAM)
  ↓ 저장장치의 데이터·스왑

이 계층을 이해할 때 핵심은 장치 이름을 외우는 것이 아니라 지역성(locality), 주소 변환, 페이지 폴트, 메모리 압박이 어떻게 이어지는지 보는 것이다.

왜 메모리 계층이 필요한가

CPU가 원하는 모든 data를 register만큼 빠르고 RAM·storage만큼 크게 보관할 수는 없다. 빠른 저장 영역은 작고 비싸며, 큰 저장 영역은 상대적으로 느리다. 그래서 system은 여러 단계의 저장 공간을 조합한다.

단계	특징	누가 주로 관리하는가
레지스터	CPU가 즉시 연산할 값, 매우 작음	compiler·CPU
L1·L2·L3 캐시	최근·인접 메모리 데이터의 일부를 cache line 단위로 보관	하드웨어
주 메모리	실행 중인 코드와 데이터의 주된 저장 공간	OS·memory controller
저장장치	파일과 실행 image의 영속 저장, 페이지의 backing 역할 가능	파일시스템·storage stack

아래로 내려갈수록 일반적으로 용량은 커지고 접근 비용은 증가한다. 다만 실제 지연은 CPU 구조, 캐시 상태, NUMA, 저장장치와 워크로드에 따라 달라진다. 고정된 숫자표보다 어떤 계층에서 miss와 대기가 생기는지 측정하는 편이 정확하다.

locality가 cache를 가능하게 한다

캐시가 작은데도 효과적인 이유는 프로그램의 메모리 접근이 완전히 무작위가 아닌 경우가 많기 때문이다.

시간 지역성

최근 접근한 data를 곧 다시 접근할 가능성이 높다는 성질이다.

for (int i = 0; i < values.length; i++) {
    sum += values[i];
}

반복문의 counter와 sum은 짧은 시간에 여러 번 사용된다.

공간 지역성

한 주소에 접근했다면 가까운 주소도 곧 접근할 가능성이 높다는 성질이다. 배열을 순서대로 읽는 패턴이 대표적이다. CPU 캐시는 보통 한 값만이 아니라 주변 byte를 cache line 단위로 가져온다.

순차 접근:  [0][1][2][3][4][5] ...
무작위 접근: [9][1][7][3][0][8] ...

두 알고리즘의 계산량이 같아도 메모리 접근 패턴에 따라 실제 실행 시간이 달라질 수 있다. 큰 자료구조에서는 cache miss, 메모리 대역폭과 prefetch 효과를 함께 봐야 한다.

CPU 캐시와 애플리케이션 캐시는 다르다

발표 자료에는 브라우저 cookie, localStorage, sessionStorage와 Redis도 “캐시” 맥락으로 들어 있었다. 하지만 이들은 CPU 캐시 계층과 직접 이어지는 한 단계가 아니다.

용어	목적	관리 주체
CPU 캐시	CPU와 RAM의 접근 비용 차이를 줄임	하드웨어
OS 페이지 캐시	파일 데이터의 I/O를 줄임	kernel
Redis·애플리케이션 캐시	반복 계산·원격 조회를 줄임	애플리케이션·운영자
브라우저 저장소	web origin의 상태·데이터 보관	브라우저·웹 애플리케이션

모두 재사용으로 비용을 줄일 수 있지만 일관성, 제거(eviction), 보안 경계가 다르다. Redis의 TTL을 CPU 캐시의 교체 정책과 같은 문제로 다루면 설계를 잘못 이해하게 된다.

가상 주소는 어떻게 물리 주소가 되는가

프로세스가 사용하는 pointer는 보통 실제 RAM 주소 자체가 아니라 **가상 주소(virtual address)**다. 운영체제는 프로세스마다 가상 주소 공간을 제공하고, 페이지 테이블을 통해 가상 페이지를 물리 frame 등에 mapping한다.

프로세스 가상 주소
        ↓
가상 페이지 번호 + 페이지 offset
        ↓  TLB 조회
   hit ─┴─ miss
           ↓ 페이지 테이블 탐색
        물리 frame + offset

이 구조는 프로세스 격리, sparse address space, 공유 mapping과 demand paging을 가능하게 한다. 서로 다른 프로세스가 같은 가상 주소 값을 사용해도 다른 물리 frame을 가리킬 수 있다.

TLB는 address translation의 cache다

매번 메모리에 접근할 때마다 여러 단계의 페이지 테이블을 끝까지 읽으면 비용이 크다. CPU의 **TLB(Translation Lookaside Buffer)**는 최근 사용한 가상 페이지와 물리 frame의 주소 변환 결과를 보관한다.

• TLB hit: 저장된 변환 결과로 빠르게 물리 주소를 얻는다.
• TLB miss: 페이지 테이블을 조회해 변환 결과를 찾고 TLB를 갱신한다.
• mapping 자체가 없거나 준비되지 않음: page fault를 통해 kernel이 처리한다.

TLB miss와 page fault는 같은 사건이 아니다. TLB에 없더라도 페이지 테이블에 유효한 mapping이 있으면 페이지 테이블을 조회한 뒤 계속 실행할 수 있다. page fault는 CPU가 현재 페이지 테이블 상태로 접근을 완료할 수 없어 kernel의 처리가 필요한 상황이다.

page fault가 곧 오류는 아니다

이름 때문에 애플리케이션 오류처럼 들리지만 page fault는 가상 메모리의 정상 동작 중에도 발생한다. 예를 들어 처음 접근한 anonymous memory에 물리 페이지를 배정하거나, file-backed page를 처음 읽을 때 fault가 날 수 있다.

대략적인 흐름은 다음과 같다.

메모리 접근
  ↓ 현재 mapping으로 처리 가능한가?
  ├─ yes: 계속 실행
  └─ no: page fault → kernel
             ├─ 유효한 접근: 페이지 준비·mapping 후 재시작
             └─ 잘못된 접근: 프로세스에 signal 전달 가능

Linux getrusage(2) 기준으로 구분하면 다음과 같다.

• minor fault (ru_minflt): I/O 없이 처리한 page fault
• major fault (ru_majflt): 처리를 위해 I/O가 필요했던 page fault

major fault가 항상 swap을 뜻하는 것은 아니다. 필요한 file-backed page를 저장장치에서 읽는 경우도 포함될 수 있다. 반대로 page fault 수만 보고 성능 문제를 단정해서도 안 된다. fault 발생률, 저장장치 지연, 애플리케이션 지연을 같은 시간축에서 확인해야 한다.

demand paging과 page 교체

운영체제는 가상 주소 공간 전체를 처음부터 RAM에 올리지 않고 실제 접근 시 페이지를 준비할 수 있다. 이를 demand paging 관점으로 설명할 수 있다.

사용 가능한 메모리가 부족해지면 kernel은 reclaim 가능한 페이지를 찾아야 한다. 변경되지 않은 file-backed page는 필요할 때 다시 읽을 수 있고, 변경된 페이지는 writeback이 필요할 수 있다. anonymous memory는 구성에 따라 swap으로 내보내거나 다른 대응이 필요하다.

수업에서는 FIFO, LFU, LRU, NUR 같은 페이지 교체 알고리즘을 배운다. 실제 kernel 구현은 단순한 교과서 알고리즘 하나로 설명되지 않지만, 다음 질문을 익히는 데 도움이 된다.

• 앞으로 다시 쓸 가능성이 낮은 페이지는 무엇인가?
• 최근 사용 여부를 어떤 정보로 근사할까?
• 페이지를 내보내는 비용과 다시 가져오는 비용은 얼마인가?
• 워크로드의 working set이 사용 가능한 RAM 안에 들어오는가?

교과서 알고리즘의 차이는 페이지 교체 알고리즘 정리에서 따로 볼 수 있다.

working set과 스래싱

working set은 일정 시간 동안 프로세스가 활발히 사용하는 페이지 집합으로 이해할 수 있다. 여러 프로세스의 active working set이 사용 가능한 메모리를 크게 넘으면 reclaim과 page-in이 반복될 수 있다.

페이지가 필요함
  ↓ 다른 페이지를 reclaim
  ↓ 잠시 뒤 reclaim한 페이지가 다시 필요함
  ↓ 또 다른 페이지를 reclaim
  ↓ 반복

이처럼 실제 연산보다 페이지 이동과 reclaim에 많은 시간을 쓰는 상태를 thrashing이라고 한다. CPU 사용률이 낮은데 애플리케이션 지연이 증가하고, major fault와 저장장치 I/O가 함께 늘 수 있다.

해결을 swap 비활성화 한 줄로 단정할 수는 없다. 먼저 다음을 구분한다.

• 정상적인 cold start인가 지속적인 메모리 압박인가
• anonymous memory인가 file cache인가
• 한 프로세스의 leak인가 전체 host의 overcommit인가
• container limit 안의 압박인가 host 전체 압박인가
• 워크로드의 working set을 줄일 수 있는가

실제 메모리 문제를 증거 중심으로 좁히는 흐름은 Linux 메모리 문제 진단에서 이어서 다룬다.

fragmentation은 한 종류가 아니다

발표 자료에서는 internal fragmentation과 external fragmentation도 다뤘다.

• internal fragmentation: 할당 단위 안에 사용하지 못하는 공간이 남는 현상
• external fragmentation: free space 총량은 충분하지만 필요한 크기의 연속 공간을 만들기 어려운 현상

페이지 단위 가상 메모리는 물리 메모리 할당의 외부 fragmentation 문제를 줄이는 데 도움이 되지만 모든 fragmentation을 없애지는 않는다. allocator의 size class, 객체 수명, huge page, 물리적으로 연속된 할당 요구 등 다른 층위의 fragmentation이 남는다.

“free memory가 있는데 왜 allocation이 실패하는가”를 볼 때도 어느 allocator와 어느 연속성 조건을 말하는지 구분해야 한다.

Linux에서 page fault와 pressure를 확인하기

한 command의 숫자 하나보다 여러 증거를 연결한다.

process 실행의 fault 관찰

perf stat -e page-faults,minor-faults,major-faults -- ./app

perf stat event 이름과 사용 가능 여부는 kernel·perf 버전에 따라 확인한다. cold cache와 warm cache를 구분하고 동일한 조건에서 반복한다.

host 전체의 swap·run queue 흐름

vmstat 1

si, so는 swap in·out의 단서이고, r, b, CPU wait와 함께 본다. snapshot 한 줄만으로 결론 내리지 말고 latency가 발생한 시간과 맞춘다.

프로세스 mapping의 메모리 구성

cat /proc/<PID>/smaps_rollup

RSS, PSS, private·shared, anonymous 등 프로세스 메모리의 구성을 보는 단서가 된다. 접근 권한과 kernel 지원 여부를 확인한다.

관찰 결과를 다음처럼 연결하면 해석이 쉬워진다.

애플리케이션 지연 상승
  + major fault rate 상승
  + 저장장치 읽기 지연 상승
  + 메모리 압박 지속
  = working set과 reclaim 경로를 우선 조사

반면 minor fault가 시작 시점에 늘었다가 안정되고 서비스 지연이 정상이라면 반드시 장애라고 볼 수 없다.

발표 자료를 다시 보며 정리한 경계

2022년 발표에는 큰 개념을 한 번에 연결해 보려는 시도가 담겨 있었다. 지금 다시 나눈다면 세 묶음으로 분리한다.

1. 하드웨어 지역성: 레지스터, CPU 캐시, RAM
2. OS 가상 메모리: 페이지 테이블, TLB, page fault, reclaim, swap
3. 애플리케이션 데이터 재사용: Redis, 브라우저 저장소, 애플리케이션 캐시

세 영역은 서로 영향을 주지만 같은 계층은 아니다. 이름이 비슷하다는 이유만으로 하나의 hierarchy에 넣지 않으면 각 영역의 성능과 일관성 문제를 더 정확히 설명할 수 있다.

원래 발표 자료 PDF도 글과 함께 유지해 당시 정리 과정을 남겨 둔다.

정리

메모리 계층을 이해하는 흐름은 다음과 같다.

1. 프로그램은 지역성을 보이므로 작은 CPU 캐시가 효과를 낼 수 있다.
2. 프로세스는 가상 주소를 사용하고 페이지 테이블이 물리 mapping을 관리한다.
3. TLB는 주소 변환 결과를 캐시한다.
4. 현재 mapping으로 접근을 끝낼 수 없으면 page fault가 발생해 kernel이 처리한다.
5. working set이 메모리를 넘고 reclaim·page-in이 반복되면 thrashing으로 이어질 수 있다.

메모리 성능은 “RAM 사용률이 높다”는 한 문장으로 설명되지 않는다. cache miss, 주소 변환, fault 종류, reclaim, I/O와 워크로드의 시간축을 연결해야 원인에 가까워진다.

참고 자료

• Linux kernel documentation: Memory Management
• Linux kernel documentation: Page Tables
• getrusage(2): resource usage and page-fault fields
• perf-stat(1): performance counter statistics