#CS#OS#Memory#Paging
페이징: 고정 크기 블록으로 메모리 분할
메모리를 바둑판처럼 똑같은 크기로 잘라서 관리하자. 외부 단편화를 해결한 현대 OS의 표준 기술.
2025년 3월 12일
Codemapo
메모리를 바둑판처럼 똑같은 크기로 잘라서 관리하자. 외부 단편화를 해결한 현대 OS의 표준 기술.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.
미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?
이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?
매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.
메모리 관리에 대해 공부하면서 제일 먼저 마주친 문제는 "프로그램 크기가 제각각인데 어떻게 메모리에 집어넣지?"였습니다. 세그먼테이션(Segmentation)을 봤을 때는 "오, 프로그램을 코드, 데이터, 스택 이렇게 의미 단위로 나누는 게 논리적이네"라고 생각했습니다. 하지만 막상 구현해보니 외부 단편화(External Fragmentation)라는 괴물이 튀어나왔습니다.
100MB 프로그램을 넣으려는데, 메모리 여기저기 50MB씩 빈 공간은 있는데 연속된 100MB는 없는 겁니다. 마치 좁은 주차장에 차를 대충 대놔서 공간은 많은데 새 차를 못 넣는 상황처럼요. 컴팩션(Compaction)으로 메모리를 다시 정렬할 수도 있지만, 그건 프로그램들을 통째로 복사해서 옮기는 거라 성능상 너무 비쌉니다.
그래서 받아들인 아이디어가 페이징(Paging)입니다. "애초에 메모리를 똑같은 크기로 잘라놓고, 프로그램도 똑같은 크기로 잘라서 빈 곳 아무 데나 넣자." 처음엔 이게 말이 되나 싶었습니다. 프로그램을 찢어놓으면 어떻게 실행하지? CPU가 코드를 순서대로 읽어야 하는데 조각이 여기저기 흩어져 있으면 어쩌지? 하지만 결국 이 방식이 현대 운영체제의 표준이 됐습니다. 그 과정을 이해하니 "아, 이래서 페이징이구나" 하고 무릎을 쳤습니다.
페이징 설명을 처음 봤을 때 이해가 안 갔던 게 "논리 주소(Logical Address)"와 "물리 주소(Physical Address)"의 차이였습니다. 교과서에선 "CPU가 보는 주소는 논리 주소고, 실제 RAM에 저장되는 주소는 물리 주소다"라고만 나와 있었습니다. 솔직히 그냥 같은 거 아닌가 싶었습니다.
제가 짠 코드에서 int a = 10;이라고 쓰면, a는 메모리 어딘가에 저장됩니다. 그럼 그 주소가 진짜 주소 아닌가요? 왜 "논리"니 "물리"니 하며 나누는 걸까요?
여기서 깨달은 건, 프로그램은 자기가 메모리 전체를 독차지하고 있다고 착각한다는 점이었습니다. 프로세스 A는 "내 메모리는 0번지부터 시작한다"고 생각하고, 프로세스 B도 똑같이 "내 메모리는 0번지부터 시작한다"고 생각합니다. 만약 둘 다 진짜 0번지에 접근하면? 서로 덮어씌우고 충돌합니다.
그래서 운영체제는 각 프로세스에게 "가상의 주소 공간"을 줍니다. 프로세스 A는 논리 주소 0번부터 시작하지만, 실제 RAM(물리 메모리)에선 52번 프레임에 저장됩니다. 프로세스 B의 논리 주소 0번은 물리 메모리의 150번 프레임에 저장되고요. 이렇게 하면 프로그램들은 서로 충돌 없이 각자 0번지부터 시작하는 착각 속에서 평화롭게 돌아갑니다.
그럼 이 "논리 주소 → 물리 주소" 변환은 누가 해줄까요? 바로 MMU(Memory Management Unit)입니다.
CPU가 "논리 주소 1024번지 읽어와"라고 명령하면, MMU가 가로챕니다. 그리고 페이지 테이블(Page Table)이라는 지도를 펼쳐 봅니다.
페이지 테이블은 이렇게 생겼습니다:
논리 페이지 번호 → 물리 프레임 번호
0 → 52
1 → 150
2 → 37
3 → 200
...
CPU가 "논리 주소 1024번지"를 요청하면, MMU는 이 주소를 두 부분으로 쪼갭니다:
그리고 페이지 테이블에서 "논리 페이지 0번은 물리 프레임 52번"이라는 걸 찾아냅니다. 최종 물리 주소는:
CPU는 이 모든 과정을 모릅니다. 그냥 "1024번지 내용 줘"라고 했을 뿐인데, MMU가 알아서 213,024번지에서 데이터를 가져다 줍니다. 이게 페이징의 핵심입니다.
이 비유가 머릿속에 확 들어왔습니다: 도서관에서 책을 빌릴 때를 생각해보세요. 저는 "해리포터 1권 줘"라고 말합니다(논리 주소). 사서는 뒤에서 "해리포터 1권은 3층 B-52 서가에 있네"라고 찾아서(페이지 테이블 조회) 가져다 줍니다(물리 주소 접근). 저는 책이 실제로 어디 있는지 몰라도 됩니다. 사서(MMU)가 다 해주니까요.
그럼 페이지를 몇 KB로 나눠야 할까요? 대부분의 운영체제는 4KB를 기본값으로 씁니다. 왜 하필 4KB일까요?
너무 작으면 어떻게 될까요? 예를 들어 페이지 크기를 1KB로 하면, 1GB 프로그램은 1,048,576개의 페이지로 쪼개집니다. 페이지 테이블에 100만 개 넘는 항목이 생기는 겁니다. 페이지 테이블 자체가 엄청난 메모리를 먹어버립니다.
반대로 너무 크면? 예를 들어 페이지 크기를 1MB로 하면, 10KB짜리 작은 프로그램도 1MB 페이지 하나를 통째로 차지합니다. 990KB가 낭비됩니다. 이게 내부 단편화(Internal Fragmentation)입니다.
4KB는 이 둘 사이의 타협점입니다. 메모리 낭비도 크지 않고, 페이지 테이블 크기도 관리 가능한 수준입니다.
최근엔 RAM이 기가바이트 단위로 늘어나면서 Huge Pages(2MB, 1GB)를 쓰는 경우도 많아졌습니다. 데이터베이스나 가상머신처럼 메모리를 엄청 먹는 프로그램들은 Huge Pages를 쓰면 페이지 테이블 크기가 줄어들어서 성능이 빨라집니다.
리눅스에서 Transparent Huge Pages (THP) 설정을 튜닝하는 이유가 여기 있습니다. 몽고DB 같은 DB를 돌릴 때 THP를 끄라는 권고를 본 적 있으신가요? 이건 DB가 작은 단위로 메모리를 관리하는데, OS가 멋대로 큰 페이지로 합쳐버리면 오히려 성능이 나빠지기 때문입니다.
4KB 페이지로 나눠도, 64비트 시스템에서 프로세스마다 가질 수 있는 가상 주소 공간은 엄청납니다(이론상 2^64바이트). 만약 페이지 테이블을 1단계로만 만들면 크기가 너무 커집니다.
그래서 실제론 다단계 페이지 테이블(Multi-level Page Table)을 씁니다. 책의 목차처럼 계층적으로 나누는 겁니다.
예를 들어 2단계 페이지 테이블은 이렇게 동작합니다:
논리 주소: | 상위 10비트 | 하위 10비트 | 오프셋 12비트 |
└─ 1단계 인덱스 ─ 2단계 인덱스 ─ 페이지 내 위치 ─┘
이렇게 하면 사용하지 않는 주소 공간에 대해선 중간 테이블 자체를 만들지 않아도 됩니다. 메모리를 많이 아낄 수 있습니다.
현대 x86-64 아키텍처는 4단계 페이지 테이블을 씁니다(PML4 → PDPT → PD → PT). 복잡해 보이지만, 실제로 사용하는 메모리 공간만 테이블을 만들기 때문에 효율적입니다.
그런데 생각해보면, CPU가 메모리 접근할 때마다 페이지 테이블을 뒤지면 느리지 않을까요? 특히 다단계 페이지 테이블이면 4번이나 메모리를 읽어야 합니다.
맞습니다. 그래서 TLB(Translation Lookaside Buffer)라는 게 있습니다. 페이지 테이블의 캐시라고 보면 됩니다.
MMU는 주소 변환을 할 때 먼저 TLB를 확인합니다. "논리 페이지 5번은 물리 프레임 몇 번이었지?" TLB에 있으면(TLB Hit) 바로 번역합니다. 없으면(TLB Miss) 페이지 테이블을 뒤져서 찾고, 그 결과를 TLB에 저장해둡니다.
프로그램은 지역성(Locality)이 있습니다. 한번 접근한 메모리 근처를 또 접근할 확률이 높습니다. 그래서 TLB 히트율은 보통 90% 이상 나옵니다. 덕분에 페이지 테이블을 매번 뒤지지 않아도 됩니다.
리눅스에서 cat /proc/cpuinfo | grep -i tlb를 치면 CPU의 TLB 정보를 볼 수 있습니다. 제 맥북은 L1 TLB가 데이터용 64 엔트리, 명령어용 128 엔트리로 나뉘어 있더군요.
논리 주소를 물리 주소로 바꾸는 과정을 코드로 짜보면 이해가 더 쉽습니다.
PAGE_SIZE = 4096 # 4KB
# 페이지 테이블 - 논리 페이지 → 물리 프레임
page_table = {
0: 52,
1: 150,
2: 37,
3: 200,
}
def translate_address(logical_address):
# 논리 주소를 페이지 번호와 오프셋으로 나눔
page_number = logical_address // PAGE_SIZE
offset = logical_address % PAGE_SIZE
# 페이지 테이블 조회
if page_number not in page_table:
raise Exception(f"Page Fault: Page {page_number} not in memory")
frame_number = page_table[page_number]
# 물리 주소 계산
physical_address = frame_number * PAGE_SIZE + offset
return physical_address
# 테스트
logical = 1024 # 논리 주소 1024번지
physical = translate_address(logical)
print(f"논리 주소 {logical} → 물리 주소 {physical}")
# 출력 - 논리 주소 1024 → 물리 주소 213024
logical = 5000 # 논리 페이지 1번 내부
physical = translate_address(logical)
print(f"논리 주소 {logical} → 물리 주소 {physical}")
# 출력 - 논리 주소 5000 → 물리 주소 614792 (150 * 4096 + 904)
이 코드를 보니 "아, 그냥 나눗셈이랑 곱셈이구나" 하고 와닿았습니다. MMU도 결국 이런 식으로 하드웨어로 구현된 겁니다.
위 코드에서 page_table에 없는 페이지를 요청하면 예외가 발생합니다. 실제 운영체제에선 이걸 페이지 폴트(Page Fault)라고 부릅니다.
페이지 폴트가 발생하면 운영체제가 끼어듭니다:
이게 바로 가상 메모리(Virtual Memory)의 기본 원리입니다. RAM보다 큰 프로그램을 돌릴 수 있는 이유입니다. 자주 쓰는 페이지만 RAM에 두고, 안 쓰는 건 디스크로 쫓아냅니다.
물론 페이지 폴트는 디스크 I/O를 동반하므로 느립니다. 페이지 폴트가 너무 자주 일어나면 스래싱(Thrashing)이 발생합니다. 프로그램이 실제 작업보다 페이지를 디스크에서 가져오는 데 시간을 더 씁니다. RAM이 부족할 때 컴퓨터가 느려지는 이유입니다.
제가 C로 프로그램 짤 때 malloc(1024)를 호출하면 메모리가 할당됩니다. 이게 페이징과 어떻게 연결될까요?
malloc은 사용자 영역에서 돌아가는 라이브러리 함수입니다. 작은 메모리 요청은 미리 받아놓은 힙(Heap)에서 나눠주지만, 큰 메모리가 필요하면 시스템 콜을 호출합니다.
리눅스에선 mmap() 또는 brk() 시스템 콜이 호출됩니다. 운영체제는 프로세스의 가상 주소 공간에서 빈 페이지들을 찾아서 "여기 쓸 수 있어"라고 알려줍니다. 이때 실제 물리 메모리는 아직 할당되지 않습니다.
진짜 물리 메모리는 처음으로 그 페이지에 쓸 때 할당됩니다. 이걸 지연 할당(Lazy Allocation) 또는 Copy-on-Write라고 합니다. 메모리를 요청만 하고 안 쓰는 경우가 많으니, 실제로 쓸 때만 할당하는 겁니다.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main() {
printf("프로세스 시작. PID: %d\n", getpid());
getchar(); // 메모리 할당 전
// 100MB 요청
char *ptr = malloc(100 * 1024 * 1024);
printf("100MB malloc 완료\n");
getchar(); // 할당 직후 (아직 물리 메모리 안 씀)
// 실제로 쓰기
for (int i = 0; i < 100 * 1024 * 1024; i++) {
ptr[i] = 'A';
}
printf("100MB 쓰기 완료\n");
getchar(); // 쓰기 후 (이제 물리 메모리 사용)
free(ptr);
return 0;
}
이 프로그램을 돌리면서 다른 터미널에서 ps aux | grep [프로세스명]으로 메모리 사용량을 보면, malloc 직후엔 RSS(실제 물리 메모리)가 거의 안 늘어나다가, 쓰기를 시작하면 확 늘어나는 걸 볼 수 있습니다.
제가 서버 개발하면서 OOM(Out of Memory) 에러를 처음 만났을 때, "어? 메모리 충분한데 왜 죽지?"라고 생각했습니다. 알고 보니 스왑(Swap) 공간도 다 차서 새로운 페이지를 할당할 수 없었던 겁니다.
도커 컨테이너를 돌릴 때도 --memory 옵션으로 메모리 제한을 걸 수 있는데, 이것도 결국 cgroup을 통해 페이지 개수를 제한하는 겁니다.
Kubernetes에서 Pod의 메모리 사용량을 모니터링할 때, working set이라는 지표를 봅니다. 이게 실제로 활발하게 쓰이는 페이지들의 집합입니다. 전체 할당된 메모리가 아니라, 진짜 필요한 메모리를 의미합니다.
결국 페이징을 이해하니, "메모리 부족" 에러가 날 때 뭘 봐야 하는지, 어디를 튜닝해야 하는지 감이 오기 시작했습니다.
페이징의 단점으로 항상 언급되는 게 내부 단편화입니다. 마지막 페이지가 꽉 안 채워져서 공간이 낭비된다는 겁니다.
10KB 프로그램이라면 4KB × 3 = 12KB를 차지하고, 2KB가 낭비됩니다. 비율로 보면 20%나 됩니다. 심각해 보입니다.
하지만 생각해보세요. 요즘 프로그램은 MB, GB 단위입니다. 100MB 프로그램이라면 평균적으로 2KB 낭비입니다. 비율로 0.002%입니다. 거의 무시할 만합니다.
반면 세그먼테이션의 외부 단편화는 달랐습니다. 100MB 빈 공간이 있는데 50MB씩 두 조각으로 나뉘어 있으면, 70MB 프로그램은 아예 못 넣습니다. 이게 진짜 문제였습니다.
그래서 현대 운영체제는 페이징을 선택했습니다. "완벽하진 않지만, 가장 실용적인 선택"이라고 받아들였습니다.
페이징은 메모리를 고정 크기 조각(Frame)으로 나누고, 프로그램도 똑같은 크기 조각(Page)으로 나눠서 관리하는 기법입니다.
핵심은 논리 주소와 물리 주소를 분리한 것입니다. 프로그램은 0번지부터 시작한다고 착각하고, 실제 RAM 어디에 저장되는지 몰라도 됩니다. MMU가 페이지 테이블을 보고 주소를 번역해줍니다.
페이지 크기는 보통 4KB입니다. 너무 작으면 페이지 테이블이 커지고, 너무 크면 내부 단편화가 심해집니다. 요즘엔 큰 프로그램을 위해 Huge Pages(2MB, 1GB)도 씁니다.
TLB는 페이지 테이블의 캐시로, 주소 변환 속도를 높입니다. 프로그램의 지역성 덕분에 히트율이 높습니다.
페이징을 이해하니, malloc이 어떻게 동작하는지, OOM 에러가 왜 나는지, 메모리 튜닝을 어떻게 해야 하는지 보이기 시작했습니다. 결국 운영체제의 모든 메모리 관리는 페이징을 기반으로 돌아갑니다. 이걸 이해하지 않고는 시스템 프로그래밍을 할 수 없다는 걸 받아들였습니다.