페이징 — 주소를 번역해 얻은 자유

한 줄 요약

가상 주소를 고정 크기 페이지 단위로 물리 프레임에 대응시키면 외부 단편화가 사라지고, 프로세스마다 독립된 주소 공간을 줄 수 있다.

왜 이게 필요했나

초기 방식은 프로세스마다 연속된 메모리 덩어리를 통째로 주는 것이었다. 이 방식은 곧 외부 단편화에 부딪힌다. 빈 공간의 총합은 충분한데 연속된 조각이 없어 새 프로세스를 못 올리는 상황이다. 압축(compaction)으로 밀어 모을 수는 있지만 그동안 시스템이 멈춘다.

페이징의 통찰은 단순하다. 연속되어야 한다는 요구를 없애자. 주소 공간을 고정 크기(보통 4KB) 페이지로 자르고, 물리 메모리도 같은 크기 프레임으로 자른다. 페이지를 아무 프레임에나 넣고, 어디에 넣었는지만 표에 적어 둔다.

가상 주소 하나가 물리 주소가 되기까지

48비트 주소를 아홉 비트씩 네 조각과 열두 비트 오프셋으로 쪼갠다. 조각마다 한 층의 표에서 다음 표를 찾는다.

흐름 강조 재생 · 다시 보려면 해제 후 선택

조각을 뗀다비트 47-39가 PML4 인덱스, 38-30이 PDPT, 29-21이 PD, 20-12가 PT다. 남은 열두 비트는 페이지 안 위치다.
네 번 읽는다층마다 한 번씩 메모리를 읽어 다음 표의 물리 주소를 얻는다. 마지막 층이 내주는 것이 실제 프레임이다.
오프셋을 붙인다프레임 시작 주소에 열두 비트를 그대로 더한다. 오프셋은 번역되지 않는다.

여기서 구분할 것 주소 하나를 읽으려고 메모리를 네 번 더 읽는 셈이다. 페이지를 통째로 옮겨도 페이지 안 배치가 그대로인 것은 오프셋이 번역되지 않기 때문이다.

잠깐, 예측해 보세요 같은 페이지 안의 두 주소는 서로 다른 프레임에 놓일 수 있을까?

설명 확인 · 채점 없는 자가 점검

없다. 프레임은 페이지 번호로만 정해지고, 오프셋은 그 안의 자리일 뿐이다. 페이지가 통째로 움직이지 반쪽만 움직이지는 않는다.

근거 문서 직접 움직여 보기

어떻게 동작하나

가상 주소는 두 부분으로 나뉜다. 위쪽 비트는 페이지 번호, 아래쪽 비트는 오프셋이다. 페이지 크기가 4KB 라면 오프셋이 12비트다. 주소 변환은 페이지 번호를 페이지 테이블에서 찾아 프레임 번호로 바꾸고, 오프셋은 그대로 붙이는 것이다. 오프셋을 건드리지 않으므로 페이지 안의 상대 위치는 보존된다.

여기서 곧바로 성능 문제가 생긴다. 페이지 테이블은 메모리에 있으므로, 메모리 접근 한 번을 위해 메모리를 두 번 읽는 셈이 된다. 이 문제를 없애는 캐시가 TLB(Translation Lookaside Buffer) 다. 최근 번역 결과를 담아 두고, 적중하면 추가 메모리 접근 없이 곧바로 물리 주소를 얻는다.

실효 접근 시간은 이렇게 계산한다. TLB 접근이 20ns, 메모리 접근이 100ns, TLB 적중률이 80퍼센트라면

적중: 20 + 100 = 120ns
실패: 20 + 100(페이지 테이블) + 100(실제 데이터) = 220ns
실효 접근 시간 = 0.8 곱하기 120 더하기 0.2 곱하기 220 = 140ns

적중률을 98퍼센트로 올리면 122ns 가 된다. 적중률 몇 퍼센트가 전체 성능을 좌우한다는 사실이 여기서 드러난다.

64비트 주소 공간에서는 페이지 테이블 자체가 거대해지므로 다단계 페이지 테이블을 쓴다. 주소를 여러 조각으로 나눠 표를 트리처럼 계층화하고, 실제로 쓰이는 가지만 만든다. x86-64 는 보통 4단계다. 단계가 늘수록 TLB 미스 비용이 커지므로, 큰 메모리를 쓰는 워크로드에서는 페이지 크기를 키우는 거대 페이지(huge page) 가 효과를 낸다. 2MB 페이지를 쓰면 같은 메모리를 512분의 1의 TLB 엔트리로 덮는다.

현장에서 만나는 모습

데이터베이스와 JVM 처럼 큰 힙을 무작위로 훑는 프로그램에서 거대 페이지가 자주 언급되는 이유가 TLB 다. 다만 리눅스의 투명 거대 페이지(THP)는 조각 모음 지연 때문에 데이터베이스에서 오히려 꼬리 지연을 만든다는 보고가 많아, PostgreSQL 이나 Redis 문서가 always 대신 madvise 나 비활성화를 권하는 경우가 있다. 좋은 기능이라도 워크로드의 접근 패턴에 따라 결론이 갈린다는 좋은 예다.

TLB 가 있는 경우와 없는 경우

같은 주소를 두 번 읽을 때 무엇이 달라지는지 견준다.

TLB 적중가상 페이지 번호로 물리 프레임을 곧바로 얻는다. 표를 한 번도 읽지 않는다.
TLB 실패네 층을 차례로 읽어 프레임을 구한 뒤 그 결과를 TLB 에 넣는다. 다음 접근부터 빨라진다.

여기서 구분할 것 TLB 는 주소 변환 결과를 담지 데이터를 담지 않는다. 캐시 적중률이 높은데도 느리다면 데이터 캐시가 아니라 TLB 를 먼저 의심한다.

잠깐, 예측해 보세요 큰 배열을 페이지 크기보다 큰 간격으로 건너뛰며 읽으면 왜 느려질까?

설명 확인 · 채점 없는 자가 점검

접근마다 다른 페이지에 닿아 TLB 가 계속 빗나가기 때문이다. 데이터는 캐시에 있어도 주소를 번역하느라 매번 네 번을 더 읽는다.

근거 문서

이어지는 퀴즈에서 확인할 것

주소가 어떻게 나뉘는지, TLB 적중률이 실효 접근 시간을 어떻게 바꾸는지 계산할 수 있는지 확인한다.