운영체제 메모리 관리: 가상 메모리와 페이징

프로세스가 보는 주소는 가짜이고, 그 가짜 주소를 실제 메모리로 바꾸는 일이 메모리 관리의 핵심입니다.

백엔드 성능 문제는 메모리 접근 패턴에서 비롯될 때가 많습니다. Redis가 왜 빠른지, OOM(Out of Memory) 킬러가 왜 프로세스를 종료하는지를 따라가면 결국 가상 메모리와 페이징에 닿습니다.

가상 메모리가 푸는 문제

가상 메모리(Virtual Memory)는 각 프로세스에 독립적인 가상 주소 공간을 주는 방식입니다. 프로세스는 0번지부터 시작하는 연속된 주소를 보지만, 그 주소가 가리키는 물리 위치는 따로 있습니다. 덕분에 물리 메모리 크기와 무관하게 큰 주소 공간을 쓸 수 있습니다.

이 방식이 없으면 두 프로세스가 같은 물리 주소를 동시에 쓰려는 충돌을 막기 어렵습니다. 가상 주소 공간을 분리하면 프로세스끼리 서로의 메모리를 직접 건드리지 못합니다. 격리와 보호가 가상 메모리의 첫 번째 이득입니다.

남은 문제는 변환입니다. 프로세스가 내미는 가상 주소를 실제 물리 주소로 누가, 어떻게 바꾸느냐가 이후 모든 내용의 출발점입니다.

페이징과 주소 변환

페이징(Paging)은 메모리를 고정 크기 조각으로 나눠 관리하는 방식입니다. 가상 주소 공간은 일정한 크기의 페이지로, 물리 메모리는 같은 크기의 프레임으로 나눕니다. 페이지 크기는 x86 계열에서 보통 4KB를 씁니다.

가상 주소는 두 부분으로 쪼개집니다. 앞부분은 페이지 번호, 뒷부분은 페이지 안에서의 위치인 오프셋입니다. 32비트 주소에 4KB(2의 12제곱 바이트) 페이지를 쓰면 오프셋이 12비트, 페이지 번호가 20비트로 갈립니다.

변환을 맡는 하드웨어가 메모리 관리 장치(Memory Management Unit, MMU)입니다. MMU는 페이지 번호를 페이지 테이블에서 찾아 프레임 번호로 바꾸고, 오프셋은 그대로 붙여 물리 주소를 만듭니다.

페이지 테이블은 프로세스마다 따로 존재합니다. 같은 가상 주소라도 프로세스가 다르면 다른 프레임을 가리키므로, 격리가 자연스럽게 유지됩니다.

페이지 테이블이 커지는 문제

페이지 테이블 자체도 메모리를 차지합니다. 32비트 시스템에서 페이지 번호가 20비트면 엔트리가 2의 20제곱, 약 100만 개입니다. 엔트리 하나를 4바이트로 잡으면 테이블 하나가 약 4MB의 연속 메모리를 요구합니다. 프로세스마다 이만큼을 통째로 잡는 것은 낭비입니다.

해법은 다단계 페이지 테이블입니다. 주소를 여러 토막으로 나눠 단계별로 테이블을 타고 내려가며, 실제로 쓰는 주소 범위의 하위 테이블만 그때그때 만듭니다. 쓰지 않는 범위는 테이블을 아예 만들지 않아 메모리를 아낍니다.

항목	단일 페이지 테이블	다단계 페이지 테이블
메모리 사용	주소 범위 전체분을 미리 할당	쓰는 범위만 단계별 할당
변환 비용	메모리 접근 1회	단계 수만큼 메모리 접근
적용	작은 주소 공간	64비트 시스템 표준

x86-64 계열은 보통 4단계 페이지 테이블을 쓰고, Intel 5단계 페이징을 지원하는 CPU는 5단계까지 확장합니다. 이때 가상 주소는 57비트로 늘어, 2의 57제곱인 약 128PB(페타바이트) 공간에 해당합니다(Intel 64 아키텍처 기준). 단계가 늘수록 변환 한 번에 필요한 메모리 접근도 함께 늘어납니다.

변환 색인 버퍼로 변환 비용 줄이기

다단계 구조에는 비용이 따라옵니다. 페이지 테이블이 메모리에 있으므로, 변환만으로도 메모리 접근이 단계 수만큼 듭니다. 여기에 실제 데이터 접근까지 더하면 메모리 참조 횟수가 크게 늘어납니다.

이 비용을 줄이는 장치가 변환 색인 버퍼(Translation Lookaside Buffer, TLB)입니다. TLB는 최근에 끝낸 주소 변환 결과를 담아두는 작은 고속 하드웨어 캐시입니다. 같은 페이지를 다시 찾으면 페이지 테이블을 거치지 않고 TLB에서 곧장 프레임 번호를 얻습니다.

TLB 적중과 실패의 비용 차이는 큽니다. 적중은 캐시 속도라 매우 빠르고, 실패는 페이지 테이블을 메모리에서 읽어야 하므로 느립니다. 적중이 약 1나노초, 실패가 수십에서 100나노초대라는 추정 수치가 흔히 인용됩니다.

접근 패턴이 변환 효율을 좌우합니다. 인접한 주소를 차례로 읽으면 같은 페이지에 머물러 TLB 적중률이 높습니다. 반대로 넓은 영역을 무작위로 건너뛰면 적중률이 떨어져 성능 저하가 커집니다.

접근 패턴	TLB 적중률(추정)	영향
순차 배열 접근	99% 이상	거의 없음
해시 테이블 무작위 접근	80~95%	중간
대규모 랜덤 접근	50~80%	큰 성능 저하

프로세스를 전환하면 가상 주소 공간이 바뀌므로 TLB의 옛 항목은 무효가 됩니다. 그래서 문맥 교환(context switch) 때 TLB를 비우는 비용이 따라옵니다. TLB 항목에 주소 공간 식별자(Address Space Identifier, ASID)를 붙이면 전체를 비우지 않고 프로세스별로 구분해 둘 수 있습니다.

큰 페이지를 쓰면 같은 수의 TLB 항목으로 더 넓은 메모리를 덮습니다. 4KB 페이지로 1024개 항목이 약 4MB를 덮는다면, 2MB짜리 대형 페이지(Huge Page)로는 같은 항목 수로 약 2GB를 덮습니다. 대신 페이지가 커지면 마지막 페이지의 낭비가 늘 수 있습니다.

페이징과 세그먼테이션, 단편화

메모리를 나누는 방식에는 페이징 말고 세그먼테이션(Segmentation)도 있습니다. 세그먼테이션은 코드, 데이터, 스택처럼 의미 단위로 가변 크기 세그먼트를 나눕니다. 논리적 분리는 깔끔하지만 단편화 양상이 페이징과 다릅니다.

기준	페이징	세그먼테이션
분할 단위	고정 크기 페이지(보통 4KB)	가변 크기 세그먼트
분할 기준	크기	의미(코드·데이터·스택)
단편화	내부 단편화	외부 단편화
현대 운영체제	주력	보조적

단편화(Fragmentation)는 메모리를 쓰지 못하고 버리는 현상입니다. 페이징은 요청 크기가 페이지 경계와 안 맞을 때 마지막 페이지의 남는 공간을 버립니다. 이것이 내부 단편화입니다. 예를 들어 5KB를 요청하면 4KB 페이지 두 장이 할당돼 3KB가 낭비됩니다.

세그먼테이션은 가변 크기라 빈 공간이 여기저기 흩어집니다. 전체 빈 공간을 합치면 충분해도, 연속된 큰 덩어리가 없어 할당에 실패할 수 있습니다. 이것이 외부 단편화입니다.

고정 크기 페이지는 어떤 빈 프레임이든 끼워 넣을 수 있어 외부 단편화가 생기지 않습니다. 현대 운영체제가 페이징을 주력으로 쓰는 이유입니다.

요구 페이징과 페이지 폴트

프로세스의 모든 페이지를 처음부터 물리 메모리에 올릴 필요는 없습니다. 요구 페이징(Demand Paging)은 페이지가 실제로 쓰일 때 비로소 메모리에 적재하는 방식입니다. 페이지 테이블의 유효 비트로 그 페이지가 지금 메모리에 있는지를 표시합니다.

없는 페이지에 접근하면 페이지 폴트(Page Fault)가 발생합니다. 이는 오류가 아니라 운영체제에 적재를 요청하는 신호입니다. 운영체제가 개입해 디스크에서 페이지를 가져오고, 빈 프레임이 없으면 교체 알고리즘으로 내보낼 페이지를 고릅니다.

페이지 폴트 처리에는 디스크 접근이 끼므로 비용이 큽니다. 메모리 접근이 나노초 단위라면 디스크 접근은 그보다 수천 배 이상 느립니다(추정). 그래서 폴트 빈도를 낮게 유지하는 것이 성능의 관건입니다.

요구 페이징은 mmap 같은 메모리 맵 파일(memory-mapped file)에서도 그대로 쓰입니다. 파일을 가상 주소 공간에 매핑해두고, 실제로 그 영역을 읽을 때 페이지 폴트로 해당 부분만 적재합니다. 큰 파일을 통째로 올리지 않고 필요한 만큼만 다루는 셈입니다.

페이지 교체와 쓰래싱

물리 메모리가 가득 차면 새 페이지를 올릴 자리를 비워야 합니다. 어떤 페이지를 내보낼지 정하는 것이 페이지 교체 알고리즘입니다. 잘 고를수록 다시 불러오는 폴트가 줄어듭니다.

알고리즘	방식	특징
FIFO(First In First Out)	가장 먼저 들어온 페이지 교체	구현 단순, Belady의 모순 발생
LRU(Least Recently Used)	가장 오래 안 쓴 페이지 교체	적중률 높음, 구현 비용
LFU(Least Frequently Used)	사용 횟수가 가장 적은 페이지 교체	빈도 반영, 과거 인기 페이지 문제
Clock	FIFO에 참조 비트를 더함	LRU 근사, 효율적
OPT(Optimal)	미래에 가장 늦게 쓸 페이지 교체	이론적 최적, 예측 불가라 기준용

LRU는 해시맵과 이중 연결 리스트를 함께 써서 조회, 갱신, 교체를 모두 O(1)에 처리합니다. 리스트는 사용 순서를 유지하고, 해시맵은 임의 키를 바로 찾게 해줍니다. Redis의 키 퇴출 정책에도 오래 안 쓴 키를 먼저 버린다는 같은 발상이 깔려 있습니다.

FIFO에는 프레임을 늘렸는데 오히려 폴트가 증가하는 Belady의 모순이 있습니다. LRU와 OPT는 스택 알고리즘 속성 덕분에 이 모순이 생기지 않습니다. 프레임을 늘렸을 때 항상 폴트가 줄거나 같다는 보장이 있습니다.

메모리가 부족해 폴트만 처리하다 일을 못 하는 상태가 쓰래싱(Thrashing)입니다. 폴트가 늘면 CPU가 노는 것처럼 보여 운영체제가 프로세스를 더 올리고, 그러면 메모리가 더 부족해져 폴트가 폭증합니다. 워킹 셋(Working Set) 모델로 활발히 쓰는 페이지를 메모리에 묶어두거나, 폴트율 상하한으로 프레임 수를 조절해 막습니다.

정리

가상 메모리는 프로세스마다 독립 주소 공간을 줘서 격리와 큰 주소 공간을 동시에 얻습니다. 그 가상 주소를 물리 주소로 바꾸는 핵심 장치가 페이징과 페이지 테이블이며, MMU가 페이지 번호를 프레임 번호로 변환합니다. 페이지 테이블이 커지는 문제는 다단계 구조로, 변환 비용은 TLB로 줄입니다. 메모리에 없는 페이지는 페이지 폴트로 적재하고, 자리가 없으면 교체 알고리즘이 내보낼 페이지를 고릅니다. 폴트가 통제를 벗어나면 쓰래싱이 되므로, 워킹 셋을 메모리에 유지하는 것이 성능의 마지막 방어선입니다.