왜 가상 메모리가 필요한가?
운영체제를 처음 공부하면 거의 예외 없이 페이지 테이블(Page Table)부터 등장한다.
페이지(Page), PTE(Page Table Entry), MMU(Memory Management Unit), TLB(Translation Lookaside Buffer)...
생소한 용어가 한꺼번에 쏟아지고 그저 페이지 테이블의 구조를 외우기 시작한다. 하지만 정작 가장 중요한 질문은 거의 하지 않는다.
왜 이런 복잡한 구조를 만들었을까?
사실 페이지 테이블은 목적이 아니다. 운영체제가 해결하고 싶었던 문제를 해결하기 위한 수단이다. 그리고 이 수단은 어느 날 갑자기 하늘에서 떨어진 것이 아니다. 수십 년에 걸쳐 여러 아이디어가 등장하고, 경쟁하고, 패배하고, 사라지면서 지금의 모습으로 다듬어졌다. 이 글에서는 페이지 테이블의 구조를 외우기 전에, 먼저 역사를 따라가 보려고 한다.
초창기 컴퓨터는 메모리를 어떻게 썼고, 어떤 문제에 부딪혔으며, 그 문제를 풀기 위해 어떤 해결책들이 등장했다가 사라졌고, 왜 결국 가상 메모리(Virtual Memory)와 페이징(Paging)이 살아남았는지. 이 흐름을 이해하고 나면, 페이지 테이블은 자연스럽게 "그럴 수밖에 없었던 결론"으로 보이게 된다.
0. 10분 요약
바쁜 사람을 위해 결론부터 적는다.
- 아주 옛날 컴퓨터는 프로그램이 물리 메모리 주소를 직접 사용했다.
- 여러 프로그램을 동시에 올리기 시작하자, 서로의 메모리를 침범하는 격리(Isolation) 문제가 터졌다.
- 첫 번째 해결책은 베이스/바운드 레지스터(Base & Bound)였다. 간단했지만 프로그램 전체가 메모리에 연속으로 통째로 올라가야 했다.
- 다음 주인공은 세그먼테이션(Segmentation)이었다. 코드/데이터/스택을 논리적 단위로 쪼개 관리했지만, 외부 단편화(External Fragmentation)라는 고질병에 시달렸다.
- 결국 승자는 페이징(Paging)이었다. 메모리를 고정 크기 조각으로 잘라 단편화 문제를 근본적으로 해결했다.
- 세그먼테이션은 패배했지만 완전히 사라지지는 않았다. 오늘날 x86-64의 플랫 메모리 모델(Flat Memory Model)과 FS/GS 레지스터에 그 흔적만 남아 있다.
그리고 페이징을 가능하게 하는 핵심 자료구조가 바로 페이지 테이블(Page Table)이다. 페이지 테이블을 제대로 이해하려면, 먼저 왜 주소를 숨겨야만 했는지 그 역사를 알아야 한다. 지금부터 그 이야기를 처음부터 해보자.
1. 태초에 메모리는 하나였다
초기의 컴퓨터의 모습을 상상 해보자. 이 시절 컴퓨터에는 한 번에 단 하나의 프로그램만 올라갔다. 메모리 구조는 극단적으로 단순했다.
0x0000 ---------------- 운영체제(아주 작은) 0x1000 ---------------- 내 프로그램 0xFFFF ----------------
프로그램은 자기가 쓸 메모리 주소를 직접 알고 있었다.
"0x2000번지에 변수 x를 두고, 0x3000번지부터 배열을 쓰자."
이렇게 프로그래머(혹은 컴파일러)가 물리 주소를 콕 집어 코드에 박아 넣었다. CPU는 명령대로 그 주소를 그대로 메모리에 전달했다.
int x = *(int *)0x2000;
CPU 입장에서는 이게 전부였다.
"0x2000에서 값을 읽어와."
CPU는 단순하다.
그 주소가 누구의 메모리인지, 커널인지, 사용자 프로그램인지, 전혀 관심이 없다. 그냥 지정된 물리 주소를 읽고 쓸 뿐이다. 이 시절에는 이게 문제가 되지 않았다.
어차피 프로그램은 하나뿐이었으니까. 충돌할 상대가 없었다.
2. 컴퓨터가 비싸지자 문제가 시작됐다
문제는 엉뚱한 곳에서 시작됐다. 컴퓨터가 너무 비쌌다.
이 비싼 기계가 디스크에서 데이터를 읽어오는 그 시간 동안 CPU가 놀고 있는 것이 너무 아까웠다.
프로그램 A: 디스크 읽는 중... (CPU 놀고 있음) CPU: 😴
그래서 사람들은 생각했다.
"한 프로그램이 입출력을 기다리는 동안, 다른 프로그램을 돌리면 되잖아?"
이것이 멀티 프로그래밍(Multiprogramming)이다. 여러 프로그램을 동시에 메모리에 올려두고, CPU를 쉴 틈 없이 돌린다.
0x0000 ---------------- 운영체제 0x1000 ---------------- Process A 0x4000 ---------------- Process B 0x8000 ---------------- Process C
아이디어는 훌륭했으나 여기서부터 문제가 시작된다.
3. 격리(Isolation): 운영체제가 가장 먼저 풀어야 했던 문제
이제 메모리에 여러 프로그램이 함께 살게 됐다. 그런데 1장에서 말했듯, 이 시절 프로그램은 물리 주소를 직접 사용한다.
Process A가 이런 코드를 실행했다고 하자.
*(int *)0x8000 = 1234;
CPU는 아무 생각이 없다.
물리주소 0x8000
해당 주소에 그대로 값을 써 버린다. 그런데 그곳은 Process C의 메모리였다. Process C는 자기도 모르는 사이에 데이터가 망가진다.
이번엔 이런 코드라면?
*(int *)0x0000 = 0;
운영체제 메모리가 박살난다. 컴퓨터 전체가 멈춘다.
결국 하나의 프로그램이 다른 프로그램은 물론, 운영체제까지 마음대로 망가뜨릴 수 있다.
실수라면 그나마 다행이지만 악의적인 프로그램이라면 의도적으로 다른 프로그램의 비밀번호를 훔치거나 데이터를 조작할 수도 있다.
많은 사람들이 운영체제의 핵심 역할을 "스케줄링"이라고 생각한다. 뭐, 물론 그것도 중요하다.
하지만 멀티프로그래밍이 등장한 순간, 운영체제가 가장 먼저 풀어야 했던 문제는 따로 있었다.
격리(Isolation)
프로세스는 서로 독립되어야 한다.
Process A: "내 메모리는 나만 건드린다." Process B: "내 메모리도 나만 건드린다." Kernel: "너희 둘 다 내 메모리는 절대 건드리지 마."
이것이 운영체제가 반드시 지켜야 하는 가장 근본적인 약속이다. 문제는 명확해졌다.
이제 해결책을 찾아야 한다. 그리고 컴퓨터 과학자들은 수십 년에 걸쳐 여러 답을 내놓는다.
4. 첫 번째 해결책: 베이스와 바운드 (Base & Bound)
가장 먼저 떠올릴 수 있는 아이디어는 이거다.
"프로그램이 쓰는 주소에 적당한 값을 더해서, 진짜 위치를 옮겨버리면 어떨까?"
이것을 재배치(Relocation)라고 한다. CPU 안에 레지스터 두 개를 둔다.
- 베이스(Base) 레지스터: 이 프로그램이 실제로 시작하는 물리 주소
- 바운드(Bound) 레지스터: 이 프로그램이 쓸 수 있는 최대 크기(한계)
이제 프로그램은 자기가 항상 0번지부터 시작한다고 착각하며 코드를 짠다. CPU는 프로그램이 내놓는 주소에 베이스를 더해 진짜 물리 주소를 만든다.
물리 주소 = Base + 프로그램이 요청한 주소 조건: 요청한 주소 < Bound (아니면 에러!)
예를 들어 Process A의 베이스가 0x1000이라면,
Process A 요청: 0x0050 ↓ (Base 0x1000 더하기) 실제: 0x1050
이 방식의 장점은 두 가지다.
- 재배치: 프로그램은 항상 0번지 기준으로 작성하면 되고, 운영체제가 베이스만 바꾸면 메모리 어디든 올릴 수 있다.
- 보호: 바운드를 넘는 주소에 접근하면 CPU가 막아준다. 옆집 메모리를 못 건드린다.
드디어 격리가 가능해졌다! 그러나 이는 곧 한계가 드러난다. 베이스/바운드는 프로그램 전체를 하나의 덩어리로 본다.
이 말은 곧,
- 프로그램 전체가 물리 메모리에 빈틈없이 연속으로 올라가야 한다.
- 프로그램이 통째로 메모리에 올라와 있어야 한다. (일부만 올리는 게 안 됨)
- 코드 영역과 데이터 영역에 서로 다른 권한을 줄 수 없다. 전부 한 덩어리니까.
- 두 프로그램이 같은 코드를 공유하기도 어렵다.
특히 첫 번째 문제가 골치 아팠다. 프로그램들이 올라왔다 내려가기를 반복하면, 메모리 곳곳에 구멍이 생긴다.
이 구멍 문제는 잠시 뒤 세그먼테이션에서 더 본격적으로 폭발한다.
5. 두 번째 주인공: 세그먼테이션 (Segmentation)
베이스/바운드의 한계는 분명했다. 프로그램을 하나의 덩어리로만 봤다는 것.
그런데 생각해 보면 프로그램은 사실 성격이 다른 여러 부분으로 나뉜다.
코드(Text) : 읽기/실행만. 바뀌면 안 됨. 데이터(Data) : 읽기/쓰기. 전역 변수 등. 힙(Heap) : 동적으로 자라남. 스택(Stack) : 위에서 아래로 자라남.
성격이 다르니, 따로 관리하면 어떨까? 이것이 세그먼테이션(Segmentation)의 핵심 아이디어다. 베이스/바운드가 한 쌍이었다면, 세그먼테이션은 각 논리적 조각(세그먼트)마다 베이스/바운드를 따로 둔다.
| 세그먼트 | Base | Bound(크기) |
|---|---|---|
| Code | 0x10000 | 0x2000 |
| Data | 0x50000 | 0x1000 |
| Stack | 0x90000 | 0x4000 |
이제 주소는 두 부분으로 나뉜다.
(어느 세그먼트인가) + (그 안에서 얼마나 떨어졌는가)
즉 (세그먼트 번호, 오프셋) 꼴이다.
CPU는 세그먼트 번호로 위 표(세그먼트 테이블)를 뒤져 베이스를 찾고, 거기에 오프셋을 더해 물리 주소를 만든다.
가상 주소: (Data 세그먼트, 0x100) ↓ Data의 Base(0x50000) + 0x100 ↓ 물리 주소: 0x50100
이 방식은 강력했다.
- 세그먼트마다 다른 권한을 줄 수 있다. (코드는 실행만, 데이터는 읽기/쓰기)
- 세그먼트마다 따로 메모리에 올리고 내릴 수 있다.
- 스택과 힙이 각자 알아서 자랄 수 있다.
- 같은 코드 세그먼트를 여러 프로세스가 공유할 수도 있다.
그래서 한 시대를 풍미했다. 대표적으로 인텔 x86이 세그먼트를 전면에 내세웠다.
C 언어를 배운 사람이라면 한 번쯤 들어봤을 CS, DS, SS, ES 같은 세그먼트 레지스터가 바로 이것이다.
CS (Code Segment) : 코드는 여기 DS (Data Segment) : 데이터는 여기 SS (Stack Segment) : 스택은 여기
세그먼테이션은 한동안 메모리 관리의 정답처럼 보였다. 한동안은.
6. 세그먼테이션의 몰락: 외부 단편화 (External Fragmentation)
세그먼테이션에는 치명적인 약점이 하나 있었다.
세그먼트는 크기가 제각각이라는 것이다. 코드는 8KB, 데이터는 1.5KB, 스택은 16KB...
이렇게 가변 크기 조각들을 물리 메모리에 욱여넣다 보면, 시간이 지날수록 끔찍한 일이 벌어진다.
처음엔 깔끔하다.
[ A코드 ][ A데이터 ][ B코드 ][ B데이터 ][ 빈 공간 ]
그런데 프로그램 A가 끝나서 내려간다.
[ 빈공간 ][ 빈공간 ][ B코드 ][ B데이터 ][ 빈 공간 ]
이제 새 프로그램 C(10KB짜리)를 올리려는데...
빈 공간이 여기 6KB, 저기 5KB로 조각조각 흩어져 있다.
총합은 11KB라서 충분한데,
연속된 10KB 공간이 없어서 못 올린다!
[ 6KB 빈공간 ][ B코드 ][ B데이터 ][ 5KB 빈공간 ] C(10KB)를 어디에도 못 넣음. 😱
이렇게 "총량은 충분한데 흩어져 있어서 못 쓰는" 현상을 외부 단편화(External Fragmentation)라고 부른다. 세그먼트는 통째로 연속된 공간에 들어가야 하기 때문에, 이 문제를 피할 수 없었다. 해결책이 없진 않았다.
흩어진 세그먼트를 한쪽으로 싹 밀어 모으는 압축(Compaction). 하지만 이건 메모리를 통째로 복사하는 엄청나게 비싼 작업이다. 게다가 압축하는 동안 시스템이 멈춘다. 세그먼테이션은 점점 한계에 부딪혔다.
가변 크기로 관리하는 한, 외부 단편화는 운명이다.
그렇다면 애초에 모든 조각의 크기를 똑같이 만들면 어떨까?
7. 세그먼테이션은 졌지만 사라지지 않았다: 흔적과 플랫 메모리 모델
세그먼테이션은 결국 페이징(곧 등장한다)에게 메모리 관리의 왕좌를 내줬다. 하지만 완전히 사라진 것은 아니다. 오늘날 우리가 쓰는 x86-64 CPU에도 세그먼트 레지스터는 여전히 존재한다. 다만 그 역할이 거의 무력화되었을 뿐이다. 현대 운영체제는 세그먼트를 이렇게 설정한다.
모든 세그먼트: Base = 0 한계 = 주소 공간 전체
즉, 모든 세그먼트가 0번지에서 시작해서 메모리 전체를 덮는다. 세그먼트로 메모리를 쪼개는 게 아니라, "세그먼트가 없는 것처럼" 만들어버린 것이다. 이렇게 세그먼트를 사실상 무효화해서, 마치 하나의 거대하고 평평한 주소 공간만 있는 것처럼 보이게 하는 방식을 플랫 메모리 모델(Flat Memory Model)이라고 부른다.
오늘날 우리가 "주소 공간"을 하나의 쭉 이어진 직선으로 상상하는 것은, 바로 이 플랫 모델 덕분이다. 재미있게도 세그먼트 레지스터 중 일부는 아직도 현역이다.
FS, GS 레지스터 → 스레드 지역 저장소(TLS), 커널의 CPU별 데이터 등에 여전히 사용됨
왕좌에서는 내려왔지만, 구석에서 조용히 다른 일을 하고 있는 것이다.
뭐, 사실 낭만이 있어서 남겨둔게 아니고 CPU도 결국 기판 위의 소프트웨어기 때문에 못버려서 레거시로 남아있는거지 현대 프로세서는 이런 개념 자체가 없는 경우도 있다.
대표적으로 지금 공부하고 있는 risc-v도 이에 해당된다.
8. 진짜 승자: 페이징 (Paging)
세그먼테이션의 마지막 질문은 이거였다.
"애초에 모든 조각의 크기를 똑같이 만들면 어떨까?"
바로 이 아이디어가 페이징(Paging)이다.
핵심은 단순하다. 가상 메모리와 물리 메모리를 모두 똑같은 크기의 작은 조각으로 자른다.
- 가상 메모리의 조각 → 페이지(Page)
- 물리 메모리의 조각 → 프레임(Frame)
조각 크기는 보통 4096바이트(4KB)로 통일한다.
가상 메모리 물리 메모리(RAM) +----------+ +----------+ | Page 0 | | Frame 0 | +----------+ +----------+ | Page 1 | | Frame 1 | +----------+ +----------+ | Page 2 | | Frame 2 | +----------+ +----------+ ... ...
이제 운영체제가 할 일은, "어느 페이지가 어느 프레임에 들어갔는지"를 표로 기록하는 것뿐이다.
여기서 마법이 일어난다. 모든 조각의 크기가 같으니, 페이지는 비어 있는 아무 프레임에나 들어갈 수 있다. 심지어 연속될 필요도 전혀 없다.
가상에서는 이어져 있지만... Page 0, Page 1, Page 2 실제 물리에서는 흩어져 있어도 됨! Frame 7, Frame 2, Frame 9
이게 왜 위대한가? 외부 단편화가 사라진다.
세그먼테이션을 괴롭히던 "연속된 빈 공간이 없어서 못 올림" 문제가 원천적으로 없어진다. 빈 프레임이 어딘가에 하나라도 있으면, 거기에 페이지 하나를 넣으면 되니까.
물론 완벽하진 않다. 예를 들어 4KB 페이지에 데이터를 4097바이트 쓰려면 페이지 두 개가 필요하고, 두 번째 페이지는 거의 비게 된다. 이렇게 페이지 안쪽에 생기는 약간의 낭비를 내부 단편화(Internal Fragmentation)라고 한다.
하지만 이건 외부 단편화에 비하면 귀여운 수준이고 충분히 감당할 만했다. 그래서 페이징은 세그먼테이션을 누르고 현대 운영체제의 표준이 되었다.
9. 모든 프로그램은 자기만의 세상을 가진다
페이징을 도입하면 또 하나의 강력한 선물이 따라온다.
프로그램에게 진짜 주소를 알려주지 않아도 된다는 것.
은행을 떠올려 보자. 손님에게 실제 금고 위치를 알려주지 않는다.
손님이 보는 것: "금고 1번, 금고 2번, 금고 3번" 직원만 아는 것: 실제 금고가 건물 어디에 있는지
메모리도 똑같다. 프로그램에게는 가짜 주소를 준다. 운영체제와 하드웨어만 진짜 주소를 안다.
이 가짜 주소가 바로
가상 주소(Virtual Address)
이고, 진짜 주소가
물리 주소(Physical Address)
다.
그 결과, 모든 프로그램은 이런 세상을 본다.
0x00000000 ... 0x10000000 ... 0xFFFFFFFF
처음부터 끝까지, 온전히 자기 혼자만 쓰는 깨끗한 주소 공간. 신기한 점은 Process A도 0x1000을 쓰고, Process B도 0x1000을 쓴다는 것이다.
둘 다 같은 주소를 쓰지만, 실제 RAM은 전혀 다르다.
Process A Virtual 0x1000 → Physical 0x81234000 Process B Virtual 0x1000 → Physical 0x91A78000
서로 다른 물리 메모리를 가리킨다. 그리고 프로그램은 이 사실을 절대 알 수 없다. 각자 자기가 메모리를 통째로 독차지하고 있다고 믿는다. 이로써 3장에서 제기했던 격리 문제가 완벽하게 풀린다. A의 페이지 테이블에는 B의 프레임이 아예 없으니, A는 B의 메모리를 털어 먹는 것이 불가능하다.
10. 누가 주소를 바꾸는가? — MMU
그렇다면 누가 0x1000을 0x81234000으로 바꿔주는 걸까?
매번 운영체제(소프트웨어)가 끼어들어 계산한다면 너무 느릴 것이다. 그래서 이 일은 하드웨어가 한다. CPU 안에 MMU(Memory Management Unit)라는 전용 회로가 있다.
프로그램이
load 0x1000
을 실행하면, 실제로는 이런 과정이 자동으로 일어난다.
load 가상 주소 ↓ MMU (페이지 테이블을 보고 변환) ↓ 물리 주소 ↓ RAM
즉, 프로그램은 평생 물리 주소를 보지 못한다. CPU가 메모리에 접근할 때마다 MMU가 매번 가상 주소를 물리 주소로 바꿔준다.
프로그램은 그저 가상 주소만 다룰 뿐이다.
11. 그런데 변환표는 어디에 있을까? — 페이지 테이블
MMU가 주소를 바꾸려면, "어느 페이지가 어느 프레임으로 가는지" 알려주는 표가 필요하다.
Virtual Physical 0x0000 → 0x8000 0x1000 → 0x9000 0x2000 → 0xA000
이 표가 바로
페이지 테이블(Page Table)
이다.
이름은 거창하지만 본질은 주소 변환표다. 그리고 프로세스마다 이 표를 따로 가진다. CPU가 프로세스를 전환할 때, "지금부터는 이 페이지 테이블을 봐"라고 MMU에게 알려주기만 하면 된다. 그러면 같은 가상 주소라도 완전히 다른 물리 메모리를 가리키게 된다. 이것이 9장에서 본 "각자의 세상"이 구현되는 방식이다.
12. 그런데 왜 1바이트 단위가 아닐까?
여기서 가장 많이 나오는 질문이 있다.
"주소마다 변환 정보를 하나씩 저장하면 안 되나요?"
겉보기엔 맞는 말이다.
하지만 계산을 해보자. 64GB 메모리가 있다고 하자. 64GB는 $ 64 \times 2^{30} $ 개의 바이트다. 즉, 약 687억 개의 주소가 있다. 주소 하나하나마다 변환 정보를 저장하면, 페이지 테이블만 수백 GB가 되어버린다. 이건 말이 안 된다.
그래서 페이징은 8장에서 봤듯 주소를 4096바이트(페이지) 단위로 묶는다.
주소 0 ~ 4095 → 페이지 0 주소 4096 ~ 8191 → 페이지 1 ...
이제 변환표는 "주소 하나"가 아니라 "페이지 하나" 단위로만 기록하면 된다. 관리해야 할 항목이 4096분의 1로 줄어든다. 페이지 크기가 4KB인 데에는 이런 현실적인 이유가 있다.
13. 페이지 테이블은 주소만 저장하지 않는다
페이지 테이블의 진짜 위력은 주소 변환에서 끝나지 않는다. 각 페이지가 어떤 권한을 가지는지도 함께 저장한다. 5장에서 세그먼테이션이 권한 분리를 자랑했던 걸 기억하는가? 페이징은 그 장점까지 페이지 단위로 흡수했다.
Text 영역 → Read, Execute Data 영역 → Read, Write Stack 영역 → Read, Write
왜 이렇게 권한을 나눌까? 프로그램 코드가 실수로(혹은 공격으로) 자기 자신을 덮어쓰면 안 되기 때문이다. 원본 코드가 손상된다.
또 데이터 영역의 내용이 함부로 실행되어도 안 된다. 해커가 데이터에 악성 코드를 심고 그걸 실행시키는 공격을 막아야 한다.
현대 CPU의 NX(Non-eXecutable) 비트가 바로 이 아이디어다.
"이 페이지는 데이터다. 절대 실행하지 마."
이렇게 메모리는 단순한 저장 공간을 넘어,
권한을 가진 객체
가 된다.
14. 페이지 테이블이 만들어낸 것들
페이지 테이블 하나 덕분에 운영체제는 놀라울 만큼 많은 기능을 공짜로 얻었다.
첫째, 프로세스 격리.
각 프로세스는 서로 다른 페이지 테이블을 가진다. 같은 가상 주소라도 전혀 다른 메모리를 본다.
둘째, 메모리 보호.
커널 페이지는 사용자 프로그램이 접근하지 못하도록 막을 수 있다.
셋째, 공유 메모리.
하나의 물리 프레임을 여러 프로세스의 페이지 테이블에 동시에 연결하면, 메모리를 안전하게 공유할 수 있다.
넷째, 연속적인 주소 공간(처럼 보이기).
프로그램은 메모리가 처음부터 끝까지 이어져 있다고 믿지만, 실제 프레임은 RAM 여기저기에 흩어져 있어도 된다. (8장)
다섯째, 디맨드 페이징(Demand Paging).
아직 실제로 올리지 않은 페이지도 "필요할 때 채우겠다"고 표시만 해 둘 수 있다. 그리고 프로그램이 그 페이지에 처음 접근하는 순간, 운영체제가 끼어들어 메모리를 할당하거나 디스크에서 내용을 읽어온다. 바로 이 디맨드 페이징 덕분에, 우리는 실제 RAM보다 큰 프로그램도 실행할 수 있고, 디스크를 메모리처럼 쓰는 스왑(Swap)도 가능해진다. 현대 운영체제의 거의 모든 메모리 기술 — 메모리 맵 파일, Copy-on-Write, 스왑 — 은 결국 이 페이지 테이블을 응용한 것이다.
15. 그런데 페이지 테이블도 너무 크다
여기까지 이해했다면 눈치 빠른 사람은 새로운 문제를 발견했을 것이다. 페이지 테이블 자체도 결국 메모리에 저장되는 자료구조다. 그런데 이 표가 생각보다 어마어마하게 크다. 직접 계산해 보자. 요즘은 64비트 CPU를 쓰지만, 주소 64비트를 전부 쓰지는 않는다.
xv6가 사용하는 RISC-V의 Sv39 모드는 그중 하위 39비트만 쓴다.
(왜 64비트를 다 안 쓰냐고? $2^{64}$는 1600만 테라바이트가 넘는다. 당분간 쓸 일이 없다. 그래서 적당히 39비트만 쓴다.)
39비트 중,
- 하위 12비트는 페이지 안에서의 위치(offset)다. → 4096바이트 페이지.
- 나머지 27비트가 "몇 번째 페이지인가"를 가리킨다.
즉 페이지는 총
$$ 2^{27} = 134{,}217{,}728 $$
개.
약 1억 3천만 개의 페이지가 있다. 이걸 12장에서 본 것처럼 단순한 일렬 배열(1단계 표)로 만든다고 해보자. 페이지마다 PTE(변환 정보) 하나가 필요하고, PTE 하나는 8바이트다.
$$ 2^{27} \times 8,\text{B} = 2^{30},\text{B} = 1,\text{GB} $$
프로세스 하나당 페이지 테이블만 1GB. 프로세스가 100개면? 100GB가 표로만 날아간다. 말이 안 된다. 게다가 더 억울한 게 있다. 대부분의 프로그램은 이 거대한 주소 공간 중 극히 일부만 쓴다. 코드 몇 페이지, 데이터 몇 페이지, 스택 한 페이지...
1억 3천만 칸짜리 표를 만들어 놓고 실제로는 수십 칸만 쓰는 셈이다.
문제의 핵심: 안 쓰는 칸까지 전부 미리 만들어 둔다.
그렇다면 답도 거기에 있다. 필요한 부분만 만들면 된다.
16. 해결책: 다단계 페이지 테이블 (트리)
핵심 아이디어는 이렇다. 거대한 표 하나를 통째로 만들지 말고, 표를 여러 단계로 쪼개서, 실제로 쓰는 가지만 만들자. 이것이 다단계 페이지 테이블(Multi-level Page Table), 즉 트리 구조다. RISC-V Sv39는 27비트짜리 페이지 번호를 9비트씩 세 토막으로 나눈다.
가상 주소 (39비트) [ 9비트 ][ 9비트 ][ 9비트 ][ 12비트 ] L2 L1 L0 offset (상위) (하위) (페이지 내 위치)
왜 하필 9비트일까?
$$ 2^9 = 512 $$
한 토막이 가리킬 수 있는 칸은 512개. 칸 하나(PTE)는 8바이트.
$$ 512 \times 8,\text{B} = 4096,\text{B} $$
정확히 한 페이지 크기(4KB)다!
즉, 각 단계의 페이지 테이블은 그 자체로 딱 한 페이지에 들어간다. 페이지를 관리하는 표가, 또 하나의 페이지에 정확히 맞아떨어지는 것이다.
구조를 그림으로 보자.
satp ──> [ L2 테이블 ] (루트, 512칸, 한 페이지) │ │ (한 칸이 아래 테이블을 가리킴) ▼ [ L1 테이블 ] (512칸, 한 페이지) │ ▼ [ L0 테이블 ] (512칸, 한 페이지) │ ▼ 실제 물리 페이지 (프레임)
루트(L2) 테이블의 각 칸은 L1 테이블 하나를 가리킨다. L1 테이블의 각 칸은 L0 테이블 하나를 가리킨다. L0 테이블의 각 칸이 드디어 진짜 물리 페이지를 가리킨다.
그리고 여기서 마법이 일어난다. 안 쓰는 가지는 아예 만들지 않는다. 예를 들어 어떤 프로그램이 주소 0 근처의 페이지 몇 개만 쓴다고 하자.
그러면 루트 테이블에서 0번 칸 하나만 유효하면 된다. 1번부터 511번 칸은 전부 "없음(invalid)"으로 둔다.
그 511개의 칸이 가리켰을 L1 테이블 511개, 그리고 그 하위에 있는 L0 테이블 511 × 512개를 통째로 안 만들어도 된다.
1GB짜리 표가, 실제로는 페이지 테이블 페이지 서너 개(수 KB)로 줄어든다.
트리 구조의 진짜 목적은 "빠른 검색"이 아니라 "안 쓰는 부분을 통째로 생략하는 것"이다.
(이게 곧 읽을 xv6 책 Chapter 3에서 "3단계 설계가 중간 레벨 511페이지와 최하위 511 × 512페이지를 절약한다"고 말하는 바로 그 내용이다.)
17. 주소 하나가 변환되는 전 과정
이제 진짜 핵심이다. 가상 주소 하나가 물리 주소로 바뀌는 과정을 처음부터 끝까지 따라가 보자. CPU가 가상 주소 하나를 들고 왔다.
가장 먼저 이 39비트를 네 토막으로 자른다.
[ L2 인덱스 ][ L1 인덱스 ][ L0 인덱스 ][ offset ] 9비트 9비트 9비트 12비트
변환은 이렇게 진행된다.
1단계. satp 레지스터가 루트(L2) 테이블의 위치를 알려준다.
그 테이블에서 L2 인덱스번째 칸(PTE)을 읽는다.
이 칸에는 다음 단계인 L1 테이블의 물리 주소가 들어 있다.
2단계. L1 테이블로 가서, L1 인덱스번째 칸을 읽는다.
여기엔 L0 테이블의 물리 주소가 들어 있다.
3단계. L0 테이블로 가서, L0 인덱스번째 칸을 읽는다.
드디어! 이 칸에 우리가 찾던 실제 물리 페이지 번호(PPN)가 들어 있다.
4단계. 물리 페이지 번호에 offset(하위 12비트)을 그대로 붙인다.
물리 주소 = (PPN << 12) | offset
이것이 최종 물리 주소다.
가상주소 ─┬─ L2 ──> 루트 테이블 ──> L1 테이블 위치 ├─ L1 ──> L1 테이블 ──> L0 테이블 위치 ├─ L0 ──> L0 테이블 ──> 물리 페이지 번호(PPN) └─ offset ─────────────> 페이지 안에서의 위치 PPN + offset = 물리 주소
offset 12비트는 왜 그냥 복사할까?
페이지는 4096바이트를 통째로 옮겨다니는 단위이기 때문이다. "몇 번째 페이지인가"는 바뀌어도, "그 페이지 안에서 몇 번째 바이트인가"는 변하지 않는다. 그래서 가상 주소든 물리 주소든 하위 12비트(페이지 내부 위치)는 항상 똑같다.
이렇게 세 단계를 타고 내려가는 과정을 페이지 테이블 워크(page table walk)라고 부른다.
xv6 Chapter 3의
walk()함수가 바로 이걸 소프트웨어로 흉내 낸 것이다. 하드웨어(MMU)는 메모리에 접근할 때마다 이 과정을 자동으로 수행한다.
그런데 만약 내려가는 도중 어떤 칸이 "없음(invalid)"이라면? 그 주소는 아직 매핑되지 않은 것이다.
하드웨어는 페이지 폴트(Page Fault) 예외를 일으키고, 처리를 운영체제에 넘긴다.
(이 페이지 폴트를 영리하게 활용하는 것이 14장에서 말한 디맨드 페이징이고, 이후 등장하는 Copy-on-Write다.)
18. PTE 안에는 무엇이 들어 있나
지금까지 "칸(PTE)"이라고 뭉뚱그려 불렀다. 이 칸 안을 들여다보자. PTE(Page Table Entry)는 8바이트(64비트)이고, 크게 두 부분으로 나뉜다.
[ ... 물리 페이지 번호(PPN) ... ][ 플래그 비트들 ]
- PPN: 이 페이지가 실제로 어느 물리 프레임에 있는지.
- 플래그: 이 페이지를 어떻게 다뤄도 되는지에 대한 규칙.
플래그 중 중요한 것들을 보자. (13장에서 본 "권한을 가진 메모리"가 바로 여기서 구현된다.)
V (Valid) : 이 칸이 유효한가? 0이면 → 페이지 폴트. R (Read) : 읽을 수 있는가? W (Write) : 쓸 수 있는가? X (eXecute) : 명령어로 실행할 수 있는가? U (User) : 사용자 모드에서 접근할 수 있는가?
이 비트들 덕분에 운영체제는 페이지마다 권한을 정밀하게 줄 수 있다.
코드(Text) : V R X (읽기/실행 O, 쓰기 X) 데이터 : V R W (읽기/쓰기 O, 실행 X)
- 코드 페이지에서 W를 빼두면, 프로그램이 실수로 자기 코드를 덮어쓰는 사고를 하드웨어가 막아준다.
- 데이터 페이지에서 X를 빼두면, 데이터에 심어진 악성 코드를 실행하려는 공격을 막는다. (13장에서 말한 NX 비트의 정체)
특히 U 비트가 사용자 계층과 커널 계층에 대한 격리의 핵심이다. 커널 전용 페이지는 U를 0으로 둔다. 그러면 사용자 프로그램이 그 주소에 접근하는 순간 폴트가 난다. 커널 메모리를 사용자가 훔쳐볼 수 없게 되는 것이다.
V 비트가 0인 PTE를 일부러 깔아두는 것이 xv6의 가드 페이지(guard page)다. 스택 바로 아래에 "없음" 페이지를 두면, 스택이 넘쳐서 그 페이지를 건드리는 순간 폴트가 나며 즉시 잡힌다.
19. 너무 느리지 않을까? — TLB
여기서 또 하나 걱정되는 게 있다. 17장에서 봤듯, 주소 하나를 변환하려면 테이블을 세 번 타고 내려가야 한다. 그 말은 곧, 메모리 접근 한 번을 위해 메모리를 세 번 더 읽어야 한다는 뜻이다.
load 0x1000 딱 한 번 하려고... → L2 테이블 읽기 (메모리 접근 1) → L1 테이블 읽기 (메모리 접근 2) → L0 테이블 읽기 (메모리 접근 3) → 그제서야 진짜 데이터 읽기 (메모리 접근 4)
한 번 할 일을 네 번 하는 셈이다. 이러면 너무 느리다. 그래서 CPU는 TLB(Translation Lookaside Buffer)라는 작은 캐시를 둔다. 한 번 변환한 결과("가상 페이지 X → 물리 프레임 Y")를 TLB에 적어둔다. 다음에 같은 페이지를 또 쓰면, 테이블을 타고 내려갈 필요 없이 TLB에서 즉시 답을 꺼낸다.
처음: 가상주소 → (테이블 3번 순회) → 물리주소 → TLB에 기록 다음: 가상주소 → TLB 적중! → 물리주소 (매우 빠름)
프로그램은 보통 같은 페이지를 반복해서 접근하므로(Locality), TLB 적중률이 매우 높다. 덕분에 다단계 페이지 테이블의 느림은 대부분 가려진다. 다만 한 가지 함정이 있다. 페이지 테이블을 바꿨는데 TLB에 옛날 정보가 그대로 남아 있으면 큰일이다. 엉뚱한(혹은 다른 프로세스의) 물리 페이지를 가리키게 되니까. 그래서 페이지 테이블을 변경하거나 프로세스를 전환할 때는 TLB를 비워줘야 한다.
RISC-V에서는
sfence.vma명령어로 TLB를 flush한다. xv6가 satp를 바꾼 직후sfence.vma를 실행하는 이유가 바로 이것이다.
// Switch the current CPU's h/w page table register to // the kernel's page table, and enable paging. void kvminithart() { // wait for any previous writes to the page table memory to finish. sfence_vma(); w_satp(MAKE_SATP(kernel_pagetable)); // flush stale entries from the TLB. sfence_vma(); }
20. CPU에게 "이 표를 봐"라고 알려주기 — satp
마지막 퍼즐 조각이다. 프로세스마다 페이지 테이블이 따로 있다고 했다. 그렇다면 CPU는 지금 어느 페이지 테이블을 써야 하는지 어떻게 알까?
satp 레지스터가 그 답이다. 이름은 Supervisor Address Translation and Protection의 약자다. 참고로 satp는 명령어가 아니라 레지스터다. 그것도 평범한 범용 레지스터가 아니라 RISC-V의 제어용 특수 레지스터(CSR, Control and Status Register)라서, 읽고 쓸 때 전용 명령어 csrr/csrw로만 접근한다. 헷갈리기 쉬우니 한 번 짚고 가자.
satp = "지금부터 주소를 변환할 땐 이 페이지 테이블을 써라"라고 MMU 책상 위에 붙여두는 포스트잇.
그런데 satp 안에는 단순히 주소만 들어 있는 게 아니다. 64비트가 이렇게 나뉜다.
63 60 59 44 43 0 +----------+----------+-----------------------------+ | MODE(4) | ASID(16) | PPN (44) | +----------+----------+-----------------------------+ MODE = 0 → 주소 변환 끔 (가상 = 물리) MODE = 8 → Sv39 켬 (우리가 본 그 3단계 트리) PPN → 루트 페이지 테이블의 물리 페이지 번호 (= 루트 테이블 물리주소 >> 12)
재밌는 건, satp에 값을 쓰는 그 순간 페이징이 켜진다는 점이다. MODE를 8로 박는 순간부터 CPU가 내놓는 모든 주소가 트리를 타고 변환되기 시작한다.
그래서 페이지 테이블 포인터를 satp 형식으로 빚어주는 도구가 필요하다. xv6는 이걸 매크로 하나로 둔다. (kernel/riscv.h)
#define SATP_SV39 (8L << 60) // MODE=8 을 최상위 4비트에 #define MAKE_SATP(pagetable) \ (SATP_SV39 | (((uint64)pagetable) >> 12)) // 물리주소 >> 12 = PPN
루트 테이블의 물리주소를 12비트 밀어 PPN으로 만들고, "Sv39 켜기" 비트를 OR로 얹는 게 전부다. 그리고 이 값을 실제 satp에 꽂는 것도 결국 csrw 한 줄이다. (kernel/riscv.h)
static inline void w_satp(uint64 x) { asm volatile("csrw satp, %0" : : "r" (x)); // satp ← x }
자, 그럼 xv6는 이 satp를 언제 건드릴까? 딱 두 순간이다.
① 부팅할 때 — 페이징을 처음 켠다.
바로 19장에서 본 kvminithart()다. w_satp(MAKE_SATP(kernel_pagetable)) 한 줄이 실행되는 순간, CPU는 "주소 = 물리주소"였던 맨몸 세상에서 "커널 페이지 테이블을 통해 변환되는 세상"으로 넘어간다. 그런데도 커널이 안 죽고 멀쩡히 다음 줄을 실행하는 건, 커널을 직접 매핑(가상=물리, 21장 ①)해 뒀기 때문이다. 전환 전후로 같은 주소가 같은 곳을 가리키니 발밑이 안 꺼진다.
② 프로세스를 전환할 때 — satp를 갈아끼워 "세상"을 바꾼다.
이제 문맥 전환(context switch)이 아주 우아해진다. 운영체제가 프로세스 A에서 B로 넘어갈 때 하는 일은 사실상 한 줄이다.
satp ← 프로세스 B의 루트 페이지 테이블 주소 (csrw) sfence.vma (TLB 비우기)
레지스터 하나만 바꾸면 그 순간부터 같은 가상 주소가 완전히 다른 물리 메모리를 가리키게 된다. A의 세상에서 B의 세상으로, 단 한 줄로 갈아탄 것이다.
xv6에서 이 전환은 유저 공간으로 돌아갈 때 trampoline.S의 userret에서 일어난다.
# a0 = MAKE_SATP(p->pagetable) ← 돌아갈 프로세스의 유저 페이지 테이블 sfence.vma zero, zero csrw satp, a0 # ← 유저 페이지 테이블로 전환! sfence.vma zero, zero
그런데 여기서 satp의 가장 음흉한 함정이 하나 있다. satp를 바꾸는 순간, 다음에 실행할 명령어의 주소(PC)까지 새 페이지 테이블로 변환된다. 만약 csrw satp 바로 다음 명령어가 새 페이지 테이블에 매핑돼 있지 않으면? CPU는 다음 명령어를 가져오지도 못하고 그대로 고꾸라진다.
그래서 xv6는 이 전환 코드(trampoline)를 커널과 모든 유저 페이지 테이블의 똑같은 가상 주소(맨 꼭대기)에 매핑해 둔다(21장 ②). 양쪽 세상에서 주소가 동일한 그 페이지 안에서 satp를 바꾸기 때문에, 갈아탄 직후에도 발 디딘 땅이 그대로 있어 안전하게 착지한다. 이름이 트램펄린(도약대)인 이유가 이거다. 한쪽 세상에서 뛰어올라 다른 쪽 세상에 사뿐히 내려앉는다.
정리하면 satp는 "지금 누구의 세상에서 주소를 해석할지" 정하는 단 하나의 스위치다.
- 부팅 때 한 번 켜고(
kvminithart),- 프로세스를 오갈 때마다 갈아끼운다(
trampoline). 그리고 바꿀 땐 항상sfence.vma로 TLB를 정리하고, 안전한 발판(직접 매핑·트램펄린) 위에서만 바꾼다.
또 하나. 각 CPU는 자기만의 satp를 가진다. 그래서 CPU마다 서로 다른 프로세스를, 서로 다른 주소 공간에서 동시에 실행할 수 있다. 8코어면 8개의 세상이 동시에 돌아가는 셈이다.
이로써 9장에서 약속했던 "모든 프로그램은 자기만의 세상을 가진다"가 드디어 하드웨어 수준에서 완성된다.
21. 운영체제는 이 모든 걸 어떻게 쓰는가
이제 부품은 다 모였다.
페이지, 프레임, 다단계 테이블, PTE, 플래그, MMU, TLB, satp.
마지막으로 실제 운영체제(xv6)가 이 부품들로 어떤 영리한 일들을 하는지 알아보자. 이 패턴들은 모두 "페이지 테이블 = 자유롭게 주무를 수 있는 간접 계층"이라는 한 가지 성질에서 나온다.
① 직접 매핑 (Direct Mapping)
커널은 자기 자신의 페이지 테이블에서 대부분의 영역을 "가상 주소 = 물리 주소"로 매핑한다.
가상 0x80000000 → 물리 0x80000000.
왜? 커널은 물리 메모리를 직접 주물러야 할 때가 많은데, 변환이 항등식이면 주소 계산이 단순해지기 때문이다.
② 한 페이지를 두 곳에 매핑 — 트램펄린(Trampoline)
페이지 테이블에서는 서로 다른 가상 주소가 같은 물리 페이지를 가리키게 할 수 있다. xv6는 trampoline 코드 한 페이지를, 모든 주소 공간의 맨 꼭대기 같은 자리에 매핑한다. 덕분에 사용자 ↔ 커널 전환 시 페이지 테이블이 통째로 바뀌어도, 그 코드만은 항상 같은 주소에서 안전하게 실행된다.
③ 일부러 비워둔 페이지 — 가드 페이지(Guard Page)
18장에서 봤듯 V=0인 PTE를 깔면 그 페이지는 "접근 즉시 폴트"가 된다. 스택 바로 아래에 이걸 두면, 스택 오버플로우를 조용한 메모리 오염이 아니라 즉각적인 크래시로 바꿔 잡아낼 수 있다.
④ 필요할 때 만들기 — 지연 할당 / 디맨드 페이징
PTE를 "없음"으로 둔 채 약속만 해두고, 프로그램이 실제로 그 페이지를 건드리는 순간 폴트를 받아 그때 메모리를 채운다. 쓰지도 않을 메모리를 미리 잡아두지 않는다. 이 모든 기법의 공통점은 하나다.
프로그램과 물리 메모리 사이에 페이지 테이블이라는 한 겹을 끼워 넣었더니, 그 한 겹을 조작하는 것만으로 격리·보호·공유·확장이 전부 가능해졌다.
마무리
긴 여정이었다. 처음 질문으로 돌아가 보자.
왜 이런 복잡한 구조(페이지 테이블)를 만들었을까?
이제 답할 수 있다.
옛날 컴퓨터는 물리 주소를 직접 썼고, 여러 프로그램을 올리자 서로를 망가뜨렸다. 운영체제가 정말 풀고 싶었던 건 주소 변환이 아니라 메모리 격리였다.
- 그 문제를 풀려고 베이스/바운드가 나왔고,
- 더 유연한 세그먼테이션이 뒤를 이었지만 외부 단편화에 무너졌다. (플랫 메모리 모델이라는 흔적만 남기고)
- 고정 크기라는 발상의 페이징이 최종 승자가 되었으며,
- 페이징을 구현하는 자료구조가 페이지 테이블,
- 표가 너무 커지는 문제는 다단계 트리로,
- 느려지는 문제는 TLB로,
- "지금 누구의 표인가"는 satp로 풀었다.
이 흐름을 손에 쥐었다면, 이제 진짜 본편을 읽을 준비가 끝났다. 다음은 xv6 책 Chapter 3. 페이지 테이블이다.
거기서 만나게 될
- Sv39, 3단계 페이지 테이블, PTE 플래그(V/R/W/X/U)
walk()가 트리를 타고 내려가는 코드- satp와
sfence.vma, TLB flush - 직접 매핑, 트램펄린, 가드 페이지
kalloc의 물리 메모리 할당,exec의 주소 공간 구성
이 모든 용어가 더 이상 외워야 할 낯선 단어가 아니라, "아, 그거" 하고 떠오르는 친숙한 개념이 되어 있을 것이다.
그렇다면 이 글의 목적은 달성된다.